gsorbier/parser-complete

A lexical analyzer + SLR Parser. The lexical analyzer converts the input regular expressions to NFAs. The SLR parser takes the input text file along with the NFAs constructed by the lexical analyzer and an input grammar and generates a parse tree. The program was written in C.

Parser Complete

This project is a complete Parser + Lexical Analyzer. The program receives as input a text file with source code inside. The lexical analyzer will convert the file into tokens recognizable by the parser. The parser will then convert the tokens to a parse tree.

Lexical Analyzer

The following Regular expressions are defined for the lexical analyzer:

delim                             [ \t\n]
ws                                {delim}+
letter                            [A-Za-z]
digit                             [0-9]
id                                {letter}({letter}|{digit})*
number                            {digit}+(\\.{digit}+)?(E[\\+\\-]?{digit}+)?
IF                                if
THEN                              then 
ELSE                              else
LT                                <
LE                                <=
EQ                                =
NE                                <>        
GT                                >
GE                                >=
WHILE                             while

They can be found in the RegDefs.c file. The lexical analyzer then converts these regular expressions into parse trees. The parse trees are then converted to NFAs (Nondeterministic Finite Automata).

#Parser The parser is an SLR parser. The following grammar is defined for the parser:

S'->S
S->SF;|SW;|SA;|F;|W;|A;
F-><IF>(Expr){S}|<IF>(Expr){S}<ELSE>{S}
W-><WHILE>(Expr){S}
A->LR
L-><ID><EQ>
Expr->R<LT>R|R<LE>R|R<EQ>R|R<NE>R|R<GT>R|R<GE>R
R->T
T->T+E|T-E|E
E->E*Q|E/Q|Q
Q->(R)|<NUMBER>|<ID>

The following are the nonterminals along with their associated token ID:

[S',     0]
[S,      1]
[F,      2]
[W,      3]
[A,      4]
[Expr,   5]
[L,      6]
[R,      7]
[E,      8]
[Q,      9]
[T,     10]

and the following are the terminals along with their associated token ID:

[WS     15]
[IF     16]
[THEN   17]
[ELSE   18]
[ID     19]
[NUMBER 20]
[LT     21]
[LE     22]
[EQ     23]
[NE     24]
[GT     25]
[GE     26]
[WHILE  27]
[+      28]
[-      29]
[*      30]
[/      31]
[(      32]
[)      33]
[{      34]
[}      35]
[;      36]

11~14 are reserved for future nonterminals.

#Usage Inside the Input folder there is a file with the name Input.txt. The user can input source code that matches the grammar inside this file. After running the program the parse tree will be generated. The Main() function can be found inside Compiler_C.c.

Examples of syntax the program will understand are:

while(1=1){
   f=3;
}
if(1=1){
   j=34-23;
}

temp = 34*34;
if(3>=34){
   a = 3;
}else{ f = 3;}

#Example Considering the input below:

if(1=1){
   j=34-23;
}

The output parse tree would be:

0
\1
\\2
\\\16
\\\32
\\\5
\\\\7
\\\\\10
\\\\\\8
\\\\\\\9
\\\\\\\\20
\\\\23
\\\\7
\\\\\10
\\\\\\8
\\\\\\\9
\\\\\\\\20
\\\33
\\\34
\\\1
\\\\4
\\\\\6
\\\\\\19
\\\\\\23
\\\\\7
\\\\\\10
\\\\\\\10
\\\\\\\\8
\\\\\\\\\9
\\\\\\\\\\20
\\\\\\\29
\\\\\\\8
\\\\\\\\9
\\\\\\\\\20
\\\\36
\\\35

#Source Files:

GENERAL:
Class_Generic.h: Generic functions for defining structs. 
Create_Object.h: Generic function for initializing structs.
LinkedList.h: Generic linked list data structure.
ParseTree.h: Generic parse tree data structure.
Stack.h: Generic stack data structure.
String.h: String operations.

LEXICAN ANALYZER:
LexAnalyzer.h: Reads the input file and returns a list of lexems
LexDefs.h: Contains a list of regular definition that are used for determining lexems
RegDefs.h: Contains a list of regular expressions. Not all the regular expressions are lexems.
The file also expands the regular expressions where another regular expression is used in side it
LexTree.h: Receives as input a regular expression and generates the associated parse tree
NFA.h: Receives as input a parse tree and generates the associated nondeterministic finite autamata (NFA).

PARSER:
Automation.h: Generates the grammar automaton
Closure.h: Generates the closure based on the input production and dot position.
First.h: Generates the FIRST set for each production
Follow.h: Generates the FOLLOW set for each nonterminal
Grammar.h: Processes the grammar matrix
ParseTable.h: Generates the parse table.
SLRParser.h: Generates a parse tree based on the input grammar and input list of tokens

License

The MIT License (MIT)