Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Jul 10, 2024
Difficulty: Medium

YACC in Compiler Design

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

YACC (Yet Another Compiler Compiler) is a computer program developed for the Unix operating system. YACC provides a tool to generate a parser for a given grammar. It is specifically designed to compile a LALR (1) grammar. YACC generates the source code for the syntactic analyzer of a language defined by a LALR (1) grammar. The input to YACC consists of the rules or grammar, and its output is a C program.

Compiler design is a complex yet fascinating field at the intersection of computer science and software engineering. At its core lies the intricate process of transforming human-readable code into machine-executable instructions. Among the multitude of tools and techniques employed in compiler construction, Yet Another Compiler Compiler (YACC) stands out as a powerful parsing tool that simplifies the development of parsers for programming languages.

yacc in compiler design

In this article, we will dive into the world of YACC.

What is YACC?

YACC serves as a powerful grammar parser and generator. In essence, it functions as a tool that takes in a grammar specification and transforms it into executable code capable of meticulously structuring input tokens into a coherent syntactic tree, aligning seamlessly with the prescribed grammar rules.

YACC was developed by Stephen C. Johnson in the 1970s. Initially, the YACC was written in the B programming language and was soon rewritten in C. It was originally designed to be complemented by Lex. 

In addition to that, YACC was also rewritten in OCaml, Ratfor, ML, ADA, Pascal, Java < Python, Ruby and Go.
 

compiler design diagram

The input of YACC in compiler design is the rule or grammar, and the output is a C program.

Parts of a YACC Program in Compiler Design

The parts of YACC program are divided into three sections:

/* definitions */
 ....


%% 
/* rules */ 
....
%% 


/* auxiliary routines */
.... 

Definitions: these include the header files and any token information used in the syntax. These are located at the top of the input file. Here, the tokens are defined using a modulus sign. In the YACC, numbers are automatically assigned for tokens. 

Let us see some examples:

%token ID
{% #include <stdio.h> %}

Rules: The rules are defined between %% and %%. These rules define the actions for when the token is scanned and are executed when a token matches the grammar.

Auxiliary Routines: Auxiliary routines contain the function required in the rules section. This Auxiliary section includes the main() function, where the yyparse() function is always called.

This yyparse() function plays the role of reading the token, performing actions and then returning to the main() after the execution or in the case of an error.

0 is returned after successful parsing and 1 is returned after an unsuccessful parsing.

The YACC is responsible for converting these sections into subroutines which will examine the inputs. This process is made to work by a call to a low-level scanner and is named Parsing

Let us now study the working of YACC in compiler design.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Workings of YACC

YACC in compiler design is set to work in C programming language along with its parser generator.

  • An input with a .y extension is given.
  • The file is invoked, and 2 files, y.tab.h and y.tab.c, are created. These files contain long codes implementing the LARl (1) Parser for grammar.
  • This file then provides yyparse.y, which tries to parse a valid sentence successfully.

For the output files, 

  • If called with the –d option in the command line, YACC produces y.tab.h with all its specific definitions.
  • If called with the –v option, YACC produces y.output having a textual description of the LALR(1) parsing table.

Example of YACC 

The YACC program code for a simple calculator is given below:

%{
#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("Incorrect\n");
tmp=1;
}
int main(){
printf("Enter an expression( +,-,*,/ or parenthesis):\n");
yyparse();
}

The lex file of the program is given below:



%option noinput nounput noyywrap
%{
#include <stdlib.h>
#include <stdio.h>
#include "y.tab.h"
extern int yylval;
%}


%%


[\t]      ;
[\n]      return 0;


[0-9]+    { yylval = atoi(yytext);
            return num;
          }
.         return yytext[0];
%%

How to Execute 

  • Save the program code to a file with a .y extension, such as calculator.y.
  • Install Yacc/Bison on your system, if it is not already installed.
  • Open a terminal or command prompt and navigate to the directory where the .y file is saved.
  • Run the following command to generate a C source file from the Yacc/Bison grammar file
yacc -d calculator.y
  • This will create two output files: y.tab.c (the C source file) and y.tab.h (the header file).
  • Compile the generated C source file and link it with the Yacc/Bison runtime library using a C compiler such as GCC:
gcc -o calculator y.tab.c -ly
  • Run the compiled program by typing its name and pressing Enter:
bash
./calculator

Explanation

Firstly, the header file is defined with all its function definitions. Then the tokens for the grammar are initialised. Finally, the grammar to use the calculator is defined.

Frequently Asked Questions

What is the main function of YACC?

The main function of YACC is to generate a parser for a given grammar specification. It takes the grammar rules and associated actions defined by the user and produces a parser that can analyze input according to those rules and perform actions accordingly.

What are the three parts of the YACC program?

The three parts of a YACC program are:

  1. Declarations: Define data types, tokens, and other necessary information.
  2. Grammar Rules: Specify the syntax of the language using context-free grammar rules.
  3. Action Statements: Define actions to be taken when specific grammar rules are recognized during parsing.

What is the algorithm of YACC?

YACC uses a parsing algorithm known as LALR (Look-Ahead Left-to-Right, Rightmost derivation) parsing. This algorithm efficiently constructs a parsing table based on the grammar rules provided and performs parsing using a stack-based approach combined with lookahead symbols.

Conclusion

In this article, we learned all about YACC in Compiler Design. It serves as a reliable tool for simplifying the creation of parsers. It transforms grammar rules into parsers efficiently, thanks to its LALR parsing algorithm. With YACC, developers can bridge the gap between human-readable code and machine instructions, making compiler design more accessible and manageable.

Recommended Readings:

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of CBasics of JavaComputer Networks, etc. along with some Contests and Interview Experiences only on Code360

Also check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, etc. as well as some Contests, Test SeriesInterview Bundles, and some Interview Experiences curated by top Industry Experts.

Happy Learning Ninja! 

 

Topics covered
1.
What is YACC?
2.
Parts of a YACC Program in Compiler Design
3.
Workings of YACC
4.
Example of YACC 
4.1.
How to Execute 
4.2.
Explanation
5.
Frequently Asked Questions
5.1.
What is the main function of YACC?
5.2.
What are the three parts of the YACC program?
5.3.
What is the algorithm of YACC?
6.
Conclusion