2.

2  Syntax Analyzer
where i – stands for if keyword
t – stands for then keyword
e – stands for else keyword
Chapter 2: Syntax Analysis a – stands for a statement
b – stands for a statement
What are we studying in this chapter?
Now, let us see “What are the various notations used when we write the grammars?” The
 The Role of the Parser various notations used in a context free grammar are shown below:
 Context-free Grammars 1. The following symbols are terminals
 Writing a Grammar a) The keywords such as if, for, while, do-while etc.
 Parsing techniques b) Digits from 0 to 9
 Top-down Parsing c) Symbols such as +, -, *, / etc
 Bottom-up Parsing - 6 hours d) The lower case letters near the beginning of alphabets such as a, b, c, d etc.
e) The bold faced letters such as id

2.1 Introduction 2. The following symbols are non-terminals

a) The lower case names such as expression, operator, operand, statement etc
Every programming language such as C or PASCAL has rules that prescribe the syntactic b) The capital letters near the beginning of the alphabets such as A, B, C, D etc
structure of well-formed programs. The syntax of programming language constructs can c) The letter S is the start symbol
be described by CFG or BNF (Backus Naur Form) notation. The parser determines the
3. The lower case letters near the end of the alphabets such as u, v, w, x, y, z represents
syntax or structure of a program. That is, it checks whether the input is syntactically
string of terminals.
correct or not. Before proceeding further, let us see what is a context free grammar, what
is derivation and some other important terms that are used in coming chapters. 4. The capital letters near the end of the alphabets such as U, V, W, X, Y, Z etc
represent grammar symbols. A grammar symbol can be a terminal or a non-terminal.
2.2 Context-free Grammars
5. The Greek letters such as α, β, γ, δ etc. represent string of grammar symbols.
Now, let us see “What is a context free grammar?”
2.3 Derivation
Definition: The context free grammar in short a CFG is 4-tuple G = (V, T, P, S) where Now, let us see “What is derivation?”
 V is set of variables. The variables are also called non-terminals.
 T is set of terminals. Definition: The process of obtaining string of terminals and/or non-terminals from the
 P is set of productions. All productions in P are of the form A→ α where A is a non- start symbol by applying some set of productions (it may include all productions) is
terminal and α is string of grammar symbols. called derivation.
 S is the start symbol. For example, if A → B and B →  are the productions, the string  can be
obtained from A- production as shown below:
Ex 1: Grammar to generate one of more a‟s is shown below:
A → a | aA A  B [ Apply the production A → B]
  [ Replace B by  using the production B → ]
Ex 2: Grammar to recognize an if-statement is shown below:
S→iCtS|iCtSeS|a The above derivation can also be written as shown below:

C→b A  
  Systematic approach to Compiler Design - 2.3 2.4  Syntax Analyzer

Observe the following points: Definition: The process of obtaining a string of terminals from a sequence of
 If a string is obtained by applying only one production, then it is called one-step replacements such that only leftmost non-terminal is replaced at each and every step is
derivation and is denoted by the symbol „ „. called leftmost derivation.
 If one or more productions are applied to get the string  from A, then we write For example, consider the following grammar:

A  
E → E+E
 If zero or more productions are applied to get the string  from A, then we write E → E*E
A  E → (E)
E → id
Example 2.1: Consider the grammar shown below from which any arithmetic
expression can be obtained. The leftmost derivation for the string id + id * id can be obtained as shown below:
E → E+E E  E+E
E → E-E lm

E → E*E  id + E
E → E/E  id + E * E
E → id  id + id * E
 id + id * id
Obtain the string id + id * id and show the derivation for the same.
2.3.2 Rightmost derivation
Solution: The derivation to get the string id + id * id is shown below.
Now, let us see “What is rightmost derivation?”
E  E+E
 id + E Definition: The process of obtaining a string of terminals from a sequence of
 id + E * E replacements such that only right most non-terminal is replaced at each and every step is
 id + id * E called rightmost derivation.
 id + id * id
For example, consider the following grammar:
Thus, the above sequence of steps can also be written as:

E  id + id * id E → E+E
E → E*E
which indicates that the string id + id * id is obtained in one or more steps by applying E → (E)
various productions. E → id
Now, let us see “What are the two types of derivations?” The two types of derivations The rightmost derivation for the string id + id * id can be obtained as shown below:
are:
 Leftmost derivation E  E+E
 Rightmost derivation
rm

 E+E*E
2.3.1 Leftmost derivation  E + E * id
 E + id * id
Now, let us see “What is leftmost derivation?”  id + id * id
  Systematic approach to Compiler Design - 2.5 2.6  Syntax Analyzer

2.4 Sentence 2.4.2 Right sentential form

Now, let us see “What is a sentence?” Now, let us see “What is right sentential form?”

Definition: Let G = (V, T, P, S) be a CFG. Any string w  (V T)* which is derivable Definition: If there is a derivation of the form S α, where at each step in the derivation
from the start symbol S such that S w is called a sentence or sentential form of G. For process only a right most non-terminal is replaced, then α is called right-sentential form
example, consider the derivation: of G.
E  E+E For example, consider the following grammar and its rightmost derivation:
 id + E
 id + E * E Grammar rightmost derivation
 id + id * E
E  E+E
 id + id * id E → E+E rm
E → E*E  E+E*E
The final string of terminals i.e., id + id * id is called sentence of the grammar. →
E (E)  E + E * id
E → id  E + id * id
Now, let us see “What the different sentential forms?” The two sentential forms are:
 Left sentential form  id + id * id
 Right sentential form In the above rightmost derivation, the string of grammar symbols obtained in each step
such as:
2.4.1 Left sentential form { E + E, E + E * E, E + E * id, E + id * id, id + id * id }
Now, let us see “What is left sentential form?” are various right-sentential forms of the given grammar.

Definition: If there is a derivation of the form S α, where at each step in the derivation Example 2.2: Obtain the leftmost derivation for the string aaabbabbba using the
process only a left most variable is replaced, then α is called left-sentential form of G. following grammar.
S → aB| bA
For example, consider the following grammar and its leftmost derivation: A → aS | bAA | a
B → bS | aBB | b
Grammar leftmost derivation
The leftmost derivation for the string aaabbabbba is shown below:
E  E+E
E → E+E lm S lm aB (Applying S  aB)
→ 
E E*E  id + E
→  aaBB (Applying B  aBB)
E (E)  id + E * E
E → id  aaaBBB (Applying B  aBB)
 id + id * E
 aaabBB (Applying B  b)
 id + id * id
 aaabbB (Applying B  b)
In the above leftmost derivation, the string of grammar symbols obtained in each step  aaabbaBB (Applying B  aBB)
such as:  aaabbabB (Applying B  b)
{ E + E, id + E, id + E * E, id + id * E, id + id * id }  aaabbabbS (Applying B  bS)
are various left-sentential forms of the given grammar.  aaabbabbbA (Applying S  bA)
 aaabbabbba (Applying A a)
  Systematic approach to Compiler Design - 2.7 2.8  Syntax Analyzer

2.4.3 Language Now, let us see “What is the yield of the tree?” The yield of a tree can be formally
defined as follows:
Now, let us see “What is the language generated by grammar?” The formal definition of
the language accepted by a grammar is defined as shown below. Definition: The yield of a tree is the string of symbols obtained by only reading the
leaves of the tree from left to right without considering the -symbols. The yield of the
Definition: Let G = (V, T, P, S) be a grammar. The language L(G) generated by the tree is derived always from the root and the yield of the tree is always a terminal string.
grammar G is
L(G) = {w | S w and w  T*} For example, consider the derivation tree (or parse tree) shown below:

i.e., w is a string of terminals obtained from the start symbol S by applying various E
productions.
E + E
For example, for the grammar A → a | aA the various strings that are generated are a, aa, E
aaa, ……and so on. id * E
id id
So, L = { a, aa, aaa, aaaa, …….}
If we read only the terminal symbols in the above parse tree from left to right we get id +
2.4.4 Derivation Tree (Parse tree) id * id and id + id * id is the yield of the given parse tree.

The derivation can be shown in the form of a tree. Such trees are called derivation or 2.5 Ambiguous grammar
parse trees. The leftmost derivation as well as the right most derivation can be
In this section, let us see “What is ambiguous grammar?”
represented using derivation trees. Now, let us see “What is derivation tree or parse tree?”
The derivation tree can be defined as shown below. Definition: Let G = (V, T, P, S) be a context free grammar. A grammar G is ambiguous
Definition: Let G = (V, T, P, S) be a CFG. The tree is derivation tree (parse tree) with if and only if there exists at least one string w  T* for which two or more left
the following properties. derivations exist or two or more right derivations exist. That is, the ambiguous grammar
1. The root has the label S. has two or more meanings or interpretations.
Since, for every derivation a parse tree exist, the ambiguous grammar can also be
2. Every vertex has a label which is in (V U T U ).
defined as the one which has two or more different parse trees for the string w derived
3. Every leaf node has label from T and an interior vertex has a label from V.
from start symbol S.
4. If a vertex is labeled A and if X1, X2, X3, …. Xn are all children of A from left,
then A  X1X2X3….Xn must be a production in P. Example 2.3: Consider the following grammar from which an arithmetic expression can
For example, consider the following grammar and its rightmost derivation along with be obtained:
parse tree: E → E+E
E → E-E
Grammar rightmost derivation Parse tree E → E*E
E  E+E E E → E/E
E → E+E rm
E → (E) | I
E → E*E  E+E*E E + E I → id
E → (E)  E + E * id
E → id  E + id * id E * Show that the grammar is ambiguous.
id E
 id + id * id
id id
  Systematic approach to Compiler Design - 2.9 2.10  Syntax Analyzer

Solution: The sentence id + id * id can be obtained from leftmost derivation in two Leftmost derivation Parse tree
ways as shown below. S
S  iCtSeS
E  E+E E  E*E  ibtSeS i C t S e S
 id + E  E+E*E  ibtiCtSeS
 id + E * E  id + E * E  ibtibtSeS
b ii C t S a
 id + id * E  id + id * E  ibtibtaeS
 id + id * id  id + id * id  ibtibtaea
b a
The corresponding derivation trees for the two leftmost derivations are shown below:
Since there are two different parse trees for the string „ibtibtaea‟ by applying leftmost
E E derivation the given grammar is ambiguous. The grammar has two interpretations or two
meanings.
E + E E * E
2.6 Eliminating ambiguity
E * E E + E id
id Some grammars that are ambiguous can be converted into unambiguous grammars. This
id id id can be done using two methods:
id
 Dis-ambiguity rule
Since the two parse trees are different for the same sentence id + id * id by applying  Using precedence and associativity of operators
leftmost derivation, the grammar is ambiguous.
2.6.1 Dis-ambiguity rule

Example 2.4: Is the following grammar ambiguous? (if-statement or if-then-else) We have already seen in the previous problem that the grammar corresponding to if-
statement is ambiguous. This is due to dangling-else. The dangling else problem can be
S → iCtS | iCtSeS | a
eliminated and thus ambiguity of the grammar can also be eliminated.
C → b
Now, let us see “What is dangling else problem?” Consider the following grammar:
The string ibtibtaea can be obtained by applying the leftmost derivation as shown
below along with parse. S → iCtS | iCtSeS | a
Leftmost derivation Parse tree C → b
S
S  iCtS where
 ibtS  i stands for keyword if
 ibtiCtSeS i C t S  C stands for Condition to be satisfied. Here C is a non-terminal
 ibtibtSeS  t stands for keyword then
 ibtibtaeS b i C t S e S  S stands statement for non-terminal
 ibtibtaea  e stands for keyword else
b a a  a stands for other statement
 b stands for other statement
The string ibtibtaea can be obtained again by applying the leftmost derivation but using
different sets of productions as shown below along with parse tree. Since the above grammar is ambiguous, we get two different parse trees for the string
Note: i –if, t –then, e – else , b – other statement, a – other statement ibtibtaea (Look at solution for previous problem for details) as shown below:
  Systematic approach to Compiler Design - 2.11 2.12  Syntax Analyzer
Step 3: The matched statement M and un-matched statement U can obtained using the
S S statement S as shown below:
S→M|U
i C t S i C t S e S
So, the final grammar which is un-ambiguous is shown below:
b i C t S e S b ii a
C t S
S→M|U
b a a M→iCtMeM
b a U→iCtS
Parse tree 1 Parse tree 2 U→iCtMeU
Since there are two parse trees for the same string ibtibtaea the given grammar is
ambiguous. Observe the following points: Observe that the above grammar associates else with closest then and eliminates
 The first parse tree associates else with 2nd if-statement ambiguity from the grammar.
 The second parse tree associates else with first if-statement.
