Beispiele für regulare Ausdrucke, Grammatiken und JJ II ... · JJ II J I Seite 1 von 62 Zurück Vollbild ein/aus Schließen Beenden Beispiele für regulare Ausdrucke, Grammatiken

Ubersicht

Kleine Grammatiken

Grammatik-Informationen

Automaten & Konflikte

Scannerdefinitionen

Attributierungen

Vollstandige Beispiele

Startseite

JJ II

J I

Seite 1 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Beispiele fur regulare Ausdrucke,

Grammatiken und

Attributierungen

Lothar Schmitz

[email protected]

23. Oktober 2003

mailto:[email protected]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 1 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

1. Ubersicht

Die Beispielsammlung beginnt mit einer Reihe kleiner Grammatiken, an denen die Unterschiede zwischen den un-terschiedlichen Parserklassen sichtbar werden (⇒ am besten mit SIC oder Jaccie erforschen!). Besonders wichtig:Grammatiken zur Formalisierung arithmetischer Ausdrucke, wie sie so oder ahnlich in praktisch allen Programmier-sprachen vorkommen.

Mit Hilfe unserer Werkzeuge kann man aus den Grammatiken Informationen ableiten, die wichtig fur die Syntax-analyse sind. In mathematisch praziser Notation werden dabei naheliegende Fragen beantwortet wie:

•”Mit welchen Zeichen kann ein (Teil-)Wort beginnen?“(⇒ first-Mengen)

•”Welche Zeichen konnen auf ein (Teil-)Wort folgen?“(⇒ follow -Mengen)

•”Kann man (bei der Top-Down-Analyse) anhand des ersten Zeichens entscheiden, mit welcher von mehreren

moglichen Alternativen man fortfahren muss?“(⇒ LL-Mengen bzw. -Konflikte)

•”Kann man (bei der Bottom-Up-Analyse) anhand des nachsten Zeichens entscheiden, ob man ein Zeichen lesen

oder nach einer Regel (welcher?) reduzieren muss?“(⇒ LR-Automaten und Konflikt-Zustande)

Die in den Abschnitten Grammatik-Informationen und Automaten & Konflikte gezeigten Informationen wurden mitSIC berechnet (mit Jaccie kommt man auf dieselben Ergebnisse).

Um Bausteine (wie Zahlen, Operatoren, Schlusselworter, Namen) komplexerer Sprachen effizient vorab erkennen zukonnen, bedient man sich sogenannter Scanner. Die Definition eines solchen Bausteins wird mit Hilfe von regularenAusdrucken beschrieben. Praktische Compiler-Compiler gestatten es, schon beim Erkennen von Zahlen o.a. Aktionen(konkret: Programmstucke) auszufuhren. Das wird im Abschnitt Scannerdefinitionen gezeigt.

Ist mit Hilfe von Scanner und Parser die Struktur der vorgelegten Zeichenreihe bestimmt, dann erfolgt die eigentlicheUbersetzung durch sogenannte Attributauswertung. Attribute sind beliebig geartete Informationsstuckchen, die denKnoten eines Syntaxbaums zugeordnet und in Baumdurchquerungen berechnet werden. Das Ubersetzungsergebnisliegt nach der Auswertung als Attribut des Wurzelknotens vor. Ubersichtliche Satze von Auswertungsregeln findetman in Abschnitt Attributierungen; die Vollstandigen Beispiele umfassen auch Scanner- und Grammatik-Definition.Alle zusammen zeigen, welch unterschiedliche Aufgaben man mit Compiler-Compilern bearbeiten kann.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 2 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

2. Kleine Grammatiken

Die Grammatikbeispiele fallen in verschiedene, uberlappende Kategorien:

Einfache Programmiersprachenteile

Hierzu gehoren arithmetische Ausdrucke (unter Berucksichtigung der Prazedenzen der Operatoren) und ge-schachtelte bedingte Anweisungen (mit

”dangling else“- Problem).

⇒ Garith, Garithll, Garithsimple⇒ Gif1, Gif2, Gif3, Gif4

Beispiele fur Parserklassen

Hier lohnt ein Blick auf alle angegeben Beispiele. Haufig unterscheiden sich verschiedene Grammatikvariantenin ihrer Zugehorigkeit zu den Klassen LL(1), LR(0), SLR(1), LALR(1) und LR(1). Da LR(1)-Sprachen haufigauch LALR(1) oder sogar SLR(1) sind, demonstrieren zwei

”unsinnige“ Grammatiken die Unterschiede zwischen

diesen Klassen. Schon einfache Sprachen wie die der Palindrome gehoren zu keiner der Klassen.

⇒ Garith, Garithll, Garithsimple⇒ Gif1, Gif2, Gif3, Gif4⇒ Gklammer1, Gklammer2, Gklammer3, Gklammerkomp⇒ Gab1, Gab2, Gab3, Gab4⇒ Gnslr, Gnlalr, Gidentity, Gepsilon⇒ Gpalin

Lehrreiche Spielsprachen

Hierzu rechne ich neben der Sprache der Palindrome die Sprachen der”Klammergebirge“ und die verwandte

Sprache der Worter mit gleicher Anzahl von as und bs. Unser kompliziertestes Beispiel ist die Komplement-sprache zu den Klammergebirgen.

⇒ Gpalin⇒ Gklammer1, Gklammer2, Gklammer3, Gklammerkomp⇒ Gab1, Gab2, Gab3, Gab4

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 3 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Folgende Regeln gehoren zur Grammatik Gnslr, die LALR(1) ist, aber nicht SLR(1):

S → C

| B d

| c A d

| d C

A → B

| a

B → b

C → A c

Folgende Regeln gehoren zur Grammatik Gnlalr, die LR(1) ist, aber nicht LALR(1):

S → a A d

| b B d

| a B e

| b A e

A → c

B → c

Auch die Grammatik Gidentity ist LR(1), aber nicht LALR(1):

S → L eq R

| R

L → star R

| id

R → L

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 4 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die einzige Daseinsberechtigung der Grammatik Gepsilon ist, dass sie viele ε-Symbole enthalt:

S → C C

| A E

A → B D

| S C

B → a C

| C S A

C → ε

D → d

| S S

E → b E b

Die Grammatik Gepsilon ist ubrigens auch nicht LR(1) und enthalt viele nutzlose Symbole, die nichts zum Sprach-

schatz beitragen. Eine einfachere Grammatik mit gleichem Sprachschatz (Gepsilon = {ε}) hat nur eine einzige Regel

und gehort zu allen von uns betrachteten Parsing-Klassen:

S → ε

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 5 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die mehrdeutige Grammatik Garithsimple berucksichtigt die Prazedenzen der verschiedenen Operatoren nicht:

E → E + E | E ∗ E | ( E ) | id

Die Regeln von Garith, der bekannten Grammatik der arithmetischen Ausdrucke geben die Prazedenzen der verschie-denen Operatoren dagegen korrekt wieder:

E → E + T

| T

T → T ∗ F

| F

F → ( E )

| id

Die Regeln von Garithll, der LL(1)-Grammatik der arithmetischen Ausdrucke

(Garithll entsteht aus Garith durch Elimination von Linksrekursion):

E → T A

A → + T A

| ε

T → F B

B → ∗ F B

| ε

F → ( E )

| id

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 6 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Sogenannte Klammergebirge entstehen, wenn man in arithmetischen Ausdrucken alles bis auf die Klammern streicht.

