07/07/07 ifc –

Es geht immer einfacher...

Axel T. Schreinerhttp://www.cs.rit.edu/~ats/talks/ifc07/

1

http://www.cs.rit.edu/~ats/talks/ifc07/

07/07/07 ifc –

LL(1) (recursive descent)

generalparserGrammatik als GraphParser als Graph-Traverse

Validierung für unix/mail Manuskripte

Wirth’s Compilerbau 1977?

3

http://www.cs.inf.ethz.ch/~wirth/books/Compilerbau0/

07/07/07 ifc –

Compilerbau Ulm 1978?

Pascal

recursive descent

J.J. HorningLR Grammars and Analysersin Bauer Compiler Construction 1974

Unix (v6), yacc und C

Pascal Makros für C

7

http://portal.acm.org/citation.cfm?id=1102008&coll=GUIDE&dl=GUIDE&CFID=27483821&CFTOKEN=51588505

07/07/07 ifc –

Grammatik

Grammatikbegriffe (darunter ein Startsymbol)

Eingabesymbole

(kontext-freie) Regeln

BNF

9

summe: zahl | summe '+' zahlzahl: Ziffernfolge

John Backus

Peter NaurNoam Chomsky

12 + 34 + 56

07/07/07 ifc –

Wurzel: StartsymbolKnoten: GrammatikbegriffAbkömmlinge: Alternative einer RegelBlatt: Eingabesymbol

Links-Rekursion: Klammerung von links

Syntaxbaum

11

summe

summe

zahl

zahl'+'

12

34

summe zahl'+'

56

summe: zahl | summe '+' zahlzahl: Ziffernfolge

12 + 34 + 56

07/07/07 ifc –

LL(1) recursive descent

14

summe

summe

zahl

zahl'+'

12

34

summe zahl'+'

56

Left-to-rightLeft-most derivation1 symbol lookahead

Erkennung traversiert Grammatik,beginnend mit Startsymbol (top-down)

Nächstes Eingabesymbol wählt, welcheAlternative der Regel verfolgt wird

Links-Rekursion stört...summe: zahl | summe '+' zahlzahl: Ziffernfolge

12 + 34 + 56

07/07/07 ifc –

Extended BNF

Syntax für Iteration vermeidet Links-Rekursion

Regeln entsprechenErkennungsfunktionen

Klammerung muß verabredet werden

17

summe: zahl ('+' zahl)*zahl: Ziffernfolge

summe() { zahl(); while (match('+')) zahl(); }zahl() { match(Ziffernfolge); }

summe

zahl zahl'+'

12 34

zahl'+'

56

07/07/07 ifc –

LR(1) Knuth 1965

20

summe

summe

zahl

zahl'+'

12

34

summe zahl'+'

56

Left-to-rightRight-most derivation1 symbol lookahead

Erkennung traversiert Eingabe (bottom-up)

Tabelle entscheidet, ob und welcheAlternative einer Regel gefunden wurde

Symbole werden zusammengefaßt; zuletztzum Startsymbol

Links-Rekursion ist ok...

summe: zahl | summe '+' zahlzahl: Ziffernfolge

12 + 34 + 56

07/07/07 ifc –

yacc Johnson 1975

yacc berechnet die Tabelle aus BNF

yyparse() interpretiert die Tabelle,holt Eingabe vom Scanner, manipulierteinen Stack mit Zuständen

und führt benutzer-definierte Aktionenmit einem parallelen Wert-Stack aus

22

{ $$ = addiere($1, $3); }{ $$ = atoi(text($1)); }

Werte

Zust!nde

Tabelle

Zeichenfolge

Scanner

Eingabesymbol

summe: zahl | summe '+' zahlzahl: Ziffernfolge

12 + 34 + 56

http://dinosaur.compilertools.net/

07/07/07 ifc –

Es geht immer einfacher...

Java, OOP und Design Patterns

Scanner

Tree Factory

Struktur der Bäume

[Fehlerbehandlung]

allerdings: Objecting to Objects (Johnson 1994)

23

http://www.usenix.org/publications/library/proceedings/sf94/full_papers/johnson.html

07/07/07 ifc –

yacc-Algorithmus selbst unverändertyyparse() und Tabelle in Java oder C#Wert-Stack: Object

Animation à la Holub

Java-Port mit nestedvm

verwendet im Mono Projekt

jay LR(1), BNF

26

Skelett jay Parser

Grammatik

http://www.cs.rit.edu/~ats/projects/lp/doc/jay/package-summary.htmlhttp://nestedvm.ibex.org/http://www.mono-project.com/Main_Page

07/07/07 ifc –

oops LL(1), EBNF

generalparser: Grammatik als Objektbaum darstellenMethoden für Erkennung und Grammatik-Prüfung

divide&conquerRegel-spezifischer Observer per Regel-Aktivierungverschiedene Factories, z.B. für Scanner und Observer

EBNF beschreibt sich selbst: bootstrapverschiedene EingabesprachenGrammatik völlig getrennt von Aktionen

31

Parser

Rule Sequence

Nonterminal Repeat 0..!

Literal

summe

zahl

'+' zahl

Nonterminal

Rule Token

zahl Ziffernfolge

summe: zahl ('+' zahl)* zahl: Ziffernfolge

summe: zahl [{'+' zahl}]zahl: Ziffernfolge

http://www.cs.rit.edu/~ats/projects/oops/edu/doc/index.html

07/07/07 ifc –

summe

summe

zahl

zahl'+'

12

34

summe zahl'+'

56

jag Pattern-basierter Visitor

