LR1 Parser und Epsilon

Question

Ich versuche, wie LR1 Parser Arbeit zu verstehen, aber ich kam mit einem seltsamen Problem auf: Was passiert, wenn die Grammatik enthält Epsilons? Zum Beispiel: wenn ich die Grammatik:

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

Es ist klar, wie zu starten:

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

... und so weiter

, aber ich weiß nicht, wie es zu tun für eine solche Grammatik:

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

Ist es richtig zu tun:

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

Und dann macht diesen Staat in der DFA zu akzeptieren?

Jede Hilfe wäre wirklich dankbar!

Answer 1

Ja, genau (man denke an dem epsilon als leerer Raum, wo es an den Seiten nicht zwei Stellen für den Punkt ist).

In einem LR (0) Automaten, würden Sie den Zustand machen zu akzeptieren und jedoch zu A. reduzieren, aufgrund der A->a A a Produktion, würde es eine Verschiebung sein / Konflikte reduzieren.

In einem LR (1) Automaten, würden Sie feststellen, ob mit Look-Ahead verschieben oder zu reduzieren (a -> Shift, alles in FOLLOW(A) -> reduzieren)

Sehen Sie den Wikipedia-Artikel