대체, 인수 분해 및 왼쪽 재귀 제거를 사용하여 LL (1) 문법 구성

Question

은 G (

)와 동일한 언어를 허용하는 LL (1) 문법을 구성합니다 (대체, 인수 분해, 왼쪽 재귀 제거)

G over Σ = {0, 1, 2}: 
    S → Y | 1X 
    X → 1X | 0 
    Y → Y0 | 1X1 | 2X2 

지금까지 이런 짓을 :

X 재귀 그렇게 남아 :

X -> 1F | 0F 
F -> 1F | e 

내가 LL를 구성 할 필요가 뭐가 (1), 수 내가 요인 Y?

Answer 1

먼저 X는 RHS가 X로 시작하지 않기 때문에 재귀 적으로 남지 않습니다. 대신 꼬리 재귀 적이며 괜찮습니다. 그러나 Y -> Y0는 Y가 왼쪽 재귀임을 알려줍니다.

S -> Y | 1X 
X -> 1X | 0 
Y -> 1X1F | 2X2F 
F -> 0F | e 

당신은 또한 추가 할 수 있으며, X에 엡실론 규칙뿐만 아니라이

X -> 1X | 0 | e 

당신이 무한한 문장으로 끝낼 수 없을거야 확인하고이 경우 다음을 수행 .