2.6.2. Eliminating ambiguity using precedence and associativity
This ambiguity whether to associate else with first if-statement or second if-statement is
called “dangling else problem”. This method is explained using the following example:

Now, let us see “How dangling else problem can be solved?” The dangling else problem Example 2.6: Convert the following ambiguous grammar into unambiguous grammar
can be solved by constructing unambiguous grammar as shown below: E → E*E|E-E
E → E^E|E/E
Example 2.5: Eliminate ambiguity from the following ambiguous grammar: E → E+E
S → iCtS | iCtSeS | a E → (E) | id
C → b The grammar can be converted into unambiguous grammar using the precedence of
Solution: In all programming languages when if-statements are nested, the first parse tree operators as well as associativity operators as shown below:
is preferred. So, the general rule is “Match each else with closest unmatched then”. This
Step 1: Arrange the operators in increaing order of the precedence along with
rule can be directly incorporated into grammar and ambiguity can be eliminated as shown
associativity as shown below:
below:
Operators Associativity non-terminal used
Step 1: The matched statement M is an if-else statement where the statement S before +,– LEFT E
else and after else keyword is matched. This can be expressed as: *, / LEFT T
M→iCtMeM ^ RIGHT P
Since there are three levels of precedence, we associate three non-terminals: E, T and P.
Step 2: An unmatched statement U is the one consisting of:
Also an extra non-terminal F, generating basic units in an arithmetic expression.
a) simple if-statement where the statement S is matched statement or unmatched
statement. The equivalent production is:
Step 2: The basic units in expression are id (identifier) and parenthesized expressions.
U→iCtS
The production corresponding to this can be written as:
b) if-else statement where the statement before else is matched and statement after
else is unmatched. The equivalent production is:
F → (E) | id
U→iCtMeU
  Systematic approach to Compiler Design - 2.13 2.14  Syntax Analyzer

Step 3: The next highest priority operator is ^ and it is right associative. So, the Step 1: Arrange the operators in increasing order of the precedence along with
production must start from the non-terminal P and it should have right recursion as shown associativity as shown below:
below:
P→F^P|F Precedence Operators Associativity non-terminal used
(lowest) *,– LEFT E
Step 4: The next highest priority operators are * and / and they are left associative. So, ^ LEFT P
the production must start from the non-terminal T and it should have left recursion as (highest) /, + RIGHT T
shown below:
Since there are three levels of precedence we associate three non-terminals: E, P and T.
T→T*P|T/P|P Also use an extra non-terminal F generating basic units in an arithmetic expression.

Step 5: The next highest priority operators are + and – and they are left associative. So, Step 2: The basic units in expression are id (identifier) and parenthesized expressions.
the production must start from the non-terminal E and it should have left recursion as The production corresponding to this can be written as:
shown below:
F → (E) | id
E→E+T|E–T |T
Step 3: The next highest priority operators are + and / and they are right associative. So,
Step 6: The final grammar which is unambiguous can be written as shown below: the production must start from the non-terminal T and it should be right recursive in RHS
of the production as shown below:
E→E+T|E–T |T
T→T*P|T/P|P T→F+T|F/T|F
P→F^P|F
F → (E) | id Step 4: The next highest priority operator is ^ and it is left associative. So, the production
must start from the non-terminal P and it should be left recursive in RHS of the
production as shown below:
Example 2.7: Convert the following ambiguous grammar into unambiguous grammar
P→P^T|T
E→E+E
E→E–E Step 5: The next highest priority operators are * and – and they are left associative. So,
E→E^E the production must start from the non-terminal E and it should be left recursive in RHS
E→E*E of the production as shown below:
E→E/E
E → (E) | id E→E+P|E–P |P
by considering * and – operators lowest priority and they are left associative, / and + Step 6: The final grammar which is unambiguous can be written as shown below:
operators have the highest priority and are right associative and ^ operator has precedence
in between and it is left associative. E→E+P|E–P |P
P→P^T|T
The grammar can be converted into unambiguous grammar using the precedence of T→F+T|F/T|F
operators as well as associativity operators as shown below: F → (E) | id
  Systematic approach to Compiler Design - 2.15 2.16  Syntax Analyzer

2.7 The Role of the Parser 2.7.1 Error Recovery strategies

First, let us see “What is parsing?” The following activities are performed whenever errors are detected by the parser:
Definition: Parsing is the process of getting tokens from the lexical analyzer and obtains  Detect the syntax errors accurately and produce appropriate error messages so that the
a derivation for the sequence of tokens and builds a parse tree. Thus, if the program is programmer can correct the program.
syntactically correct, the parse tree is generated. If a derivation for the sequence of tokens  It has to recover from the errors quickly and detect subsequent errors in the program.
does not exist i.e., if the program is syntactically wrong, it results in syntax error and the  Error handler should take all the actions very fast and should not slowdown the
parser displays the appropriate error messages. The parse trees are very important in compilation process.
figuring out the meaning of a program or part of the program. The parse tree is also called
syntax tree. Parser also called syntax analyzer is the one which does parsing. Now, let us see “What are error recovery strategies of the parser (or syntax analyzer)?”
The various error recovery techniques are:
The block diagram that shows the interaction of parser with other modules and phases is  Panic mode recovery
shown below:  Error productions
 Phrase level recovery
Symbol
 Global correction
table
Panic Mode Recovery: It is the simplest and most popular error recovery method. When
token an error is detected, the parser discards symbols one at a time until next valid token
source Lexical Syntax parse Rest of (called synchronizing token) is found. The typical synchronizing tokens are:
program analyzer
get
analyzer tree phases  statement terminators such as semicolon
next token  Expression terminators such as \n

It often skips a considerable amount of input without checking it for additional errors.
Error Once the synchronizing token found, the parser will continue from that point onwards to
Handler identify the subsequent errors. In situations where multiple errors are in the same
statement, this method is not useful.
The role of the parser or the various activities that are performed by the parser are shown
below: For example, consider the erroneous expression:
 Parser reads sequence of tokens from the lexical analyzer
(5 ** 2) +8
 The parser checks whether the tokens obtained from lexical analyzer can be
