Description

Syntax Analysis/Parsing- (LL(1) predictive parser)

NOTE: Refer lecture notes, Chapter 4 (until sec 4.4).

For each of the grammars, perform the following steps and implement a predictive LL(1) parser.
STEP (2) For the LL(1) grammar obtained from step 1, manually compute the FIRST() set of all symbols in the grammar, and also compute the FOLLOW() set for all non-terminals. Store this information in another file e.g., file named “FirstFollow.txt”.
STEP (3) Write a C program to implement a table driven predictive parser for the LL(1) grammar obtained in step 1. Your implementation should contain two different modules/functions. The first module should construct the LL(1) parsing table from the
NOTE: Use Lex/Flex to generate a lexical analyzer for recognizing tokens.

Submission: Along with the source-code (step 3), for each example input grammar, submit files “grammarLL.txt”. and “First-Follow.txt”. Provide additional README file with other information (e.g., instructions to run, sample test inputs considered).
——————————————————————————————————-
Example grammars are given below. Please note that only the steps that need to be done manually (steps 1, and 2) should be redone when you consider a different grammar.

Grammar 1:

Grammar 2:
For the following grammar, the non-terminals are
N = { AE, BE, D, DL, E, F, ES, IOS, IS, NE, P, PE, RE, S, SL, T, TY, VL, WS },

the terminals are
T = { + , −, ∗, /, =, <, >, (, ), {, }, :=, ; , and, else, end, ic, id, if, int, do, fc, float, not, or, print, prog, scan, str, then, while },

Most of the terminals are self-explanatory (id is an (identifier), ic is an integer constant, fc is a floating-point constant, str is a string of characters, := is an assignment etc.

The production rules are given in the next page (the start symbol is P).

P → prog DL SL end
DL → D DL | ε
D → TY VL ;
TY → int | float
VL → id VL | id
SL → S SL | ε
S → ES | IS | WS | IOS
ES → id := E ;
IS → if BE then SL end | if BE then SL else SL end
WS → while BE do SL end
IOS → print PE | scan id
PE → E | str
BE → BE or AE | AE
AE → AE and NE | NE
NE → not NE | { BE } | RE
RE → E = E | E < E | E > E
E → E + T | E − T | T
T → T F | T / F | F
F → ( E ) | id | ic | fc