What is a YACC parser generator?

Yet Another Compiler Compiler (YACC) is a tool that generates a parser program for a given LALR(1)LALR (1) stands for the Look-Ahead-Left-Right parser. In LALR (1), the same productions with different Look-Aheads are combined. grammar. It processes the grammar and outputs a C program. YACC takes help from the Lex tool (a lexical analyzer generator) to tokenize an input stream.

Note: To learn more about the LEX lexical analyzer generator, we can click here

Parts of the YACC program

A YACC program contains three main sections:

  • Definitions

  • Rules

  • Auxiliary routines

Definitions

Definitions are at the top of the YACC input file. They include header files or any information about the regular definitions or tokensA sequence of characters that have a collective meaning used to represent information of characters. We define the tokens using a modulus sign, whereas we place the code specific to C, such as the header files, within %{\% \{ and %}\%\}.

Some examples are as follows:

  • %token ID

  • {% #include <stdio.h> %}

Rules

Rules are between %%\%\% and %%\%\%. They define the actions we take when we scan the tokens. They execute whenever a token in the input stream matches with the grammar. Any action in C is placed between curly brackets ( {}\{\}).

Auxiliary routines

Auxiliary routines includes functions that we may require in the rules section. Here, we write a function in regular C syntax. This section includes the main() function, in which the yyparse() function is always called.

The yyparse() function reads the tokens, performs the actions, and returns to the main when it reaches the end of the file or when an error occurs. It returns 00 if the parsing is successful, and 11 if it is unsuccessful.

Example

The following code is an example of a YACC program of a simple calculator taking two operands. The .y extension file contains the YACC code for the parser generation, which uses the .l extension file that includes the lexical analyzer.

file.y
lexfile.l
%{
#include <ctype.h>
#include <stdio.h>
int yylex();
void yyerror();
int tmp=0;
%}
%token num
%left '+' '-'
%left '*' '/'
%left '(' ')'
%%
line :exp {printf("=%d\n",$$); return 0;};
exp :exp '+' exp {$$ =$1+$3;}
| exp '-' exp {$$ =$1-$3;}
| exp '*' exp {$$ =$1*$3;}
| exp '/' exp {$$ =$1/$3;}
| '(' exp ')' {$$=$2;}
| num {$$=$1;};
%%
void yyerror(){
printf("The arithmetic expression is incorrect\n");
tmp=1;
}
int main(){
printf("Enter an arithmetic expression(can contain +,-,*,/ or parenthesis):\n");
yyparse();
}

Explanation

In the file.y YACC file:

  • Lines 1–7: We initialize the header files with the function definitions.

  • Lines 9–12: We initialize the tokens for the grammar.

  • Lines 16–23: We define the grammar used to build the calculator.

  • Lines 27–34: We define an error function with the main function.

In lexfile.l Lex file:

  • Lines 1–7: The header files are initialized along with the YACC file included as a header file.

  • Lines 11–18: The regular definition of the expected tokens is defined such as the calculator input will contain digits 0-9.

Execution

To execute the code, we need to type the following commands in the terminal below:

  • We type lex lexfile.l and press "Enter" to compile the Lex file.

  • We type yacc -d yaccfile.y and press "Enter" to compile the YACC file.

  • We type gcc -Wall -o output lex.yy.c y.tab.c and press "Enter" to generate the C files for execution.

  • We type ./output to execute the program.

Terminal 1
Terminal
Loading...
Copyright ©2024 Educative, Inc. All rights reserved