Lemon Parser

Prerequisite for the Parser Generator

Submitted by vivekanandan on Mon, 03/15/2010 - 08:21

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

Submitted by vivekanandan on Fri, 03/12/2010 - 10:04

lemon_parser/lemLexical 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++

Submitted by vivekanandan on Fri, 03/12/2010 - 10:02

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

Submitted by vivekanandan on Fri, 03/12/2010 - 09:46

Lemon uses LALR (1) parsers means Look Ahead exactly one token from Left to Right. 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

Submitted by vivekanandan on Fri, 03/12/2010 - 09:44

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 :