Die naheliegendste Formalisierung Gklammer1 besagt, dass Klammergebirge in Klammern eingebettet werden durfen,dass zwei aufeinanderfolgende Klammergebirge wieder ein Klammergebirge ergeben und dass ein Klammergebirgeauch leer sein kann (diese Grammatik ist mehrdeutig und damit auch nicht LR(1)):

S → ( S )

| S S

| ε

Die zweite Formalisierung Gklammer2 besagt, dass ein Klammergebirge entweder leer ist oder mit einer offnendenKlammer beginnt, die zusammen mit ihrer schließenden Klammer ein Klammergebirge umfasst, auf das wiederumein Klammergebirge folgen kann (diese Grammatik ist LL(1) und SLR(1), aber nicht LR(0)):

S → ( S ) S

| ε

Die dritte Formalisierung Gklammer3 beschreibt die Sprache der nicht-leeren Klammergebirge und ist interessant alsAusgangspunkt der Konstruktion der Grammatik Gklammerkomp (beide Grammatiken sind LR(1)):

S → A

A → A B

| B

B → ( )

| ( A )

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 7 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Grammatik Gklammerkomp ergibt sich aus der Grammatik Gklammer3 nach einer von Heilbrunner gefundenen

Konstruktion, mittels derer man zu einer gegebenen LR(1)-Grammatik G eine weitere LR(1)-Grammatik G′ mitkomplementarem Sprachschatz erhalt.

Gklammerkomp beschreibt demnach genau die Folgen von Klammern (offnende bzw. schließende), die keine gultigen

Klammergebirge sind:

S → D

A → A B

| B

B → ( )

| ( A )

C → ( C

| ) C

| ε

D → ) C

| A ) C

