Usuwanie lewej rekurencji w gramatyce przy jednoczesnym zachowaniu lewego powiązania operatora

Mam problem z tym ćwiczeniem:

Niech G będzie następującą dwuznaczną gramatyką dla rachunku λ:

E → v | λv.E | EE | (E)

gdzie E jest pojedynczym nieterminalnym symbolem, λv.E oznacza abstrakcję względem zmiennej v w E, a EE oznacza aplikację.

1. Zdefiniuj gramatykę LL (1) G ′, tak aby L (G ′) = L (G), a dwuznaczność G została rozwiązana poprzez narzucenie następujących zwyczajowych konwencji:
   1. abstrakcja jest właściwym skojarzeniem;
   2. aplikacja pozostanie skojarzona;
   3. aplikacja ma wyższy priorytet niż abstrakcja.
2. Pokaż tabelę parsowania LL (1) dla G ′ i drzewo parsowania uzyskane podczas parsowania łańcucha λv1. λv2. v1v2v1.

Wyeliminowałem pierwszeństwo i asocjację ustalania dwuznaczności, uzyskując tę ​​gramatykę:

E -> EF | F
F -> λv.G | G
G -> (E) | v

który nie jest LL (1), ponieważ produkcja E -> EFjest rekurencyjna. Jednak eliminując lewą rekurencję z tej produkcji, otrzymuję:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

który nie jest zgodny z wymaganiem 1.2.

Szukałem rozwiązania w Internecie, ale wydaje się, że nie można wyeliminować lewostronnej rekurencji zachowującej lewe skojarzenie.

Jednak to ćwiczenie pojawiło się na egzaminie kompilatora kilka lat temu, więc musi być poprawna odpowiedź.

Dziękuję za pomoc

Zgodność lewego skojarzenia i analizy LL (1)

Właśnie natrafiłeś na jedną z głównych niespójności w stosowaniu składni bezkontekstowej (CF). Ludzie chcą wybrać gramatykę, aby parsowanie odzwierciedlało zamierzoną strukturę zdania, zbliżoną do jego semantyki, szczególnie w przypadku operatorów niepowiązanych, takich jak aplikacja . To była pierwotna intencja gramatyki CF w lingwistyce. Ale jednocześnie ograniczają się do technologii parsowania, która będzie tolerować tylko niektóre typy gramatyk.

Rzeczywiście, jeśli parsowanie ma odzwierciedlać lewą asocjatywność operatora, to gramatyka jest koniecznie lewostronnie rekurencyjna, ponieważ górny węzeł aplikacji w parsowaniu koniecznie dodaje najwyższy prawy termin niepaparetizowanych kolejnych aplikacji. Zatem analiza LL nie wchodzi w rachubę. Masz rację.

Są na to dwa sposoby. Nie można polegać na parserze, który daje sztywne „drzewo analizy składniowej”, które ma być wykorzystane do późniejszych etapów przetwarzania (takich jak zmniejszenie wyrażenia lambda tutaj). Doprowadziło to do koncepcji drzew abstrakcyjnych składni (AST), które można budować z drzewa parsowania, ale o innej strukturze.

Innym rozwiązaniem jest użycie bardziej ogólnych technik parsowania, które przyjmą dowolną gramatykę CF i parsują zgodnie z nią. Ogólne parsery CF to dobrze rozwinięta technologia (i nie przestaję się zastanawiać, dlaczego LL jest tak popularny).

Nie mam pojęcia, co można uznać za właściwą odpowiedź na te sprzeczne wymagania.

Chciałbym pokazać, że są one sprzeczne z wymogami. Podaj pierwszą gramatykę, która spełnia ograniczenia asocjatywności i priorytetu, a następnie przekształć gramatykę w i gramatykę LL (1) do analizy.

Fakt, że coś pojawiło się w czasopiśmie lub na egzaminie, nie jest całkowitą gwarancją, że jest to poprawne. I może też się mylę ... ale oprócz mojej wiedzy na ten temat dokonałem też sprawdzenia.

O tym konkretnym przykładzie

Biorąc to pod uwagę, pierwsza sugerowana gramatyka nie wydaje się całkiem poprawna. Nie ma sposobu na wytworzenie λu.λv.v.

Jedna sztuczka, którą należy wiedzieć, to zacząć od operatorów (tutaj abstrakcja lub aplikacja) o najniższym priorytecie (abstrakcja). To samo dotyczy wyrażeń arytmetycznych.

Moja próba:

E  -> A | λv.E
A  -> FA'
A' -> A | ɛ
F  -> (E) | v

Ta gramatyka to LL (1) i powinna szanować wymagane właściwości.