Spread Knowledge

CS606 - Compiler Construction - Lecture Handout 30

User Rating:  / 0
PoorBest 

Related Content: CS606 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Compiler Construction

Parser Generators

Parser generators exist for LL(1) and LALR(1) grammars. For example,

  • LALR(1) - YACC, Bison, CUP
  • LL(1) – ANTLR
  • Recursive Descent - JavaCC

YACC Parser Generator

YACC – Yet Another Compiler Compiler, appeared in 1975 as a Unix application. The other companion application Lex appeared at the same time. These two greatly aided the construction of compilers and interpreters. The input to YACC consists of a specification text file. The structure of the file is

definitions
%%
rules
%%
C/C++ functions

Here, for example, is the YACC file for a calculator

%token NUMBER LPAREN RPAREN
%token PLUS MINUS TIMES DIVIDE
%%
expr : expr PLUS expr
| expr MINUS expr
| expr TIMES expr
| expr DIVIDE expr
| LPAREN expr RPAREN
| MINUS expr
| NUMBER
;

%%

The Flex input file for a calculator is

%{
#include "y.tab.h"
%}
digit [0-9]
ws [ \t\n]+
%%
{ws} ;
{digit}+ {return NUMBER;}
"+" {return PLUS;}
"*" {return TIMES;}
"/" {return DIVIDE;}
"–" {return MINUS;}
%%

The following diagram outlines the process of building a parser with YACC and Lex.

YACC and Lex