| G = (N, T, P, S) |
|---|
| N : | { S, ST, SL, E } |
|---|
| T : | { :=, ;, else, endif, id, if, n, then, $ } |
|---|
| S : | S |
|---|
| P : | S | ::= | ST $ |
|---|
| | ST | ::= | id := E | | | ST | ::= | if E then SL endif | | | ST | ::= | if E then SL else SL endif | | | SL | ::= | ST | | | SL | ::= | SL ; ST | | | E | ::= | id | | | E | ::= | n |
Diese Grammatik beschreibt eine Syntax für Anweisungen (ST), Anweisungsfolgen (SL),
Zuweisungen und Verzweigungen. Sie ist für die LL-Syntaxanalyse
aus zwei Gründen nicht geeignet: Die beiden Verzweigungsregeln
beginnen mit den gleichen Symbolfolgen. Hier wird eine Faktorisierung
notwendig sein. Die Anweisungsfolgen (SL) sind über eine Linksrekursion
definiert, diese muss in eine Rechtsrekursion überführt werden.
Die Iterationen bei der Berechnung der FIRST-Mengen
| | S | ST | SL | E |
|---|
| 0. | { } | { } | { } | { } |
|---|
| 1. | { } | { id, if } | { id, if } | { id, n } |
|---|
| 2. | { id, if } | { id, if } | { id, if } | { id, n } |
|---|
| 3. | { id, if } | { id, if } | { id, if } | { id, n } |
|---|
Die nullable Tabelle ist trivial, da keine epsilon-Produktionen
vorkommen, daher ist die FOLLOW-Tabelle für den Aufbau der
Parsertabelle
nicht notwendig.
Die LL-Parser-Tabelle
| | := | ; | else | endif | id | if | n | then | $ |
|---|
| S | - | - | - | - | S ::= ST $ | S ::= ST $ | - | - | - |
|---|
| ST | - | - | - | - | ST ::= id := E | ST ::= if E then SL endif
ST ::= if E then SL else SL endif | - | - | - |
|---|
| SL | - | - | - | - | SL ::= ST
SL ::= SL ; ST | SL ::= ST
SL ::= SL ; ST | - | - | - |
|---|
| E | - | - | - | - | E ::= id | - | E ::= n | - | - |
|---|
Die Grammatik ist nicht LL(1): 3 Zelle(n) mit Konflikten
Es gibt jeweils zwei Ableitungsmöglichkeiten
für ST und den look ahead if, und für SL
wegen der Linksrekursion.
Eine gleichwertige Grammatik ohne Linksrekursion und mit Faktorisierung
| G = (N, T, P, S) |
|---|
| N : | { S, ST, EP, SL, RL, E } |
|---|
| T : | { :=, ;, else, endif, id, if, n, then, $ } |
|---|
| S : | S |
|---|
| P : | S | ::= | ST $ |
|---|
| | ST | ::= | id := E | | | ST | ::= | if E then SL EP endif | | | EP | ::= | | | | EP | ::= | else SL | | | SL | ::= | ST RL | | | RL | ::= | | | | RL | ::= | ; ST RL | | | E | ::= | id | | | E | ::= | n |
Es sind zwei neue Nichtterminalsymbole dazugekommen: EP (else part)
und RL (rest list)
und an zwei Stellen werden epsilon-Produktionen verwendet.
Die nullable-, FIRST- und FOLLOW-Tabellen
nullable
| | S | ST | EP | SL | RL | E |
|---|
| 0. | - | - | - | - | - | - |
|---|
| 1. | - | - | true | - | true | - |
|---|
| 2. | - | - | true | - | true | - |
|---|
FIRST
| | S | ST | EP | SL | RL | E |
|---|
| 0. | { } | { } | { } | { } | { } | { } |
|---|
| 1. | { } | { id, if } | { else } | { id, if } | { ; } | { id, n } |
|---|
| 2. | { id, if } | { id, if } | { else } | { id, if } | { ; } | { id, n } |
|---|
| 3. | { id, if } | { id, if } | { else } | { id, if } | { ; } | { id, n } |
|---|
FOLLOW
| | S | ST | EP | SL | RL | E |
|---|
| 0. | { } | { } | { } | { } | { } | { } |
|---|
| 1. | { } | { $, else, endif, ; } | { endif } | { else, endif } | { else, endif } | { $, then } |
|---|
| 2. | { } | { $, else, endif, ; } | { endif } | { else, endif } | { else, endif } | { $, then, else, endif, ; } |
|---|
| 3. | { } | { $, else, endif, ; } | { endif } | { else, endif } | { else, endif } | { $, then, else, endif, ; } |
|---|
Die LL-Parser-Tabelle
| | := | ; | else | endif | id | if | n | then | $ |
|---|
| S | - | - | - | - | S ::= ST $ | S ::= ST $ | - | - | - |
|---|
| ST | - | - | - | - | ST ::= id := E | ST ::= if E then SL EP endif | - | - | - |
|---|
| EP | - | - | EP ::= else SL | EP ::= | - | - | - | - | - |
|---|
| SL | - | - | - | - | SL ::= ST RL | SL ::= ST RL | - | - | - |
|---|
| RL | - | RL ::= ; ST RL | RL ::= | RL ::= | - | - | - | - | - |
|---|
| E | - | - | - | - | E ::= id | - | E ::= n | - | - |
|---|
Die Grammatik ist LL(1)
Es gibt keine mehrfachen Einträge in der Tabelle
Eine Linksableitung
Für die Zeichenreihe
if n then id := n ; id := id else id := n endif
wird eine Linksableitung mit einem LL-Parser und der Tabelle
konstruiert.
| Aktion |
Verarbeitet |
Keller |
Eingabe |
| init |
|
S |
if n then id := n ; id := id else id := n endif $ |
|---|
| S ::= ST $
| |
ST $ |
if n then id := n ; id := id else id := n endif $ |
|---|
| ST ::= if E then SL EP endif
| |
if E then SL EP endif $ |
if n then id := n ; id := id else id := n endif $ |
|---|
| shift |
if |
E then SL EP endif $ |
n then id := n ; id := id else id := n endif $ |
|---|
| E ::= n
| if |
n then SL EP endif $ |
n then id := n ; id := id else id := n endif $ |
|---|
| shift |
if n |
then SL EP endif $ |
then id := n ; id := id else id := n endif $ |
|---|
| shift |
if n then |
SL EP endif $ |
id := n ; id := id else id := n endif $ |
|---|
| SL ::= ST RL
| if n then |
ST RL EP endif $ |
id := n ; id := id else id := n endif $ |
|---|
| ST ::= id := E
| if n then |
id := E RL EP endif $ |
id := n ; id := id else id := n endif $ |
|---|
| shift |
if n then id |
:= E RL EP endif $ |
:= n ; id := id else id := n endif $ |
|---|
| shift |
if n then id := |
E RL EP endif $ |
n ; id := id else id := n endif $ |
|---|
| E ::= n
| if n then id := |
n RL EP endif $ |
n ; id := id else id := n endif $ |
|---|
| shift |
if n then id := n |
RL EP endif $ |
; id := id else id := n endif $ |
|---|
| RL ::= ; ST RL
| if n then id := n |
; ST RL EP endif $ |
; id := id else id := n endif $ |
|---|
| shift |
if n then id := n ; |
ST RL EP endif $ |
id := id else id := n endif $ |
|---|
| ST ::= id := E
| if n then id := n ; |
id := E RL EP endif $ |
id := id else id := n endif $ |
|---|
| shift |
if n then id := n ; id |
:= E RL EP endif $ |
:= id else id := n endif $ |
|---|
| shift |
if n then id := n ; id := |
E RL EP endif $ |
id else id := n endif $ |
|---|
| E ::= id
| if n then id := n ; id := |
id RL EP endif $ |
id else id := n endif $ |
|---|
| shift |
if n then id := n ; id := id |
RL EP endif $ |
else id := n endif $ |
|---|
| RL ::=
| if n then id := n ; id := id |
EP endif $ |
else id := n endif $ |
|---|
| EP ::= else SL
| if n then id := n ; id := id |
else SL endif $ |
else id := n endif $ |
|---|
| shift |
if n then id := n ; id := id else |
SL endif $ |
id := n endif $ |
|---|
| SL ::= ST RL
| if n then id := n ; id := id else |
ST RL endif $ |
id := n endif $ |
|---|
| ST ::= id := E
| if n then id := n ; id := id else |
id := E RL endif $ |
id := n endif $ |
|---|
| shift |
if n then id := n ; id := id else id |
:= E RL endif $ |
:= n endif $ |
|---|
| shift |
if n then id := n ; id := id else id := |
E RL endif $ |
n endif $ |
|---|
| E ::= n
| if n then id := n ; id := id else id := |
n RL endif $ |
n endif $ |
|---|
| shift |
if n then id := n ; id := id else id := n |
RL endif $ |
endif $ |
|---|
| RL ::=
| if n then id := n ; id := id else id := n |
endif $ |
endif $ |
|---|
| shift |
if n then id := n ; id := id else id := n endif |
$ |
$ |
|---|
| shift |
if n then id := n ; id := id else id := n endif $ |
|
|
|---|
| accept |
if n then id := n ; id := id else id := n endif $ |
|
|
|---|
|
Compilerbau: 
