LEX YACC Tutorial February 28 2008 Tom St John 1 Outline Overview of Lex and Yacc Structure of Lex Specification Structure of Yacc Specification Some Hints for Lab1 2 Overview Lex A LEXical Analyzer Generator generates lexical analyzers scanners or Lexers Yacc Yet Another Compiler Compiler generates parser based on an analytic grammar Flex is Free scanner alternative to Lex Bison is Free parser generator program written for the GNU project alternative to Yacc 3 Scanner Parser Lex and Yacc symbol table Source Program Scanner token Parser C Compiler name tab c name tab h lex yy c Lex flex Yacc bison Lex spec l Yacc spec name y 4 Skeleton of a Lex Specification l file x l lex yy c is generated after running lex x l C global variables prototypes comments This part will be embedded into lex yy c DEFINITION SECTION RULES SECTION C auxiliary subroutines Define how to scan and what action to take for each token Any user code 5 Lex Specification Definition Section You should include this Yacc will generate this file automatically include zcalc tab h include zcalc h include math h User defined header file 6 Lex Specification Rules Section Format pattern pattern Regular Expression corresponding actions corresponding actions C Expression Example 1 9 0 9 1 9 0 9 Unsigned integer will be accepted as a token yylval dval yylval dval atoi atoi yytext yytext return return NUMBER NUMBER You need to define these two in y file 7 Two Notes on Using Lex 1 Lex matches token with longest match Input abc Rule a z Token abc not a or ab 2 Lex uses the first applicable rule Input post Rule1 post Rule2 a zA Z printf Hello printf World It will print Hello not World 8 Skeleton of a Yacc Specification y file x y x tab c is generated after running yacc x y C global variables prototypes comments DEFINITION SECTION PRODUCTION RULES SECTION Declaration of tokens recognized in Parser Lexer How to understand the input and what actions to take for each sentence C auxiliary subroutines 9 Yacc Specification Definition Section 1 zcalc l 1 9 0 9 1 9 0 9 yylval dval yylval dval atoi atoi yytext yytext return return NUMBER NUMBER include include zcalc h zcalc h include include string h string h int int flag flag 0 0 zcalc y union union int int dval dval token token dval dval NUMBER NUMBER 10 Yacc Specification Definition Section 2 Define operator s precedence and associativity We can solve problem in slide 13 left left left left type type dval dval expression expression statement statement statement list statement list type type dval dval logical expr logical expr Define nonterminal s name With this name you will define rules in rule section 11 Yacc Specification Production Rule Section 1 Format nontermname symbol1 symbol2 corresponding actions symbol3 symbol4 corresponding actions or nontermname2 Regular expression C expression 12 Yacc Specification Production Rule Section 2 Example statement expression expression printf g n expression expression expression expression 1 1 1 3 3 expression expression 1 3 final value by performing non terminal s action Only for writing not reading NUMBER n value of the nth concatenated element What will happen if we have input 2 3 4 Avoiding Ambiguous Expression That s the reason why we need to define operator s precedence in definition section 13 Hints for Lab1 Exercise 2 Q How to recognize prefix postfix and infix in Lexer A Step1 Add these rules to your l file prefix postfix infix Should be put in the rule section return PREFIX return POSTFIX Case sensitive return INFIX Step2 declare PREFIX POSTFIX and INFIX as token in your y file 14 Hints for Lab1 Exercise 2 Q How to combine three modes together A You may have following grammar in your yacc file int flag 0 Default setting statement PREFIX flag 0 INFIX flag 1 POSTFIX flag 2 expression expression expr pre expr in expr post expr pre expr pre expr pre if flag 0 2 3 expr in expr in expr in if flag 1 1 3 15 Hints for Lab1 Exercise 3 Q What action do we use to define the octal and hexadecimal token A You can simply use strtol functions for this long strtol const char nptr char endptr int base 16 Hints for Lab1 Exercise 4 5 Q How to build up and print AST 1 Define the struct for AST and linked list structure having AST nodes typedef struct EXP struct EXP exp1 struct EXP exp2 struct OP operator AST Instead of using struct if you use union here It s easier to handle the terminal nodes name and numbers 2 In yacc file your statement and expressions should be ast type no longer dval type 17 Hints for Lab1 Exercise 4 5 3 Functions for making expression It can be different functions by the type of the node kinds of expression number name and so on You can make functions like makeExpression struct EXP exp1 struct EXP exp2 struct OP operator The action field for each production in your yacc file can call any function you have declared Just as a sentence is recursively parsed your AST is recursively built up and traversed 18 A case study The Calculator zcalc l zcalc y include zcalc h include zcalc tab h Yacc d zcalc y include y tab h union double dval struct symtab symp token dval NUMBER 0 9 0 9 0 9 eE 0 9 yylval dval atof yytext return NUMBER struct symtab sp symlook yytext yylval symp sp return NAME left type dval expression statement list statement n statement list statement n a zA Z a zA Z0 token symp NAME t statement NAME expression 1 value 3 expression printf g n 1 expression expression expression 1 3 expression expression 1 3 NUMBER 1 NAME 1 value struct symtab symlook char s this function looks up the symbol table and check whether the symbol s is already there If not add s into symbol table int main yyparse return 0 19 References Lex and Yacc Page http dinosaur compilertools net 20