successfully generated. This is done by obtaining a derivation for the sequence of  The parser scans the input from left to right and finds no mistake after reading (, 5
tokens and builds the parse tree. and *.
 If a derivation is obtained using the sequence of tokens it indicates that program is  After reading the second *, it knows that no expression has consecutive * operators
syntactically correct and the parse tree is generated. and it displays an error “Extra * in the input”
 If a derivation is not obtained using the sequence of tokens it indicates that program is  Now, it has to recover from the error. In panic mode recovery, it skips all input
syntactically wrong and the parse tree is not generated. Now, the parser reports symbols till the next integer 2 is encountered. Here, 2 is the synchronizing token.
appropriate error messages clearly and accurately along with line numbers  Thus, error is detected and recovered from the error in panic mode recovery
 Parser also recovers from each error quickly so that subsequent errors can be detected
and displayed so that the user can correct the programs.
  Systematic approach to Compiler Design - 2.17 2.18  Syntax Analyzer

Error Productions: In this type of error recovery strategy, we introduce error The parsers are classified as shown below:
productions. The error productions specify commonly known mistakes in the grammar.
When we implement the parser, when an error production is used, it displays the Recursive descent parser with backtracking
appropriate error message. For example, consider the expression 10x. Mathematically it Top down parser
means multiply 10 with x. But, in a programming language we should write 10*x. Such Recursive descent parser with no-backtracking
errors can be identified very easily by incorporating error productions and within the (Predictive parser)
body of the function, display appropriate error messages.
SLR (Simple LR)
Disadvantages Bottom up parser LALR (Look Ahead LR)
 Can resolve many errors, but not all potential errors.
Canonical LR
 The introduction of error productions will complicate the grammar
2.8 Top-down Parsing
Phrase Level Recovery: It is an error correcting method. On discovering an error, a
parser may perform local correction on the remaining input. This is normally done by Now, let us see “What is top down parser?”
inserting, deleting or/and replacing the input and enable the parser to continue parsing.
Definition: The process of constructing a parse tree for the string of tokens (obtained
Ex: Replacing a comma by a semicolon, deleting an extraneous semicolon, or inserting a from the lexical analyzer) from top i.e., starting from the root node and creating the nodes
missing semicolon. of the parse tree in preorder in depth-first-search manner is called top down parsing
technique. Thus, top-down parsing can be viewed as an attempt to find a leftmost
Disadvantages derivation for an input string and constructing the parse tree for that derivation. The
 Very difficult to implement parser that uses this approach is called top down parser. Since the parsing starts from top
 Slows down the parsing of correct programs (i.e., root) down to the leaves, it is called top down parser.
 Proper care must be taken while choosing replacements as they may lead to infinite
loops.
Example 2.8: Show the top-down parsing process for the string id + id * id for the
Global Correction: This is also one of the error correction strategies. The various points grammar
to remember in this error correction method are: E→E+E
 These methods replace incorrect input with correct input using least-cost-correction E→E*E
algorithms. E → (E)
 These algorithms take an incorrect input string x and grammar G, and find a parse E → id
tree for a related string y, such that the number of insertions, deletions and changes of
tokens required to transform x into y is as small as possible. Solution: The string id + id * id can be obtained by the grammar by applying leftmost
 These methods are costly to implement in terms of time and space and hence are only derivation as shown below:
of theoretical interest.
E  E+E (fig a) step 1
lm
2.7.2 Parsing techniques  id + E (fig b) step 2
 id + E * E (fig c) step 3
In this section, let us see “What are the different types of parsers?”
 id + id * E (fig d) step 4
 id + id * id (fig e) step 5
  Systematic approach to Compiler Design - 2.19 2.20  Syntax Analyzer

The above derivation can be written in the form of a parse tree from the start symbol Definition: A recursive descent parser is a top down parser in which parse tree is
using top-down approach as shown below: constructed from the top starting from root node and selecting the productions from left
to right (if two or more alternative productions exists). For every non-terminal there
exists a recursive procedure and the right hand of the production of that non-terminal is
E root E root implemented as the body of the procedure. The sequence of terminals and non-terminals
E root
on the right hand side of the production correspond to matching with input symbols and
calls to other procedures while selecting the alternate production is implemented using
E + E E + E switch or if-statements. Thus, the syntax or structure of the resulting program closely
mirrors that of the grammar it recognizes.
id
For example, the procedure for the production A → α can be written as shown below:
(Fig. a) (Fig. b) (Fig. c)

E root E root E root procedure A () // Function header

{
……
E + E E + E E + E …… body of the function
……
id E * E id E * E id E * E }

Observe the following points:

id id id
 For the variable A on the left hand side of the production, we write the function
(Fig. d) (Fig. e) (Fig. f) header
 For the string of grammar symbols denoted by α on the right hand side of the
production corresponds to the function body.
Initial: Start from root node E  Thus, for every non-terminal in the grammar we write the procedure or function as in
previous two steps.
Step 1: Replace E with E + E using E → E + E. It is shown in figure (b)

Step 2: Replace E with id using E → id. It is shown in figure (c). Working: The recursive descent parser works as shown below:
 Execution starts from the function that corresponds to the start symbol of the
Step 3: Replace E with E * E using E → E * E. It is shown in figure (d). grammar
 If the body of the function scans the entire input string, then parsing is successful.
Step 4: Replace E with id using E → id. It is shown in figure (e). Otherwise, the input string is not proper and parsing halts.
 Each non-terminal is associated with a parsing procedure or a function that can
Step 5: Replace E with id using E → id. It is shown in figure (f). recognize any sequence of tokens generated by that non-terminal

2.8.1 Recursive descent parser  Within the function, both non-terminals and terminals are matched
 To match the non-terminal A, we call the function/procedure A which corresponds to
Now, let us see “What is recursive descent parser?” non-terminal A. These calls may be recursive and hence the name recursive descent
parser.
  Systematic approach to Compiler Design - 2.21 2.22  Syntax Analyzer

 To match the terminal a, we compare current input symbol with a. If there is match, it
is syntactically correct and we increment the input pointer and get the next token // function corresponding to the production T → F
 If the current input symbol is not a, it is syntactically wrong and appropriate error procedure T()
message is displayed {
F();
 Some error correction may be done to recover from each error quickly so that }
subsequent errors can be detected and displayed so that the user can correct the
programs. // function corresponding to the production F → (E) | id
// F→( E ) | id
The general procedure for a recursive-descent parsing that uses top-down parser is shown procedure F()
below: {
if (input_symbol == „(„ )
Example 2.9: Algorithm for recursive descent parser (backtracking is not supported)
advance input pointer
procedure A() // A → X1X2X3…….Xk E();
{ if (input_symbol == „)‟)
for i = 1 to k do advance input pointer
if (Xi is a non-terminal) else
call procedure Xi(); error()
else if (Xi is same as current input symbol a) end if
advance the input to the next symbol
else else if (input_symbol == id)
error(); advance input pointer
end for else
} error();
end if
Now, let us write the recursive parsers for some of the grammars. }

Now, let us see “What are the different types of recursive descent parsers?” The recursive
Example 2.10: Write the recursive descent parser for the following grammar descent parser can be classified into two types:
E→T  Recursive descent parser with backtracking
T→F  Recursive descent parser without backtracking (predictive parser)
F → (E) | id
2.8.2 Recursive descent parser with backtracking
// function corresponding to the production E → T
procedure E() Now, let us see “What is the need for backtracking in recursive descent parser?” The
{ backtracking is necessary for the following reasons:
T();  During parsing, the productions are applied one by one. But, if two or more
} alternative productions are there, they are applied in order from left to right one at a
time.
  Systematic approach to Compiler Design - 2.23 2.24  Syntax Analyzer

 When a particular production applied fails to expand the non-terminal properly, we Step 3: Since two productions are there from A, the first production A → ab is selected
have to apply the alternate production. Before trying alternate production, it is and non-terminal A is expanded as shown below:
necessary undo the activities done using the current production. This is possibly only
using backtracking. S root S root
But, the recursive descent parsers with backtracking are not frequently used. So, we just
c A d c A d b does not
concentrate on how they work with example.
match with d
Example 2.11: Show the steps involved in recursive descent parser with backtracking for a b a b
the input string cad for the following grammar match(a) and
c a d c a d
S → cAd ↑ increment i/p ↑
A → ab | a pointer
input pointer input pointer
Solution: The three parts that are used while parsing the string are:
Step 4: Observe that by selecting A → ab the input string is not matched. So, we have to
Given grammar String to be parsed Parse tree reset the pointer to input symbol a (so as to get the parse tree shown in step 2). This is
S (root) done using backtracking and is shown in (fig a). After backtracking try expanding A
S → cAd cad
using the second production A → a and then proceed comparing as shown in (fig b).
A → ab | a ↑
input pointer
S root S root
Observe that input-pointer points to the next character to be read.
c A d c A d match(a) and
Step 1: The only unexplored node is S and we apply the production S → cAd to expand increment i/p
the non-terminal S as shown below: cad a
pointer
S root ↑ cad
input pointer ↑
c input pointer
A d
match(c) and increment i/p pointer (Fig a.)
c ad
↑ Step 5: Now, the next symbol d in grammar is compared with d in the input and they
input pointer match. Finally, we halt and announce successful completion of parsing.

Step 2: Now, the next node to be expanded is A and input pointer points to a as shown Now, let us see “For what type of grammars recursive descent parser cannot be
below: constructed? What is the solution?”
S root
The recursive descent parser cannot be constructed for a grammars having:
c A d  Ambiguity. The solution is to eliminate ambiguity from the grammar.
 Left recursion. The solution is to eliminate left recursion from the grammar.
cad  Two or more alternatives having a common prefix. The solution is to left factor the
↑ grammar.
input pointer
  Systematic approach to Compiler Design - 2.25 2.26  Syntax Analyzer

2.8.3 Left recursion In the above derivation, note that in the partial derivation to get the string E + T, the first
symbol is E which is same as the symbol from which the derivation started. But, the
Now, let us see “What is left recursion? What problems are encountered if a recursive string E+T is obtained from E by applying two or more productions. So, the given
descent parser is constructed for a grammar having left recursion?” grammar even though it is not having immediate left recursion, it has indirect left
recursion and hence the grammar is left recursive.
Definition: A grammar G is said to be left recursive if it has non-terminal A such that
there is a derivation of the form:

Now, let us write the recursive descent parser for the grammar having left recursion.
A  A (Obtained by applying one or more productions)
Example 2.12: Consider the production E→ E + T . Write the recursive descent parser.
where  is string of terminals and non-terminals. That is, whenever the first symbol in a
partial derivation is same as the symbol from which this partial derivation is obtained, Solution: The recursive descent parser for the production E→ E + T can be written as
then the grammar is said to be left-recursive grammar. A grammar may have: shown below:
 immediate left recursion
 indirect left recursion // function corresponding to the production E → E + T
procedure E()
Immediate left recursion: A grammar G is said to have immediate left recursion if it has a {
production of the form: E();
A → A
For example, consider the following grammar: if (input_symbol = „+‟)
advance input pointer
E→E+T|T else
T→T*F|F error
F → (E) | id end if
In the above grammar consider the first two productions: T();
E→E+T }
T→T*F
Observe that in the above two productions, the first symbol on the right hand side of the Now, let us see “What is the problem in constructing recursive descent parser for the
production is same as the symbol on the left hand side of the production. So, the given grammar having left recursion?” Observe the following points (with respect to the above
grammar has immediate left recursion in two productions. procedure which has left recursion)
 When a procedure is invoked, the parameter values along with return address will be
Indirect left recursion: A left recursion involving derivations of two or more steps so that pushed on to the stack and hence stack size decreases
the first symbol on the right hand side of the partial derivation is same as the symbol  The procedure E() is called recursively infinitely without consuming any input and
from which the derivation started is called indirect left recursion. For example, consider hence the size of the stack grows very fast and stack will be full soon.
the following grammar:  Since there is no space left on the stack to push parameter values and return address,
E→T the system crashes.
T→F  So. the recursive descent parser that is built using left-recursive grammar can cause a
F → E + T | id parser to go into an infinite loop eventually crashing the system and hence the left
recursive grammar is not suitable for recursive descent parser. Hence, we have to
Consider the following derivation: eliminate left recursion from the grammar and then parse the string.
E  T F  E+T
  Systematic approach to Compiler Design - 2.27 2.28  Syntax Analyzer

2.8.4 Procedure to eliminate left recursion

Example 2.13: Eliminate left recursion from the following grammar
Consider the production of the form: E → E +T | T
A → A | β T→ T*F|F
F → (E) | id
where β do not start with A. Note that the above grammar has left recursion. Now, let us
see how to eliminate left recursion. The various strings that can be generated by above
Solution: The given grammar is shown below:
grammar are shown below:
st nd rd th E → E +T | T
Derivation: 1 2 3 4 and so on. T→ T*F|F
Aβ A A A A A A F → (E) | id
β  A  A
Since the first symbol on the right hand side of E-production and T-production is same as
 β   A
the symbol on the left hand side of the production, the grammar has immediate left
 β 
recursion. Now, the immediate left recursion can be eliminated from the grammar as
shown below:
{ β, β , β , β ……..}
Observe from above derivations that the language L consists of β followed zero or more Left recursive productions Right recursive productions
α‟s. The same language can be represented and generated using different grammar as A → A1|A2|A3|……|An|β1 | β2| β3| ……..| βm A→ β1A' | β2A' | β3A'| ……..| βm A'
shown below:
A'→ 1A'| 2A'| 3A'|……|nA'| ϵ
L = { β i | i  0}
↓ ↓
1) E → E + T | T E → TE'
A → β A' where A' should generate zero or more α‟s
↓ ↓ ↓ ↓ E'→ +TE' | ϵ
From A' we can get zero or more α‟s using the following productions:
A → A 1 | β1
A' → ϵ | αA'
So the final grammar that generate β followed by zero or more α‟s which do not have 2) T → T * F | F T → FT'
left recursion is shown below: ↓ ↓ ↓ ↓ T'→ *FT' | ϵ
A → β A' A → A 1 | β1
A' → ϵ | αA'
3) F → (E) | id F → (E) | id
Thus, the grammar which has left recursion can be written in the form of another
grammar that does not have left recursion as shown below: The final grammar obtained after eliminating left recursion can be written as shown
below:
Left recursive grammar Right recursive grammar
A → A | β A → β A' E → TE'
A'→ ϵ | αA' E1→ +TE' | ϵ
In general, T → FT'
A → A1|A2|A3|……|An|β1 | β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βm A' T1→ *FT' | ϵ
F → (E) | id
A'→1A'| 2A'|3A'|……|nA'| ϵ
  Systematic approach to Compiler Design - 2.29 2.30  Syntax Analyzer

Now, we can write the recursive descent parser for the above grammar which is obtained
after eliminating left recursion.
// function corresponding to the production: T' → * F T'| ϵ
Example 2.14: Write the recursive descent parser for the following grammar: procedure TDASH()
E → TE' {
E'→ +TE' | ϵ if ( inputsymbol == „*‟)
{
T → FT' advance input pointer
T'→ *FT' | ϵ F();
F → (E) | id TDASH();
}
The recursive descent parser for the above grammar is shown below. Note that for each }
non-terminal there is a procedure and the right hand side of the production is // function corresponding to the production: F → ( E ) | id
implemented as the body of the procedure as shown below: procedure F()
{
// function corresponding to the production: E → T E' if ( inputsymbol == „(„)
procedure E() {
{ advance input pointer
T(); E();
EDASH(); if ( inputsymbol == „)‟)
} advance input pointer
else error();
// function corresponding to the production: E' → + T E' |  }
procedure EDASH() else
{ {
if ( inputsymbol == „+‟) if (inputsymbol == id )
{ advance input pointer
Advance input pointer else error();
T(); }
EDASH(); }
}
} Example 2.15: Obtain top-down parse for the string id+id*id for the following grammar
E → TE'
E' → + TE' | 
// function corresponding to the production: T → F T' T → FT'
procedure T()
T' → *FT' | 
{
F(); F → (E) | id
TDASH(); The top-down parse for the string id+id*id for the above grammar can be written as
} shown below:
  Systematic approach to Compiler Design - 2.31 2.32  Syntax Analyzer

E lm E lm E Step 2: Consider the production: A → Ac | Sd | ϵ. Replacing the non-terminal S by the

production S → Aa | b we get following A-production:
T E1 T E1 A → Ac | Aad | bd | ϵ
lm E lm E lm F E T1
Step 3: Now, the grammar obtained after eliminating indirect left recursion is shown
T E1 T E1 T E1 below:
S → Aa | b
F T1 F T1 F T1 + T E1 A → Ac | Aad | bd | ϵ
id id ϵ id ϵ Now, immediate left recursion can be eliminated as shown below:

Left recursive productions Right recursive productions

lm E lm E lm E
A → A1|A2|A3|……|An|β1 | β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βm A'
T E1 T E1 T E1 A'→1A'| 2A'|3A'|……|nA'| ϵ
1 1 1 1 1 1
F T + T E F T + T E F T + T E 1) S → Aa | b S → Aa | b
id ϵ F T 1 id ϵ F T1 id ϵ F T1

id id * F T1 2) A → A c | A ad | bd | ϵ A → bd A'| ϵ A'
↓ ↓ ↓ ↓ ↓ A'→ cA'| adA'|ϵ
lm E lm E lm E A → A 1| A 2 | β1 | β2

T E1 T E1 T E1 So, the final grammar obtained after eliminating left recursion is shown below:
1 1 1 1 1 1
F T + T E F T + T E F T + T E S → Aa | b S → Aa | b
id ϵ F T 1 id ϵ F T 1 id ϵ F T ϵ
1
A → bd A'| A'
A → bd A'| ϵ A' can be written as
1 1 1
id * F T id * F T id * F T
A'→ cA'| adA'|ϵ A'→ cA'| adA'|ϵ
id id ϵ id ϵ
Now, let us “Write the algorithm to eliminate left recursion” The algorithm to eliminate
Example 2.16: Eliminate left recursion from the following grammar:
left recursion is shown below:
S → Aa | b
A → Ac | Sd | ϵ
Example 2.17: Algorithm to eliminate left recursion (including indirect left recursion)
Solution: Left recursion can be eliminated as shown below:
Input : Grammar G without ϵ-productions and with no cycles
Step 1: The S-production does not have immediate left recursion. So, let us not consider
Output: Grammar without left recursion. It may have ϵ-productions
the production S → Aa | b
Arrange the non-terminals in the order A1, A2, A3,……..An
  Systematic approach to Compiler Design - 2.33 2.34  Syntax Analyzer

for i = 1 to n do  The two B-productions have a common prefix “b” on the right side of the production.
for j = 1 to i-1 do  Since common prefix is present in both A-productions and B-productions, it is not
Let Aj → β1 | β2 | β3 |….. βk left-factored grammar.
Replace Ai → Ajα by Ai → β1α | β2α | β3α |….. βkα
end for Note: If two or more productions starting from same non-terminal have a common prefix,
Eliminate immediate left recursion among Ai productions the grammar is not left-factored.
end for
Now, let us see “What is the use of left factoring?” Left factoring is must for top down
2.8.5 Left factoring parser such as recursive descent parser with backtracking or predictive parser which is
also recursive descent parser without backtracking. This is because, if A-production has
Now, let us see “What is left factoring? What is the need for left factoring?” two or more alternate productions and they have a common prefix, then the parser has
some confusion in selecting the appropriate production for expanding the non-terminal A
Definition: A grammar in which two or more productions from a non-terminal A do not
have a common prefix of symbols on the right hand side of the A-productions is called Ex 1: Consider the following grammar that recognizes the if-statement:
left factored grammar. The left-factored grammar is suitable for top-down parser such as
recursive descent parser with or without backtracking. S → if E then S else S | if E then S

