Ich habe ein Problem mit dieser Übung:
Sei G die folgende mehrdeutige Grammatik für den λ-Kalkül:
E → v | λv.E | EE | (E)
wobei E das einzelne nicht-terminale Symbol ist, λv.E die Abstraktion der Variablen v in E darstellt und EE die Anwendung darstellt.
- Definieren Sie eine LL (1) -Grammatik G 'so, dass L (G') = L (G) ist und die Mehrdeutigkeit von G durch Auferlegen der folgenden üblichen Konventionen aufgelöst wird:
- Abstraktion ist richtig assoziativ;
- Anwendung bleibt assoziativ;
- Anwendung hat eine höhere Priorität als Abstraktion.
- Zeigen Sie die LL (1) -Parsing-Tabelle für G 'und den Analysebaum, der beim Parsen der Zeichenfolge erhalten wurde
λv1. λv2. v1v2v1
.
Ich habe die Priorität und Assoziation von Mehrdeutigkeiten beseitigt und diese Grammatik erhalten:
E -> EF | F
F -> λv.G | G
G -> (E) | v
Das ist nicht LL (1), da die Produktion E -> EF
rekursiv bleibt. Wenn ich jedoch die linke Rekursion aus dieser Produktion eliminiere, erhalte ich:
E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v
das entspricht nicht der Anforderung 1.2.
Ich habe im Internet nach einer Lösung gesucht, aber es scheint nicht möglich zu sein, die Linksrekursion zu eliminieren, um die linke Assoziativität zu erhalten.
Diese Übung wurde jedoch vor einigen Jahren bei der Compilerprüfung geprüft, daher muss es eine richtige Antwort geben.
Danke für deine Hilfe.
quelle
Mein Versuch:
Diese Grammatik ist LL (1) und sollte die erforderlichen Eigenschaften berücksichtigen.
quelle