Building a simple compiler series (8)–Yacc

Yacc(Yet another compiler-compiler), another powerful tool for generator a parser according to a specify context free grammar.

Yacc provides a general tool for imposing structure on the input to a computer program. The Yacc user prepares a specification of the input process; this includes rules describing the input structure, code to be invoked when these rules are recognized, and a low-level routine to do the basic input. Yacc then generates a function to control the input process. This function, called a parser, calls the user-supplied low-level input routine (the lexical analyzer) to pick up the basic items (called tokens) from the input stream. These tokens are organized according to the input structure rules, called grammar rules; when one of these rules has been recognized, then user code supplied for this rule, an action, is invoked; actions have the ability to return values and make use of the values of other actions.

Yacc file specifcation just like below which is similar with the Lex file specification.

declarations
%%
rules
%%
programs

Here is a quick demo which based on here. You can refer to that link for more iinformation.I add a main function and a yyerror function. I will add more detail information and other examples in next post. Here is just a simple example which shows what’s the yacc like, how to use it, and what is it like.

%{
#  include
#  include
int  regs[26];
int  base;
%}
%start  list
%token  DIGIT  LETTER
%left  '|'
%left  '&'
%left  '+'  '-'
%left  '*'  '/'  '%'
%left  UMINUS      /*  supplies  precedence  for  unary  minus  */
%%      /*  beginning  of  rules  section  */
list :    /*  empty  */
     |  list  stat  '\n'
     |  list  error  '\n'
               {    yyerrok;  }
     ;
stat :    expr
               {    printf( "%d\n", $1 );  }
     |  LETTER  '='  expr
               {    regs[$1]  =  $3;  }
     ;
expr :    '('  expr  ')'
               {    $$  =  $2;  }
     |  expr  '+'  expr
               {    $$  =  $1  +  $3;  }
     |  expr  '-'  expr
               {    $$  =  $1  -  $3;  }
     |  expr  '*'  expr
               {    $$  =  $1  *  $3;  }
     |  expr  '/'  expr
               {    $$  =  $1  /  $3;  }
     |  expr  '%'  expr
               {    $$  =  $1  %  $3;  }
     |  expr  '&'  expr
               {    $$  =  $1  &  $3;  }
     |  expr  '|'  expr
               {    $$  =  $1  |  $3;  }
     |  '-'  expr       %prec  UMINUS
               {    $$  =  -  $2;  }
     |  LETTER
               {    $$  =  regs[$1];  }
     |  number
     ;
number    :   DIGIT
               {    $$ = $1; base  =  ($1==0)  ?  8  :  10;  }
     |  number  DIGIT
               {    $$  =  base * $1  +  $2;  }
     ;
%%      /*  start  of  programs  */
yylex() {      /*  lexical  analysis  routine  */
              /*  returns  LETTER  for  a  lower  case  letter,  yylval = 0  through  25  */
              /*  return  DIGIT  for  a  digit,  yylval = 0  through  9  */
              /*  all  other  characters  are  returned  immediately  */
     int  c;
     while(  (c=getchar())  ==  ' '  )  {/*  skip  blanks  */  }
     /*  c  is  now  nonblank  */
     if(  islower(  c  )  )  {
          yylval  =  c  -  'a';
          return  (  LETTER  );
          }
     if(  isdigit(  c  )  )  {
          yylval  =  c  -  '0';
          return(  DIGIT  );
          }
     return(  c  );
     }
main()
{
    return yyparse();
}
int yyerror(char *s)
{
    fprintf(stderr,"%s\n",s);
    return 0;
}

The input file.

The result of the expression.