Context-Free-Grammer가 왜 필요한가?
이 전까지 배웠던 것 : Regular Expression→ NFA->DFA
그런데 중첩된 괄호의 경우 ( ) 로 표현하면 여는 괄호와 닫는 괄호의 갯수가 안맞을 수 있음
사람이 만들어내는 언어중에는 정규표현식으로 표현할 수 있는 구문도 나올 수 있고, 이를 찾기 위해서는 다른 방식의 grammar를 찾아야 함
Context-Free Grammar(CFG)
Terminal과 Nonterminal의 상관관계를 표현한 문법
Context Free Grammar G = < Terminal , Nonterminal , Production , Start Symbol >
Derivation
CFG의 기본적인 rule은 좌측항에 항상 Nonterminal이 들어와야 한다는 것인데, 우측항이 Terminal과 Nonterminal의 결합 형태로 들어올 수 있다.
Nonterminal 남지 않을때까지 계속 production을 적용하는 것
사전에 정의된 Grammar를 이용해서 Replacement를 하는 과정
한계(Ambiguity)
**leftmost Derivation / rightmost Derivation**if else 문제도 있음
위와 같은 규칙을 만들어 해결
level 1 → higher precedence (* ? first)
level 2 → lower precedence (+ - second)
Left-Recursive
를 해결 해주기 위해 다음과 같은 방법을 취함
Right Recursion이라고 해서 loop 내에서 recursion이 무한하게 반복되는 left recursive와는 다르다.
Left Recursion으로 terminal로 끝내고자 할때는 무조건 첫번째 string으로 β가 나와야 한다. 그런데 Left Recursion인 경우에는 첫번째 문자가 Aα이 될경우에는 β가 나올때까지 계속 Replacement가 일어날 것이다.
앞에서 전제하기론 CFG 자체가 Leftmost Derivation을 따르고 있는데 이처럼 앞에 무슨 string이 나올건지가 불확실한 상태에서는 해당 단어가 grammar속에 속하는지를 확신할 수 없을 것이다.
반면 오른쪽처럼 Right Recursive꼴로 바꾼 경우에는 명확하게 첫번째 string이 정의되어 있기 때문에 그 다음문자에 대한 예측을 할 수 있게 된다. 그냥 α 나 Empty String이 나오면 Terminal이 되기 때문이다. 이렇게 해주는 과정 자체를 Left Factoring 이라고 한다.