Ex 1: The grammar to generate string consisting of at least one „a‟ followed by at least Observe the following points:
one „b‟ can be written as shown below:  Both productions starts with keyword if.
S → aAbB  So, when we get the input „if‟ from the lexical analyzer, we cannot tell whether to use
A→ aA | ϵ Left factored grammar the first production or to use the second production to expand the non-terminal S.
B → bB | ϵ  So, we have to transform the grammar so that they do not have any common prefix.
That is, left factoring is must for parsing using top-down parser.
Observe the following points:
 The S-production has only one production and it cannot have common prefix on the Now, the question is “How to do left factoring?” The left-factoring can be done as
right side of the production. shown below:
 The two A-productions do not have any common prefix on the right side.
 Finally two B-productions do not have any common prefix on the right side of that 1) Consider two A-productions with common prefix α:
production A → αβ1| αβ2

Ex 2: The grammar that generates string consisting of at least one „a‟ followed by at least 2) Let the input begins with string derived from α. Since α is the common prefix, we
one „b‟ can also be written as shown below: retain α and we replace either β1 or β2 by the non-terminal A'. So, we can write the
above production as:
S → AB
A→ aA | a Non Left factored grammar A → α A'
B → bB | b
where A' can produce either β1 or β2 using the production:
Observe the following points:
A' → β1| β2
 The S-production has only one production and it is not having common prefix on the
right side of the production.
 The two A-productions have a common prefix “a” on the right side of the production.
  Systematic approach to Compiler Design - 2.35 2.36  Syntax Analyzer

Now, after seeing the input derived from α, we can expand A' either to β1 or to β2. So,
the given grammar is converted into left-factored grammar as shown below: Example 2.19: Do the left-factoring for the following grammar:
S → iCtS | iCtSeS | a
A → αβ1| αβ2 A → α A' C → b
A' → β1| β2
Solution: The given grammar is shown below:

Non left-factored grammar Left-factored grammar S → iCtS | iCtSeS | a

C → b
Now, let us “Write the algorithm for doing left-factoring” The algorithm for doing left-
factoring is shown below: Since S-production has common prefix iCtS in more than one production, left factoring is
necessary. Left factoring the above grammar can be done using the algorithm shown
Example 2.18: The algorithm for left-factoring below:

Algorithm LEFT_FACTOR(G) Given productions Left-factored productions

A→ α A' | γ
Input: Grammar G A → αβ1 | αβ2 | αβ3 |….. αβn | γ A'→ β1 | β2 | β3 |….. βn

Output: An equivalent left-factored grammar 1) S → iCtS ϵ | iCtS eS | a S → iCtSS' | a

Method: The following procedure is used: A→ α β1 | α β2 | γ S'→ ϵ | eS

1) For each non-terminal A, find the longest prefix α which is common to two or more 2) C → b C→ b
of its alternatives.
So, the final grammar which is obtained after doing left-factoring is shown below:
2) If there is a production of the form:
S → iCtSS' | a
A → αβ1 | αβ2 | αβ3 |….. αβn | γ
S'→ ϵ | eS
where γ do not start with α, then the above A-production can be written as shown C→ b
below:

A→ α A' | γ 2.8.6 Problems with top down parser

A'→ β1 | β2 | β3 |….. βn Now, let us “Briefly explain the problems associated with top-down parser?” (JUY-
AUG-2009) The various problems associated with top down parser are:
Here, A' is a new non-terminal. Ambiguity in the grammar

3) Repeatedly apply the transformation in step 2 as long as two alternatives for a non- Left recursion
terminal have a common prefix Non-left factored grammar

4) Return the final grammar which is left-factored Backtracking

  Systematic approach to Compiler Design - 2.37 2.38  Syntax Analyzer

 Ambiguity in the grammar: A grammar having two or more left most derivations or A grammar in which two or more productions from every non-terminal A do not have
two or more right most derivations is called ambiguous grammar. For example, the a common prefix of symbols on the right hand side of the A-productions is called left
following grammar is ambiguous: factored grammar. (Refer previous section for doing left-factoring)

E → E + E | E – E | E * E | E / E | ( E ) | id  Backtracking: The backtracking is necessary for top down parser for following
reasons:
The ambiguous grammar is not suitable for top-down parser. So, ambiguity has to be
1) During parsing, the productions are applied one by one. But, if two or more
eliminated from the grammar. (For details refer section 2.6)
alternative productions are there, they are applied in order from left to right one at
a time.
 Left-recursion: A grammar G is said to be left recursive if it has non-terminal A
such that there is a derivation of the form: 2) When a particular production applied fails to expand the non-terminal properly,
 we have to apply the alternate production. Before trying alternate production, it is
A  A (Obtained by applying one or more productions) necessary undo the activities done using the current production. This is possibly
where  is string of terminals and non-terminals. That is, whenever the first symbol only using backtracking.
in a partial derivation is same as the symbol from which this partial derivation is
obtained, then the grammar is said to be left-recursive grammar. For example, Even though backtracking parsers are more powerful than predictive parsers, they are
consider the following grammar: also much slower, requiring exponential time in general and therefore, backtracking
parsers are not suitable for practical compilers.
E→E+T|T
T→T*F|F 2.8.7 Recursive descent parser with no-backtracking (Predictive parser)
F → ( E ) | is
Now, let us see “What is a predictive parser? Explain the working of predictive parser. “
The above grammar is unambiguous but, it is having left recursion and hence, it is not
suitable for top down parser. So, left recursion has to be eliminated (For details refer Definition: Predictive parser is a top down parser. It is an efficient way of implementing
section 2.8.3 and 2.8.4) a recursive descent parser by maintaining a stack explicitly rather than implicitly via
recursive calls. The predictive parser can correctly guess or predict which production to
 Non-left factored grammar: If A-production has two or more alternate productions use if two or more alternative productions are there. This is done using two ways:
and they have a common prefix, then the parser has some confusion in selecting the  By looking at the next few tokens (often called lookahead) it selects the correct
appropriate production for expanding the non-terminal A. For example, consider the production out of two or more alternatives productions and expand the non-terminal
following grammar that recognizes the if-statement:
 Without backtracking. So, there is no question of undoing bad choices using
S → if E then S else S | if E then S backtracking. In fact, bad choices will never occur.

Observe the following points: Since, it can predict which production to use while parsing, it is called predictive parser.
 Both productions starts with keyword if. The predictive parsers accepts a restricted grammar called LL(k) grammars (defined in
 So, when we get the input „if‟ from the lexical analyzer, we cannot tell whether to section 2.10)
use the first production or to use the second production to expand the non-
terminal S. Now, let us see “What are the various components of predictive parser? How it works?”
 So, we have to transform the grammar so that they do not have any common The working of predictive parser can be explained easily by knowing the various
prefix. That is, left factoring is must for parsing using top-down parser. components of the predictive parser. The block diagram showing the various parts of
predictive parser are shown below:
  Systematic approach to Compiler Design - 2.39 2.40  Syntax Analyzer
3) If X is a terminal and ≠ a, that is, the symbol on top of the stack is not equal to the
Input buffer current input symbol, then error()
a1a2a3……an$ The predictive parser has
four components namely: 4) If X is a non-terminal and a is the input symbol, the parser consults the parsing table
 Input M[X, a] which contains either an X production or an error entry. If X → UVW is the
corresponding production, the parser pops X from the stack and pushes U, V and W
 Stack
in reverse order onto the stack.
Output
X Parser program  Parsing table
Y Now, before seeing how the parser parses the string, let us “Explain parsing table and
Z  Parsing program how to use the parsing table? or “What information is given in the predictive parsing
$  Output table?” The parsing table details and how it can be used can be explained using the
Stack example.

Example 2.20: Consider the following grammar and the corresponding predictive parsing
Parsing table table:
 Input : The input buffer contains the string to be parsed and the input string ends E → TE'
GRAMMAR
with „$‟. Here, $ indicates the end of the input. E' → + TE' | 
 Stack : It contains sequence of grammar symbols and „$‟ is placed initially on top of T → FT'
the stack. When $ is on top of the stack, it indicates that stack is empty. T' → *FT' | 
F → (E) | id
 Parsing table : It is a two dimensional array M[A, a] where A is a non-terminal and
lookahead tokens
a is terminal or $. The non-terminal A represent the row index and terminal a
represent the column index. The entry in M[A, a] contains either a production or M  2d parsing table
blank entry. id + * ( ) $
E E → TE' E→ TE'
 Parser : It is a program which takes different actions based on X which is the symbol
on top of the stack and the current input symbol a. E' E' → +TE' E' →  E' → 
T T → FT' T → FT'
 Output: As output, the productions that are used are displayed using which the parse
T' T' → T' → *FT1 T' → T' →
tree can be constructed.
F F → id F → (E)
Working of the parser: The various actions performed by the parser are shown below:
leftmost variable
1) If X = a = $, that is, if the symbol on top of the stack and the current input symbol is
$, then parsing is successful. The various information that we get from the above parsing table are shown below:
 The symbols present in the first column of table M i.e., E, E', T, T' and F represent
2) If X = a ≠ $, that is, if the symbol on top of the stack is same as the current input
left most non-terminals in the derivation. Let us denote the non-terminal in general
symbol but not equal to $, then pop X from the stack and advance the input pointer to
by A
point to next symbol.
  Systematic approach to Compiler Design - 2.41 2.42  Syntax Analyzer
Method: Initially the $ and S are placed on the stack and the input buffer contains input
 The symbols present in the first row such as id, +, *, (, ) and $ represent next input string w ending with $. The algorithm shown below uses the parsing table and produce
tokens obtained from the lexical analyzer. Let us denote the terminal in general by the parse tree. But, instead of displaying the parse tree, we generate the productions that
„a’. are used to generate the parse tree.

 The entry in a particular row A and column „a’ denoted by M[A, a] may be either Let input pointer points to the first symbol of w
blank or a production. This is the production predicted for a variable A when the
input symbol is „a’. Now, parsing is done as shown below: Let X = S be the symbol on top of the stack.

while (X ≠ $) // Stack is not empty

