LL (1) nie może być wieloznaczne

Question

Jak można pokazać, że gramatyka LL (1) może być niejednoznaczna?

Wiem, co jest niejednoznaczną gramatyką, ale nie może udowodnić powyższego twierdzenia/lematu.

Answer 1

Myślę, że to prawie bezpośredni rezultat definicji LL (1). Spróbuj dowodzić przez sprzeczność; załóżmy, że masz gramatykę LL (1), która jest niejednoznaczna i szukaj czegoś, co możesz pokazać jako prawdziwe, a nie prawdziwe. Jako punkt wyjścia "co zawsze wiesz podczas przetwarzania danych wejściowych?"

Wygląda na to, że problem z pracą domową i tak naprawdę nie ukończyłem problemu, tak jak naszkicowałem powyżej, zatrzymam się tam.

Answer 2

Wykazać, że żadna niejednoznaczna gramatyka nie może być grą LL (1). Aby uzyskać wskazówki, zobacz http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf, slajdy 18-20. Zobacz także http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, str. 11 i poprzedni.

Answer 3

Oto mój pierwszy projekt na dowód. To może wymagać pewnego dostrojenia, ale myślę, że obejmuje wszystkie przypadki. Myślę, że wiele rozwiązań jest możliwych. To jest bezpośredni dowód.

(uwaga boczny: szkoda tak nie obsługuje matematycznych, takich jak lateks.)

Dowód

przez T i N są zbiory symboli zaciskowych i nieterminalnych .

Niech następujący przytrzymaj

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 

pamiętać, że gramatyka jest LL (1), jeżeli następuje zachodzi dla każdej pary produkcjach A -> B i 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 

Rozważmy język z LL (1), z A -> B i A -> C. To znaczy, że istnieje pewien ciąg terminali TZ, które dopuszczają wielokrotne wyprowadzenia przez odrębne drzewa parse.

Załóżmy, że lewa derywacja osiąga S ->* TAY ->* TZ. Następnym krokiem może być TAY -> TBY lub TAY -> TCY. W ten sposób język jest niejednoznaczny, jeśli zarówno BY ->* Z i CY ->* Z. (Warto zauważyć, że A oznacza dowolne nie-końcowe, czy nie taki przypadek występuje, język nie jest wieloznaczne).

Przypadek 1: Z = pusty

Zasadą 1 LL (1) gramatyk , najwyżej jeden z B i C może wyprowadzić pusty (niejednoznaczny przypadek).

Przypadek 2: Z nie jest pusty i nie B ani C uzyskania pusty

Zasadą 2 LL (1) gramatyki, co najwyżej jeden spośród B i C, może pozwolić na dalsze wyprowadzenie ponieważ prowadzi zacisk Z nie może być zarówno w przypadku First(B), jak i First(C) (przypadek niejednoznaczny).

Przypadek 3: Z niepusty i albo MaybeEmpty(B) lub MaybeEmpty(C)

Zanotować przez reguły 1 LL (1) gramatyki, B, C nie może wynikać zarówno puste. Załóżmy zatem, że MaybeEmpty(C) jest prawdziwe.

Daje to dwie pod-skrzynki.

Przypadek 3a: CY -> Y; oraz Przypadek 3b: CY ->* DY, gdzie D nie jest pusty.

W 3a musimy wybrać między BY ->* Z i CY -> Y ->* Z, ale zauważ, że First(Y) subset-of Follow(A). Ponieważ Follow(A) nie przecina się z First(B), tylko jedna pochodna może być kontynuowana (niejednoznaczna).

W 3b musimy wybrać między BY ->* Z i CY ->* DY ->* Z, ale zauważ, że First(D) subset-of First(C). Ponieważ First(C) nie przecina się z First(B), tylko jedna pochodna może być kontynuowana (niejednoznaczna).

Tak więc w każdym przypadku pochodzenie można rozszerzyć tylko o jedną z dostępnych produkcji. Dlatego gramatyka nie jest niejednoznaczna.