|
|
I-PROGR3 WS03 - PROGRAMMIEREN3 - Vorlesung mit Übung
|
In der letzten Vorlesung wurde das Konzept der lexikalischen Analyse mit dem Werkzeug flex (früher lex) eingeführt. Bei einer lexikalischen Analyse wird eine Zeichenkette in aueinanderfolgende Zeichengruppen analysiert, wobei jede konkrete Zeichenkette --auch Token genannt-- Elemente einer Zeichenklasse --oft auch Type genannt-- sein kann. Eine lexikalische Analyse bschränkt sich allerdings auf eine zusammenhängende Folge von Zeichen; die Zusammenhänge zwischen Token werden nicht mehr analysiert. Sie gehören einer neuen Analysesicht an, die man gewöhnliche syntaktische Analyse nennt. Für die syntaktische Analyse steht mit bison (früher 'yacc') ein weiteres leistungsfähiges Werkzeug zur Verfügung.
Betrachten wir ein Beispiel.
Angenommen man will einen Taschenrechner für die Grundrechenarten simulieren. Unter Verwendung der Postfix-Notation wären dann Eingaben wie die folgenden üblich:
4 3 + (= 7)
2 4 * 3 + (= 11)
4 5 + 3 / (= 3)
Die Token dieser Beispiele sind entweder Zahlen '4', '3' usf oder Operationszeichen wie '+', '*' etc. Um diese zu identifizieren benötigt man eine lexikalische Analyse. Z.B. könnte man mit flex festlegen, dass gelten soll:
%{
#include<stdio.h>
%}
NUM [0-9]+
OP [\+\*\-/]
%%
{NUM} printf("NUM ");
{OP} printf("OP\n");
%%
int main(){
yylex();
return(1);
}
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> flex i-progr3-vl6-lex-calc.l gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> gcc -o lexcalc1 lex.yy.c -lfl gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> ./lexcalc1 3 4 + NUM NUM OP 2 4 + 3 * NUM NUM OP NUM OP
Wie man hier sieht, kann man so zwar einfach die lexikalischen Items erkennen, nicht aber die Zusammenhänge zwischen diesen; diese Zusammenhänge benötigt man aber, will man komplexe arithmetische Operationen durchführen. Hier bietet sich nun bison an.
Die Analyse von Beziehungen zwischen Token führt in den Bereich der syntaktischen Analyse. In der Chomsky-Hierarchie beginnt diese ungefähr bei Stufe 2 abwärts.
Charakteristisch für eine syntaktische Analyse ist es, dass man Regeln angibt, die besagen, welche Token T zu einer bestimmten syntaktischen Klasse K gehören können und welche Folgen von syntaktischen Klassen wieder neue syntaktische Klassen bilden können.
Bezogen auf das obige Beispiel könnte man z.B. vereinbaren, dass ein arithmetischer Ausdruck AEXPR entweder aus einem Token NUM besteht oder aus der TOKEN-FOLGE 'NUM NUM OP'. Ferner könnte man vereinbaren, dass AEXPR AEXPR OP wieder ein arithmetischer Ausdruck ist.
Typischerweise würde man solche syntaktischen Regeln wie folgt aufschreiben:
AEXPR: NUM | AEXPR AEXPR OP
D.h. ein AEXPR kann entweder durch den Ausdruck NUM ersetzt werden oder durch den Ausdruck AEXPR AEXPR OP.
Das obige Beispiel würde damit wie folgt analysierbar:
3 4 + NUM NUM OP AEXPR AEXPR OP AEXPR ---------------------- 2 4 + 3 * NUM NUM OP NUM OP AEXPR AEXPR OP AEXPR OP AEXPR AEXPR OP AEXPR
Um solche syntaktischen regeln innerhalb von Bison beschreiben zu können, muss man --ähnlich wie bei Flex-- eine spezielle bison-Beschreibungsdatei erstellen. Diese hat als Sufix '.y' statt '.l' wie im Falle von flex.
Der Aufbau einer bison-Beschreibungsdatei ist analog wie die einer flex-Beschreibungsdatei:
%{
PROLOGUE
The PROLOGUE section contains macro definitions and declarations of
functions and variables that are used in the actions in the grammar
rules. These are copied to the beginning of the parser file so that
they precede the definition of `yyparse'. You can use `#include' to
get the declarations from a header file. If you don't need any C
declarations, you may omit the `%{' and `%}' delimiters that bracket
this section.
You may have more than one PROLOGUE section, intermixed with the
BISON DECLARATIONS. This allows you to have C and Bison declarations
that refer to each other.
%}
BISON DECLARATIONS
The BISON DECLARATIONS section contains declarations that define
terminal and nonterminal symbols, specify precedence, and so on. In
some simple grammars you may not need any declarations.
%%
GRAMMAR RULES
The "grammar rules" section contains one or more Bison grammar
rules, and nothing else. *Note Syntax of Grammar Rules: Rules.
There must always be at least one grammar rule, and the first `%%'
(which precedes the grammar rules) may never be omitted even if it is
the first thing in the file).
%%
EPILOGUE
The EPILOGUE is copied verbatim to the end of the parser file, just
as the PROLOGUE is copied to the beginning. This is the most convenient
place to put anything that you want to have in the parser file but
which need not come before the definition of `yyparse'. For example,
the definitions of `yylex' and `yyerror' often go here.
If the last section is empty, you may omit the `%%' that separates it
from the grammar rules.
The Bison parser itself contains many static variables whose names
start with `yy' and many macros whose names start with `YY'. It is a
good idea to avoid using any such names (except those documented in this
manual) in the epilogue of the grammar file.
Comments enclosed in `/* ... */' may appear in any of the sections.
Der Bison-Algorithmus übernmmt die Token von einem lexikalischen Analysator (z.B. flex) und packt diese Token auf den parser stack. Dieses Übernehmen eines Token in den Parser stack wird auch shiften genannt (nicht zu verwechseln mit der Operation push, die ein einzelnes Item auf den Stack legt. Sobald sich einige Einheiten auf dem Parser Stack mit Hilfe einer Regel durch ein einzelnes Symbol ersetzen lassen, werden diese ersetzbaren Symbole durch das neue Symbol ersetzt. Man spricht in diesem Fall auch von Reduktion. Der Reduktionsprozess ist am Ziel angelangt, wenn sich keine weiteren Symbole mehr reduzieren lassen und das letzte Symbol auf dem Parser Stack das Startsymbol der Regeln ist. Ist dies nicht der Fall, liegt ein Fehler vor.
Ein solcher Pars-Algorithmus wird auch als Bottom-up Parser bezeichnet.
Das vorausgehende Beispiel würde also wie folgt abgearbeitet werden:
EINGABE: 3 4 + LEXIKALISCHE ANALYSE: NUM NUM OP Shift: NUM Reduktion: AEXPR (<-- Mehr Input) Shift: NUM Reduktion: AEXPR (<-- Mehr Input) Shift: OP Reduktion: AEXPR (<-- Kein weiterer Input; Startsymbol)
/*-----------------------------------------
* Reverse polish notation calculator.
*
* Example taken from the info-file for 'bison'
*
****************************************/
/*************************************
* bison part
*
**************************************/
%{ /* PROLOGUE */
#define YYSTYPE double
#include <math.h>
#include <stdio.h> /*Neede by following functions */
%}
/* BISON DECLARATIONS */
%token NUM
%% /* Grammar rules and actions follow. */
input: /* empty */
| input line
;
line: '\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
;
exp: NUM { $$ = $1; }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
/* Exponentiation */
| exp exp '^' { $$ = pow ($1, $2); }
/* Unary minus */
| exp 'n' { $$ = -$1; }
;
%%
/* EPILOGUE */
/* The lexical analyzer returns a double floating point
number on the stack and the token NUM, or the numeric code
of the character read if not a number. It skips all blanks
and tabs, and returns 0 for end-of-input. */
#include <ctype.h>
int
yylex (void)
{
int c;
/* Skip white space. */
while ((c = getchar ()) == ' ' || c == '\t')
;
/* Process numbers. */
if (c == '.' || isdigit (c))
{
ungetc (c, stdin);
scanf ("%lf", &yylval);
return NUM;
}
/* Return end-of-input. */
if (c == EOF)
return 0;
/* Return a single char. */
return c;
}
/* A simple main-function -----------------------------------------------*/
int
main (void)
{ /* yydebug nur setzen, wenn benoetigt ! Zugleich '-t' benutzen */
yydebug=1;
return yyparse ();
}
/* A simple error-function -----------------------------------------------*/
void
yyerror (const char *s) /* called by yyparse on error */
{
printf ("%s\n", s);
}
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> bison rpcalc.y
Dies erzeugt die Datei rpcalc.tab.c, die u.a. die Funktion yyparse() definiert.
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> gcc -o rpcalc2 rpcalc.tab.c -lm rpcalc.y:95: warning: type mismatch with previous implicit declaration rpcalc.tab.c:1163: warning: previous implicit declaration of `yyerror' rpcalc.y:95: warning: `yyerror' was previously implicitly declared to return `int'
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> ./rpcalc2 3 4 + bison exp: 7 4 5 + 2 * bison exp: 18 4 5 + 2 * 9 / bison exp: 2
Will man Debug-Informationen abfragen, dann muss man bison mit der '-t' (:= trace) Option starten und vorher auch die Variable yydebug=1; (z.B. im C-text) setzen.
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> bison -t rpcalc.y
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> gcc -o rpcalc rpcalc.tab.c -lm
rpcalc.y:96: warning: type mismatch with previous implicit declaration
rpcalc.tab.c:1163: warning: previous implicit declaration of `yyerror'
rpcalc.y:96: warning: `yyerror' was previously implicitly declared to return `int'
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> ./rpcalc
Starting parse
Entering state 0
Reducing via rule 1 (line 28), -> input
state stack now 0
Entering state 1
Reading a token: 3 4 +
Next token is token NUM ()
Shifting token 258 (NUM), Entering state 3
Reducing via rule 5 (line 36), NUM -> exp
state stack now 0 1
Entering state 6
Reading a token: Next token is token NUM ()
Shifting token 258 (NUM), Entering state 3
Reducing via rule 5 (line 36), NUM -> exp
state stack now 0 1 6
Entering state 9
Reading a token: Next token is token '+' ()
Shifting token 43 ('+'), Entering state 10
Reducing via rule 6 (line 37), exp exp '+' -> exp
state stack now 0 1
Entering state 6
Reading a token: Next token is token '\n' ()
Shifting token 10 ('\n'), Entering state 7
Reducing via rule 4 (line 33), exp '\n' -> line
bison exp: 7
state stack now 0 1
Entering state 5
Reducing via rule 2 (line 29), input line -> input
state stack now 0
Entering state 1
Reading a token:
Abschliessend sei noch gezeigt, wie man das obige Beispiel mit flex und bison gestalten kann.
Zunächst benötigt man eine flex-Spezifikationsdatei, mit der man eine lexikalische Analyse durchführen kann.
/************************************
*
* lexcalc2.l
*
* idea: Recognizes floats written as INT'.'INT
*
* COMPILATION:
* flex lexcalc2.l
*
*
****************************************************/
%{
#include
#include
#include "rpcalc3.tab.h" /* Einlesen der TOKEN-Definitionen */
%}
YYSTYPE yylval;
%%
[ \t] { ; }
[0-9]+[.]?[0-9]* { sscanf(yytext,"%lf",&yylval); return(NUM); }
\+ { return(ADD); }
\- { return(SUB); }
\* { return(MUL); }
\/ { return(DIV); }
\^ { return(POW); }
\n { return(LF); }
%%
Wie man ersehen kann, benötigt man zur Erstellung des C-Quelltextes aber eine Headerdatei, die die TOKEN-Definitionen enthält. Diese kann man aus der bison-Datei mit der Option '-d' automatisch generieren lassen:
/*-----------------------------------------
* Reverse polish notation calculator.
*
* Example taken from the info-file for 'bison'
*
****************************************/
/*************************************
* bison part
*
**************************************/
%{ /* PROLOGUE */
#include
#include
#define YYSTYPE double
%}
/* BISON DECLARATIONS */
%token NUM ADD SUB MUL DIV POW LF
%% /* Grammar rules and actions follow. */
input: /* empty */
| input line
;
line: LF { ; }
| exp LF {$$ = $1; printf(" bison exp: %.2lf \n", $1); }
;
exp: NUM { $$ = $1; printf(" bison NUM: %.2lf \n", $$); }
| exp exp ADD { $$ = $1 + $2; printf(" bison ADD: %.2lf \n", $$); }
| exp exp SUB { $$ = $1 - $2; printf(" bison SUB: %.2lf \n", $$); }
| exp exp MUL { $$ = $1 * $2; printf(" bison MUL: %.2lf \n", $$); }
| exp exp DIV { $$ = $1 / $2; printf(" bison DIV: %.2lf \n", $$); }
| exp exp POW { $$ = pow ($1, $2); printf(" bison POW: %.2lf \n", $$); }
;
%%
/* EPILOGUE */
/* The lexical analyzer returns a double floating point
number on the stack and the token NUM, or the numeric code
of the character read if not a number. It skips all blanks
and tabs, and returns 0 for end-of-input. */
/* A simple main-function -----------------------------------------------*/
int
main (void)
{
/* yydebug=1; *************/
return yyparse ();
}
/* A simple error-function -----------------------------------------------*/
void
yyerror (const char *s) /* called by yyparse on error */
{
printf ("%s\n", s);
}
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> bison -d rpcalc3.y
Dies erzeugt die Datei rpcalc3.tab.h
#ifndef BISON_RPCALC__TAB_H
# define BISON_RPCALC__TAB_H
/* Tokens. */
#ifndef YYTOKENTYPE
# define YYTOKENTYPE
/* Put the tokens into the symbol table, so that GDB and other debuggers
know about them. */
enum yytokentype {
NUM = 258,
ADD = 259,
SUB = 260,
MUL = 261,
DIV = 262,
POW = 263,
LF = 264
};
#endif
#define NUM 258
#define ADD 259
#define SUB 260
#define MUL 261
#define DIV 262
#define POW 263
#define LF 264
#ifndef YYSTYPE
typedef int yystype;
# define YYSTYPE yystype
#endif
extern YYSTYPE yylval;
#endif /* not BISON_RPCALC__TAB_H */
Dann kann man mit flex die Datei lex.yy.c erzeugen und dann die endgültige Datei rpcalc3
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> flex lexcalc2.l gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> gcc -o rpcalc3 rpcalc3.tab.c lex.yy.c -lm -lfl rpcalc3.y:69: warning: type mismatch with previous implicit declaration rpcalc3.tab.c:1176: warning: previous implicit declaration of `yyerror' rpcalc3.y:69: warning: `yyerror' was previously implicitly declared to return `int' lexcalc2.l:30:1: warning: no newline at end of file
Diese liefert dann das gewünschte Ergebnis:
gerd@kant:~/public_html/fh/I-PROGR3/I-PROGR3-TH/VL6> ./rpcalc3 3 4 + bison NUM: 3.00 bison NUM: 4.00 bison ADD: 7.00 bison exp: 7.00 4 5 + 2 * bison NUM: 4.00 bison NUM: 5.00 bison ADD: 9.00 bison NUM: 2.00 bison MUL: 18.00 bison exp: 18.00
In den Übungsstunden