1) If E is on top of the stack and id is the input symbol, the parser consults the
If ( X == a) // stack symbol = input symbol
parsing table M[E, id], gets the production E → TE'. Now, the parser removes E
Pop X from the stack
from the stack and push TE' in reverse order. So, the entry M[E, id] = E → TE'
indicates that in the current leftmost derivation, E is the left most non-terminal. Advance the input pointer.
When the token id is read from the input, we expand the non-terminal E using the else if X is a terminal
production E → TE'.
Error()
2) If E' is on top of the stack and input is „)‟, the parser consults the parsing table else if M[X, a] is blank
M[E', )] and gets the production E' → ϵ. Now, the parser removes E' from the Error()
stack. But, nothing is there on the right side of the production to push. That is, the
else if M[X, a] = X → Y1Y2Y3…….Yk
entry M[E', )] = E' → ϵ indicates that in the current leftmost derivation, E' is the
leftmost non-terminal and it is replaced by ϵ. Thus, only the leftmost variable is Output the production X → Y1Y2Y3…….Yk
replaced at each step when the input symbol (lookahead token) is read from the Remove X from the stack
input buffer which results in leftmost derivation. Thus, we say that predictive
parsing will mimic the leftmost derivation. Push Y1, Y2,Y3,…….Yk in reverse order
endif
3) The entry in row E and column „+‟ is blank. This indicates an error entry and the
Let X = top stack symbol
parser should display appropriate error messages.
end while
Now, the various actions performed by the parser are can be implemented using algorithm. The
complete algorithm to parse the string using predictive parser is shown below:
The initial configuration of the parser

Example 2.21: The predicative parsing algorithm

Stack Input
$S w$
Input: The string w ending with $ (end of the input) and the parsing table Final configuration of parser, if parsing is successful

Output: If w  L(G) i.e., if the input string is generated successfully from the parser, the Stack Input
parse tree using leftmost derivation is constructed. Otherwise, the parser displays error $ $
message.
  Systematic approach to Compiler Design - 2.43 2.44  Syntax Analyzer

$ E' T' F id+id*id$ F → id [Remove F and push id]

Example 2.22: Consider the following grammar and the corresponding predictive
parsing table: $ E' T' id id+id*id$ match(id) [Remove id increment i/p ptr]
E → TE'
GRAMMAR $ E' T' +id*id$ T' →  '
[Remove T from stack]
E' → + TE' | 
T → FT' $ E' +id*id$ E' → +TE' ' '
[Remove E and push +TE in reverse]
T' → *FT' | 
F → (E) | id $ E' T+ +id*id$ match(+) [Remove + increment i/p ptr]

M Parsing Table $ E' T id*id$ T → FT' '

[Remove T and push FT in reverse]
id + * ( ) $
E $ E' T' F id*id$ F → id [Remove F and push id]
E → TE' E→ TE'
E' E1 → +TE' E' →  E' →  $ E' T' id id*id$ match(id) [Remove id and increment i/p ptr]
T T → FT' T → FT'
$ E' T' *id$ T1 → *FT' ' '
[Remove T and push *FT in reverse]
T' T' → T1 → *FT' T' → T' →
F F → id F → (E) $ E' T' F * *id$ match (*) [Remove * increment i/p ptr]

Show the sequence of moves made by the predictive parser for the string id+id*id during parsing. $ E' T' F id$ F → id [Remove F and push id]

Solution: The sequence of moves made by the parser for the string id+id*id is shown $ E' T' id id$ match(id) [Remove id and increment i/p ptr]
below:
$ E' T' $ T' →  '
[Remove T from stack]
id + * ( ) $
E E → TE' E→ TE' $ E' $ E' →  '
[Remove E from stack]

E' E' → +TE' E' →  E' →  $ $ ACCEPT

T T → FT' T → FT'
T' T' → T' → *FT' T' → T' → Since the stack contains $ and the input pointer points to $, the string id+id*id is parsed
successfully.
F F → id F → (E)
2.9 FIRST and FOLLOW
M[E, id] = E → TE'
Stack Input Output Action The predictive parser can be easily constructed once we know FIRST and FOLLOW sets.
These sets of symbols help us to construct the predictive parsing table very easily.
$E id+id*id$ E → T E' '
[Remove E and push TE in reverse]
2.9.1 Computing FIRST symbols
$ E' T id+id*id$ T → F T' '
[Remove T and push FT in reverse]
Now, let us “Define FIRST(α)”
  Systematic approach to Compiler Design - 2.45 2.46  Syntax Analyzer

Definition: FIRST(α) is defined as set of terminals that appear in the beginning of Now, the question is “What is the use of FIRST sets?” The FIRST sets can be used
derivation derived from α. Formally, FIRST(α) is defined as shown below: during predictive parsing while creating the predictive parsing table as shown below:
 Consider the A-production A→ α | β and assume FIRST(α) and FIRST(β) are disjoint
ϵ if α = ϵ Definition 1 i.e., FIRST(α) ∩ FIRST(β) = {} which is an empty set.
FIRST(α) = ϵ if α ϵ Definition 2
 If the input symbol obtained from lexical analyzer is a and if a is in FIRST(α) then
a if α aβ Definition 3
use the production A→ α during parsing.
 If the input symbol obtained from lexical analyzer is b and if b is in FIRST(β) then
Example 2.23: Compute FIRST sets for each non-terminal in the following grammar use the production A→ β during parsing.
E → TE'
E' → + TE' |  Thus, using FIRST sets we can choose what production to use between the two
productions A→ α | β when input symbol is a or b.
T → FT'
T' → *FT' |  Now, let us see “What are the rules to be followed to compute FIRST(X)?” or “What is
F → (E) | id the algorithm to compute FIRST(X)?” The algorithm or the rules to compute FIRST(X)
are shown below:
Solution: The FIRST sets for the given grammar can be computed by obtaining various
derivations as shown below: ALGORITHM FIRST(X)

E  T E' F T' E'  ( E ) T'E' Rule 1: If X → a where a is a terminal, then FIRST(X) ← a

E  T E' F T' E'  id T'E' Rule 2: If X → ϵ, then FIRST(X) ← ϵ

Rule 3: If X → Y1Y2Y3………Yn and if Y1Y2Y3………Yi – 1 ϵ, then
FIRST(X) ← non-ϵ symbols in FIRST(Yi).
FIRST(E) =
FIRST(T) = Rule 4: If X → Y1Y2Y3………Yn and Y1Y2Y3………Yn ϵ, then FIRST(X) ← ϵ
FIRST(F) = { (, id }
Rule 5: If X is a terminal or , ϵ then FIRST(X) ← X
Consider the derivations not used in previous derivation:
E'  + T E' T'  * F T' Now, let us see how FIRST sets are computed by taking some specific examples:
E'  ϵ T'  ϵ
1) Rule 1 is applied if the first symbol on the right hand side of the production is a
terminal. If so, then add only the first symbol.
So, FIRST(E') = {ϵ, + } So, FIRST(T') = { ϵ, * }
 Ex 1: if A → aBC, then FIRST(A) = {a}
Now, the final FIRST sets are written as shown below:  Ex 2: if E → +TE1 then FIRST(E) = {+}
 Ex 3: if A → abc, then FIRST(A) = {a}
E E' T T' F 2) Rule 2 is applied only for ϵ-productions
FIRST (, id ϵ, + (, id ϵ, * (, id  Ex 1: if A → ϵ, then FIRST(A) = { ϵ }
 Ex 2: if E1 → ϵ, then FIRST(E1) = { ϵ }
3) Rule 3 is applied for all productions not considered in first two steps
  Systematic approach to Compiler Design - 2.47 2.48  Syntax Analyzer

Ex : Consider the productions: S A B C

S → ABCd FIRST ϵ, + ϵ, * ϵ, %
A→ ϵ | +B
B→ ϵ | *B
C→ ϵ | %B To compute FIRST(S) consider the production S → ABC and apply rule 3 as shown
below:
FIRST(A), FIRST(B), FIRST(C) are computed using rules 1 and 2 as shown below: a) S → ABC Add non- ϵ symbols of FIRST(A) to FIRST(S)
S A B C
FIRST ϵ, + ϵ, * ϵ, % b) S → A BC Since A ϵ, add non- ϵ symbols of FIRST(B) to FIRST(S)

To compute FIRST(S) consider the production S → ABCd and apply rule 3 as shown c) S → AB C Since AB ϵ, add non-ϵ symbols of FIRST(C) to
below: FIRST(S)
a) S → ABCd Add non- ϵ symbols of FIRST(A) to FIRST(S)
d) S → ABC Since ABC ϵ, add ϵ to FIRST(S)
b) S → A BCd Since A ϵ, add non- ϵ symbols of FIRST(B) to FIRST(S)
So, all the above actions are pictorially represented as shown below:
c) S → AB Cd Since AB ϵ, add non-ϵ symbols of FIRST(C) to
FIRST(S) S A B C
FIRST %, *, +, ϵ ϵ, + ϵ, * ϵ, %
d) S → ABC d Since ABC ϵ, add non-ϵ symbols of FIRST(d) to
FIRST(S) step (d)
So, all the above actions are pictorially represented as shown below: step (a)
step (b)
S A B C step (c)
FIRST %, *, +, d ϵ, + ϵ, * ϵ, %

step (d) 5) Rule 5 is applied only for terminals.

 Ex 1: + is terminal. So, FIRST(+) = { + }
step (a)  Ex 2: a is a terminal. So, FIRST(a) = {a}
step (b)
 Ex 3: id is a terminal. So, FIRST(id) = {id}
step (c)

4) Rule 4 is applied for all productions whose RHS gives ϵ Note: FIRST(X1X2X3………Xn) can be computed as follows :
1) FIRST(X1X2X3………Xn) ← Non- ϵ symbols of FIRST(X1)
Ex : Consider the productions: 2) if FIRST(X1) = ϵ, then FIRST(X1X2X3………Xn) ← FIRST(X2) - ϵ
S → ABC 3) if FIRST(X1) and FIRST(X2) = ϵ then FIRST(X1X2X3………Xn) ← FIRST(X3) - ϵ
A→ ϵ | +B ……..
B→ ϵ | *B ……..
C→ ϵ | %B 4) If FIRST(X1), FIRST(X2),….. and FIRST(Xn) = ϵ, then FIRST(X1X2…Xn) ← ϵ
FIRST(A), FIRST(B), FIRST(C) are computed using rules 1 and 2 as shown below:
  Systematic approach to Compiler Design - 2.49 2.50  Syntax Analyzer
1 Add non- ϵ symbols of FIRST(A)
Example 2.24: Let FIRST(A) = {+, ϵ }, FIRST(B) = { *, ϵ } and FIRST(C) = { %, - }
Compute FIRST(ABC) 2 Since FIRST(A) contains ϵ, we add non- ϵ symbols of FIRST(B)

Solution: Using FIRST(A), FIRST(B) and FIRST(C), the FIRST(ABC) can be obtained 3 Since FIRST(A) and FIRST(B) contains ϵ, we add non- ϵ symbols of FIRST(C)
as shown below:
4 Since FIRST(A), FIRST(B) and FIRST(C) contains ϵ, we add ϵ symbol
A B C
FIRST(ABC) FIRST +, ϵ *, ϵ %, - So, FIRST(ABC) = {+, *, %, -, ϵ }
non- ϵ symbols 1 2 3
+ 2.9.2 Computing FOLLOW symbols
non- ϵ symbols
* Once we know, how to compute FIRST sets, let us concentrate on how to compute
FOLLOW sets. Before proceeding further, let us “Define FOLLOW(A)?”
non- ϵ symbols
%, - Definition: The FOLLOW(A) for a non-terminal A is defined as the set of terminals a
that will appear immediately to the right of A in some sentential form. That is, the set of
1 Add non- ϵ symbols of FIRST(A) terminals a such that there exists a derivation of the form:
S αAaβ
2 Since FIRST(A) contains ϵ, we add non- ϵ symbols of FIRST(B)
for some α and β. If A is appeared as the last symbol in some sentential form, then place
3 Since FIRST(A) and FIRST(B) contains ϵ, we add non- ϵ symbols of FIRST(C) $ into FOLLOW(A) where the symbol $ is treated as “endmarker” symbol.
Now, let us see “What is the algorithm to compute FOLLOW(A)?” The algorithm to
So, FIRST(ABC) = {+, *, %, - } compute FOLLOW(A) is shown below:

ALGORITHM FOLLOW(A)
Example 2.25: Let FIRST(A) = {+, ϵ }, FIRST(B) = { *, ϵ } and FIRST(C) = { %, -, ϵ }
Compute FIRST(ABC) Rule 1: FOLLOW(S) ← $ where S is the start symbol.

Solution: Using FIRST(A), FIRST(B) and FIRST(C), the FIRST(ABC) can be obtained Rule 2: If A → B is a production and  ≠  then FOLLOW(B) ← non- symbols in
as shown below: FIRST()
Rule 3: If A → B is a production and  , then FOLLOW(B) ← FOLLOW(A)
A B C
FIRST(ABC) FIRST +, ϵ *, ϵ %, -, ϵ
non- ϵ symbols 1 2 Example 2.26: Compute FIRST and FILLOW sets for the following grammar:
+ 3
E → TE'
non- ϵ symbols
* E' → + TE' | 
non- ϵ symbols T → FT'
%, -
T' → *FT' | 
F → (E) | id
ϵ ϵ 4
  Systematic approach to Compiler Design - 2.51 2.52  Syntax Analyzer

a) Computing FIRST sets: The FIRST sets can be computed as shown below:
Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B)
Rule 1: E' → + TE' T' → * FT' F→ ( E ) Copy from right to left (Put arrow from Copy from left to right (Put arrow from
F → id right left on RHS of the production) LHS of production to RHS)

Rule 2: E' → ϵ T' → ϵ

E → T E' E → T E'
+, ϵ *, ϵ (, id A→αB β A→αB β

E E' T T' F
E → T E' Rule 2 not applicable E→ T E'
Rule 3 - (a) Rule 3 - (b) A→ α B β A→ α B β

Rule 3: Consider the productions not considered earlier and obtain FIRST sets as shown
below: E1 → + T E' E' → + T E'
a) E → T E' Add “FIRST(T) - ϵ” to FIRST(E) i.e., draw an A → α B β A→ α B β
edge from T to E in above figure.

E1 → + T E' Rule 2 not applicable E' → + T E'

b) T → F T' Add “FIRST(F) - ϵ” to FIRST(T) i.e., draw an
A → α B β A → α B β
edge from F to T in above figure.

In the above figure, transfer FIRST(T) to FIRST(E) and from FIRST(F) to FIRST(T). So,
T → F T' T → F T'
the final FIRST sets are shown below:
A→αB β A→αB β

