# Lemon Parser

## Prerequisite for the Parser Generator

Finite state machine (FSM) or Finite state automaton (FSA) :

It is a model of behavior composed of a finite number of states which machine is used in Artificial Intelligence, languages, network protocol, compilers.

All FSM has 5 Tuples or Action are (Q,A,f,q0,qn)

q0 = A finite set of start states

qn = A finite set of final states

Q=> finite set of state(all states like q0,q1,q2..qn)

f=> transition function

A=>input symbol=> Set of Terminal and NonTerminal.

## The Lemon Parser Algorithm

lemon_parser/lem**Lexical analysis:**

it scans the source code of CFG and load the grammer to the symbol table. If ther is any error in CFG it just report & halts down.

**FindRulePrecedences:**

Find precedence of symbols & set it

**FirstSet:**

Compute FIRST(X):

If X is a terminal, then FIRST(X) = {X}

X is a nonterminal, travel all production of X until find first terminal .

Construct Parse Stack

Convert backward propagation link to forward link

**FollowSet:**

**Compute Action table**

## Lemon Parser for Turbo C++

Hi,

Replace the function symbol comparison by the following code which is used in

**quick sort** , it works well in both Linux & Turbo c++also.

int Symbolcmpp(struct symbol **a, struct symbol **b){ return strcmp((**a).name, (**b).name) ; }

and re compile lemon.c file , then now lemon is ready for the TC.

## Understanding Lemon generated Parser

Lemon uses LALR (1) parsers means **L**ook **A**head exactly one token from **L**eft to **R**ight. When the parser receive the input Token, it also reads previous State number from the Parser stack. Using this Token and State number Parser process with the pre calculated Tables like yy_action, yy_shift_ofst, yy_reduce_ofst , Depends upon the values the corresponding action shift or Reduce is performed .

Current Token with Previous State Number => Action

**Parser Action :**

## Now Lemon Parser with VCG Graph

**Visualization of Compiler Graphs (VCG):**

The VCG for lemon parser is available. it has function ReportVcgGraph which generate the graph with the argument -v when compiling the lemon.

Function FindStates construct the State Table.Each State holds the action table if there is a shift then it holds next possible lookahead symbol with corresponding states.

**Construction of VCG Graph :**