Left-Factoring

같은 기호들을 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의 결과, 생성규칙이 하나 더 추가됨