LR1 파서 및 엡실론

Question

LR1 파서가 어떻게 작동하는지 이해하려고 노력하고 있지만 이상한 문제를 생각해 냈습니다. 문법에 엡실론이 포함되어 있다면 어떨까요? 예를 들어, 문법이있는 경우 :

S -> A
A -> a A | B
B -> a

시작 방법은 분명합니다.

S -> .A
A -> .a A 
A -> .B

... 등등

그러나 나는 그런 문법을 위해 그것을하는 방법을 모른다 :

S -> A
A -> a A a | \epsilon

해야 할 일이 맞습니까?

S -> .A
A -> .a A a
( A -> .\epsilon )

그런 다음 DFA 에서이 상태를 수락합니까?

모든 도움이 정말 감사하겠습니다!

Answer 1

예, 정확히 (엡실론을 빈 공간으로 생각하십시오.

LR (0) Automaton에서, 당신은 주를 수락하고 A로 줄일 것입니다. A->a A a 생산, 교대/감소 갈등이있을 것입니다.

LR (1) Automaton에서 Lookahead를 사용하여 전환 할 것인지 감소할지 여부를 결정합니다 (a -> 교대, 무엇이든 FOLLOW(A) -> 감소)

참조 위키 백과 기사