| A ( E

| ( E

| ε

E → ( E

| A ( E

| A

| ε

Konnen Sie erlautern, was die einzelnen Regeln dazu beitragen?

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 8 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die folgenden vier Grammatiken erzeugen alle die Sprache (uber {a, b}) der Worter die gleich viele as und bs enthalten.Gab1 und Gab3 sind nicht LR(1); die beiden anderen sind jeweils LL(1) und SLR(1), aber nicht LR(0).

In der ersten Formalisierung Gab1 sind aus A genau die Worter herleitbar, die ein a mehr als bs enthalten; analogenthalten die aus B herleitbaren Worter ein b mehr als as und die aus S herleitbaren Worter gleich viele as und bs:

S → a B

| b A

| ε

A → a S

| b A A

| a

B → b S

| a B B

| b

Die zweite Formalisierung Gab2 ergibt sich durch einen”geringfugigen“ Umbau aus Gab1:

S → a B S

| b A S

| ε

A → b A A

| a

B → a B B

| b

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 9 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die dritte Formalisierung Gab3 ahnelt im Aufbau der Grammatik Gklammer2:

S → a S b S

| b S a S

| ε

Die vierte Formalisierung Gab4 unterscheidet bei den Teilwortern zwischen solchen, die mit a beginnen (und aus Aherleitbar sind) und solchen, die mit b beginnen (und aus B herleitbar sind):

S → a A b S

| b B a S

| ε

A → a A b A

| ε

S → b B a B

| ε

Folgende Regeln gehoren zur Grammatik Gpalin (der Palindrome uber {0, 1}), die nicht LR(1) ist:

S → 0 S 0

| 1 S 1

| 0

| 1

→ ε

(Alle Grammatiken zur Sprache der Palindrome sind nicht LR(1).)

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 10 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Imperative Programmiersprachen enthalten u.a. Zuweisungen und bedingte Anweisungen; letztere konnen”einseitig“

(if ... then ...) oder”zweiseitig“ (if ... then ... else ...) vorkommen.

Bei den folgenden vier Grammatiken geht es darum, geschachtelte Programmteile aus Zuweisungen und bedingtenAnweisungen zu beschreiben.

Die erste, naheliegende Formalisierung Gif1 ist syntaktisch mehrdeutig (bekannt als”dangling else“-Problematik —

zu welchem then gehort ein else?):

S → if bed then S else S

| if bed then S

| zuweisung

Die zweite Formalisierung Gif2 schafft Eindeutigkeit, indem ein else immer dem unmittelbar vorangehenden then

zugeordnet wird:

S → if bed then A else S

| if bed then S | zuweisung

A → if bed then A else A | zuweisung

Die dritte Formalisierung Gif3 schafft Eindeutigkeit durch Verwendung eines abschließenden fi:

S → if bed then S else S fi

| if bed then S fi | zuweisung

In der vierten Formalisierung Gif4 werden die gemeinsamen Teile der ersten und zweiten Alternative aus Gif3 zu-sammengefasst:

S → if bed then S R | zuweisung

R → else S fi

| fi

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 11 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

3. Grammatik-Informationen

Wir zeigen die erwahnten, automatisch berechneten Informationen anhand der Grammatiken Garith und Garithll:

LL(1)-informations for: Arith

First sets:E -> T { id ( }E -> E + T { id ( }T -> T * F { id ( }T -> F { id ( }F -> id { id }F -> ( E ) { ( }

Follow sets:E { # + ) }F { # + ) * }T { # + ) * }

Lookahead sets:E -> T { id ( }E -> E + T { id ( }T -> T * F { id ( }T -> F { id ( }F -> id { id }F -> ( E ) { ( }

Bei First sets steht nach jeder Alternative die Menge der terminalen Symbole, mit denen eine Zeichenreihebeginnen kann, die sich aus der rechten Seite der Alternative ableiten lasst. Bei Grammatiken ohne ε-Symbole wieGarith stimmen die First sets mit den Lookahead sets uberein.

Der Follow set eines nichtterminalen Symbols X enthalt die terminalen Zeichen, die in irgendeiner Satzform aufX unmittelbar folgen konnen. Die Follow sets werden zur Konstruktion der Lookahead sets und verschiedenerLR-Automaten benotigt.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 12 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Analog erhalt man fur Garithll:

LL(1)-informations for: ArithLL

First sets:E -> T A { id ( }T -> F M { id ( }A -> { }A -> + T A { + }F -> id { id }F -> ( E ) { ( }M -> * F M { * }M -> { }

Follow sets:E { # ) }F { # + ) * }T { # + ) }A { # ) }M { # + ) }

Epsilon-symbols:MA

Da die Grammatik Garithll zwei ε-Symbole enthalt, unterscheiden sich die First sets und die Lookahead sets

auf der nachsten Seite ein wenig.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 13 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Lookahead sets:E -> T A { id ( }F -> id { id }F -> ( E ) { ( }T -> F M { id ( }A -> { # ) }A -> + T A { + }M -> * F M { * }M -> { # + ) }

Um bei der Top-Down-Analyse anhand des ersten Zeichens zu entscheiden, mit welcher von mehreren moglichenAlternativen man fortfahren muss, bedient man sich der Lookahead sets, welche die terminalen Symbole enthalten,mit denen eine Alternative (bzw. die daraus abgeleitete Zeichenreihe) beginnen kann.

Bei Garith zeigen folgende Zeilen, dass man so nicht zwischen den beiden Alternativen von E unterscheiden kann.Die Grammatik ist also nicht LL(1)!

Lookahead sets:E -> T { id ( }E -> E + T { id ( }

Im Unterschied dazu haben die verschiedenen Alternativen zu F, A und M in Garithll jeweils disjunkte Lookahead

sets. Da die Nichtterminale E und E nur jeweils eine Alternative haben — also nichts zu unterscheiden ist — ist dieGrammatik LL(1)!

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 14 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Symbole der Grammatik Gepsilon sind fast alle ε-Symbole, auch wenn nur eine ε-Regel vorkommt:

LL(1)-informations for: Epsilon

First sets: S -> C C { } S -> A E { a b d }

A -> S C { a b d } A -> B D { a b d }

B -> a C { a } B -> C S A { a b d }

C -> { }

D -> d { d } D -> D S { d }

E -> b E b { b }

Follow sets:S { # a b d }A { b d }B { d }C { # a b d }D { # a b d }E { # a b d }

Epsilon-symbols:BCSA

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 15 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

4. Automaten & Konflikte

Wir greifen hier einige der schon eingefuhrten Grammatiken heraus und zeigen verschiedene Arten von LR-Automaten,welche die Zuordnung der Grammatiken zu Parserklassen belegen.

Da Automaten bereits fur einfache Grammatiken sehr umfangreich sind, haben wir einige kleinere Grammatikenausgewahlt. Die Darstellung ist so, wie sie mit unseren Werkzeugen (hier SIC) erzeugt werden kann.

• Die Grammatik Gpalin ist nicht LR(1) und damit auch nicht in einer der anderen Parser-Klassen (LALR(1),

SLR(1), LR(0), LL(1)), weil ihr LR(1)-Automat ALR(1)(Gpalin) Konfliktzustande enthalt. Tatsachlich ist nicht

nur die Grammatik mehrdeutig, sondern sogar die Sprache der Palindrome inharent mehrdeutig. Es kann alsokeine Grammatik zu dieser Sprache geben, die einen deterministischen Parser besitzt. Mit SIC und Jaccie kannman auch mit nichtdeterministischen Parsern arbeiten (ggfs. dem Parser die richtige Entscheidung sagen oderihn mit Backtracking probieren lassen).

• Die Grammatik Gidentity ist LALR(1), weil der Automat ALALR(1)(Gidentity) konfliktfrei ist, aber nicht

SLR(1), weil der Automat ASLR(1)(Gidentity) Konfliktzustande enthalt.

• Die Grammatik Gklammer2 ist SLR(1), weil der Automat ASLR(1)(Gklammer2) konfliktfrei ist, aber nichtLR(0), weil der Automat ALR(0)(Gklammer2) Konfliktzustande enthalt.

• Aus den gleichen Grunden ist die praktische und nur wenig umfangreichere Grammatik Garith SLR(1), weil derAutomat ASLR(1)(Garith) konfliktfrei ist, aber nicht LR(0), weil der Automat ALR(0)(Garith) Konfliktzustandeenthalt.

In der vom Werkzeug verwendeten Fassung der Grammatik sind die Symbole”ausgeschrieben“ (z.B. Expression

statt E) und das terminale Symbol id ersetzt durch die beiden darin enthaltenen Alternativen name und number.Man sieht, dass schon bei kleinen praktischen Beispielen die Automaten sehr schnell sehr umfangreich werden.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 16 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Der Automat ALR(1)(Gpalin) hat 20 Zustande. Wegen des Umfangs zeigen wir nur die vier”0“-Konflikte (nebst den

sie enthaltenden Zustanden), denn die anderen vier Konflikte (fur das Zeichen”1“) sind vollig symmetrisch:

1. conflict for: 0

S -> 1 · ,0S -> · 0,1S -> · 0 S 0,1

Conflict-state: I1

S -> 1 · S 1,0S -> 1 · ,0S -> · 1 S 1,1S -> · 0,1S -> · 1,1S -> · 0 S 0,1S -> · ,1

2. conflict for: 0

S -> · 0,0S -> · 0 S 0,0S -> · ,0

Conflict-state: I14

S -> 0 · ,#S -> 0 · S 0,#S -> · 1 S 1,0S -> · 0,0S -> · 1,0S -> · 0 S 0,0S -> · ,0

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 17 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

3. conflict for: 0

S -> 0 · ,0S -> · 0,0S -> · 0 S 0,0S -> · ,0

Conflict-state: I16

S -> 0 · ,0S -> 0 · S 0,0S -> · 1 S 1,0S -> · 0,0S -> · 1,0S -> · 0 S 0,0S -> · ,0

4. conflict for: 0

S -> · 0,0S -> · 0 S 0,0S -> · ,0

Conflict-state: I18

S -> 0 · ,1S -> 0 · S 0,1S -> · 1 S 1,0S -> · 0,0S -> · 1,0S -> · 0 S 0,0S -> · ,0

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 18 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Der Automat ASLR(1)(Gidentity) hat einen einzigen shift-reduce-Konflikt (siehe weiter unten):

SLR(1)-Automaton for: Identity

I0: S’ -> · S,#S -> · L eq R,#S -> · R,#L -> · star R,#,eqL -> · id,#,eqR -> · L,#,eq

star -> I1R -> I8S -> I5L -> I2id -> I4

I1: L -> star · R,#,eqL -> · id,#,eqL -> · star R,#,eqR -> · L,#,eq

star -> I1R -> I7L -> I3id -> I4

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 19 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

I2: S -> L · eq R,#R -> L · ,#,eq

eq -> I9

I3: R -> L · ,#,eq

I4: L -> id · ,#,eq

I5: S’ -> S · ,#

I6: S -> L eq R · ,#

I7: L -> star R · ,#,eq

I8: S -> R · ,#

I9: S -> L eq · R,#L -> · id,#,eqL -> · star R,#,eqR -> · L,#,eq

star -> I1R -> I6L -> I3id -> I4

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 20 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Conflicts

1. conflict for: eq

S -> L · eq R,#R -> L · ,#,eq

Conflict-state: I2

S -> L · eq R,#R -> L · ,#,eq

Der entsprechende Zustand des Automaten ALALR(1)(Gidentity) ist konfliktfrei, die Grammatik Gidentity also

LALR(1):

I2: S -> L · eq R,#R -> L · ,#

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 21 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Der Automat ALR(0)(Gklammer2) und danach die in ihm enthaltenen shift-reduce-Konflikte:

LR(0)-Automaton for: Klammer2

I0: S’ -> · SS -> · left S right SS -> ·

S -> I1left -> I4

I1: S’ -> S ·

I2: S -> left S · right S

right -> I5

I3: S -> left S right S ·

I4: S -> left · S right SS -> · left S right SS -> ·

S -> I2left -> I4

I5: S -> left S right · SS -> · left S right SS -> ·

S -> I3left -> I4

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 22 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Conflicts

1. conflict for: left

S -> · left S right SS -> ·

Conflict-state: I0

S’ -> · SS -> · left S right SS -> ·



Conflict-state: I4

S -> left · S right SS -> · left S right SS -> ·



Conflict-state: I5

S -> left S right · SS -> · left S right SS -> ·

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 23 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Der Automat ASLR(1)(Gklammer2) dagegen ist konfliktfrei, die Grammatik Gklammer2 also SLR(1):

SLR(1)-Automaton for: Klammer2

I0: S’ -> · S,#S -> · left S right S,#,rightS -> · ,#,right

S -> I1left -> I4

I1: S’ -> S · ,#

I2: S -> left S · right S,#,right

right -> I5

I3: S -> left S right S · ,#,right

I4: S -> left · S right S,#,rightS -> · left S right S,#,rightS -> · ,#,right

S -> I2left -> I4

I5: S -> left S right · S,#,rightS -> · left S right S,#,rightS -> · ,#,right

S -> I3left -> I4

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 24 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Der Automat ALR(0)(Garith) und danach die drei in ihm enthaltenen Konflikte:

LR(0)-Automaton for: Arith

I0: S’ -> · ArithmeticArithmetic -> · ExpressionExpression -> · Expression addOp TermExpression -> · TermFactor -> · openingBracket Expression closingBracketFactor -> · numberFactor -> · nameTerm -> · FactorTerm -> · Term multOp Factor

openingBracket -> I1Term -> I6Factor -> I3number -> I9Arithmetic -> I10name -> I11Expression -> I12

I1: Factor -> openingBracket · Expression closingBracketExpression -> · Expression addOp TermExpression -> · TermFactor -> · openingBracket Expression closingBracketFactor -> · numberFactor -> · nameTerm -> · FactorTerm -> · Term multOp Factor

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 25 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

openingBracket -> I1Term -> I6Factor -> I3number -> I9name -> I11Expression -> I13

I2: Expression -> Expression addOp · TermFactor -> · openingBracket Expression closingBracketFactor -> · numberFactor -> · nameTerm -> · Term multOp FactorTerm -> · Factor

name -> I11Factor -> I3Term -> I5openingBracket -> I1number -> I9

I3: Term -> Factor ·

I4: Term -> Term multOp Factor ·

I5: Expression -> Expression addOp Term ·Term -> Term · multOp Factor

multOp -> I7

I6: Expression -> Term ·Term -> Term · multOp Factor

multOp -> I7

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 26 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

I7: Term -> Term multOp · FactorFactor -> · nameFactor -> · numberFactor -> · openingBracket Expression closingBracket

name -> I11Factor -> I4openingBracket -> I1number -> I9

I8: Factor -> openingBracket Expression closingBracket ·

I9: Factor -> number ·

I10:S’ -> Arithmetic ·

I11:Factor -> name ·

I12:Arithmetic -> Expression ·Expression -> Expression · addOp Term

addOp -> I2

I13:Expression -> Expression · addOp TermFactor -> openingBracket Expression · closingBracket

addOp -> I2closingBracket -> I8

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 27 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Conflicts

1. conflict for: addOp

Arithmetic -> Expression ·Expression -> Expression · addOp Term

Conflict-state: I12

Arithmetic -> Expression ·Expression -> Expression · addOp Term

2. conflict for: multOp

Expression -> Expression addOp Term ·Term -> Term · multOp Factor

Conflict-state: I5

Expression -> Expression addOp Term ·Term -> Term · multOp Factor

3. conflict for: multOp

Expression -> Term ·Term -> Term · multOp Factor

Conflict-state: I6

Expression -> Term ·Term -> Term · multOp Factor

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 28 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die entsprechenden Zustande des Automaten ASLR(1)(Garith) sind konfliktfrei, die Grammatik Garith also SLR(1):

I12:Arithmetic -> Expression · ,#Expression -> Expression · addOp Term,#,addOp,closingBracket

addOp -> I2

I5: Expression -> Expression addOp Term · ,#,addOp,closingBracketTerm -> Term · multOp Factor,#,addOp,closingBracket,multOp

multOp -> I7

I6: Expression -> Term · ,#,addOp,closingBracketTerm -> Term · multOp Factor,#,addOp,closingBracket,multOp

multOp -> I7

In allen Fallen erlaubt der hinzugekommene Rechtskontext, eindeutig zwischen shift- und reduce-Aktion zu unter-scheiden. Im Zustand I5 beispielsweise kommt das Shift-Symbol multop des Items

[Term -> Term · multOp Factor,...]

nicht unter den zulassigen Rechtskontexten aus { #,addOp,closingBracket } des Reduktionsitems

[Expression -> Expression addOp Term · ,...]

vor.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 29 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

5. Scannerdefinitionen

Die zwei wesentlichen Teile einer Scannerdefinition sind:

Patterns:

Das sind benannte regulare Ausdrucke, durch die verschiedene regulare Sprachen definiert werden, die manin der Eingabe erkennen mochte. Die Menge der Patterns muss vollstandig sein in dem Sinn, dass jedesEingabezeichen auch verarbeitet werden kann (diese Forderung wird wegen der Anbindung an eine Grammatikgestellt, s.u.).

Tokens:

Dieser Teil der Scannerdefinition stellt den Anschluss des Scanners an einen Parser dar: Mit jedem Token(terminalen Symbol der Grammatik) wird ein regularer Ausdruck verbunden. Umgekehrt muss es nicht zujedem regularen Ausdruck auch ein Token geben: Haufig dienen einige der Patterns als Hilfsdefinitionen.

Wir betrachten drei Beispiele:

• Definitionen von verschiedenen Zahlarten, Bezeichnern und Operatoren, wie sie in Programmiersprachen vor-kommen. Ein Eingabebeispiel und das entsprechende Resultat zeigt die Wirkung der Definitionen, insbesonderedie Auflosung von Uberlappungssituationen.

• Als umfangreicheres und realistischeres Beispiel die Scannerdefinition zu MiniDoc, einem selbstdefinierten LATEX-Ausschnitt.

• Das dritte Beispiel demonstriert an der Verarbeitung von Bank-Uberweisungsformularen die Verwendung vonbenutzerdefinierten Verarbeitungszustanden und bei der Formulierung von Aktionen. Aktionen konnen zu Be-ginn und bei Erkennung eines Tokens verwendet werden und bestehen aus Programmstucken. Dieses Beispielist SIC-spezifisch (die Programmstucke sind in Smalltalk abgefasst).

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 30 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Zahlarten demonstrieren Schreibweisen, wie sie in den genannten Programmiersprachen (u.a.) erlaubt sind. Wirunterscheiden hier PL1- und Algol60-Zahlen daran, ob bei Fließpunktkonstanten die Ziffernfolge vor dem Dezimal-punkt leer sein darf oder nicht. In Ada-Zahlkonstanten konnen Zifferngruppen (hier rechtsbundig der Lange 3) durchUnterstriche von einander abgesetzt werden. Die anderen Regularen Ausdrucke (RAs) sind entweder Alternativen vonEinzelsymbolen (z.B. addOpRA) oder Bereichsangaben (wie bei Buchstaben bzw. Ziffern) oder daraus zusammenge-setzt (Bezeichner und Zahlen).

Patterns:addOpRA $+|$-multOpRA $*|$/openingBracketRA $(closingBracketRA $)letterRA {$a-$z}|{$A-$Z}digitRA {$0-$9}nameRA letterRA(letterRA|digitRA)[0-*]numberRA digitRA[1-*]algol60RA ($+|$-)[0-1]numberRA($.numberRA)[0-1]($E$-[0-1]numberRA)[0-1]pl1RA ($+|$-)[0-1]($.numberRA|numberRA($.numberRA)[0-1])($E$-[0-1]numberRA)[0-1]adaRA digitRA[1-3]($_digitRA[3-3])[0-*]

Tokens:addOp addOpRAmultOp multOpRAopeningBracket openingBracketRAclosingBracket closingBracketRAname nameRAada adaRApl1 pl1RAalgol60 algol60RAunsignedInteger numberRA

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 31 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Konnen Sie erklaren, warum die Eingabe

1E- 22_133_1234.1 -22.33E-12 - 22 -2E2 2E.2 .33E-12.2 -22.33 -12++.2EE2 12

die folgende Aufteilung in Token ergibt (der Text aus der Eingabezeichenfolge steht jeweils hinter dem Tokennamen)?

unsignedInteger�1�

name�E�

addOp�-�

ada�22_133_123�

pl1�4.1�

algol60�-22.33E-12�

addOp�-�


algol60�-2E2�


name�E�

pl1�.2�

pl1�.33E-12�

pl1�.2�

algol60�-22.33�

algol60�-12�

addOp�+�

pl1�+.2�

name�EE2�


Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 32 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Minidoc-Tokens sind großenteils Schlusselworter, aber auch Zahlen und Bezeichner.

Patterns:digit {$0-$9}numberpattern digit [1-*]letter {$a-$z}|{$A-$Z}wordpattern letter [1-*]docStylepattern ’\documentstyle{simple}’beginDocpattern ’\begin{document}’endDocpattern ’\end{document}’newpattern ’\newcommand’oBpattern ’{’cBpattern ’}’oSpattern ’[’cSpattern ’]’setpattern ’\setcounter{theorem}’oppattern $+|$-|$*equalspattern $=refpattern ’\ref’beginDisplaypattern ’\begin{displaymath}’endDisplaypattern ’\end{displaymath}’beginEqupattern ’\begin{equation}’endEqupattern ’\end{equation}’sharppattern $#backslashpattern $\uppattern $^downpattern $_sqrtpattern ’\sqrt’fracpattern ’\frac’oPpattern ’(’cPpattern ’)’plusminuspattern ’+-’punctuationpattern $.|$,|$!|$?labelpattern ’\label’ref $( numberpattern $/ numberpattern $)

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 33 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Tokens:number numberpatternword wordpatterndocStyle docStylepatternbeginDoc beginDocpatternendDoc endDocpatternnew newpatternoB oBpatterncB cBpatternoS oSpatterncS cSpatternset setpatternop oppatternequals equalspatternref refpatternbeginDisplay beginDisplaypatternendDisplay endDisplaypatternbeginEqu beginEqupatternendEqu endEqupatternsharp sharppatternbackslash backslashpatternup uppatterndown downpatternsqrt sqrtpatternfrac fracpatternoP oPpatterncP cPpatternplusminus plusminuspatternpunctuation punctuationpatternlabel labelpattern

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 34 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Eingabe

\documentstyle{simple}\newcommand{\mult}[2](#1 + #2)*(#1 - #2)\newcommand{\plus}[0](x + \sqrt{y})\newcommand{\minus}[0](x - \sqrt{y})\setcounter{theorem}{3}

\begin{document}In Bronsteins TASCHENBUCH DER MATHEMATIK findet mandie nachfolgende Umformung.\begin{equation}

\frac{1}{\plus}\label{eins}

\end{equation}\begin{equation}

=\frac{\minus}{\mult{x}{\sqrt{y}}}\label{zwei}

\end{equation}\begin{equation}

=\frac{\minus}{x ^ {2} - y} \label{drei}\end{equation} Der Uebergang von \ref{zwei}nach \ref{drei} beruht auf \ref{quadrat} undsollte jedem einleuchten.\begin{equation}

\mult{a}{b}=a ^ {2} - b ^ {2} \label{quadrat}\end{equation}

\end{document}

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 35 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

ergibt (gekurzt auf Anfang bis einschließlich Makrodefinition”mult“):

docStyle�\documentstyle{simple}�

new�\newcommand�

oB�{�

backslash�\�

word�mult�

cB�}�

oS�[�

number�2�

cS�]�

oP�(�

sharp�#�

number�1�

op�+�

sharp�#�

number�2�

cP�)�

op�*�

oP�(�

sharp�#�

number�1�

op�-�

sharp�#�

number�2�

cP�)�

...

endDoc�\end{document}�

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 36 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Uberweisungsformulare enthalten an (durch Zeilen- und Spaltenbereich definierten) Eintragungsstellen Angaben,die zwar ahnlich aufgebaut sind, aber je nach Ort verschieden interpretiert werden.

Interessant sind an diesem Beispiel weniger die Definitionen der Regularen Ausdrucke:

Patterns:digitpattern {$0-$9}smallletterpattern {$a-$z}capitalletterpattern {$A-$Z}symbolpattern {(0)-(255)}namepattern capitalletterpattern smallletterpattern[0-*]accountpattern digitpattern[1-*]zipcodepattern digitpattern[8-8]wordpattern symbolpattern[1-*]europattern digitpattern[1-*]centpattern digitpattern[2-2]

Verschiedene konkurrierende Ziffernfolgen (Kontonummer, Postleitzahl, Euro- und Centzahlen) sind nur an bestimm-ten Formularpositionen zulassig und schließen einander dadurch aus.

Noch allgemeiner sind wordpatterns: Sie sind beliebig lange, nichtleere Zeichenfolgen, wobei jedes enthalteneSymbol einem der ASCII-Zeichen mit den Codes 0 bis 255 entspricht — das trifft auf alle Eingabezeichen zu.

Ein entsprechendes Word-Token muss sich in einer der Zeilen 9, 13 oder 15 und im Spaltenbereich von Spalte 6 bisSpalte 59 befinden, um erkannt zu werden:

Tokens:Word wordpattern

start:[(#(9,13,15) includes: (internals at: #line)) &((internals at: #column) >= 6)]

end:[(internals at: #column) <= 59]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 37 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Namen konnen sowohl Familien- als auch Vornamen sein. Hier fordert unser Beispiel, dass zuerst der Familiennameund dann der Vorname angegeben wird. Da beide nacheinander im gleichen Formularfeld stehen, wird zwischen beidenanhand eines benutzerdefinierten

”Verarbeitungszustands“ unterschieden, der laut Definition einer von den folgenden

beiden sein muss:

States:#Normal#FamilyNameRecognized

Im Zustand Normal wird der Familienname erkannt, im Zustand FamilyNameRecognized der Vorname.

Das Eingabefeld fur Namen-Token befindet sich in Zeile 5 zwischen den Spalten 6 und 59:

FamilyName namepatternstart:[((internals at: #line) = 5) &

((internals at: #column) >= 6) &((internals at: #state) = #Normal)]

end:[(internals at: #column) <= 59]action: [internals at: #state put: #FamilyNameRecognized.]

ChristianName namepatternstart:[((internals at: #line) = 5) &

((internals at: #column) >= 6) &((internals at: #state) = #FamilyNameRecognized)]

end:[(internals at: #column) <= 59]

Nach dem Erkennen eines Namensteils wird im action-Teil der benutzerdefinierte Verarbeitungszustand fortgeschal-tet.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 38 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Ahnlich die Erkennung der ubrigen Token in den ihnen zugeordneten Eingabefeldern des Uberweisungsformulars:

AccountNo accountpatternstart:[((internals at: #line) = 7) &

((internals at: #column) >= 6)]end:[(internals at: #column) <= 26]action: [internals at: #state put: #Normal.]

ZipCode zipcodepatternstart:[((internals at: #line) = 7) &

((internals at: #column) >= 44)]end:[(internals at: #column) <= 59]

Euro europatternstart:[((internals at: #line) = 11) &


Cent centpatternstart:[((internals at: #line) = 11) &


Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 39 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

6. Attributierungen

Wir betrachten zwei einfache Grammatiken und dazu jeweils zwei Attributierungen.

• Das erste Beispiel stammt von Donald Knuth, dem Erfinder der attributierten Grammatiken, und wurde vonihm als Einfuhrungsbeispiel verwendet.

Die Grammatik beschreibt den Aufbau von Binarzahlen ohne Vorzeichen, aber optional mit Nachkommateil.Beide Attributierungen definieren die Zuordnung des Zahlwerts zu der gegebenen Zeichenreihe.

– Die erste Attributierung verwendet drei Attribute, darunter ein ererbtes.

– Die zweite Attributierung zeigt am Beispiel, dass man auch ganz ohne ererbte Attribute auskommen kann(manchmal sind sie aber sehr praktisch zu verwenden).

• Dem zweiten Beispiel liegt die Grammatik Garith zugrunde, und zwar in der ausfuhrlichen Fassung aus dem Au-tomaten ALR(0)(Garith), wobei allerdings die Alternative Factor -> name gestrichen wurde, um das Beispieluberschaubar zu halten.

Die beiden Attributierungen leisten in diesem Fall Unterschiedliches:

– Die Auswertungs-Attributierung ermittelt — ahnlich wie oben bei den Binarzahlen — den numerischenWert des Ausdrucks.

– Die Ubersetzungs-Attributierung ubertragt den arithmetischen Ausdruck in eine Folge von Maschinenbe-fehlen, die (mit Hilfe eines Auswertungskellers) den Wert des Ausdrucks bestimmen.

Die Auswertungs-Attributierung beschreibt Auswertung durch einen Interpreter, die Ubersetzungs-AttributierungAuswertung durch einen Compiler.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 40 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Syntax der Binarzahlen ist gegeben durch die Scannerdefinition:

Patterns:zeroPattern $0onePattern $1fullstopPattern $.

Tokens:zero zeroPatternone onePatternfullstop fullstopPattern

und die Grammatik:

Startsymbol:N

Rules:N -> L fullstop L

| L

L -> L B| B

B -> one| zero

Eine Zahl (Number N) ist eine Liste (L) von Bits (B) oder eine Vorkomma-Liste, die durch einen Dezimalpunkt vonder Nachkomma-Liste getrennt ist.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 41 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die erste Attributierung verwendet folgende Attribute:

Attributes:�w�l�s

Dabei steht

• das synthetisierte Attribut �w fur den Wert des zugehorigen Knotens,

• das synthetisierte Attribut �l fur die Lange und

• das ererbte Attribut �s fur die Stelle in der Zahl (positiv bei Vorkomma-, negativ bei Nachkommastellen).

Die Attribute sind den Nichtterminalen wie folgt zugeordnet:

Nonterminals:N �wL �w �l �sB �w �s

In einem vollstandig attributierten Syntaxbaum enthalt also

• jeder N-Knoten ein �w-Attribut

• jeder L-Knoten ein �w-, ein �l- und ein �s-Attribut

• jeder B-Knoten ein �w- und ein �s-Attribut

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 42 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

In der ersten der folgenden Attributauswertungsregeln steht

• wN fur das �w-Attribut des N-Knotens auf der linken Seite

• wL1 fur das �w-Attribut des ersten L-Knotens auf der rechten Seite

• wL2 fur das �w-Attribut des zweiten L-Knotens auf der rechten Seite

Rules with [Attribute Rules]:N -> L fullstop L

[wN := wL1 + wL2][sL1 := 0][sL2 := 0 - lL2]

N -> L[wN := wL][sL := 0]

L -> L B[wL1 := wL2 + wB][lL1 := lL2 + 1][sL2 := sL1 + 1][sB := sL1]

L -> B[wL := wB][lL := 1][sB := sL]

B -> one[wB := 2 ** sB]

B -> zero[wB := 0]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 43 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die zweite Attributierung kommt bei der Berechnung des Zahlwerts ohne das ererbte �s-Attribut aus:

Nonterminals:N �wL �w �lB �w

Auch werden weniger (aber andere) Attributauswertungsregeln benotigt:

Rules with [Attribute Rules]:

N -> L fullstop L[wN := wL1 + wL2/(2**lL2)]

N -> L[wN := wL]

L -> L B[wL1 := 2*wL2 + wB][lL1 := lL2 + 1]

L -> B[wL := wB][lL := 1]

B -> one[wB := 1]

B -> zero[wB := 0]

Wahrend bei der ersten Attributierung jedes Bit gleich den seiner Stelle entsprechenden Wert zugeordnet bekam,fangen wir hier mit den

”Nennwerten“ 0 und 1 an und berucksichtigen die Gewichte beim Zusammenbau von

Zahlteilen geeignet.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 44 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Auswertungs-Attributierung arithmetischer Ausdrucke verwendet ein einziges Attribut �value:

Nonterminals:Arithmetic �valueExpression �valueFactor �valueTerm �value

und die Auswertungsregeln sind naheliegend:


Arithmetic -> Expression[valueArithmetic := valueExpression]

Expression -> Term[valueExpression := valueTerm]

Expression -> Expression addOp Term[valueExpression1 :=

(if stringaddOp = ’+’ thenvalueExpression2 + valueTerm

elsevalueExpression2 - valueTerm)]

Factor -> openingBracket Expression closingBracket[valueFactor := valueExpression]!

Factor -> number[valueFactor := intValue(stringnumber)]

Term -> Factor[valueTerm := valueFactor]

Term -> Term multOp Factor[valueTerm1 :=

(if stringmultOp = ’*’ thenvalueTerm2 * valueFactor

elsevalueTerm2 / valueFactor)]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 45 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Ubersetzungs-Attributierung arithmetischer Ausdrucke benotigt auch nur ein Attribut (�code), in dem die Folgeder Maschinenbefehle aufgesammelt wird und das allen nichtterminalen Symbolen zugeordnet ist.


Arithmetic -> Expression[codeArithmetic := codeExpression]

Expression -> Term[codeExpression := codeTerm]

Expression -> Expression addOp Term[codeExpression1 :=

(if stringmultOp = ’*’ thencodeExpression2 || codeTerm || ’ ADD W !SP+, !SP+, -!SP’

elsecodeExpression2 || codeTerm || ’ SUB W !SP+, !SP+, -!SP’)]

Term -> Factor[codeTerm := codeFactor]

Term -> Term multOp Factor[codeTerm1 :=

(if stringmultOp = ’*’ thencodeTerm2 || codeFactor || ’ MULT W !SP+, !SP+, -!SP’

elsecodeTerm2 || codeFactor || ’ DIV W !SP+, !SP+, -!SP’)]

Factor -> openingBracket Expression closingBracket[codeFactor := codeExpression]

Factor -> number[codeFactor := ’ MOVE W I ’ || stringnumber || ’ , -!SP’]

Strings sind in Hochkommata eingeschlossen und werden mit || konkateniert.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 46 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Angewandt auf die Beispieleingabe

123 * 256 / ( 5 + 56767 )

ergibt die erste Attributiertung den Zahlwert (man beachte, dass die Attributauswertungssprache Smalltalk mitgekurzten Bruchen rechnet und das Ergebnis daher prazise ist)

Arithmetic_value:

(2624/4731)

und die zweite Attributiertung die Befehlsfolge:

Arithmetic_code:

MOVE W I 123 , -!SPMOVE W I 256 , -!SPMULT W !SP+, !SP+, -!SPMOVE W I 5 , -!SPMOVE W I 56767 , -!SPADD W !SP+, !SP+, -!SPDIV W !SP+, !SP+, -!SP

Die ersten beiden Befehle kellern nacheinander die Zahlkonstanten 123 und 256. Der nachste Befehl entnimmt demKeller zwei Werte, multipliziert sie und kellert das Resultat. Danach wird die nachste Zahl 5 gekellert usw. ZumSchluss befindet sich im Keller eine einzige Zahl, namlich der Wert des Ausdrucks (naturlich mit Rundungsfehlernbehaftet).

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 47 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

7. Vollstandige Beispiele

Wir betrachten zwei weitere Beispiele:

• Im ersten Beispiel geht es um logische Ausdrucke mit den ublichen Operatoren (and, or, not). Zusatzlichgibt es bedingte Ausdrucke (ahnlich denen in der Programmiersprache C) und let-Ausdrucke, in denen (wie infunktionalen Programmiersprachen) benannte Konstanten eingefuhrt und und initialisiert werden.

– Die Infix-Syntax beschreibt die Sprache der logischen Ausdrucke in der ublichen Infix-Notation.

– Die Prafix-Syntax beschreibt i.W. die gleiche Sprache, wobei aber Operatoren in Prafix-Notation geschrie-ben werden.

Mit zwei Attributierungen kann man zwischen beiden Sprachen Ping-Pong spielen:

– Die Ping-Attributierung ubertragt einen in Infix-Notation vorliegenden, bedingten logischen Ausdruck indie Prafix-Notation.

– Die Pong-Attributierung leistet die Umkehrung, bringt aber nichts Neues und wird deswegen weggelassen.

• Dem zweiten Beispiel liegen der Boxen-Scanner sowie die Boxen-Grammatik zugrunde. Letztere beschreibttextuell Bilder aus geschachtelten und ubereinander bzw. nebeneinander gestellten Rechtecken.

Wieder zwei Attributierungen (diesmal beide in Smalltalk):

– Die Anzeige-Attributierung erzeugt in einem eigenen Fenster die grafische Darstellung des textuell be-schriebenen Bilds.

– Die Postscript-Attributierung ubertragt die textuelle Darstellung in eine Postscript-Grafik.

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 48 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Infix-Syntax ist gegeben durch die Scannerdefinition:

Patterns:letterPattern {$a-$z}|{$A-$Z}digitPattern {$0-$9}identifierPattern letterPattern (letterPattern|digitPattern)[0-*]boolPattern ’true’|’false’letPattern ’let’inPattern ’in’assignPattern ’:=’andPattern ’and’orPattern ’or’notPattern ’not’openingParenPattern $(closingParenPattern $)condPattern $?colonPattern $:semicolonPattern $;

Tokens:identifier identifierPatternbool boolPatternlet letPatternin inPatternassign assignPatternand andPatternor orPatternnot notPatternopeningBracket openingParenPatternclosingBracket closingParenPatterncondition condPatterncolon colonPatternsemicolon semicolonPattern

und die Grammatik:

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 49 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Startsymbol:S

Rules:S -> logD

logD -> deklP logK| logK

logK -> logE condition logE colon logE| logE

logE -> logE or logT| logT

logT -> logT and logF| logF

logF -> not logF| bool| identifier| openingBracket logD closingBracket

deklP -> let dekls in

dekls -> dekl| dekl semicolon dekls

dekl -> identifier assign bool

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 50 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Prafix-Syntax ist gegeben durch die Grammatik:

Startsymbol:S

Rules:S -> logExpr

logExpr -> condition logExpr logExpr logExpr| or logExpr logExpr| and logExpr logExpr| not logExpr| identifier| bool| deklP logExpr

deklP -> let dekls in

dekls -> dekl| dekl dekls

dekl -> identifier bool

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 51 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Zu den beiden Grammatiken gibt es Ping-Pong-Attributierungen, die jeweils den entsprechenden Satz zur anderenGrammatik erzeugen, z.B. zu

let a := true in a or false ? (let a := false ; b:= true in a or a) : not true

aus der Infix-Notation den Satz

let a true ? or a false let ; a false b true or a a not true

aus der Prafix-Notation und umgekehrt. (Man beachte, dass die Prafix-Notation mit weniger syntaktischen Trenn-symbolen auskommt, aber nicht besonders leserlich ist.)

Ein komplizierteres Beispiel: Aus dem Infix-Ausdruck

let a := true; b := false in(not

(let c := true in( b or c ?(let d:= false in c or d and a or b) :(let d:= true in c or d and a or b and not b))

))

ergibt sich der Prafix-Ausdruck

let ; a true b falsenot

let c true? or b clet d false or or c and d a blet d true or or c and d a and b not b

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 52 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Ping-Attributierung ist gegeben durch (alle nichtterminalen Symbole haben ein synthetisiertes text-Attribut):


S -> logD[textS := textlogD]

logD -> deklP logK[textlogD := textdeklP, ’ ’ , textlogK]

logD -> logK[textlogD := textlogK]

logK -> logE condition logE colon logE[textlogK := stringcondition ||’ ’|| textlogE1 ||’ ’|| textlogE2 ||’ ’|| textlogE3]

logK -> logE[textlogK := textlogE]

logE -> logE or logT[textlogE1 := stringor ||’ ’|| textlogE2 ||’ ’|| textlogT]

logE -> logT[textlogE := textlogT]

logT -> logT and logF[textlogT1 := stringand ||’ ’|| textlogT2 ||’ ’|| textlogF]

logT -> logF[textlogT := textlogF]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 53 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Teil 2 der Attributierung:

logF -> not logF[textlogF1 := stringnot || ’ ’ || textlogF2]

logF -> bool[textlogF := stringbool]

logF -> identifier[textlogF := stringidentifier]

logF -> openingBracket logD closingBracket[textlogF := textlogD]

deklP -> let dekls in[textdeklP := stringlet || ’ ’ || textdekls || ’ ’ || stringin]

dekls -> dekl[textdekls := textdekl]

dekls -> dekl semicolon dekls[textdekls1 := ’; ’ || textdekl || ’ ’ || textdekls2]

dekl -> identifier assign bool[textdekl := stringidentifier || ’ ’ || stringbool]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 54 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Boxen-Syntax ist gegeben durch den Boxen-Scanner:

Patterns:openingBracketPattern $[closingBracketPattern $]rightPattern $>openingParenthesisPattern $(closingParenthesisPattern $)downPattern $vdigitPattern {$0-$9}numberPattern digitPattern[1-*]

Tokens:openingBracket openingBracketPatternclosingBracket closingBracketPatternright rightPatternopeningParenthesis openingParenthesisPatternclosingParenthesis closingParenthesisPatterndown downPatternnumber numberPattern

und die Boxen-Grammatik:

Rules:Painting -> Picture

Picture -> Box| Picture right Box| Picture down Box| openingBracket Picture closingBracket

Box -> openingBracket Width Height closingBracket| openingParenthesis Picture closingParenthesis

Width -> number

Height -> number

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 55 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Eine Beispieleingabe

[ ( [ [50 60] ] > [30 100] > ([ [50 60] ] ) ) v [200 25] ]

und was der Scanner daraus macht:

openingBracket�[�

openingParenthesis�(�



number�50�

number�60�

closingBracket�]�


right�>�


number�30�

number�100�


right�>�

openingParenthesis�(�



number�50�

number�60�



closingParenthesis�)�

closingParenthesis�)�

down�v�


number�200�

number�25�



Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 56 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Anzeige-Attributierung ist gegeben durch die Attribute:

Nonterminals and their attributes:

Picture �width �height �boxes �positionBox �width �height �boxes �positionWidth �widthHeight �heightPainting �boxes

Teil 1 der Attributauswertungsregeln:

Rules:Picture -> Box

[widthPicture := widthBox][heightPicture := heightBox][boxesPicture := boxesBox][positionBox := positionPicture]

Picture -> Picture right Box[widthPicture1 := widthPicture2 + 4 + widthBox][heightPicture1 := heightPicture2 max: heightBox][boxesPicture1 := boxesPicture2 , boxesBox][| yPos yDiff |

yPos := positionPicture1 y.yDiff := heightBox - heightPicture2.yDiff > 0 ifTrue: [yPos := yPos + (yDiff // 2)].positionPicture2 := positionPicture1 x @ yPos]

[| yPos yDiff |yPos := positionPicture1 y.yDiff := heightPicture2 - heightBox.yDiff > 0 ifTrue: [yPos := yPos + (yDiff // 2)].positionBox := positionPicture1 x + 4 + widthPicture2 @ yPos]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 57 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden


Picture -> Picture down Box[widthPicture1 := widthPicture2 max: widthBox][heightPicture1 := heightPicture2 + 4 + heightBox][boxesPicture1 := boxesPicture2 , boxesBox][| xPos xDiff |

xPos := positionPicture1 x.xDiff := widthBox - widthPicture2.xDiff > 0 ifTrue: [xPos := xPos + (xDiff // 2)].positionPicture2 := xPos @ positionPicture1 y]

[| xPos xDiff |xPos := positionPicture1 x.xDiff := widthPicture2 - widthBox.xDiff > 0 ifTrue: [xPos := xPos + (xDiff // 2)].positionBox := xPos @ (positionPicture1 y + 4 + heightPicture2)]

Picture -> openingBracket Picture closingBracket[widthPicture1 := 10 + widthPicture2][heightPicture1 := 10 + heightPicture2][boxesPicture1 := boxesPicture2 ,

(Array with: (positionPicture1 extent: widthPicture1 @ heightPicture1))][positionPicture2 := positionPicture1 + (5 @ 5)]

Box -> openingBracket Width Height closingBracket[widthBox := widthWidth asNumber][heightBox := heightHeight asNumber][boxesBox := Array with: (positionBox extent: widthBox @ heightBox)]

Box -> openingParenthesis Picture closingParenthesis[widthBox := widthPicture][heightBox := heightPicture][boxesBox := boxesPicture][positionPicture := positionBox]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 58 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden


Height -> number[heightHeight := stringnumber]

Width -> number[widthWidth := stringnumber]

Painting -> Picture[positionPicture := 4 @ 4][| windowWidth windowHeight window component |boxesPainting := boxesPicture.

"Das Folgende dient dazu, das Ergebnis ineinem Smalltalk-Fenster grafisch darzustellen.Der meiste Teil des Codes dient dem Anlegeneines Fensters der richtigen Groesse:"Cursor execute showWhile:

[windowWidth := widthPicture + 14 min: 640.windowHeight := heightPicture + 14 min: 480.(window := ScheduledWindow new) component:

(BorderDecorator on: (component := CompositePart new)).window minimumSize: windowWidth @ windowHeight.window maximumSize: windowWidth @ windowHeight.windowWidth = 640

ifTrue: [window component useHorizontalScrollBar].windowHeight = 480

ifTrue: [window component useVerticalScrollBar]ifFalse: [window component noVerticalScrollBar].

"Die naechste Zeile erzeugt den Fensterinhalt, d.h.alle darzustellenden Rechtecke:"

boxesPicture do: [:box | component add: box asStroker]."... und dann wird das Fenster geoeffnet:"window open.window label: ’Boxes’]]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 59 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Ergebnis bei Anwendung auf die Beispieleingabe textuell:

Painting_boxes:#(35@29 corner: 85@89

30@24 corner: 90@9494@9 corner: 124@109133@29 corner: 183@89128@24 corner: 188@949@113 corner: 209@1384@4 corner: 214@143)

und als Screenshot:

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 60 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Die Postscript-Attributierung ist gegeben durch die Attribute:

Nonterminals and their attributes:

Picture �width �height �position �postscriptBox �width �height �position �postscriptWidth �widthHeight �heightPainting �postscript

Die Auswertungsregeln fur alle Attribute außer �postscript sind wie in der vorigen Attributierung und werden nichtwiederholt.

Teil 1 der �postscript-Attributauswertungsregeln:

Picture -> Box[postscriptPicture := postscriptBox]

Picture -> Picture right Box[postscriptPicture1 := postscriptPicture2 , postscriptBox]

Picture -> Picture down Box[postscriptPicture1 := postscriptPicture2 , postscriptBox]

Picture -> openingBracket Picture closingBracket[postscriptPicture1 := postscriptPicture2 , ’ ’ ,positionPicture1 x printString , ’ ’ , positionPicture1 y printString ,’ moveto ’ , widthPicture1 printString , ’ ’ , heightPicture1 printString ,’ box’]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 61 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Teil 2 der �postscript-Attributauswertungsregeln:

Box -> openingBracket Width Height closingBracket[postscriptBox := ’ ’ , positionBox x printString , ’ ’ ,positionBox y printString , ’ moveto ’ , widthBox printString , ’ ’ ,heightBox printString , ’ box’]

Box -> openingParenthesis Picture closingParenthesis[postscriptBox := postscriptPicture]

Height -> number

Width -> number

Painting -> Picture[postscriptPainting :=

’/box {/bwidth exch def/bheight exch def0 bwidth rlinetobheight 0 rlineto0 bwidth neg rlinetoclosepath

} defnewpath’ , postscriptPicture ,’strokeshowpage’]

Ubersicht

Kleine Grammatiken



Scannerdefinitionen

Attributierungen


Startseite

JJ II

J I

Seite 62 von 62

Zuruck

Vollbild ein/aus

Schließen

Beenden

Ergebnis textuell:

/box {/bwidth exch def/bheight exch def0 bwidth rlinetobheight 0 rlineto0 bwidth neg rlinetoclosepath

} defnewpath

131 125 moveto 50 60 box126 120 moveto 60 70 box190 105 moveto 30 100 box229 125 moveto 50 60 box224 120 moveto 60 70 box105 209 moveto 200 25 box100 100 moveto 210 139 box

strokeshowpage

und als Screenshot (in manueller Nachbearbeitung auf den Kopf gestellt, weil die Koordinatensysteme fur Bildschirmund Postscript in der senkrechten Dimension entgegengesetzt orientiert sind):

Documents

Beispiele für regulare Ausdrucke, Grammatiken und JJ II ... · JJ II J I Seite 1 von 62 Zurück Vollbild ein/aus Schließen Beenden Beispiele für regulare Ausdrucke, Grammatiken