Embed Size (px)
Citation preview
Fabian Berlin
Syntaktische Analyse – Bottom-up
Im Rahmen des Seminars „Übersetzung von künstlichen Sprachen“
2
Gliederung
1. Grundlagen der Bottom-Up-Syntaxanalyse
2. Operator-Precedence-Syntaxanalyse
3. LR-Syntaxanalyse 3.1 LR-Syntaxanalysealgorithmus
3.2 LR(0)
3.3 SLR(1)
3.4 LR(1)
3.5 LALR(1)
4. Zusammenfassung
3
Einführung in die Bottom-Up-Syntaxanalyse
Grammatik G1:
Regel 1: S → aABe
Regel 2: A → Abc | b
Regel 3: B → d
a b b c d e
S
a A B e
a A d e
a A b c d e
Regel 2: A → b
Regel 2: A → Abc
Regel 3: B → d
Regel 1: S → aABe
Ziel:
Anwendung von Reduktionsschritten, um von der Eingabe auf das Startsymbol S zu reduzieren
4
Einführung in die Bottom-Up-Syntaxanalyse
S
A
B
A
a b b c d e
Anwendung einer umgekehrten Rechtsableitung
Problem: Bestimmung von Handles (rechte Seiten von Regeln, die reduziert werden können, um vorhergehenden Schritt der Rechtsableitung zu erhalten)
Idee: Nutzung eines Stacks
A → b
A → Abc
B→ d
S→ aABe
5
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
6
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$
3
4
5
6
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
Shift: Inputsymbol auf den Stack schieben (bis Handle erscheint)
7
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$
4
5
6
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
Reduce: reduzieren des Handle
8
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$
5
6
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
9
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$
6
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
10
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$
7
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
11
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$
8
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
12
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$
9
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
13
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$
10
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
14
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$
11
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
15
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $
12
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
16
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $ Reduce 9
12 $ E + T * F $
13
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
17
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $ Reduce 9
12 $ E + T * F $ Reduce 5
13 $ E + T $
14
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
18
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $ Reduce 9
12 $ E + T * F $ Reduce 5
13 $ E + T $ Reduce 2
14 $ E $
15
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
19
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $ Reduce 9
12 $ E + T * F $ Reduce 5
13 $ E + T $ Reduce 2
14 $ E $ Reduce 1
15 $ S $
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
20
Syntaxanalyse mit einem StackNr. Stack: Input: Aktion:
1 $ id + num * id$ Shift id
2 $ id + num * id$ Reduce 9
3 $ F + num * id$ Reduce 7
4 $ T + num * id$ Reduce 4
5 $ E + num * id$ Shift +
6 $ E + num * id$ Shift num
7 $ E + num * id$ Reduce 8
8 $ E + F * id$ Reduce 7
9 $ E + T * id$ Shift *
10 $ E + T * id$ Shift id
11 $ E + T * id $ Reduce 9
12 $ E + T * F $ Reduce 5
13 $ E + T $ Reduce 2
14 $ E $ Reduce 1
15 $ S $ Accept
Grammatik G2:
1 S E
2 E E + T
3 E E –T
4 E T
5 T T * F
6 T T / F
7 T F
8 F num
9 F id
Accept: Eingabe entsprach der Grammatik erfolgreiches Ende
21
Operator-Precedence-Syntaxanalyse
Definition von Relationen zwischen dem obersten Stackelement und dem ersten Eingabesymbol (begrenzt auf Terminalsymbole)
Vorgehen:
< oder =: Shift
>: Reduce
Handles werden erkannt: <: linke Markierung des Handle
>: rechte Markierung des Handle
Relation: Semantik:
a <• b a hat niedrigere Priorität als b
a •> b a hat höhere Priorität als b
a = b a und b haben gleiche Priorität
$ <• id •> + <• id •> * <• id•> $
Erstes Handle
22
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2
3
4
5
6
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
23
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3
4
5
6
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
24
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4
5
6
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
25
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5
6
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
26
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
27
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
28
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7 $ E<•+<•* <• id$ Shift: <•id
8
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
29
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7 $ E<•+<•* <• id$ Shift: <•id
8 $E<•+<•*<•id •> $ Red: E id
9
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
30
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7 $ E<•+<•* <• id$ Shift: <•id
8 $E<•+<•*<•id •> $ Red: E id
9 $E<•+<•*E •> $ Red: E E*E
10
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
31
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7 $ E<•+<•* <• id$ Shift: <•id
8 $E<•+<•*<•id •> $ Red: E id
9 $E<•+<•*E •> $ Red: E E*E
10 $E<•+E •> $ Red: E E+E
11
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
32
Ablauf OP-Parser
Nr Stack: R. Input: Aktion:
1 $ <• id+id*id$ Shift: <•id
2 $<•id •> +id*id$ Red: E id
3 $E <• +id*id$ Shift: <•+
4 $E<•+ <• id*id$ Shift: <•id
5 $E<•+<•id •> *id$ Red: E id
6 $ E<•+E <• *id$ Shift: <•*
7 $ E<•+<•* <• id$ Shift: <•id
8 $E<•+<•*<•id •> $ Red: E id
9 $E<•+<•*E •> $ Red: E E*E
10 $E<•+E •> $ Red: E E+E
11 $E $ Accept
+ * ( ) id $
+ •> <• <• •> <• •>
* •> •> <• •> <• •>
( <• <• <• = <•
) •> •> •> •>
id •> •> •> •>
$ <• <• <• <•
Grammatik G3:
Regel 1: E E + E
Regel 2: E E * E
Regel 3: E ( E )
Regel 4: E id
Input
Stac
k
33
Operator-Grammatik
Grammatik muss folgende Bedingungen erfüllen, damit sie mit OP-Parser behandelt werden kann:1. Keine zwei aufeinander folgenden Nichtterminale auf der rechten
Seite einer Produktion.
2. Keine Produktion mit gleicher rechter Seite.
3. Keine ε-Produktionen.
sehr schwaches Verfahren!
34
LR-Syntaxanalyse
LR(k)LR(1)LALR(1)
SLR(1)
LR(0)LL(0)
LL(1)
LL(k)
Alle eindeutigen Grammatiken
LR(k)-Syntaxanalyse:L: left-to-right-parse
R: rightmost derivation: Rechtsableitung
k: k-token lookahead: Anzahl im Voraus betrachteter Inputsymbole
Quelle: Appel, Palsberg (2002).
35
Modell eines LR-Parsers
Action[sm,ai] = shift s |
reduce A β |
accept |
error.
a1 … ai … an $
Sm
Xm
Sm-1
Xm-1
…
S0
LR-Syntaxanalyse-Programm
Input
Syntaxanalyse-tabelle
Stack
Terminalsymbole
Output
Syntaxbaum
Zu
-stand
Action
(Terminale)
X1… Xn
Goto
(Nichtterminale)
X1… Xn
0
1
…
Goto[s‘, A]
36
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2
3
4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
37
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3
3
4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
38
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 T + id $ Reduce 3 2
3
4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
39
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 T 2 + id $ Reduce 3 2
3
4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
40
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
41
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4 $ 0 E 1 + id $ Shift 4
5
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
42
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4 $ 0 E 1 + id $ Shift 4
5 $ 0 E 1 + 4 id $ Shift 3
6
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
43
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4 $ 0 E 1 + id $ Shift 4
5 $ 0 E 1 + 4 id $ Shift 3
6 $ 0 E 1 + 4 id 3 $ Reduce 3 5
7
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
44
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4 $ 0 E 1 + id $ Shift 4
5 $ 0 E 1 + 4 id $ Shift 3
6 $ 0 E 1 + 4 id 3 $ Reduce 3 5
7 $ 0 E 1 + 4 T 5 $ Reduce 1 1
8
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
45
Ablauf LR-Parser
Nr Stack Input Action Goto
1 $ 0 id + id $ Shift 3
2 $ 0 id 3 + id $ Reduce 3 2
3 $ 0 T 2 + id $ Reduce 2 1
4 $ 0 E 1 + id $ Shift 4
5 $ 0 E 1 + 4 id $ Shift 3
6 $ 0 E 1 + 4 id 3 $ Reduce 3 5
7 $ 0 E 1 + 4 T 5 $ Reduce 1 1
8 $ 0 E 1 $ Accept
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
46
LR-Syntaxanalysetabelle-Konstruktion
Allgemeines Vorgehen:Erstellen von:
1. „Dummy-Produktion“: S‘ S (S ist altes Startsymbol).
2. Endlichem Automat.
3. Syntaxanalysetabelle.
47
Erstellen eines Zustandsübergangsgraphen
Grundbegriffe:
Items: Produktionen mit Markierungspunkt auf rechter Seite; zeigt an wie weit man im Parseprozess vorangeschritten ist.
A •XYZ
A X•YZ
A XY•Z
A XYZ•
Closure-Operation: fügt weitere Items zu einer Menge von Items hinzu.
Goto-Operation: Definiert Zustandsübergänge zwischen Mengen von Items/Zuständen des Automaten.
48
Erstellen eines Zustandsübergangsgraphen
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Closure-Operation anwenden!
49
Erstellen einer LR(0)-Syntaxanalysetabelle
Punkt am rechten Ende eines ItemsFalls Dummy-Item: Accept
Sonst Reduce
I J, mit X Terminalsymbol: Shift
I J, mit X Nichtterminalsymbol: Goto
50
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0
1
2
3
4
5
51
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1
2
3
4
5
52
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2
3
4
5
53
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3
4
5
54
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4
5
55
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5
56
Erstellen der LR(0)-Syntaxanalysetabelle
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
S •EE •E+TE •TT •id
S E•E E•+T
E T• T id•
S E+ •TT •id
E E+T•
E +
T id id T
I0
I2
I1
I3
I4
I5
Action Goto
Zust id + $ E T
0 s3 1 2
1 s4 acc
2 r2 r2 r2
3 r3 r3 r3
4 s3 5
5 r1 r1 r1
57
LR(0)-Syntaxanalyse
Grammatik G4:
Regel 1: E E + T
Regel 2: E T
Regel 3: T id
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
58
LR(0)-Syntaxanalyse
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 r2 s3, r2 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
S •EE •T+EE •TT •id
E
T
id
I0
S E• I1
E T•+EI2E T•
T id• I4
E T+ •EE •T+EE •TT •id
I3E T+E• I5
E
T+
59
LR(0)-Syntaxanalyse
Zwei mögliche Konflikte bei LR-Analyse:Shift-reduce-Konflikt
Reduce-reduce-Konflikt
60
SLR(1)-Syntaxanalyse
SLR(1)-Syntaxanalyse ist Erweiterung von LR(0):Anzahl von Reduce-Einträgen in Action-Tabelle kann verringert werden
Reduce-Aktionen werden nicht mehr für jedes Terminalsymbol eines Zustands eingetragen
Eintrag nur bei Terminalsymbolen, die sich in FOLLOW-Menge des Nichtterminals der Regel befinden
Informale FOLLOW-Definition:X ist ein Nichtterminal
FOLLOW(X) ist die Menge aller Terminale, die in einem Wort direkt rechts neben X stehen können
61
SLR(1)-SyntaxanalysetabelleFOLLOW(S): {$}
FOLLOW(E): {$}
FOLLOW(T): {+,$}
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 r2 s3, r2 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 s3 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
LR(0)-Syntaxanalysetabelle SLR(1)-Syntaxanalysetabelle
62
SLR(1)-SyntaxanalysetabelleFOLLOW(S): {$}
FOLLOW(E): {$}
FOLLOW(T): {+,$}
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 r2 s3, r2 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 s3 r2
3 s4 5 2
4 r3 r3
5 r1 r1 r1
LR(0)-Syntaxanalysetabelle SLR(1)-Syntaxanalysetabelle
63
SLR(1)-SyntaxanalysetabelleFOLLOW(S): {$}
FOLLOW(E): {$}
FOLLOW(T): {+,$}
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 r2 s3, r2 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 s3 r2
3 s4 5 2
4 r3 r3
5 r1
LR(0)-Syntaxanalysetabelle SLR(1)-Syntaxanalysetabelle
64
SLR(1)-SyntaxanalysetabelleFOLLOW(S): {$}
FOLLOW(E): {$}
FOLLOW(T): {+,$}
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 r2 s3, r2 r2
3 s4 5 2
4 r3 r3 r3
5 r1 r1 r1
Grammatik G5:
Regel 1: E T + E
Regel 2: E T
Regel 3: T id
Action Goto
Zust id + $ E T
0 s4 1 2
1 acc
2 s3 r2
3 s4 5 2
4 r3 r3
5 r1
LR(0)-Syntaxanalysetabelle SLR(1)-Syntaxanalysetabelle
65
LR(1)-Syntaxanalyse
Mit SLR(1) erstellte Syntaxanalysetabelle für Grammatik G6:
FOLLOW(S‘): {$}
FOLLOW(S): {$}
FOLLOW(E): {+,=,$}
Action Goto
Zust = + id $ S E
0 s3 1 2
1 acc
2 s4 s6
3 r4 r4 r2/r4
4 s8 5
5 s6 r1
6 s7
7 r3 r3 r3
8 r4 r4 r4
Grammatik G‘6:
Regel 0: S‘ S
Regel 1: S E = E
Regel 2: S id
Regel 3: E E + id
Regel 4: E id
66
LR(1)-Syntaxanalyse
id
S
S’
$
S’
S
E = E
id id
S’
S
+
idid
E
$ $
Anwendung von Regel 2
Anwendung von Regel 4
Anwendung von Regel 4
Grammatik G‘6:
Regel 0: S‘ S
Regel 1: S E = E
Regel 2: S id
Regel 3: E E + id
Regel 4: E id
Action Goto
Zust = + id $ S E
0 s3 1 2
1 acc
2 s4 s6
3 r4 r4 r2/r4
4 s8 5
5 s6 r1
6 s7
7 r3 r3 r3
8 r4 r4 r4
67
LR(1)-Syntaxanalyse
SLR(1)-Syntaxanalyse Nutzung von FOLLOW-Mengen
Globale Betrachtung, Zustand wird nicht berücksichtigt
LR(1)-SyntaxanalyseNutzung von LOOKAHEAD-Mengen
Für jeden Zustand wird Information mitverwaltet, welche Terminale auf ein Nichtterminal nach Reduktion einer bestimmten Reduktionsregel im Zustandsautomaten folgen können
68
LR(1)-Syntaxanalyse
Änderungen im Vergleich zu SLR(1):Verwendung von LR(1)- anstelle von LR(0)-Items.
Definition von closure- und goto-Operation für Behandlung der LOOKAHEAD-Mengen abgeändert. Anfangszustand ist [S‘ S, $].
Action-Tabelle nutzt LOOKAHEAD-Mengen und nicht FOLLOW-Mengen.
69
LR(1)-Syntaxanalyse
S‘ •S {$} S •E=E {$}S •id {$}E •E+id {+,=}
I0
E •id {+,=}
S‘ S• {$}
S
I1
S id• {$}
id
E id• {+,=}
I3
S E•=E {$}
E
E E•+id {+,=}
I2
I4
I6
+
=
Grammatik G‘6:
0: S‘ S
1: S E = E
2: S id
3: E E + id
4: E id
Kern LOOKAHEAD-Menge
70
LR(1)-Syntaxanalyse
Mit LR(1) erstellte Syntaxanalysetabelle für Grammatik G6:
Action Goto
Zust = + id $ S E
0 s3 1 2
1 acc
2 s4 s6
3 r4 r4 r2
4 s8 5
5 s9 r1
6 s7
7 r3 r3
8 r4 r4
9 s10
10 r3 r3
Grammatik G‘6:
Regel 0: S‘ S
Regel 1: S E = E
Regel 2: S id
Regel 3: E E + id
Regel 4: E id
71
LR(1)-Syntaxanalyse
LR(1) mächtiges Verfahren
Anzahl Zustände: Typische Programmiersprachen bei LR(0)/SLR(1) mehrere 100
Typische Programmiersprache bei LR(1) werden mehrere 1000
Motivation für LALR(1):Weniger Zustände als LR(1)
Trotzdem mächtig genug für typische Programmiersprachen
Vorgehen bei LALR(1):Zustände eines LR(1)-Zustandsübergangsgraphen mit gleichen Kernen zusammenfassen
72
LALR(1)-Syntaxanalyse
S’→ .S {$}S → .E=E {$}S → .id {$}E → .E+id {+,=}E → .id {+,=}
S
E
S’→ S. {$}
I1
S → id. {$}E → id. {+,=}
S → E.=E {$}E → E.+id {+,=}
S → E=.E {$}E → .E+id {+,$}E → .id {+,$}
=
I0
I3 I2 I4
E → id. {+,$}
I8
id
E → E+.id {+,=}
I6
+
E → E+id. {+,=}id
I7
S → E=E. {$}E → E.+id {+,$}
I5
E → E+.id {+,$}
I9
E → E+id. {+,$}
I10
E
+
id
Gleiche Kerne
73
LALR(1)-Syntaxanalyse
Mit LALR(1) erstellte Syntaxanalysetabelle für Grammatik G6:
Action Goto
Zust = + id $ S E
0 s3 1 2
1 acc
2 s4 s69
3 r4 r4 r2
4 s8 5
5 s69 r1
69 s710
710 r3 r3 r3
8 r4 r4
Grammatik G‘6:
Regel 0: S‘ S
Regel 1: S E = E
Regel 2: S id
Regel 3: E E + id
Regel 4: E id
74
Zusammenfassung
Operator-Precedence-Syntaxanalyse Einfach umzusetzendes Verfahren
Geringe Mächtigkeit
LR-Parser Mächtigste effiziente Parser
LR(0), SLR(1), LALR(1), LR(1)
Gleicher Ablaufalgorithmus, Unterschied Syntaxanalysetabelle
Immer Konstruktion eines Zustandsautomaten, aus dem Syntaxanalysetabelle abgeleitet werden kann
Meist wird LALR(1) eingesetzt
Derzeitige Algorithmen der Syntaxanalyse ausreichend für gängige Programmiersprachen
75
Fragen, Kommentare, Diskussion
