LL (1) kann nicht mehrdeutig sein

Question

Wie kann gezeigt werden, dass keine LL (1) Grammatik mehrdeutig sein kann?

Ich weiß, was mehrdeutige Grammatik ist, aber konnte das obige Theorem/Lemma nicht beweisen.

Answer 1

Ich denke, es ist fast ein direktes Ergebnis der Definition von LL (1). Probieren Sie Beweis durch Widerspruch aus; Angenommen, Sie haben eine mehrdeutige LL (1) -Grammatik und suchen nach etwas, das Sie als wahr und nicht als wahr anzeigen können. Als Ausgangspunkt "Was wissen Sie immer, wenn Sie Eingaben verarbeiten?"

Da dies wie ein Hausaufgabenproblem aussieht und ich das Problem eigentlich nicht mehr gelöst habe, als ich oben skizziert habe, werde ich damit aufhören.

Answer 2

Beweisen Sie, dass keine mehrdeutige Grammatik eine LL (1) Grammatik sein kann. Für Hinweise, siehe http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf, Dias 18-20. Siehe auch http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, pg. 11 und vorhergehende.

Answer 3

Hier ist mein erster Entwurf bei einem Beweis. Es könnte eine Feinabstimmung erfordern, aber ich denke, es deckt alle Fälle ab. Ich denke viele Lösungen sind möglich. Dies ist ein direkter Beweis.

(Randbemerkung: es ist schade, SO nicht Mathe, wie in LaTeX nicht unterstützt.)

Proof

Let T und N die Sätze von Terminal und nicht-Terminal-Symbole sein .

Lassen folgendes halten

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

anzumerken, dass eine Grammatik LL (1) ist, wenn folgendes gilt für jedes Paar von Produktionen A -> B und A -> C:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

Betrachten Sie eine Sprache mit LL (1), mit A -> B und A -> C. Das heißt, es gibt eine Reihe von Terminals TZ, die mehrere Ableitungen von verschiedenen Parsebäumen erlaubt.

Angenommen, die linke Ableitung erreicht S ->* TAY ->* TZ. Der nächste Schritt kann entweder TAY -> TBY oder TAY -> TCY sein. Somit ist die Sprache zweideutig, wenn sowohl BY ->* Z als auch CY ->* Z. (Man beachte, dass, da A eine beliebige Nicht-Terminal, wenn kein solcher Fall liegt vor, die Sprache ist nicht eindeutig.)

Fall 1: Z = leer

nach Regel 1 von LL (1) Grammatiken , höchstens einer von B und C kann einen leeren (nicht zweideutigen Fall) ableiten.

Fall 2: Z nicht leer ist, und weder B noch C herzuleiten leer

durch die Regel 2 von LL (1) Grammatiken, höchstens eines von B und C weitere Ableitung, da der führende Anschluß der Z erlauben kann kann nicht in beiden sein First(B) und First(C) (nicht eindeutiger Fall).

Fall 3: Z nicht leer ist, und entweder MaybeEmpty(B) oder MaybeEmpty(C)

Notiere die durch Regel 1 von LL (1) Grammatiken, B und C können beide nicht leer ableiten. Nehmen wir an, dass MaybeEmpty(C) wahr ist.

Dies ergibt zwei Unterfälle.

Fall 3a: CY -> Y; und Fall 3b: CY ->* DY, wobei D nicht leer ist.

In 3a müssen wir wählen zwischen BY ->* Z und , aber beachten Sie, dass First(Y) subset-of Follow(A). Da sich Follow(A)First(B) nicht schneidet, kann nur eine Ableitung (nicht eindeutig) ablaufen.

In 3b müssen wir wählen zwischen BY ->* Z und CY ->* DY ->* Z, aber beachten Sie, dass First(D) subset-of First(C). Da sich First(C)First(B) nicht schneidet, kann nur eine Ableitung (nicht eindeutig) ablaufen.

Somit kann die Ableitung in jedem Fall nur um eine der verfügbaren Produktionen erweitert werden. Daher ist die Grammatik nicht mehrdeutig.