Transcript ppt - Pacific University

CS310
Lex & Yacc
Today’s reference:
UNIX Programming Tools:
lex & yacc
by: Levine, Mason, Brown
Chapter 1, 2, 3
November 1, 2006
CS 310 – Fall 2006
Pacific University
Automatic Parser Generators
• You supply the tokenizer
– Lex/Flex
– code to break the string into terminals
• You supply the grammar
• Output source code that will produce a parser
– Yacc/Bison (produces C code)
– NewYacc (produces C code, a bit more powerful
than Yacc, keeps more state)
– Jacc (produces Java code)
– decorate the grammar rules with source code to
perform various tasks
CS 310 – Fall 2006
Pacific University
Lex (Flex*)
• Lex:
– specify the terminals or regular expressions that
represent the terminals
– produces a C source file as output that will
divide input into tokens
file.l -> lex -> lex.yy.c
* Flex and Bison are the GNU equivalents of Lex and Yacc
CS 310 – Fall 2006
Pacific University
%{
/* sample demonstration*/
/* identify is and are as verbs */
%}
%%
[\t ]+
/* ignore whitespace */
is |
are
{ printf(“%s: is a verb”, yytext); }
[a-zA-Z]+ { printf(“%s: not a verb”, yytext);}
%%
main()
{
yylex();
}
CS 310 – Fall 2006
Pacific University
%{
/* count verbs and nonverbs */
int verbCount=0, nonVerbCount=0;
%}
%%
[\t ]+
is |
are
/* ignore whitespace */
{
printf(“%d verbs\n”, ++verbCount);
[a-zA-Z]+ {
printf(“%d non-verbs\n”,
++nonVerbCount); }
%%
main()
{
yylex();
printf(“%d verbs| %d nonverbs\n”, verbCount,
nonVerbCount);
}
CS 310 – Fall 2006
Pacific University
}
Yacc (Bison)
• Yacc:
– take the tokens (terminals) from lex and apply a
grammar
– produce C file
– check syntax
file.y -> yacc -> y.tab.[c|h]♦
– y.tab.c contains the C code to apply the
grammar
– y.tab.h contains the data structures to be used
by lex to pass data to yacc
♦bison
names the file file.tab.[c|h]
CS 310 – Fall 2006
Pacific University
%{
#include <stdio.h>
%}
%token VERB NOUN
%%
paragraph: sentence
{ printf(“paragraph\n”); }
| paragraph sentence {printf(“paragraph\n”);}
sentence: nounphrase verbphrase { printf(“sentence\n”); }
nounphrase: NOUN { printf(“noun\n”); }
verbphrase: VERB { printf(“verb\n”); }
%%
extern FILE *yyin; extern int lineno; extern char* yytext;
main(){
do{
yyparse();
}while(!feof(yyin));
}
void yyerror(char *msg){
printf(“ERROR: (%d:%s) %s\n”,lineno, yytext, msg);
}
CS 310 – Fall 2006
Pacific University
%{
What lex file will we need?
/* identify is and are as verbs */
/* identify computer, bob, alice as nouns */
#include “y.tab.h” /* shared data with yacc*/
int lineno=1;
%}
%%
[\t ]+
/* ignore whitespace */
is |
are
{ return(VERB); }
computer |
bob |
alice { return(NOUN);}
\n
%%
{ lineno++;}
CS 310 – Fall 2006
Pacific University
Build the executable
yacc –dv yaccfile.y
lex lexfile.l
gcc –o parser lex.yy.c y.tab.c -lfl
Examples will
be posted after
class on the CS310
schedule!
A Makefile will be
provided.
CS 310 – Fall 2006
Pacific University
Shift/Reduce Conflicts
stmt:
IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
Solutions:
–
–
Rewrite the grammar.
Use precedence to tell the parser how to handle this
%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
stmt:
IF expr THEN stmt %prec LOWER_THAN_ELSE
| IF expr THEN stmt ELSE stmt
CS 310 – Fall 2006
Pacific University