Co z tymi gramatykami i parserem minimalnym, aby je rozpoznać?

Question

Próbuję dowiedzieć się, jak zrobić kompilator. W tym celu dużo czytam na temat języka bez kontekstu. Ale jest jeszcze kilka rzeczy, których sam nie mogę osiągnąć.

Ponieważ jest to mój pierwszy kompilator, istnieją pewne praktyki, których nie jestem świadomy. Moje pytania są zadawane z myślą o zbudowaniu generatora analizatora składni, a nie kompilatora ani lexera. Niektóre pytania mogą być oczywiste ..

Wśród moich odczytów są: Bottom-Up Parsing, Top-Down Parsing, Formal Grammars. Pokazany obraz pochodzi z: Miscellanous Parsing. Wszystko pochodzi z klasy Stanford CS143.

Oto punkty:

0) Jak zrobić (dwuznaczne/jednoznaczne) i (lewo-rekurencyjne/prawym rekurencyjna) wpływa na zapotrzebowanie na jednego algorytmu lub innego? Czy istnieją inne sposoby na zakwalifikowanie gramatyki?

1) Niejednoznaczna gramatyka to taka, która zawiera kilka parse drzew. Ale czy wybór lewostronnego wyprowadzenia lub wyprowadzenia prawostronnego nie powinien prowadzić do jedności drzewa parsowania?

[EDIT: Odpowiedź here]

2,1), ale nadal jest niejednoznaczność gramatyki związanej k? Mam na myśli podanie gramatyki LR (2), czy jest niejednoznaczny dla parsera LR (1) i niejednoznaczny dla LR (2)?

[EDIT: Nie, gramatyka LR (2) oznacza, że ​​parser potrzebuje dwóch żetonów wyprzedzających, aby wybrać odpowiednią regułę do użycia. Z drugiej strony, niejednoznaczna gramatyka to taka, która prawdopodobnie prowadzi do kilku drzewek. ]

2.2) Czyli parser LR (*), o ile można to sobie wyobrazić, nie będzie miał żadnej niejednoznacznej gramatyki, a następnie może przeanalizować cały zestaw języków bez kontekstu?

[EDYCJA: Odpowiedź: Ira Baxter, LR (*) ma mniejszą moc niż GLR, ponieważ nie obsługuje wielu drzewek parse. ]

3) W zależności od poprzednich odpowiedzi, poniższe pytania mogą być sprzeczne. Biorąc pod uwagę parsowanie LR, czy niejednoznaczne gramatyki uruchamiają przesunięcie - zmniejszają konflikt? Czy jednoznaczna gramatyka może wywołać jedno z nich? W jaki sposób zredukować konflikty?

[EDYCJA: to jest to, niejednoznaczne gramatyki prowadzą do zmiany w celu zmniejszenia i zmniejszenia liczby konfliktów. Przez przeciwieństwo, jeśli nie ma konfliktów, gramatyka jest jednoznaczna. ]

4) Czy umiejętność parsowania gramatyki lewostronnej jest zaletą parsera LR (k) w stosunku do LL (k), czy jest to jedyna różnica między nimi?

[EDIT: tak. ]

5) wyrażanie G1:

G1 : 
S -> S + S 
S -> S - S 
S -> a 

5,1) G1 jest zarówno lewy rekurencyjne prawym rekurencyjne i niejednoznaczne, mam rację? Czy to gramatyka LR (2)? Jedno byłoby jednoznaczne:

G2 : 
S -> S + a 
S -> S - a 
S -> a 

5.2) Czy G2 jest ciągle niejednoznaczny? Czy parser dla G2 potrzebuje dwóch uprzedzeń?Przez faktoryzację mamy:

G3 : 
S -> S V 
V -> + a 
V -> - a 
S -> a 

5.3) Czy teraz parser dla G3 potrzebuje tylko jednej strony wczytującej? Jakie są przeciwwagi dla tych przekształceń? Czy LR (1) wymaga minimalnego analizatora składni?

5.4) G1 pozostaje rekurencyjnych, aby analizować je z parsera LL jedna potrzeba, aby przekształcić go w prawej rekurencyjnego gramatyki:

G4 : 
S -> a + S 
S -> a - S 
S -> a 

następnie

G5 : 
S -> a V 
V -> - V 
V -> + V 
V -> a 

5,5) Czy G4 potrzebuje co najmniej parsera LL (2)? Tylko G5 można parsowac przez parser LL (1), G1-G5 definiują ten sam język, a tym językiem jest (a (+/- a)^n). Czy to prawda ?

5.6) Jaki jest minimalny zestaw dla każdej gramatyki od G1 do G5?

6) W końcu, ponieważ gramatyki wielu różnych języków mogą definiować ten sam język, w jaki sposób wybrano gramatykę i powiązany z nią parser? Czy wynikowe drzewo składniowe jest nieistotne? Jaki wpływ ma drzewo analizy?

Bardzo dużo zadaję i naprawdę nie oczekuję pełnej odpowiedzi, w każdym razie każda pomoc byłaby bardzo cenna.

Thx do czytania!

Answer 1

"Wiele gramatyk może definiować ten sam język, jak wybrać ..."?

Zazwyczaj wybrać taki, który spełnia następujące kryteria:

• koncepcyjnie tak proste, jak można zrobić to (implikacja: mniejszy niż innych)
• tory terminologię w podręczniku langauge miarę możliwości
• najmniej kwota gięcia w celu spełnienia ograniczeń generatora parsera

to ostatnie może bałagan swojego koncepcyjnego prostoty i wykres różnych stylów parsera pokazuje liczbę różnych problemów, które napotykasz w zależności od wybranego generatora. Jest to pogarszane przez fakt, że wybór często odbywa się dobrze, zanim faktycznie wybierzesz gramatykę.

Jednym ze sposobów zminimalizowania gięcia gramatycznego jest wybranie generatora analizatora składni, który obsługuje gramatykę bezkontekstową. GLR parsing ma tę istotną zaletę. Używam go od 15 lat i zrobiłem z nim dziesiątki prawdziwych langauges.