YACC - A tool for writing parsers

• Parsers check the syntax of a programming language.

• YACC programs receive a stream of tokens from a lexer as input.

• Only one token lookahead.

YACC - Internals

• Transforms grammar into LR(1) parser.
• Builds LALR(1) tables and combines with C driver.

YACC - File Format

%{
     C Declarations and includes
%}
Definitions

%token ...    %left ...
%union {      %nonassoc ...
...           %type ...
}             %start ...

%%
Rules

rule1: rule_definition { action }
      | rule_definition { action }
      ...
      ;
...
%%
User Subroutines (C code)

YACC - Rule Definitions

Rule definitions consistion of

• tokens,
• character constants ('c'),
• other rules.

YACC - Example

%{
/* Example yacc source file
 * Adapted from "Lex & Yacc" by Levine,
 * Mason, and Brown
 */
%}
%union {
    char *string;
    int integer;
}
%token <string> NAME
%token <integer> NUMBER
%type <integer> expression
%%

YACC - Example

program: statement 
    | program statement
    ;
statement: NAME '=' expression {symset($1,$3);}
    |    expression
    ;
expression: NUMBER '+' NUMBER {$$ = $1 + $3;}
    |     NUMBER '-' NUMBER {$$ = $1 - $3;}
    ;
%%
void symset(char *name, int value) {...}

main() {
   yyparse();
}

YACC - Running YACC

To run yacc on a source file, use the command:

yacc -d source.y

This produces the files y.tab.c which is the C source for the parser, and y.tab.h which is a header file that defines all the tokens used by yacc. Best included by lex programs.

To compile this (assuming your lex file is lex.yy.c), use:

cc -o prog y.tab.c lex.yy.c -ly -ll

YACC - Notes

• A little less picky than lex on spacing.
• First rule is selected as starting rule by default.
• Look at manual page!!!
• Once again, try things early!!!