|
In diesem Beispiel wird untersucht, welche Eigenschaften
die "natürliche" Grammatik für arithmetische Ausdrücke mit +, -, * und
/ als zweistellige Operatoren
und mit ( und ) als Klammern besitzt, und ob diese für das LL-Parsen geeignet ist.
Die Grammatik
| G = (N, T, P, S) |
|---|
| N : | { E, T, F } |
|---|
| T : | { (, ), *, +, -, /, id, num } |
|---|
| S : | E |
|---|
| P : | E | ::= | E + T |
|---|
| | E | ::= | E - T | | | E | ::= | T | | | T | ::= | T * F | | | T | ::= | T / F | | | T | ::= | F | | | F | ::= | ( E ) | | | F | ::= | id | | | F | ::= | num |
Diese Grammatik wird erweitert um ein neues Startsymbol
und ein Ende-Kennzeichen, um beim Analysieren den
Eingabestrom nicht laufend gegen eof abzufragen.
Die erweiterte Grammatik
| G = (N, T, P, S) |
|---|
| N : | { S, E, T, F } |
|---|
| T : | { (, ), *, +, -, /, id, num, $ } |
|---|
| S : | S |
|---|
| P : | S | ::= | E $ |
|---|
| | E | ::= | E + T | | | E | ::= | E - T | | | E | ::= | T | | | T | ::= | T * F | | | T | ::= | T / F | | | T | ::= | F | | | F | ::= | ( E ) | | | F | ::= | id | | | F | ::= | num |
Das neue Startsymbol ist S, die eof-Marke ist $
Die Iterationen bei der Berechnung der nullable-Symbole
| | S | E | T | F |
|---|
| 0. | - | - | - | - |
|---|
| 1. | - | - | - | - |
|---|
Da keine epsilon-Produktionen in der Grammatik vorkommen, ist die
Berechnung der nullable-Tabelle trivial. Nach einem Durchlauf ist
erkannt worden, dass keine epsilon-Produktionen vorkommen.
Die Iterationen bei der Berechnung der FIRST-Mengen
| | S | E | T | F |
|---|
| 0. | { } | { } | { } | { } |
|---|
| 1. | { } | { } | { } | { (, id, num } |
|---|
| 2. | { } | { } | { (, id, num } | { (, id, num } |
|---|
| 3. | { } | { (, id, num } | { (, id, num } | { (, id, num } |
|---|
| 4. | { (, id, num } | { (, id, num } | { (, id, num } | { (, id, num } |
|---|
| 5. | { (, id, num } | { (, id, num } | { (, id, num } | { (, id, num } |
|---|
Die FIRST-Mengen werden schrittweise über F, T, und E bis
zu S hin vergrößert.
Die Iterationen bei der Berechnung der FOLLOW-Mengen
| | S | E | T | F |
|---|
| 0. | { } | { } | { } | { } |
|---|
| 1. | { } | { $, +, -, ) } | { $, +, -, *, / } | { $, +, -, *, / } |
|---|
| 2. | { } | { $, +, -, ) } | { $, +, -, *, /, ) } | { $, +, -, *, /, ) } |
|---|
| 3. | { } | { $, +, -, ) } | { $, +, -, *, /, ) } | { $, +, -, *, /, ) } |
|---|
Da keine epsilon-Produktionen vorkommen, brauchen
die FOLLOW-Mengen eigentlich nicht berechnet zu werden,
da sie für die Parser-Tabelle nicht benötigt werden.
Die LL-Parser-Tabelle
| | ( | ) | * | + | - | / | id | num | $ |
|---|
| S | S ::= E $ | - | - | - | - | - | S ::= E $ | S ::= E $ | - |
|---|
| E | E ::= E + T
E ::= E - T
E ::= T | - | - | - | - | - | E ::= E + T
E ::= E - T
E ::= T | E ::= E + T
E ::= E - T
E ::= T | - |
|---|
| T | T ::= T * F
T ::= T / F
T ::= F | - | - | - | - | - | T ::= T * F
T ::= T / F
T ::= F | T ::= T * F
T ::= T / F
T ::= F | - |
|---|
| F | F ::= ( E ) | - | - | - | - | - | F ::= id | F ::= num | - |
|---|
Die Grammatik ist nicht LL(1): 6 Zelle(n) mit Konflikten
Wegen der Linksrekursionen für E und T ist die Grammatik
keine LL-Grammatik, sowohl bei E als auch bei T hat man
bei look ahead von (, id und num
drei Regeln zur Auswahl.
Die Grammatik ohne Linksrekursion
Die Linksrekursionen für E und T müssen eliminiert werden,
es ergibt sich dann folgende transformierte Grammatik,
die aber die gleiche Sprache definiert.
| G = (N, T, P, S) |
|---|
| N : | { S, E, E', T, T', F } |
|---|
| T : | { (, ), *, +, -, /, id, num, $ } |
|---|
| S : | S |
|---|
| P : | S | ::= | E $ |
|---|
| | E | ::= | T E' | | | E' | ::= | | | | E' | ::= | + T E' | | | E' | ::= | - T E' | | | T | ::= | F T' | | | T' | ::= | | | | T' | ::= | * F T' | | | T' | ::= | / F T' | | | F | ::= | ( E ) | | | F | ::= | id | | | F | ::= | num |
Als neue Nichtterminalsymbole sind E' und T' dazugekommen
Die Iterationen bei der Berechnung der nullable-Symbole
| | S | E | E' | T | T' | F |
|---|
| 0. | - | - | - | - | - | - |
|---|
| 1. | - | - | true | - | true | - |
|---|
| 2. | - | - | true | - | true | - |
|---|
Da jetzt epsilon-Produktionen in der Grammatik vorkommen, ist die
Berechnung der nullable-Tabelle nicht mehr so einfach. Dennoch ist die
Tabelle nach zwei Durchläufen fertig berechnet.
Die Iterationen bei der Berechnung der FIRST-Mengen
| | S | E | E' | T | T' | F |
|---|
| 0. | { } | { } | { } | { } | { } | { } |
|---|
| 1. | { } | { } | { +, - } | { } | { *, / } | { (, id, num } |
|---|
| 2. | { } | { } | { +, - } | { (, id, num } | { *, / } | { (, id, num } |
|---|
| 3. | { } | { (, id, num } | { +, - } | { (, id, num } | { *, / } | { (, id, num } |
|---|
| 4. | { (, id, num } | { (, id, num } | { +, - } | { (, id, num } | { *, / } | { (, id, num } |
|---|
| 5. | { (, id, num } | { (, id, num } | { +, - } | { (, id, num } | { *, / } | { (, id, num } |
|---|
Die Iterationen bei der Berechnung der FOLLOW-Mengen
| | S | E | E' | T | T' | F |
|---|
| 0. | { } | { } | { } | { } | { } | { } |
|---|
| 1. | { } | { $, ) } | { $ } | { $, +, - } | { $, +, - } | { $, +, -, *, / } |
|---|
| 2. | { } | { $, ) } | { $, ) } | { $, +, -, ) } | { $, +, -, ) } | { $, +, -, *, /, ) } |
|---|
| 3. | { } | { $, ) } | { $, ) } | { $, +, -, ) } | { $, +, -, ) } | { $, +, -, *, /, ) } |
|---|
Da E' und T' epsilon-Produktionen enthalten, müssen
die FOLLOW-Mengen jetzt berechnet werden.
Die LL-Parser-Tabelle
| | ( | ) | * | + | - | / | id | num | $ |
|---|
| S | S ::= E $ | - | - | - | - | - | S ::= E $ | S ::= E $ | - |
|---|
| E | E ::= T E' | - | - | - | - | - | E ::= T E' | E ::= T E' | - |
|---|
| E' | - | E' ::= | - | E' ::= + T E' | E' ::= - T E' | - | - | - | E' ::= |
|---|
| T | T ::= F T' | - | - | - | - | - | T ::= F T' | T ::= F T' | - |
|---|
| T' | - | T' ::= | T' ::= * F T' | T' ::= | T' ::= | T' ::= / F T' | - | - | T' ::= |
|---|
| F | F ::= ( E ) | - | - | - | - | - | F ::= id | F ::= num | - |
|---|
Die Grammatik ist LL(1)
Da an jeder Stelle in der Tabelle höchstens eine Produktion auftaucht,
ist diese Grammatik eine LL-Grammatik. Aus der Tabelle kann also
auf systematische Weise zum Beisiel ein recursive descent Parser erzeugt werden.
Eine Linksableitung
Für die Zeichenreihe
id + id * ( id + num )
wird eine Linksableitung mit einem LL-Parser und der Tabelle
konstruiert.
Es werden schrittweise die Symbole auf der linken Seite des Stacks
verarbeitet:
Die terminalen Symbole werden mit dem look ahead verglichen und
eingelesen,
die nicht terminalen Symbole werden gemäß der Parser-Tabelle durch die
rechte Seite der Regel ersetzt.
| Aktion |
Verarbeitet |
Keller |
Eingabe |
| init |
|
S |
id + id * ( id + num ) $ |
|---|
| S ::= E $
| |
E $ |
id + id * ( id + num ) $ |
|---|
| E ::= T E'
| |
T E' $ |
id + id * ( id + num ) $ |
|---|
| T ::= F T'
| |
F T' E' $ |
id + id * ( id + num ) $ |
|---|
| F ::= id
| |
id T' E' $ |
id + id * ( id + num ) $ |
|---|
| shift |
id |
T' E' $ |
+ id * ( id + num ) $ |
|---|
| T' ::=
| id |
E' $ |
+ id * ( id + num ) $ |
|---|
| E' ::= + T E'
| id |
+ T E' $ |
+ id * ( id + num ) $ |
|---|
| shift |
id + |
T E' $ |
id * ( id + num ) $ |
|---|
| T ::= F T'
| id + |
F T' E' $ |
id * ( id + num ) $ |
|---|
| F ::= id
| id + |
id T' E' $ |
id * ( id + num ) $ |
|---|
| shift |
id + id |
T' E' $ |
* ( id + num ) $ |
|---|
| T' ::= * F T'
| id + id |
* F T' E' $ |
* ( id + num ) $ |
|---|
| shift |
id + id * |
F T' E' $ |
( id + num ) $ |
|---|
| F ::= ( E )
| id + id * |
( E ) T' E' $ |
( id + num ) $ |
|---|
| shift |
id + id * ( |
E ) T' E' $ |
id + num ) $ |
|---|
| E ::= T E'
| id + id * ( |
T E' ) T' E' $ |
id + num ) $ |
|---|
| T ::= F T'
| id + id * ( |
F T' E' ) T' E' $ |
id + num ) $ |
|---|
| F ::= id
| id + id * ( |
id T' E' ) T' E' $ |
id + num ) $ |
|---|
| shift |
id + id * ( id |
T' E' ) T' E' $ |
+ num ) $ |
|---|
| T' ::=
| id + id * ( id |
E' ) T' E' $ |
+ num ) $ |
|---|
| E' ::= + T E'
| id + id * ( id |
+ T E' ) T' E' $ |
+ num ) $ |
|---|
| shift |
id + id * ( id + |
T E' ) T' E' $ |
num ) $ |
|---|
| T ::= F T'
| id + id * ( id + |
F T' E' ) T' E' $ |
num ) $ |
|---|
| F ::= num
| id + id * ( id + |
num T' E' ) T' E' $ |
num ) $ |
|---|
| shift |
id + id * ( id + num |
T' E' ) T' E' $ |
) $ |
|---|
| T' ::=
| id + id * ( id + num |
E' ) T' E' $ |
) $ |
|---|
| E' ::=
| id + id * ( id + num |
) T' E' $ |
) $ |
|---|
| shift |
id + id * ( id + num ) |
T' E' $ |
$ |
|---|
| T' ::=
| id + id * ( id + num ) |
E' $ |
$ |
|---|
| E' ::=
| id + id * ( id + num ) |
$ |
$ |
|---|
| shift |
id + id * ( id + num ) $ |
|
|
|---|
| accept |
id + id * ( id + num ) $ |
|
|
|---|
|
Compilerbau & Formale Sprachen: LL-Analyse: Beispiel für Arithmetische Ausdrücke
