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ę.
- 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:
- abstrakcja jest właściwym skojarzeniem;
- aplikacja pozostanie skojarzona;
- aplikacja ma wyższy priorytet niż abstrakcja.
- 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 -> EF
jest 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
źródło
Moja próba:
Ta gramatyka to LL (1) i powinna szanować wymagane właściwości.
źródło