FIRST (, id +, ϵ (, id *, ϵ (, id
T → F T' Rule 2 not applicable T→ F T'
E E' T T' F A→ α B β A→ α B β
b) Computing FOLLOW sets:
T' → * F T' T' → * F T'
A → α B β A→ α B β
E $, ) E' $, ) T +, $, ) T' +, $, ) F +, *, $, )

T' → * F T' Rule 2 not applicable T' → * F T'

Rule 1: $ is placed in FOLLOW(E) since E is the start symbol. A → α B β A → α B β

Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B
is a non-terminal. In the first column shown below, copy from FIRST(β) to F → (E) F → (E)
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B). A → αB β Rule 3 not applicable
A → αB β
  Systematic approach to Compiler Design - 2.53 2.54  Syntax Analyzer

Now, let us see “What are the steps to be followed while constructing the predictive For every production of the form A → α, we compute FIRST(α) and entries of the
parser?” The various steps to be followed while constructing the predictive parser are parsing table can be done as shown below:
shown below:
 If the grammar is ambiguous, eliminate ambiguity from the grammar Productions a = FIRST() M[A, a] = A→α Rule
 If the grammar has left recursion, eliminate left recursion A→α
 If the grammar has two or more alternatives having common prefix, then do left- E → TE' (, id M [ E, ( ] = E → TE' 1
factoring A  M [ E, id ] = E → TE'
 The resulting grammar is suitable for constructing predictive parsing table
E' → + TE' + M [ E', + ] = E' → +TE' 1
2.9.3 Constructing predictive parsing table
A 
Now, using FIRST and FOLLOW sets, we can easily construct the predictive parsing  2
table and the productions are entered into the table M[A, a] where E' →  M [ E', ) ] = E' → 
 M is a 2-dimensional array representing the predictive parsing table A  M [ E', $ ] = E' → 
 A is a non-terminal which represent the row values
 a is a terminal or $ which is endmarker and represent the column values T → FT' (,id M [ T, ( ] = T → FT' 2
Now, let us “Write the algorithm to construct the predictive parsing table” The complete A  M [ T, id] = T → FT'
algorithm is shown below:
ALGORITHM Predictive_Parsing_Table(G, M) T' → *FT' * M [ T', *] = T' → *FT' 2
Input : Grammar G A 
 3
Output : Predictive parsing table M T' →  M [ T', + ] = T' → 
A  M [ T', ) ] = T' → 
Procedure : For each production A → α of grammar G apply the following rules
M [ T', $ ] = T' → 
1) For each terminal a in FIRST(α), add A→ α to M[A, a]
2) If FIRST(α) contains , for each symbol b in FOLLOW(A), add A→ α to M[A, b] F → (E) ( M [ F, ( ] = F → (E) 2
A 
F → id id M [ F, id ] = F → id 2
Example 2.27: Obtain the predictive parsing table for the following grammar
A 
E → TE'
E' → + TE' |  The parsing table is shown below:
T → FT'
T1 → *FT' |  id + * ( ) $
F → (E) | id E E → TE' E → TE'
E' E' → +TE' E' →  E' → 
Solution: The FIRST and FOLLOW sets of each non-terminal of the given grammar are
T T → FT' T → FT'
shown below: (See example 2.26 for details)
E E' T T' F T' T' →  T' → *FT' T' →  T' → 

FIRST (, id +, ϵ (, id *, ϵ (, id F F → id F → (E)
FOLLOW ), $ ), $ +, ), $ +, ), $ +, *, ), $
  Systematic approach to Compiler Design - 2.55 2.56  Syntax Analyzer

Note: Since there are no multiple entries in the parsing table, the given grammar is called Solution: We know that the grammar is not left-factored since, two productions have
LL(1) grammar. If multiple entries are present in the parsing table, the grammar is not common prefix “iCtS”. So, it is necessary to do the left-factoring for the given grammar.
LL(1). The predictive parser accepts only the language generated from LL(1) grammar. The left-factored grammar (for details refer section 2.8.5, example 2.19) is shown below:

2.10 LL (1) Grammars S → iCtSS'| a

In this section, let us see “What is LL (1) grammar?” S'→ ϵ | eS
C→ b
Definition: The grammar from which a predictive parser, that is, recursive descent parser
without backtracking is constructed is called LL(1) grammar where The following procedure is used:
 The first L stands for left-to-right scan of the input  Compute FIRST sets and FOLLOW sets
 The second L stands for leftmost derivation. So, the predictive parsers always mimic  Check whether the grammar is LL(1) or not
the leftmost derivation.  Obtain the parsing table
 The digit 1 indicates number of tokens to lookahead.
Step 1: The first symbols can be computed as shown below:
In LL(1) parsing technique or predictive parsing if two or more alternative productions
are there, the predictive parser also called LL(1) parser chooses the correct production by Rule 1: S → i CtSS' S' → e S C→b
guessing using one lookahead token. S→ a
Now, let us see “What grammars are not LL(1)?” The following grammars are not LL(1)
Rule 2: S' → ϵ
grammars:
 Ambiguous grammar is not LL(1)
 Left recursive grammar is not LL(1) i, a e, ϵ b
 The grammar which is not left factored (that is, if two or more alternative productions
have common prefix), the grammar is not LL(1) Rule 3: This rule is not applied, since all productions are already considered when we
 The grammar that results in multiple entries in the parsing table is not LL(1). apply first two rules. So, the final FIRST sets are shown below:
Now, the question is “How to check whether a given grammar is LL(1) or not without S S' C
constructing the predictive parser?” The grammar is said to be LL(1) if following two FIRST i, a e, ϵ b
conditions are satisfied:
 For every production of the form A → α1 | α2 | α3 | …….αn:
FIRST(αi) ∩ FIRST(αj) must be empty for all i, j  n where i ≠ j FOLLOW sets:

 For every non-terminal A such that FIRST(A) contains ϵ: S S' C

FIRST(A) ∩ FOLLOW(A) must be empty FOLLOW $, e $, e t

Example 2.28: Compute FIRST and FOLLOW symbols and predictive parsing table for
the following grammar: Rule 1: $ is placed in FOLLOW(S) since S is the start symbol.
S → iCtS | iCtSeS | a
Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B
C→ b
is a non-terminal. In the first column shown below, copy from FIRST(β) to
Is the following grammar LL(1)?
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
  Systematic approach to Compiler Design - 2.57 2.58  Syntax Analyzer

Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B) Condition 2: If FIRST(A) contains ϵ Condition to be satisfied is
FIRST(A) ∩ FOLLOW(A) = ϕ
t
S → i C t S S' rule 3 not applicable FIRST(S') has ϵ FIRST(S') ∩ FOLLOW(S')
A→αB β { e, ϵ } ∩ {$, e} = {e}

S → i C t S S' S → i C t S S' Note: Condition 2 is not satisfied:

A→ α B β A→ α B β
Since one of the condition fails, the given grammar is not LL(1). For a grammar to be
LL(1), the both the conditions must be satisfied.
S → i C t S S' rule 2 not applicable S → i C t S S' Construction of predictive parsing table: For every production of the form A → α, we
A→ α B β A→ α B β compute FIRST(α) and entries of the parsing table can be done as shown below:

Productions a = FIRST() M[A, a] = A→α Rule

S' → e S rule 2 not applicable S' → e S A→α
A → α B β A→ α B β i 1
S → iCtSS' M [ S, i ] = S → iCtSS'
Note: The productions S → a and C → b are not considered while computing FOLLOW A 
since there are no variables in those productions. So, the FIRST and FOLLOW sets for S→ a a M [ S, a ] = S→a 1
the left-factored grammar are shown below: A 
S' → eS e M [ S ', e ] = S' → eS 1
S S' C
A 
FIRST a, i e, ϵ b  2
S' →  M [ S ', e ] = S' → 
FOLLOW $, e $, e t
A  M [ S ', $ ] = S' → 
To check whether the grammar is LL(1) or not: Without constructing the predictive
parser also we can check whether the grammar is LL(1) or not. If the grammar is LL(1), C→ b b M [ C, b ] = C→b 1
the following two conditions must be satisfied: A 

Condition 1: For a given production Condition to be satisfied The parsing table is shown below:
A → α1 | α2 | α3 | …….αn FIRST(α1) ∩ FIRST(α2) ∩….FIRST(αn) = ϕ
a b e i t $
S → i C t S S' | a FIRST(iCtSS') ∩ FIRST(a) S S→a S → iCtSS'
{i} ∩ {a}= ϕ
S1 S'→ eS S' → 
S'→ ϵ | eS FIRST(ϵ) ∩ FIRST(eS)
{ ϵ } ∩ {e}= ϕ S' → 
C C→b
Note: Condition 1 is satisfied
  Systematic approach to Compiler Design - 2.59 2.60  Syntax Analyzer
c) Computing FIRST and FOLLOW: The first set can be computed as shown below:
Example 2.29: Given the following grammar:
S → a | (L) Rule 1: S → ( L ) L' → , S L'
L→ L , S | S S→ a
a) Is the grammar suitable for predictive parser?
b) Do the necessary changes to make it suitable for LL(1) parser Rule 2: L' → ϵ
c) Compute FIRST and FOLLOW sets for each non-terminal
d) Obtain the parsing table and check whether the resulting grammar is LL(1) or not. S a, ( L L' ,ϵ
e) Show the moves made by the predictive parser on the input “( a , ( a , a ) )”

Solution: The given grammar is shown below: Rule 3: Consider the productions not considered earlier and obtain FIRST sets as shown
S → a | (L) below:
L→ L , S | S a) L → S L' Add “FIRST(S) - ϵ” to FIRST(L)

a) Consider the production: L → L , S In the above figure, transfer FIRST(S) to FIRST(L). So, the final FIRST sets are shown
below:
Since the first symbol on RHS of the production is same as the symbol on LHS of the
production, the given grammar is having left-recursion and hence, it is not suitable S L L'
for predictive parser. FIRST a, ( a, ( ,ϵ

b) To make it suitable for LL(1) parser or predictive parser, we need to eliminate left- FOLLOW sets:
recursion as shown below: (For details refer section 2.8.4)
FOLLOW S L L'
Left recursive productions Right recursive productions $ ) )
A → A1|A2|A3|……|An|β1 | β2| β3| ……..| βm A→ β1A'| β2A'|β3A'| ……..|βm A'
A'→1A'| 2A'|3A'|……|nA'| ϵ Rule 1: $ is placed in FOLLOW(S) since S is the start symbol.

1) S → a | (L) S→ a | (L) Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B
is a non-terminal. In the first column shown below, copy from FIRST(β) to
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
2) L → L , S | S L → SL'
↓ ↓ ↓ ↓ L'→ , S L' | ϵ Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B)
A → A 1 | β1
)
The final grammar obtained after eliminating left recursion can be written as shown S→ ( L ) rule 3 not applicable
below: A→αB β
S→ a | (L)
L → SL' L → S L'
L → S L'
L'→ , S L' | ϵ A→αB β
A→αB β
  Systematic approach to Compiler Design - 2.61 2.62  Syntax Analyzer

L → S L' rule 2 not applicable The above entries can be entered into parsing table as shown below:
L→ S L'
A→ α B β A→ α B β
( ) a , $
S S → (L) S→a
L1 → , S L' L' → , S L' L L→ SL1 L→ SL1
A→ αB β A→ αB β L1 L1 →  L1 → , SL1

Since there are no multiple entries in the parse table, the resulting grammar obtained after
1 L' → , S L' results in self-loop eliminating left recursion is LL(1).
L → , S L' rule 2 not applicable
A→ α B β A→ α B β and hence discard
e) The moves made by the predictive parser on the input “( a , ( a , a ) )” is shown
below:
Note: The productions S → a and L' → ϵ are not considered while computing
Stack Input Output Action
FOLLOW since they do not have non-terminals in those productions. So, the FIRST
and FOLLOW sets for the left-factored grammar are shown below:
$S (a,(a,a))$ S → (L) [Remove S and push (L) in reverse]
S L L' $)L( (a,(a,a))$ Match ( Pop ( and increment i/p pointer
FIRST a ( a ( ,ϵ
$)L a,(a,a))$ L→ SL' '
[Remove L and push SL in reverse]
FOLLOW ,$) ) )
d) Construction of parsing table: For every production of the form A → α, we $ ) L' S a,(a,a))$ S→ a [Remove S and push a in reverse]
compute FIRST(α) and entries of the parsing table can be done as shown below:
$ ) L' a a,(a,a))$ Match a Pop a and increment i/p pointer

Productions a = FIRST() M[A, a] = A→α Rule

A→α $ ) L' ,(a,a))$ L' → , SL' ' '
Remove L and push ,SL in reverse

