Grammar Conversion
Ambiguous grammar를 unambiguous로 변환.
즉, Syntax analysis의 효율이 나쁜 문법을 효율이 좋은 문법으로 변환한다는 것이다.
Conversion method
- Elimination of useless production rules
- Elimination of epsilon production rules
- Elimination of single production rules
- Elimination of left-recursion
- Left-factoring
Elimination of useless production rules
Uesless production rule - useless symbol를 가지고 있는 production rule
Elimination of useless production rules - 문장을 만들어내는 과정에서, string을 생성할 수 없는 non-terminal symbol이나 start symbol로부터 도달 불가능한 기호를 제거하는 것
Terminating Nonterminals
Example : Elimination of useless production rules
Accessible Symbols
Example : Elimination of useless production rules
항상 Terminating nonterminals를 찾아낸 후 이를 이용하여 useless rule을 식별 및 제거를 하고 이후에
Accessible symbols를 찾아낸 후 이를 이용하여 useless rule 식별 및 제거를 해야 한다.
Elimination of epsilon-production rules
시작점이 바뀌는 것을 조심하자
Single production rules
Proper Grammar
useless production rule을 가지고 있지 않고, cycle-free, 𝜀-free 하므로 이 문법은 proper하다.
Left-factoring
Backtracking
Elimination of left-recursion
Remove indirect left-recursion
'3-2 > 기초컴파일러' 카테고리의 다른 글
| Syntax Analysis (0) | 2021.10.16 |
|---|---|
| Pushdown Automata (0) | 2021.10.16 |
| Context-free Grammar, Parse Tree, Ambiguous Grammar (0) | 2021.09.30 |
| Lexical Analysis(Scanning) (0) | 2021.09.28 |
| NFA->DFA, State Minimization (0) | 2021.09.18 |