반응형
같은 기호들을 prefix로 갖는 2개 이상의 생성규칙이 존재할 경우, 공통된 prefix를 인수분해하는 것을 left-factoring이라고 한다.
구문분석기가 어떤 생성규칙을 적용해야할 지 결정할 수 없어서, 규칙의 선택값을 순차적으로 재시도하게 되는 현상(backtracking)을 방지하기 위해서 left-factoring을 수행한다.
입력 : 문법 G
출력 : 동일한 left-factoring된 문법
방법
begin
repeat
Find the production A -> αβ1|αβ2||...|αβn|γ (*γ는 문자열*)
Find the longest prefix α ;
If α ≠ ε then
replace all tha A -> αβ1|αβ2||...|αβn|γ
by A -> αA'|γ
A -> β1|β2|...|βn (*A'는 새로운 Non-terminal*)
until 공통된 prefix를 갖는 Non-terminal이 존재하지 않음
end.
출력 : 동일한 left-factoring된 문법
방법
begin
repeat
Find the production A -> αβ1|αβ2||...|αβn|γ (*γ는 문자열*)
Find the longest prefix α ;
If α ≠ ε then
replace all tha A -> αβ1|αβ2||...|αβn|γ
by A -> αA'|γ
A -> β1|β2|...|βn (*A'는 새로운 Non-terminal*)
until 공통된 prefix를 갖는 Non-terminal이 존재하지 않음
end.
[핵심] Left-Factoring의 결과, 생성규칙이 하나 더 추가됨
반응형
'B1:기초 Basement' 카테고리의 다른 글
| 푸시다운 오토마타 ( Push-Down Automata ) (0) | 2006.12.03 |
|---|---|
| Left-Recursion (0) | 2006.12.03 |
| 단일 생성규칙 (single production) 제거 (0) | 2006.12.03 |
| ε(epsilon)-생성규칙 제거 (0) | 2006.12.03 |
| 모호성 (Ambiguity), 모호한 문법 (Ambiguous Grammer) (0) | 2006.12.03 |