Building a compiler Part. 2 of 4 Getting Started with yacc

In the previous blog we discussed about the first phase of compilation namely lexical analysis, (Although the term 'first phase' was used, you know that all phases run simultaneously by fetching required information from the previous phases and the symbol table) in this blog we will discuss about syntax analysis and how to write a parser using YACC/BISON.

Syntax Analysis

A syntax analyzer takes the stream of tokens and creates a parse tree which gives information about the precedence and association of the operators. To construct this parse tree, the syntax analyzer takes help of the symbol table having information of each token. Once done, the acceptance of the statements in the code is decided by parsing them, this can be top-down or bottom-up.

Top-down parsers start from the starting symbol S in the stack and pop the non-terminal from top of stack and substitute with the right-hand side of a corresponding production, if there is a match with input string, the terminal is popped. This is repeated till the string is not completely parsed, if the stack is empty then the string is accepted.

Bottom-up parsers (also called shift reduce parsers) on the other hand start with the input string, pushing the input symbols into the stack and replacing the top of stack with left hand non-terminal of the corresponding production, if the final symbol in the stack is the start symbol S, then the string is accepted.

Grammar

Before going into the YACC tool, let us get an idea of what a grammar is and how does a compiler ensure syntax correctness. Simply put a grammar is a set of rules any language (C, C++, Java, English, Spanish, French or Urdu). These rules are expected to be followed in constructing meaningful statements for the language. 

Mathematically, it is a quadruple (T, N, P, S) where 

T is the set of terminals

N is the set of non-terminals

P is the set of productions

S is the start symbol

We have already met a grammar - regular grammar while trying to construct expressions to identify tokens in the lexical analysis phase. In case of syntax analysis, the language type used is CFG (context free grammar level 2). This puts some restrictions on the two sides of the production, meaning the productions are of type: X -> Y where |X| <= |Y| and X = N and Y = (T + N)*. The parser uses this grammar rules to check for the correctness of the statements.

Also, almost all parsers (except a few like the operator precedence) expect the grammar provided to them for creating the parse tree to be unambiguous, if we supply an ambiguous one there might be conflicts (for a shift reduce parser, there can be shift-reduce or reduce-reduce conflicts)

YACC - Yet Another Compiler Compiler

YACC is the software to create such a parser (bottom-up LALR(1) to be specific). It takes grammar in BNF form and gives a parser as output which constructs the parse tree in bottom-up manner.

The format is similar to the way we wrote LEX:

definitions

%%

productions/rules

%%

subroutines

The productions as mentioned in BNF form:

X :   <expression1> 

      | <exprssion2>

      .

      .

      ;

Calculator

Now let's get practical, we will be designing a calculator which will be able to solve basic math equations and store data in variables (a to z or A to Z).

calc-ad.l

The lex.l code creates the tokenizer, this passes the token type and a value associated with the token to the parser. If the token is an integer, it passes the value, if it is a variable, then it returns the character. In case of operators, it returns it as token itself.

calc-ad.y

The yacc.y file creates the parser, it specifies the grammar rules. The grammar specified should be un-ambiguous, meaning it should be able to distinguish when an expression contains an operand which has operators on both sides, it should always select evaluation of side with a specific operator (fixed precedence) and if the operator is same, it should pick the same side consistently (fixed associativity). This is to ensure only one LMD, RMD or parse tree is created.

We have incorporated only + and * for this calculator but can be extended to - and / as well. Also, all statements end with ; so, expect a syntax error if you enter a statement which doesn't end with it.

YYSTYPE is declared to be a union so that in case of token of type VARIABLE, yylval can hold characters and in case of token of type INTEGER, it can hold numbers.

To run the program:

> yacc -d calc.y

This creates files named yy.tab.c and yy.tab.h (declaration of token)

> lex calc-ad.l

> gcc yy.tab.c lex.yy.c -o calc-ad

> ./calc-ad

Source code:

calc-ad

References

Grammar in TOC » CS Taleem