S→ a a M [ S, a ] = S→a 1
$ ) L' S , ,(a,a))$ Match , Pop „,‟ and increment i/p pointer
A 
S→ (L) ( M [ S, ( ] = S→(L) 1 $ ) L' S (a,a))$ S → (L) Remove S and push (L) in reverse
A 
a ( 1 $ ) L' ) L ( (a,a))$ Match ( Pop ( and increment i/p pointer
L → SL' M [ L, a ] = L → SL'
A  M [ L, ( ] = L → SL' $ ) L' ) L a,a))$ L→ SL' '
Remove L and push SL in reverse
 2
L' →  M [ L', ) ] = L'→  $ ) L' ) L'S a,a))$ S→ a Remove S and push a in reverse
A 
L' → , SL' , M [ L', „,‟] = L' → , SL' 1 $ ) L' ) L' a a,a))$ S→ a Pop a and increment i/p pointer

A  $ ) L' ) L' ,a))$ L' → , SL' ' '

Remove L and push ,SL in reverse
  Systematic approach to Compiler Design - 2.63 2.64  Syntax Analyzer

$ ) L' ) L' S , ,a))$ Match , Pop „,‟ and increment i/p pointer
b) To make it suitable for LL(1) parser or predictive parser, we need to do left factoring
(For details refer section 2.8.5). If an A-production has two or more alternate
$ ) L' ) L' S a))$ S→ a Remove S and push a
productions and they have a common prefix, then the parser has some confusion in
selecting the appropriate production for expanding the non-terminal A. So, left
$ ) L' ) L' a a))$ Match a Pop a and increment i/p pointer
factoring is must for top down parser. This can be done as shown below:

$ ) L' ) L' ))$ L' →  Pop L' Given productions Left-factored productions
A→ α A' | γ
$ ) L' ) ))$ Match ) Pop ) and increment i/p pointer
A → αβ1 | αβ2 | αβ3 |….. αβn | γ A'→ β1 | β2 | β3 |….. βn

$ ) L' )$ L' →  Pop L'

1) E → 5 + T | 3 – T E → 5+T|3–T
$) )$ Match ) Pop ) and increment i/p pointer

$ $ Accept 2) T → V ϵ | V * V | V + V T → V T'
A → α β1 | α β 2 | α β3 T'→ ϵ | * V | + V
Note: Since stack is empty and i/p pointer also points to $ which is endmarker, parsing is
successful
3) V → a|b V→ a|b
Example 2.30: Given the following grammar:
E → 5+T|3–T So, the final grammar which is obtained after doing left-factoring is shown below:
T → V | V*V | V+V E → 5+T|3–T
V→ a|b T → V T'
a) Is the grammar suitable for predictive parser?
b) What is the use of left-factoring? Do the left factoring for the above grammar T'→ ϵ | * V | + V
c) Compute FIRST and FOLLOW sets for each non-terminal V→ a|b
d) Without constructing the parsing table, check whether the grammar is LL(1) or c) Computing FIRST and FOLLOW: The first set can be computed as shown below:
not.
e) By constructing the parsing table, check whether the grammar is LL(1) or not. Rule 1: E → 5 + T T' → * V V→ a
E→ 3-T E→ b
Solution: The given grammar is shown below: T' → + V
Rule 2: T' → ϵ
E → 5+T|3–T
T → V | V*V | V+V T * +ϵ V
E 53 T' ab
V→ a|b
a) The E-productions and V productions are suitable for parsing. But, consider the Rule 3: Consider the productions not considered earlier and obtain FIRST sets as shown
production: below:
T → V | V*V | V+V
b) T → V T' Add “FIRST(V) - ϵ” to FIRST(T)
In the T-production, one or more productions have a common prefix V and hence the
given grammar is not left-factored grammar. So, the given grammar is not suitable In the above figure, transfer FIRST(V) to FIRST(T). So, the final FIRST sets are shown
for predictive parser. below:
  Systematic approach to Compiler Design - 2.65 2.66  Syntax Analyzer
Note: The productions T1→  and V → a | b are not considered while computing
5, 3 T a, b T 1
*, +, ϵ a, b FOLLOW since there are no non-terminals in those productions.
FIRST E V
FOLLOW sets: So, the FIRST and FOLLOW sets for the left-factored grammar are shown below:
E T T1 V
$ T $ T1 $ V *, + ,$
FOLLOW E FIRST 5, 3 a, b *,+ , ϵ a,b
FOLLOW $ $ $ *,+,$
Rule 1: Place $ into FOLLOW(S) since S is the start symbol.
d) Now, for the grammar to be LL(1) the following two conditions must be satisfied:
Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B
is a non-terminal. In the first column shown below, copy from FIRST(β) to a. The first condition has to be satisfied:
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
Production Condition to be satisfied
Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B) A → α1 | α2 | α3 | ……. FIRST(αi) ∩ FIRST(αj) = ϕ

E →5+T|3–T FIRST (5 + T) ∩ FIRST( 3 – T) = ϕ

E→ 5+ T rule 2 not applicable E→ 5+T
A→ α B β A→ α B β V→ a|b FIRST (a) ∩ FIRST(b) = ϕ

Observe that the first condition is satisfied

E→ 3– T rule 2 not applicable E→ 3– T
A→ α B β A→ α B β b. The second condition has to be satisfied:

If FIRST(A) = ϵ Condition to be satisfied

T → V T1 T → V T1 FIRST(A) ∩ FOLLOW(A) = ϕ
A→αBβ A→αB β
If FIRST(T1) = ϵ FIRST(T1) ∩ FOLLOW(T1)
{*, +, ϵ }∩ {$} = ϕ
T → V T1 rule 2 not applicable T→ V T1
A→ α B β A→ α B β
Observe that the second condition is satisfied

Since, both conditions are satisfied, the resulting grammar is LL(1)

T1 → * V rule 2 not applicable T1 → * V
A→ αB β A→ αB β e) Construction of Parsing table: For every production of the form A → α, we
compute FIRST(α) and entries of the parsing table can be done as shown below:

T1 → + V rule 2 not applicable T1 → + V Productions a = FIRST() M[A, a] = A→α Rule

A→ αB β A→ αB β A→α
E→5+T 5 M [ E, 5 ] = E→5+T 1
A 
  Systematic approach to Compiler Design - 2.67 2.68  Syntax Analyzer

E→3–T 3 M [ E, 3 ] = E→3–T 1 a) The FIRST and FOLLOW sets are computed as shown below:
A 
T → VT1 a, b M [ T, a ] = T → VT1 1 Step 1: The first symbols can be computed as shown below:
A  M [ T, b ] = T → VT1
X→a

Rule 1: Z → d Y→ c
T1 →  M [ T 1, $ ] = T1 →  2
A  Rule 2: Y→ ϵ
T1 → *V * M [ T1 , * ] = T1 → *V 1
A  d X a Y c, ϵ
Z
T1 → +V + M [ T1 , + ] = T1 → +V 1
A 
V→a a M [ V, a ] = V→a 1 Rule 3: Consider the productions not considered earlier and obtain FIRST sets as
A  shown below:
V→b b M [ V, b ] = V→b 1
A 
1) Z → XYZ Add “FIRST(X) - ϵ” to FIRST(Z)
The parsing table is shown below:
2) Z → XYZ Since FIRST(X) has ϵ, add “FIRST(Y) - ϵ” to FIRST(Z)
5 3 a b * + $
E E→5+T E→3–T
T T → VT1 T → VT1
3) Z → XYZ Since FIRST(X) and FIRST(Y) has ϵ, add “FIRST(Z) - ϵ”
T1 T1→ *V T1→ +V T1 →  to FIRST(Z)
V V→a V→b
4) X → Y Add “FIRST(Y) - ϵ” to FIRST(X)
Since there are no multiple entries in the parse table, the resulting grammar obtained after
doing left factoring is LL(1).
5) X → Y Since Y ϵ, add ϵ to FIRST(X)
Example 2.31: Given the following grammar:
Z → d | XYZ
Y → ϵ|c So, the final FIRST sets are shown below:
X→ Y|a
FIRST Z a, c, d X a, c, ϵ Y c, ϵ
a) Compute FIRST and FOLLOW sets for each non-terminal
b) Without constructing the parsing table, check whether the grammar is LL(1) or
not. FOLLOW sets:
c) By constructing the parsing table, check whether the grammar is LL(1) or not.

Solution: The given grammar is shown below: FOLLOW Z $ X a, c, d Y a, c, d

Z → d | XYZ
Y → ϵ|c
X→ Y|a Rule 1: Place $ into FOLLOW(Z) since Z is the start symbol.
  Systematic approach to Compiler Design - 2.69 2.70  Syntax Analyzer

Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B c) Construction of Parsing table: It can be constructed as shown below:
is a non-terminal. In the first column shown below, copy from FIRST(β) to
Productions a = FIRST() M[A, a] = A→α Rule
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
A→α
Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B) Z→d d M [ Z, d ] = Z→d 1
A 
β Z → XYZ a, c, d M [ Z, a ] = Z → XYZ 1
Z→ XYZ β = FIRST(Y) - ϵ + Rule 3 is not applicable A  M [ Z, c ] = Z → XYZ
A→ α B β FIRST(Z) - ϵ M [ Z, d ] = Z → XYZ
Y→ c c M [ Y, c ] = Y→ c 1
β A 
Z→ XYZ β = FIRST(Z) - ϵ Rule 3 is not applicable Y→   M [ Y, a ] = Y→
A→ α Bβ A  M [ Y, c ] = Y→ 2
M [ Y, d ] = Y→

Z→ XYZ rule 2 not applicable Z→ XYZ FOLLOW (X)

A→ α Bβ A→ α B β X→a a M [ X, a ] = X→a 1
A 
X→Y c,  M [ X, c ] = X→Y 1
X→ Y rule 2 not applicable X→ Y
A 
A→ αB β A→ α B β
M [ X, a ] = X→Y
M [ X, c ] = X→Y
M [ X, d ] = X→Y
Note: The productions Z → d, Y → ϵ | c and X → a are not considered while 2
computing FOLLOW since there are no non-terminals in those productions. So, the FOLLOW (X)
FIRST and FOLLOW sets for the left-factored grammar are shown below:
The parsing table is shown below:
Z X Y
FIRST a,c,d a,c, ϵ c,ϵ a c d $
FOLLOW $ a,c,d a,c,d Z Z→ XYZ Z→ XYZ Z→d
b) Now, for the grammar to be LL(1) the following two conditions must be satisfied: Z→ XYZ
X X→a X→Y X→Y
a. The first condition to be satisfied: X→Y
Y Y→ Y→ c Y→
Production Condition to be satisfied Y→
A → α1 | α2 | α3 | ……. FIRST(αi) ∩ FIRST(αj) = ϕ
Since there are multiple entries in the parse table, the given grammar is not LL(1).
Z → d | XYZ FIRST (d) ∩ FIRST( XYZ)
{d} ∩ {a,c,d} = d Example 2.32 : Left factor the following grammar and obtain LL(1) parsing table
E→T+E|T
Condition 2 is not satisfied. Hence, the grammar is not LL(1). T → float | float * T | (E)
  Systematic approach to Compiler Design - 2.71 2.72  Syntax Analyzer

Solution: Since the right hand side of E-production and T-production has common In the above figure, transfer FIRST(T) to FIRST(E). So, the final FIRST sets are
prefixes, this grammar is not suitable for parsing. So, we have to do left factoring and see shown below:
that two or more productions do not have common prefix. Left-factoring can be done as
shown below: FIRST E float, ( E1 +,  T float, ( T1 *, 

The left factoring can be done to the given grammar as shown below: FOLLOW sets:

Given productions Left-factored productions

FOLLOW E $, ) E1 $, ) T +, $, ) T1 +,$, )
A→ α A1 | γ
A → αβ1 | αβ2 | αβ3 |….. αβn | γ A1→ β1 | β2 | β3 |….. βn
Rule 1: Place $ into FOLLOW(S) since S is the start symbol.
1) E → T + E | T E → T E1 Rule 2 &3 : Apply rule 2 and 3 for every production of the form A → αBβ where B
A→ α β1 | α β2 E1 → + E |  is a non-terminal. In the first column shown below, copy from FIRST(β) to
FOLLOW(B) and in the second column copy from FOLLOW(A) to FOLLOW(B).
2) T → float | float * T | (E) T → float T1 | ( E )
A→ α β 1 | α β2 | γ T1→  | *T Rule 2 (β ≠ ϵ) FOLLOW(B) ← FIRST(β) - ϵ Rule 3 (β ϵ) FOLLOW(A) → FOLLOW(B)
So, the grammar obtained after doing left factoring is shown below:
E → T E1 E → T E1 E → T E1
E1 → + E |  A→ α B β A→ α B β
T → float T1 | ( E )
T1→  | *T
E → T E1 rule 2 not applicable E → T E1
A→ α B β A→ α B β
a) The FIRST and FOLLOW sets can be computed as shown below:
FIRST sets: are computed as shown below: E → + E1 rule 2 not applicable E → + E1
Step 1: The first symbols can be computed as shown below: A→ α B β A→ α B β

