프로그래밍 언어 Syntax 표현(기술)

Terminologies

- Alphabet

- String

- Language (알파벳으로 만들 수 있는 모든 String 의 집합)

- Sentence : Language 의 한 String

- Lexeme : 의미적 요소의 최소 단위

- Token : lexeme 의 카테고리

- Language recognizer / generator  (인식기, 생성기)

 

Lexeme (어휘 항목) : 구문 기술이 아닌 어휘 명세에 의해 주어지는 것으로, literal, operator, special word 등으로 이루어짐

즉 프로그래밍 언어는 문자가 아닌 Lexeme 으로 이루어졌다고 말할 수 있음

 

프로그래밍 언어의 구문 기술에는 Lexeme 은 고려되지 않음

 

Syntax (구조, 문법) : expression, statement, program units 의 형태

Semantic (의미) : expression, statement, program units 의 의미

Syntax와 Semantic 이 합쳐져야 비로소 언어를 정의할 수 있음 (어느 한가지 만으로는 완전히 정의가 불가능)

Syntax 를 표현하는 방법

CFG(Context Free Grammar)

CFG = (N, T, P, S)

N = Nonterminal symbols ( 변수 목록 )

T = Terminal symbols ( 상수 목록 )

P : Productions ( or Rules 규칙 )

S : Start symbol

 

A -> B

B -> BB | 1

 

BNF(Backus-Naur Form)

사실 이 둘은 비슷함. BNF 는 다른 언어를 설명하는 메타언어

<LHS> -> <RHS> 의 꼴

 

<while-statment> -> while ( <expression> ) <statment>

 

Derivation

BNF나 CFG 의 규칙에 따라 주어진 문장을 만들어나가는 것을 Derivation 이라 함

그렇게 만들어진 최종 구문을 Sentence 라고 함

언어가 만들 수 있는 모든 Sentence 의 집합을 Language 라고 함

 

<assign> -> <id> := <expr>

<id> -> A | B | C

<expr> -> <id> + <expr>

                 | <id> * <expr>

                 | ( <expr> )

                 | <id>

 

위와 같은 언어가 있을 때 A := B * (A + C) 를 Derivation

 

Leftmost derivation

<assign> -> <id> := <expr>

               -> A := <expr>

               -> A := <id> * <expr>

               -> A := B * <expr>

               -> A := B * ( <expr> )

               -> A := B * ( <id> + <expr> )

               -> A := B * ( A + <expr> )

               -> A := B * ( A + <id> )

               -> A := B * ( A + C )

 

Rightmost derivation

<assign> -> <id> := <expr>

               -> <id> := <id> * <expr>

               -> <id> := <id> * ( <expr> )

               -> <id> := <id> * ( <id> + <expr> )

               -> <id> := <id> * ( <id> + <id> )

               -> <id> := <id> * ( <id> + C )

               -> <id> := <id> * ( A + C )

               -> <id> := B * ( A + C )

               -> <id> := B * ( A + C )

 

정리

Leftmost derivation 은 왼쪽부터 전개해 나가는거고, Rightmost derivation 은 오른쪽부터 전개해나가는것

 

이러한 전개 과정은 Parse tree 로도 표현이 가능

 

Amibuity

하나의 sentence 를 만드는데 두 개 이상의 서로 다른 parse tree 가 만들어질 수 있는 Language를 ambiguious 하다. 라고 함

 

어떤 언어가 모호함을 보이려면 단 하나의 sentence 라도 모호함을 보이면 되고,

어떤 언어가 모호하지 않음을 보이려면 모든 sentence 가 모호하지 않음을 보여야 하므로 이는 굉장히 어렵다.

 

연산자 우선순위

Parse tree 로 그렸을 때 아랫쪽에 있을 수록 먼저 평가가 되므로 우선순위가 높다.

 

따라서

곱하기가 우선순위가 더 높은 경우 <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> + <term>                | <term> <term> -> <term> * <factor>                | <factor> <factor> -> ( <expr> )                | <id>

더하기가 우선순위가 더 높은 경우 <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> * <term>                | <term> <term> -> <term> + <factor>                | <factor> <factor> -> ( <expr> )                | <id>

Left recursive <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> + <term>                | <term> <term> -> <term> + <factor>                | <factor> <factor> -> ( <expr> )                | <id>

Right recursive <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <term> + <expr>                | <term> <term> -> <factor> + <term>                | <factor> <factor> -> ( <expr> )                | <id>

 

C언어의 if-else 모호함

<if-stat> -> if ( <expr> ) <statement>

                 | if ( <expr> ) <statement> else <statement>

 

if ( a ) if ( b ) x := 1; else x := 2;

if ( a ) if ( b ) x := 1; else x := 2;

 

모호하지 않게 바꾸려면

<stmt> -> <matched> | <unmatched>

<matched> -> if (<logic_expr>) <matched> else <matched>

                    | any non-if statement

<unmatched> -> if ( <logic_expr> ) <stmt>

                    | if ( <logic_expr> ) <matched> else <unmatched>

 

 

EBNF(Extended BNF)

[]  :  옵션. 있어도 되고 없어도 되는 것들

{}  :  반복. 1개는 무조건 있고, 여러 개 있어도 되는 것들

(|) :  n 개 중 하나를 고르는 것

 

EBNF 가 설명을 더 잘 하는 것은 아니고, 가독성과 작성력을 올려준 BNF 이다.

 

BNF <expr> -> <expr> + <term>                 | <expr> - <term>                 | <term> <term> -> <term> * <factor>                 | <term> / <factor>                 | <factor> <factor> -> <exp> ** <factor>                 | <exp> <exp> -> ( <expr> )                 | <id>

EBNF <expr> -> <term> { ( + | - ) <term> } <term> -> <factor> { ( * | / ) <factor> } <factor> -> { <exp> ** } <exp> <exp> -> ( <expr> ) | <id>