|
Wie sieht ein Ableitungsbaum mit Linksrekursion aus? Welche Alternative es gibt, verdeutlicht die Animation.
Die hier verwendete Beispielgrammatik soll dabei folgende Regeln enthalten:
Schritt 1 (Linksableitung von 'acbcbbc')
Schritt 2 (Rechtsableitung mit modifizierten Regeln)
|
Betrachten Sie nochmals die entstehenden Regeln aus dem Beispiel genauer.
A  a C und
A A B C
Die erste in perfekt. Sie ist bereits eine gültige Regel des GNF-Formats. Welche Probleme hingegen bereitet die zweite Regel?
Was passiert, wenn man versucht, das A der rechten Regelseite nach dem auf Seite 3 vorgestellten Verfahren zu ersetzen?
Problem der Linksrekursion
In dem vorgestellten Verfahren wurde der Ersetzungsschritt eines Nichtterminals z.B. A vorweggenommen, indem anstelle dieses Nichtterminals jeweils die rechte Regelseite einer A-Regel eingefügt wird. Das muss für alle A-Regeln wiederholt werden.
Eine linksrekursiven Regel führt bei diesem Ersetzungsvorgang gerade dieses Nichtterminal - in unserem Fall A - wieder ein; der Vorgang findet kein Ende.
Welche Lösungsmöglichkeiten bestehen?
Beseitigung der Linksrekursion
Gegeben eine Grammatik G; seien
A A α1 | ... | A αn alle linksrekursive A-Regel und
A β1 | ... | βm
die restlichen A-Regeln.
G' ist eine modifizierte Grammatik ohne Linksrekursion, wobei alle A-Regeln durch folgende Regeln ersetzt werden.
- A βi | βi B (1<=i<=m)
- B αi | αi B (1<=i<=n)
(B ist ein neues, nicht in G vorhandenes Nichtterminal.)
Das Prinzip wird durch die Animation links verdeutlicht.
Mit den nun vorgestellten Hilfsverfahren - Beseitigung der Linksrekursion und Vorwegnahme eines Ableitungsschrittes durch Regelzusammenzug - ist es möglich, eine Chomsky-Normalform-Grammatik in Greibachnormalform umwandeln.
Probieren Sie ein wenig, z.B. an der Beispielgrammatik für die CNF. Den Beweis und das komplette Verfahren finden Sie u.a. in Hopcroft & Ullman (1994).
|
1
2
3
4
5
6
Schleifenlemma