Rule 1: E1 → + E T → float T1 T1 → * T
T→ ( E ) T→ float T1 rule 2 not applicable T→ float T1
A→ α B β A→ α B β
Rule 2: E1 →  T1 → ϵ

E1 +,  T float, ( T1 *,  T → (E) T → (E)

E Rule 3 not applicable
A → αB β A → αB β

Rule 3: Consider the productions not considered earlier and obtain FIRST sets as
shown below: T1 → * T rule 2 not applicable T1 → * T
E → T E1 Add “FIRST(T) - ϵ” to FIRST(E) A → αB β A→ α B β
  Systematic approach to Compiler Design - 2.73 2.74  Syntax Analyzer
1 1
Note: The productions T →  and E →  are not considered while computing  The terminal on top of the stack does not match with the next input symbol
FOLLOW since there are no non-terminals in those productions. So, the FIRST and  When non-terminal A is on top of the stack, a is the next input symbol and M[A, a]
FOLLOW sets for the left-factored grammar are shown below: has blank entry (blank denote an error)
E E1 T T1 The error recovery is done using panic mode and phrase-level recovery as shown below:
FIRST float, ( +,  float, ( *, 
FOLLOW $,) $, ) +,$,) +,$,)  Panic mode: In this approach, error recovery is done by skipping symbols from the
input until a token matches with synchronizing tokens. The synchronizing tokens are
b) Construction of Parsing table: For every production of the form A → α, we
selected such that the parser should quickly recover from the errors that are likely to
compute FIRST(α) and entries of the parsing table can be done as shown below:
occur in practice. Some of the recovery techniques are shown below:
1) For a non-terminal A, consider the symbols in FOLLOW(A). These symbols can
Productions a = FIRST() M[A, a] = A→α Rule be considered as synchronizing tokens and are added into parsing table replacing
A→α only blank entries. Now, whenever there is a mismatch, keep skipping the tokens
E → T E1 float, ( M [ E, float ] = E → T E1 1 till we get one of the synchronizing character and remove A from the stack. It is
A  M [ E, „(„ ] = E → T E1 likely that parsing can continue.
E1 → + E + M [ E1 , + ] = E1 → + E 1 2) For a non-terminal A, consider the symbols in FIRST(A). These symbols can also
A  be considered as synchronizing characters and add to the parsing table replacing
E1 →   M [ E 1, $ ] = E1 →  2 only blank entries. Now, whenever there is a mismatch, keep skipping the tokens
A  M [ E1, „)‟ ] = E1 →  till we get one of the synchronizing character and remove A from the stack. It is
T → float T1 float M [ T, float ] = T → float T1 1 also likely that parsing can continue.
A  3) If a terminal on top of the stack cannot be matched, pop the terminal from the
stack and issue “Error message” and insert the corresponding terminal and
T→(E) ( M [ T, ( ] = T→(E) 1
continue parsing.
A 
T1 →   M [ T 1, $ ] = T1 →  2 For example, consider the parsing table containing synchronizing tokens and
A  M [ T1, „)‟ ] = T1 →  sequence of moves made by the parser in example 2.33 given later in this section.
M [ T 1, + ] = T1 → 
T1 → * T * M [ T1 , * ] = T1 → * T 1 Phrase level recovery: This recovery method is implemented by filling the blank entries
A  in the predictive parsing table with pointers to error routines. These routines may change,
insert, replace or delete symbols from the input and issue appropriate error messages.
The parsing table is shown below:
They may also pop from the stack.
float * + ( ) $
E E → T E1 E → T E1
E1 E1 → + E E1 →  E1 →  Example 2.33: Consider the following grammar
1 E → TE1
T T → float T T→(E)
E1 → + TE1 | 
T1 T1 → * T T1 →  T1 →  T1 →  T → FT1
T1 → *FT1 | 
2.11 Error recovery in predictive parsing
F → (E) | id
Now, let us see “How error recovery is done in predictive parsing?” An error is detected and the parsing table (Refer example 2.27 for details)
during predictive parsing when the following two situations occur:
  Systematic approach to Compiler Design - 2.75 2.76  Syntax Analyzer

id + * ( ) $ $ E1 T1 F id * + id$ F → id Remove F and push id in reverse

E E → TE1 E→ TE1 $ E1 T1 id id * + id$ Match id Pop id and increment i/p pointer
E1 E1 → +TE1 E1 →  E1 →  1 1 1 1
$E T * + id$ T → *FT Remove T1 and push *FT1 in reverse
T T → FT1 T → FT1
1 1
T1 T1 → T1 → *FT1 T1 → T1 → $E T F* * + id$ Match * Pop * and increment i/p pointer

F F → id F → (E) 1
$E T F 1
+ id$ error, skip Pop + from the input

Add the synchronizing tokens for the above parsing table and show the sequence of $ E1 T1 F id$ F → id Remove F and push id in reverse

moves made by parser for the string “ ) id * + id” 1

$ E T id1
id$ Match id Pop id and increment i/p pointer

Solution: The synchronizing characters are the characters present in FIRST or FOLLW $ E1 T1 $ Match id Pop id and increment i/p pointer
1 1 1
sets of each non-terminal. In our example, let us add synchronizing characters by $E T $ T → Remove T1 from the stack
considering FOLLOW of each non-terminal replacing each blank entry in the parsing 1 1
table. The FOLLOW sets of each non-terminal are shown below (Refer example 2.26 for $E $ E → Remove E1 from the stack
details): $ $ ACCEPT

E E 1
T T 1
F Note: Observe that parsing is successful and the parser has also recognized two errors.
FOLLOW $, ) $, ) +, $, ) +, $, ) +, *, $, ) By looking at these errors if the programmer corrects the program, parsing action is
successful without any errors.
Now, FOLLOW(E) = { $, ) }. So, M[E, $] = M[E,)] = synch only for blank entries.
Computing FIRST sets: The first sets of LHS of the production is nothing but the
Similarly, FOLLOW(F) = {+, *, $, ) }. So, M[F,+] = M[F,*] = M[F, $] = M[F,) = synch.
terminals obtained from the first symbols on the RHS of the production.
On similar lines we add synchronizing characters to the parsing table as shown below:
So, FIRST(E) = FIRST(T) = FIRST(F) = (, id
id + * ( ) $
E E → TE1 E→ TE1 synch synch Computing FOLLOW sets: The FOLLOW sets of any non-terminal A on RHS of the
E1 E1 → +TE1 E1 →  E1 →  production are obtained the following rules:
T T → FT1 synch T → FT1 synch synch 1) Sets of terminals immediately following A or sets of first symbols obtained from the
T1 T1 → T1 → *FT1 T1 → T1 → non-terminals immediately following A
F F → id synch synch F → (E) synch synch 2) If A is on LHS of the production and B is right most symbol on RHS of the
production then FOLLOW(B) = FOLLOW(A)
Now, the sequence of moves made by the parser for the string “ ) id * + id” is shown
below:
Exercises
Stack Input Output Action
1) What is a context free grammar? What is derivation? What are the two types of
$E ) id * + id$ error, skip Remove ) from the input derivations?

$E id * + id$ E → TE1 Remove E and push TE1 in reverse 2) Define the terms: leftmost derivation, rightmost derivation, sentence
1 1
$E T id * + id$ T → FT 1
Remove T and push FT in reverse
  Systematic approach to Compiler Design - 2.77 2.78  Syntax Analyzer

3) What the different sentential forms? What is left sentential form? What is right 12) What are error recovery strategies of the parser (or syntax analyzer)?”
sentential form?
13) What is top down parser? Show the top-down parsing process for the string id + id *
4) Define the terms: Language, derivation tree, yield of a tree, ambiguous grammar id for the grammar
i. E → E + E
5) Show that the following grammar is ambiguous ii. E → E * E
E → E+E iii. E → (E)
E → E-E iv. E → id
E → E*E
E → E/E 14) What is recursive descent parser? Write the algorithm for recursive descent parser
E → (E) | I 15) Write the recursive descent parser for the following grammar
I → id E→T
6) Is the following grammar ambiguous? (if-statement or if-then-else) T→F
S → iCtS | iCtSeS | a F → (E) | id
C → b 16) What are the different types of recursive descent parsers? What is the need for
7) What is dangling else problem? How dangling else problem can be solved backtracking in recursive descent parser
8) Eliminate ambiguity from the following ambiguous grammar: 17) Show the steps involved in recursive descent parser with backtracking for the input
string cad for the following grammar
S → iCtS | iCtSeS | a
S → cAd
C → b
A → ab | a
9) Convert the following ambiguous grammar into unambiguous grammar using normal
18) For what type of grammars recursive descent parser cannot be constructed? What is
precedence and associativity of the operators
the solution?
E → E*E|E-E
E → E^E|E/E 19) What is left recursion? What problems are encountered if a recursive descent parser is
E → E+E constructed for a grammar having left recursion?
E → (E) | id 20) Write the procedure to eliminate left recursion
10) Convert the following ambiguous grammar into unambiguous grammar 21) Eliminate left recursion from the following grammar
E→E+E E → E +T | T
E→E–E T→ T*F|F
E→E^E F → (E) | id
E→E*E
E→E/E 22) Write the recursive descent parser for the following grammar:
E → (E) | id E → TE1
E1→ +TE1 | ϵ
by considering * and – operators lowest priority and they are left associative, / and + T → FT1
operators have the highest priority and are right associative and ^ operator has T1→ *FT1 | ϵ
precedence in between and it is left associative. F → (E) | id
11) What is parsing? What are the different types of parsers? 23) Obtain top-down parse for the string id+id*id for the following grammar
E → TE1
  Systematic approach to Compiler Design - 2.79 2.80  Syntax Analyzer
1
E → + TE | 
1 34) Compute FIRST and FOLLOW symbols and predictive parsing table for the
T → FT1 following grammar and check whether the grammar is LL(1) or not.
T1 → *FT1 |  S → iCtS | iCtSeS | a
F → (E) | id C→ b

24) Eliminate left recursion from the following grammar: 35) Given the following grammar:
S → Aa | b S → a | (L)
A → Ac | Sd | ϵ L→ L,S|S
a. Is the grammar suitable for predictive parser?
25) Write the algorithm to eliminate left recursion b. Do the necessary changes to make it suitable for LL(1) parser
26) What is left factoring? What is the need for left factoring? How to do left factoring? c. Compute FIRST and FOLLOW sets for each non-terminal
Write the algorithm for doing left-factoring d. Obtain the parsing table and check whether the resulting grammar is LL(1) or not.
e. Show the moves made by the predictive parser on the input “( a , ( a , a ) )”

27) Do the left-factoring for the following grammar: 36) Given the following grammar:
E → 5+T|3–T
S → iCtS | iCtSeS | a T → V | V*V | V+V
C → b V→ a|b
a. Is the grammar suitable for predictive parser?
28) Briefly explain the problems associated with top-down parser?
b. What is the use of left-factoring? Do the left factoring for the above grammar
29) What is a predictive parser? Explain the working of predictive parser. c. Compute FIRST and FOLLOW sets for each non-terminal
d. Without constructing the parsing table, check whether the grammar is LL(1)
30) What are the various components of predictive parser? How it works? e. By constructing the parsing table, check whether the grammar is LL(1).
31) Define FIRST and FOLLOW sets and write the rules to compute FIRST and 37) Given the following grammar:
FOLLOW sets Z → d | XYZ
32) Consider the following grammar: Y → ϵ|c
E → TE1 X→ Y|a
E1 → + TE1 |  a. Compute FIRST and FOLLOW sets for each non-terminal
T → FT1 b. Without constructing the parsing table, check whether the grammar is LL(1).
c. By constructing the parsing table, check whether the grammar is LL(1).
T1 → *FT1 | 
F → (E) | id 38) Left factor the following grammar and obtain LL(1) parsing table
a) Compute FIRST and FILLOW sets for the following grammar: E→T+E|T
b) Obtain the predictive parsing table T → float | float * T | (E)
c) Show the sequence of moves made by the parser for the string id+id*id
d) Add the synchronizing tokens for the above parsing table and show the sequence 39) How error recovery is done in predictive parsing
of moves made by parser for the string “ ) id * + id”
33) What is LL (1) grammar? How to check whether a given grammar is LL(1) or not
without constructing the predictive parser