9.13.  A Real Parser: Yacc

yacc (yet another compiler compiler) command converts a context-free grammar into a set of tables for a simple automaton that executes an LALR(1) parsing algorithm. The grammar may be ambiguous; specified precedence rules are used to break ambiguities.

The output file,

y.tab.c ,

must be compiled by the C compiler to produce a function

yyparse ().

This program must be loaded with the lexical analyzer program,

yylex (),

as well as

main ()

and

yyerror (),

an error handling routine. These routines must be supplied by the user; the

lex (1)

command is useful for creating lexical analyzers usable by yacc.

One example: calc.y

 1      
 2      /*
 3       *      a simple calculator
 4       */
 5      %{
 6      #include <stdio.h>
 7      %}
 8      %%
 9      
10      program:
11          /* null */
12          | program sum '\n'  { printf("----> %d\n", $2); }
13          | program '\n'
14      
15      sum:
16          product             /* $$ = $1; */
17          | sum '+' product   { $$ = $1 + $3; }
18          | sum '--' product   { $$ = $1 -- $3; }
19      
20      product:
21          factor
22          | product '*' factor { $$ = $1 * $3; }
23          | product '/' factor { $$ = $1 / $3; }
24      
25      factor:
26          digits
27          | '(' sum ')'       { $$ = $2; }
28      
29      digits:
30          digit               { $$ = $1--'0'; }
31          | digits digit      { $$ = 10*$1 + $2--'0'; }
32      
33      digit:
34          '0' | '1' | '2' | '3' | '4'
35          | '5' | '6' | '7' | '8' | '9'
36      
37      %%
38      
39      yylex()
40      {
41          return yylval = getchar();
42      }

% bison calc.y
% gcc -o calc calc.tab.c -ly
% calc
1+2*7
--> 15

Add the power functionality to the grammar.

Here is the grammar:

 1      
 2      /*
 3       *      a simple calculator with power functionality
 4       */
 5      %{
 6      #include <stdio.h>
 7      #include <math.h>
 8      %}
 9      %%
10      
11      program:
12          /* null */
13          | program sum '\n'  { printf("----> %d\n", $2); }
14          | program '\n'
15      
16      sum:
17          product             /* $$ = $1; */
18          | sum '+' product   { $$ = $1 + $3; }
19          | sum '--' product   { $$ = $1 -- $3; }
20      
21      product:
22          pow
23          | product '*' pow   { $$ = $1 * $3; }
24          | product '/' pow   { $$ = $1 / $3; }
25      
26      pow:
27          factor
28          | factor '^' pow    { $$ = (int)pow((double)$1,
29                                              (double)$3);
30                              }
31      
32      
33      
34      
35      factor:
36          digits
37          | '(' sum ')'       { $$ = $2; }
38      
39      digits:
40          digit               { $$ = $1--'0'; }
41          | digits digit      { $$ = 10*$1 + $2--'0'; }
42      
43      digit:
44          '0' | '1' | '2' | '3' | '4'
45          | '5' | '6' | '7' | '8' | '9'
46      
47      %%
48      
49      yylex()
50      {
51          return yylval = getchar();
52      }

% calc_p
1+2
--> 3
1+2^2
--> 5

Last modified 22/May/97