Syntaxbaum eignet sich kaum zur Verarbeitung

Formelbaum:Klasse für LiteralBlatt für Token

Präprozessor:Knoten-Klassen wählen AktionenVererbung als Muster

34

Add: Object Object { return (int)visit(0) + (int)visit(1); }};Leaf: Integer { return $1;};

Add

LeafAdd

56

12

Leaf Leaf

34

http://www.cs.rit.edu/~ats/projects/lp/doc/jag/package-summary.html

07/07/07 ifc –

JLex

jay

grammar rules

BNF

regular

expressions

factory

tree classes

lexical analysis

symbols

syntax analysis

pj

12 + 34 + 56

Add Add Leaf 12 Leaf 34 Leaf 56

pj JLex-Scanner, Bäume, error

Präprozessor für jay:

Scanner aus Literalen und Muster für TokenFactory für Formelbaum (EOPL2)Animation und Fehlerbehandlung

37

public class summe {%token <Integer> Zahlenfolge {digits}digits = [0-9]+%%<Node> summe: summe '+' zahl <Add> | zahl;<Node> zahl: Zahlenfolge <Leaf>;%%}

http://www.cs.rit.edu/~ats/projects/lp/doc/pj/package-summary.htmlhttp://www.cs.princeton.edu/~appel/modern/java/JLex/http://www.cs.indiana.edu/eopl/

07/07/07 ifc –

wcs Compilerbau im Web

wcs.Applet emuliert eine Konsole und ist Delegate für eine fingierte System Klasse in jeder package

38

tomcat

wcs Servlet

pj... javac

HTML form Applet

http://www.cs.rit.edu/~ats/projects/lp/doc/wcs/package-summary.htmlhttp://wcs.cs.rit.edu:8080/wcs/wcs?form=true&processor.0=javac&source.0=http://www.cs.rit.edu/~ats/talks/wcs/hello.txt&sink.0=applethttp://wcs.cs.rit.edu:8080/wcs/wcs?processor.0=javac&source.0=http://www.cs.rit.edu/~ats/talks/wcs/hello.txt&sink.0=applet

07/07/07 ifc –

oops3.net (greedy) LL(1), XBNF

39

public class parser {

%%

<void> Comment = '#.*';

<void> WhiteSpace = '[ \r\t\n]+';

<Integer> Number = '[0-9]+';

<Sum>? sum: term (add | subtract)*;

<Add> add: '+' term;

<Subtract> subtract: '-' term;

term: Number | '(' sum ')';

%%

}

oops3 parser

# input

3 - (4 + 5)

2 Sum

Integer 3

2 Subtract

2 Sum

Integer 4

2 Add

Integer 5

javac

Algorithmen als VisitorsLL(1) Test optional

Baum-Struktur unabhängig von GrammatikSyntax für left-assoziative Konstruktion

Permutationen

http://www.cs.rit.edu/~ats/projects/oops3/doc/http://www.cs.rit.edu/~ats/projects/oops3.net/doc/

07/07/07 ifc –

Parser visit start ruleRule n: rhs visit right-hand sideLiteral 'a' advance inputToken Id advance inputNonterminal n visit ruleSequence a b visit descendants

Repeata+a*a?

greedy loop: visit descendant

Xor a|b visit proper descendant

Recognition Visitor

40

07/07/07 ifc –

Parser visit start ruleRule n: rhs visit right-hand sideLiteral 'a' advance inputToken Id advance input collect valueNonterminal n visit ruleSequence a b visit descendants

Repeata+a*a?

greedy loop: visit descendant

Xor a|b visit proper descendant

Building: Flat

41

07/07/07 ifc –

Parser visit start ruleRule n: rhs visit right-hand side build nodeLiteral 'a' advance inputToken Id advance input collect valueNonterminal n visit rule collect nodeSequence a b visit descendants

Repeata+a*a?

greedy loop: visit descendant

Xor a|b visit proper descendant

Building: Parse Tree

42

07/07/07 ifc –

Parser visit start ruleRule <C> n: rhs visit right-hand side C n(aList)Literal 'a' advance inputToken Id advance input collect valueNonterminal n visit rule collect CSequence a b visit descendants

Repeata+a*a?

greedy loop: visit descendant

Xor a|b visit proper descendant

Building: Tree

rule collection is delegated by reflection on rule name.ArrayList results are flattened during collection.

43

07/07/07 ifc –

XBNF: Counts

Repeat can use any range, not just 0, 1, and ∞.

item +item ?item *item 1..item ..1item ..item 2..3

44

07/07/07 ifc –

XBNF: Delimited Lists

Delimit extends Repeatany range of more then 1 can have a separator (which may even be empty).

item +item ?item *item 1.. / delimiteritem ..1item ..item 2..3

45

07/07/07 ifc –

XBNF: Permutations

unordered full set (permutation):

unordered subset:

top-level nested ranges are counted at the level of the permutation, i.e., their constituents can be permuted.

{ item, item ... }{ item, item ... } / delimiter

[ item, item ... ][ item, item ... ] / delimiter

46

07/07/07 ifc –

pj2 LR(1), EBNF

Präprozessor wie pj

Baum-Strukturierung wie oops3

kombiniert EBNF vollständig mit LR(1),erlaubt also zum Beispiel auch Links-Rekursion

47

07/07/07 ifc –

Es geht immer einfacher...wcs

XML für Job-Beschreibung und Programm-Strukturlose Koppelung für neue ToolsSilverlight?

pj2XBNF

jagXPath-artige Syntax?Syntax für beans-artige Zugriffe?

oops3LL(k)Fehlerbehandlung

48