[PL] Syntax Analysis : Context Free Grammer

1. Context Free Grammer의 구성 요소

Terminal

Constant Literal (키워드, identifier, number, operator)

Non-terminal

규칙을 기반으로, 터미널을 대체하는 symbol

Production

non-terminal이 어떻게 terminal로 대체되는지에 대한 규칙

• 왼쪽에는 non-terminal만 올 수 있다.
• 화살표 (arrow) ->
• 오른쪽에는 non-terminal, terminal 모두 올 수 있다.

📌 Example

Non-terminal : <A>
Terminal : 0, 1, <$\epsilon$>
Production : <A> -> 0 <A>| 1<A> | <$\epsilon$>
<A> => {<$\epsilon$>, 0, 1, 00, 01, 01, 10, 11, 000, ... }

2. CFG와 Regular Expression

➡️ CFG는 Regular Expression보다 표현력이 높다.

$(^n)^n$ 을 RE는 표현 못하지만 CFG는 표현할 수 있다.

➡️ RE는 더욱 더 Compact 하다.

ID = [a-z][0-9 a-z A-Z _]*
CFG는 더욱 더 어렵게 표현할 수밖에 없다.

📌 Example

CFG로 (()) 나타내기

<S> -> (<S>) | <$\epsilon$>

<S> -> <$\epsilon$>
<S> -> (<S>) => (<$\epsilon$>) => "()"
<S> -> (<S>) => ((<S>)) => (($\epsilon$)) => "(())"

📌 Example

ID = [a-z][0-9 a-z A-Z _]* 를 CFG로 나타내기

S -> LE
L -> a | .. | z
E -> $\epsilon$ | 0 | 1 .. | 9 | a ..
E -> EE
💬 E -> EE 요건 모지?!

<S> -> a<A> | b<A> | c<A> .. | z<A>
<A> -> 0<A> | 1<A> | 2<A> .. | 9<A> | .. A<A> | .. | $\epsilon$

3. Formal definition of Context Free Grammer

G = ( $\sum$, N, P, S )

$\sum$ : Terminals(알파벳들)의 유한한 집합

N : Non-Terminal의 유한한 집합

P : Production rule의 유한한 집합

S : Start Non-terminal ( S $\in$ N )

📌 Example

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

"ac" 가 올바른 문법인가?!

<S> -> a<A>c -> a$\epsilon$c -> ac

"aac" 는 올바른 문자열인가?!

<S> -> a<A>c -> aa<A>c -> aa$\epsilon$c -> aac

4. Derivation

Derivation 할 때에는 => 을 사용한다. (production rule에는 -> )

➡️ Rightmost Derivation

항상 오른쪽 non terminal부터 expand 한다.

📌 Example

EXP -> EXP + EXP
EXP -> EXP * EXP
EXP -> NUM

1 + 2 * 3 은 Valid한가? YES!

EXP => EXP EXP => EXP 3 =>EXP + EXP 3 => EXP + 2 3 => 1 + 2 * 3

➡️ Leftmost Derivation

항상 왼쪽 non terminal부터 expand 한다.

📌 Example

EXP -> EXP + EXP
EXP -> EXP * EXP
EXP -> NUM

1 + 2 * 3 은 Valid한가?

EXP => EXP EXP => EXP + EXP EXP => 1 + EXP EXP => 1 + 2 EXP => 1 + 2 * 3