[PL] Syntax의 표현

Terminology

• language(언어) : 알파벳으로 만들 수 있는 모든 String의 집합
• Sentence(문장) : Language의 한 String
• Lexeme(어휘) : 의미적 요소의 최소 단위
• Token(토큰) : Lexeme의 카테고리
• Syntax(구조, 문법) : expression, statement, program units의 형태, 구조
• Semantics(의미) : expression, statementm program units의 의미
  
  

Syntax를 표현하는 방법

CFG(Context Free Grammar)

CFG = (N, T, P, S)
- N = Nonterminal symbols (변수 목록)
- T = Terminal symbols (상수 목록)

- P : Productions (or Rules 규칙)

- S : Start symbol (시작 변수)

 

문법 G가 있을 때 G의 모든 생성 규칙이 A -> x의 형태를 가지면 G를 CFG라고 정의한다.

A : nonterminal symbol (LHS)

x : a string that is composed of terminal or nonterminal symbol(RHS)

 

BNF(Backus-Naur Form)

BNF는 다른 언어를 표현하기 위한 메타언어로 CFG의 한 갈래이다.

<LHS> -> <RHS>의 형태를 가진다.

ex) 대입문 형식 : <assign> -> <var> = <expression>

 

Derivation(유도)

BNF나 CFG의 규칙에 따라 주어진 문장을 만들어나가는 것을 Derivation(유도)이라고 한다.

즉,  nonterminal과 terminal로 구성된 문장인 Sentential form을 모두 terminal로 이루어진 문장인 Sentence로 바꾸는 것이다.

 

Derivation은 Leftmost derivation(좌측 유도)과 Rightmost derivation(우측 유도)으로 구분할 수 있는데 Leftmost derivation은 각 유도 단계에서 가장 왼쪽 nonterminal을 선택하여 이를 대상으로 생성 규칙을 적용하는 것이고 Rightmost derivation은 각 유도 단계에서 가장 오른쪽 nonterminal을 선택하여 이를 대상으로 생성규칙을 적용하는 것이다.

 

ex)

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

<id> -> A | B | C

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

                 | <id> * <expr>

                 | ( <expr>)

                 | <id>

 

위와 같은 문법이 있을 때 'A = B * ( A + C )'의 유도 과정은 다음과 같다.

 

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 )

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

 

이러한 유도 과정은 parse tree로도 표현할 수 있다.

 

Ambiguous(모호함)

하나의 sentence를 만드는데 두 개 이상의 서로 다른 parse tree가 만들어질 수 있는 문법은 ambiguous 하다고 한다.

 

※ Operator Precedence(연산자 우선순위)

모호함 판단에 있어서 중요한 개념이 연산자 우선순위이다. 

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 associativity <assign> -> <id> := <expr> <id> -> A | B | C <expr> -> <expr> + <term>                | <term> <term> -> <term> * <factor>                | <factor> <factor> -> (<expr>)                | <id>

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

 

※ If - else 문의 모호함

<if-stat> -> if ( <expr> ) then <stmt>

                 | if ( <expr> ) then <stmt> else <stmt>

<stmt>  -> <if_stmt>          // 이 규칙이 추가되면 언어가 모호해진다.

 

왜냐하면 if (<expr>) then if (<expr>) then <stmt> else <stmt>라는 syntax에 대해 두 가지 parse tree가 나오게 되는데 else가 어떤 if와 연결되어야 할지 모호해지기 때문이다. 따라서 다음과 같이 바꿔주어 모호함을 해결할 수 있다.

 

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

<matched> -> if (<expr>) then <stmt>

                          | 임의의 if가 아닌 문장

<unmatched> -> if (<expr>) then <stmt>

                          | if (<expr>) then <matched> else <unmatched>  

 

EBNF(Extended BNF)

• [] : 옵션. 있어도 되고 없어도 되는 부분
• {} : 반복. 0개 또는 여러 개 있어도 되는 부분
• (|) : 선택. n개 중 하나를 고르는 부분

BNF <expr> -> <expr> + <term>                 | <expr> - <term>                 | <term> <term> -> <term> * <factor>                 | <term> / <factor>                 | <factor>

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

---