Fabian Berlin Syntaktische Analyse – Bottom-up Im Rahmen des Seminars Übersetzung von...

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