#################################### YACC #####################################
LALR(1)-Parser
parser.y -> Yacc -> y.tab.c
y.tab.c -> C-Compiler -> a.out
Eingabe -> a.out -> Ausgabe
Spezifikationsfile: parser.y
yacc parser.y
gcc y.tab.c -ly
-ly!!! Damit Yacc-Bibliotheken eingebunden werden.
Der erzeugte Parser steht als Funktion yyparse() zur Verfügung
Yacc-Spezifikation
Deklarationen
%%
Grammatik
%%
Hilfsprozeduren
%{
#include <ctype.h>
#include <stdio.h>
%}
%token NUMBER
%%
lines : lines expr '\n' {printf("%d\n", $2); }
| lines '\n'
|
;
expr : expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
| term
;
term : term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 * $3; }
| factor
;
factor : '(' expr ')' { $$ = $2; }
| NUMBER
;
%%
int yylex() {
int c;
c = getchar();
if (isdigit(c)) {
ungetc(c, stdin);
scanf("%d", &yylval);
return NUMBER;
}
return c;
}
Yacc-Spezifikationen, Grammatik-Teil:
- Nichtterminale (lines, expr, term, ...)
- Terminale (Token):
- Einzelne Zeichen, Typ char oder int '+', '(', '\n'
- Explizit deklarierte Token (NUMBER); Im Deklarationsteil
%token NUMBER
- Produktionen
############################## SCHEME ###############################
(+ 5 5 5 5)
(* (+ 2 3) 5)
(* (+ 1 2) 4)
(< 1 2)
(< 2 1)
(> 1 2)
(> 2 1)
(define (square x) (* x x))
(define (sqr x) (* x x))
(square 2)
(sqr 2)
############################ PYTHON ###################################
# Kommentar
2 + 2
(2+2)*4
100/16
1/16
1.0/16.0
"Hallo"
print('Super')
a = [100, 200, 300]
a[0]
a[1]
a[2]
############################## Uebersetzerbau ##########################
Syntaxanalyse: Die zweite Phase der Übersetzung ist die Syntaxanalyse
Syntaxbaum/Ableitungsbaum: Die Aufgabe der Syntaxanalyse besteht darin aus der Folge von Token einen Syntaxbaum zu berechnen
if id[1] cop[>=] const[10] then id[2] := const[1] end
Baum, Abbildung, siehe Seite 41
Grammatik: Basis für die Syntaxanalyse ist eine Grammatik
Einige Regeln einer Grammatik:
stmt ::= assignment | cond
cond ::= if boolexpr then stmt end |
if boolexpr then stmt else stmt end
numexpr ::= id | const
Zwei Strategien:
1. Top-down-Analyse
2. Bottom-up
Top-down-Analyse: Baut den Baum von der Wurzel zu den Blättern hin auf
Bottom-up-Analyse: Der Baum wird von den Blättern her aufgebaut
Dabei ist die Grundidee, so lange Token der Eingabefolge zu lesen und sich zu merken, bis eine vollständige rechte Seite einer Grammatikregel gelesen worden ist.
Kontextfreie Grammatiken und Syntaxbäume
Kontextfreie Grammatiken: Die Syntax höherer Programmiersprachen wird durch kontextfreie Grammatiken beschrieben
Definition: Eine kontextfreie Grammatik ist ein Quadrupel G = (N, E, P, S), wobei gilt:
1. N ist ein Alphabet von Nichtterminalen
2. E ist ein Alphabet von Terminalen. Die Alphabete N und E sind disjunkt
3. P = N x (N U E)* ist eine Menge von Produktionsregeln
4. S in N ist das Startsymbol
Nichtterminale: stmt, cond, ...
Terminale: if, id, ...
Produktionen: Paare bestehnd aus einem Nichtterminal und einer Folge von Nichtterinalen und Terminalsysmbolen
stmt ::= assignment | cond
{(stmt, assigment), (stmt, cond)}
Produktionsregeln werden in formalen Betrachtungen häufig mit Pfeilen notiert.
(A, alpha)
A -> alpha
A -> alpha1, A -> alpha2, ..., A -> alphan
A -> alpha1 | alpha2 | ... | alphan
Nichtterminale: A, B, C, X, Y, Z, ...
Terminale: a, b, c, ...
...
Top-down-Analyse
Ableitungsbaum und Eingabefolge werden von links nach rechts gelesen
Solange beide Folgen gleiche ... kann man weiterlesen ...
Falls zwei nicht übereinstimmende Terminalsymbole angetroffen werden, so ist
1. entweder eine vorher getroffene Produktion falsch gewesen und rückgängig zu machen
2. Die Eingabefolge syntaktisch nicht korrekt.
stmt -> assigment | cond | loop
assignment -> id := expr
cond -> if boolexpr then stmt fi |
if boolexpr then stmt else stmt fi
loop -> while boolexpr do stmt od
expr -> boolexpr | numexpr
boolexpr -> numexpr cop numexpr
term -> term * factor | factor
factor -> id | const | (numexpr)
In dieser Sprache:
if b > 0 then a := 1 fi
if id cop const then id := const fi
linksrekursive Produktionen: Das zu ersetzende Nichtterminal auf der rechten Seite der Produktion tritt wieder ganz links auf.
Top-down-Analyse: Top-down-Analyse mit Backtracking
Top-Down-Analyse: Linksrekursive Produktionen und Verlaufen in Sackgassen
