Konwersja gramatyki wieloznacznej na jednoznaczną

Przykład ma dwie gramatyki:

Dwuznaczne:

E → E + E | E ∗ E | (E) | a

Jednoznaczne:

E → E + T | T
T → T ∗ F | F
F → (E) | a

Gramatyka jednoznaczna została wyprowadzona z niejednoznacznej przy użyciu informacji nie określonych w gramatyce niejednoznacznej:

• operator " * "wiąże się mocniej niż operator"+".
• oba operatory ' * ' i ' + ' pozostają asocjacyjne.

Bez informacji zewnętrznej, nie ma możliwości dokonania transformacji.

Z zewnętrznym informacje, możemy powiedzieć, że:

a * a + b * b

Jest zgrupowane tak, jakby było napisane:

(a * a) + (b * b)

Zamiast jako:

a * ((a + b) * b)

Druga zakłada, że ' + 'wiąże się mocniej niż'*', i że operatory wiążą się z prawej do lewej, a nie z lewej do prawej.

Komentarz

W Jaki Sposób Asocjacja pojawi się na obrazku dla przykładów takich jak:

    S → aA | Ba
    A → BA | a
    B → aB | epsilon

Jest to gramatyka wieloznaczna, więc jak przejść do jej konwersji na jednoznaczną?

I zastanów się, czy' epsilon ' to ε, pusty ciąg; przeanalizujmy gramatykę w obie strony.

Ε jest pustym łańcuchem

Reguła dla B mówi, że A B jest albo pustym ciągiem, albo a, po którym następuje poprawne b, co oznacza nieskończenie długi ciąg 0 lub więcej a.

Zasada mówi, że A jest albo a, albo A B, po którym następuje a. tak więc nieskończenie długi ciąg a może być również A. Tak więc gramatyka nie ma możliwości wyboru, czy ciąg a jest albo A, albo B.

I reguła dla S nie jest pomocna; S jest albo a, po którym następuje nieskończenie długi ciąg a lub nieskończenie długi ciąg a, po którym następuje a. wymaga co najmniej jednego a, ale dowolna liczba a od jednego do góry jest w porządku, ale gramatyka nie ma podstaw do decydowania między lewą i prawą alternatywą.

Więc ta gramatyka jest z natury niejednoznaczna i nie może, w mojej ocenie, być jednoznaczna; z pewnością nie może być jednoznaczna bez innych informacji nie w nasze posiadanie.

Ε nie jest pustym łańcuchem

A jeśli ε nie jest pustym łańcuchem?

• B jest albo ε, albo ae.
• A jest albo a, albo A B, po którym następuje a (więc albo a, ae lub aae).
W 1995 roku został wybrany do Izby Gmin.]}
• lub: S to B, po którym następuje a (stąd ea lub aea).

W tym przypadku gramatyka jest jednoznaczna w obecnej postaci (choć niekoniecznie LR (1)). / Align = "left" / o znaczeniu "epsilon" w komentarzu/pytaniu.

Asocjacja