[PL] Syntax Analysis : BNF, EBNF, Syntax Diagram

1. Backus- Naur Form (BNF)

Context Free Grammer는 BNF를 이용하여 표현될 수 있다.

BNF는 Programming Language 문법을 표현하는 데 좋다.

-> 을 ::= 으로 대체한다.

📌Example

CFG

$\sum$ = { a, b, c } // 3개의 알파벳
N = { <S>, <A>} // 2개 논 터미널
P = { <S> -> a<A>c, <A>->a<A>, <A>->b, <A>->$\epsilon$ }
S = <S>

BNF

S ::= aAc
A ::= aA
| b
| $\epsilon$

📌Example

CFG

<EXP> -> (<EXP>+<EXP>)
<EXP> -> (<EXP>*<EXP>)
<EXP> -> <NUM>
<EXP> -> 1|42|17..

BNF

<EXP> ::= ( <EXP> + <EXP> )
| ( <EXP> * <EXP> )
| <NUM>
<NUM> ::= 1, 42, 17 ...

2. Extended BNF

BNF

<expr> ::= <expr> + <term> | <term>
<term> ::= <term> * <factor> | <factor>
<factor> ::= number | (<expr>)

=> Syntax가 재귀적으로 정의되어 있기 때문에 이해하기 어렵다.

expr은 term으로 term은 factor으로 factor은 expr 로..

EBNF

• BNF와 EBNF의 차이는 EBNF는 대부분의 Recursive 스타일을 삭제한다는 것이다.
• {}와 []을 이용하여 반복을 표현한다.
• 즉, '재귀적 표현'을 '반복적 표현'으로 변경한다.

{ ... } = zero or more
{ .. $\}^7_0$ = 0 ~ 7
[ .. ] = zero or one (optional)

<expr> ::= <term> {+ <term>}

<expr> 은 <term> 혹은 <term> + <term> 혹은 그 이상

<term> ::= <factor> {* <factor>}

<term> 은 <factor> 혹은 <factor>*<factor> 혹은 그 이상

<factor> ::= number | (<expr>)

📌 Example

EBNF에서는 여러 Operator들을 grouping하여 보다 문법을 간편하게 나타낼 수 있다.

3. Syntax Diagram

EBNF는 Diagram으로 나타낼 수 있다.

Syntax Diagram은 문법을 좀 더 잘 이해하기 위해 다이어그램으로 나타낸 것이다.

Terminal : Circle
Non-terminal : Square
Sequence : Arrow

{}는 zero or more이므로, Non-terminal Loop에서 이와 같이 나타낼 수 있다.

[]는 zero or one 이기 때문

첫 번째 term은 무조건 오고, 그 뒤에 term이 추가적으로 올 수도/ 아닐수도 있으므로

📌Example

4. Parser의 역할 : CFG로 해당 문자열이 적합한지 확인하기

"Sting s is valid string? s $\in$ L(G) "

parser은 우리가 준 CFG를 이용하여 해당 문자열s가 적합한지 확인한다.

CFG 문법으로, 주어진 문자열 s가 우리의 언어에 적합한지 "production rule을 역순으로 적용하여" 확인할 수 있다.

📌 Example

이러한 문법에서, 아래 세 가지 string은 올바른 문법인가?!