October 8

* Exam Review


* Lex and Yacc

   Lex provides a simple lexical analysis of input text.
   The input file contains regular expressions describing acceptable text
      and associates actions with each regular expression.

   source program -> lexical analyzer - (token) -> parser

   A Lex program consists of three parts

   declarations
   %%
   translation rules
   %%
   auxiliary procedures

   declarations:  declare variables, constants, and regular definitions
   translation rules:
      p1 {action1}
      p2 {action2}
      ...
      pn {actionn}

   Each pi is a regular expression and each actioni is a program fragment.
      The program gragment can return a token to pass to the parser.

   Matching is performed in the order that strings appear in the file
   Can group characters such as [a-cx-z] to indicate a, b, c, x, y, and z



Sample Lex file

letter [a-zA-Z]
digit  [0-9]

%%

"variable"      { fprintf(stderr, "Parsed VARIABLE token\n"); return(TVAR); }
"("             { fprintf(stderr, "Parsed ( token\n"); return(TLPAREN); }
")"             { fprintf(stderr, "Parsed ) token\n"); return(TRPAREN); }
{letter}({letter}|{digit})*     { pident(yytext); return(TIDENT); }

%%

pident(in)
   char *in;
{
   fprintf(stderr, "Parsed identifier %s\n", in);
}


Yacc is a parser.
   Yacc converts a CFG into a set of tables.
   A yacc file has three parts:

   declarations
   %%
   translation rules
   %%
   supporting C routines

   declarations:  define constants (tokens defined by lex program)
   translation rules:  CFG rules to parse input and associated actions


Sample Yacc file

%token TVAR TLPAREN TRPAREN TIDENT

%%

acceptable_input        :       TVAR variable { fprintf(stderr, "Done\n"); }

variable                :       ident
                        |       TLPAREN ident TRPAREN

ident                   :       TIDENT

%%

#include "lex.yy.c"
#include 

main()
{
   return(yyparse());
}


yyerror(s)
   char *s;
{
   fprintf(stderr, "%s\n", s);
}



Sample run:

>lex l
(This creates the file "lex.yy.c")

>yacc y
(This creates the file "y.tab.c")

>cc y.tab.c -ly -ll

>a.out
variable ab2
Parsed VARIABLE token
Parsed identifier ab2
Done
 
>a.out
variable (ab2)
Parsed VARIABLE token
Parsed ( token
Parsed identifier ab2
Parsed ) token
Done