Chapter 3 – Syntax Analysis

Principles of Context Free Grammar

• In formal language theory, Context Free Language (CFL) is a

language generated by Context Free Grammar. Four parameters define
context free grammar (G).
• G= {V, ∑ , S, P}
• V: Set of Variable or Non Terminal Symbols.
• ∑: Set of terminal symbols
• S: Start Symbol
• P: Production Rule
• For generating a language that generates an equal number of a’s and
b’s is in the format of anbn. The context free grammar is as follows.
• G = {(S,A), (a,b), (S ->aAb, A -> aAb | ϵ )}
• Considering the start symbol,
• S–>aAb
• By applying A -> aAb
• →aa Abb
• By applying A -> aAb again,
• →aaaAbbb
• By applying A -> ϵ (This symbol denotes an empty string)
• →aaabbb
• →a3b3
• When considering the output, the number of a’s is equal to number
of b’s. It has the an bn form.
PARSING
• Parsing is the process to determine whether the start symbol can derive the
program or not.
• If the Parsing is successful then the program is a valid program otherwise
the program is invalid.
• There are generally two types of Parsers:
• Top-Down Parsers:
• In this Parsing technique we expand the start symbol to the whole program.
• Recursive Descent and LL parsers are the Top-Down parsers.
• Bottom-Up Parsers:
• In this Parsing technique we reduce the whole program to start symbol.
• Operator Precedence Parser, LR(0) Parser, SLR Parser, LALR Parser and CLR Parser
are the Bottom-Up parsers.
What is Recursive Descent Parser?

• Recursive Descent Parser uses the technique of Top-Down Parsing

without backtracking.
• It can be defined as a Parser that uses the various recursive procedure
to process the input string with no backtracking.
• It can be simply performed using a Recursive language.
• The first symbol of the string of R.H.S of production will uniquely
determine the correct alternative to choose.
Steps in Recursive descent Parser
• If input is Non-Terminal then call corresponding procedure of non-
terminal
• If input is terminal symbol then compare terminal with input symbol.
• If terminal = input symbol, increment the input pointer.
• If non-terminal produce more than one production then all the
production code should be return in corresponding procedure.
• There is no need to define the main function.
Example
E-> iE’ Eprime()
E’->+iE’|e {
Solution: If (input==‘+’)
Input++;
E() If (input==‘i’)
Input++;
{
Eprime();
If (input==‘I’)
else
Input++;
Return();
Eprime();
}
}
Predictive Parser (or) Non- Recursive Predictive Parsing
(or) LL(1) Parser
• Predictive parser has the capability to predict which production is to be
used to replace the input string. The predictive parser does not suffer
from backtracking.
• To accomplish its tasks, the predictive parser uses a look-ahead pointer,
which points to the next input symbols.
• To make the parser back-tracking free, the predictive parser puts some
constraints on the grammar and accepts only a class of grammar known
as LL(k) grammar.
•
Components of Predictive Parsing
• A LL(1) parser has the following components:
(1) buffer: an input buffer which contains the string to be passed
(2) stack: a pushdown stack which contains a sequence of grammar symbols
(3) A parsing table: a 2d array M[A, a]
where
A->non-terminal, a->terminal or $
(4) output stream:
end of the stack and an end of the input symbols are both denoted with $
• LL parser is denoted as LL(k). The first L in LL(k) is parsing the input from left to right,
the second L in LL(k) stands for left-most derivation and k itself represents the number of
look aheads. Generally k = 1, so LL(k) may also be written as LL(1).
Construction of LL(1) Parser
• Remove the Left Recursion
• Eliminate Left Factoring
• Find FIRST() and FOLLOW()
• Construct the Parsing table
• Check Whether the string is accepting by parser or not
Construction of Parsing Table
• Parsing table that shows which production rule to select from several
alternatives available for expanding a given non-terminal and the first
terminal symbol that should be produced by that non-terminal.
• The parsing table consists of rows and columns where there are row
for each non-terminal and a column for each terminal symbol
including $, the end marker for the input string.
Algorithm for Construction of Parsing Table:
• The main Concept ->With the help of FIRST() and FOLLOW() sets,
this parsing can be done using just a stack that avoids the recursive
calls.
• For each rule, A->x in grammar G:
• For each terminal ‘a’ contained in FIRST(A) add A->x to M[A, a] in the
parsing table if x derives ‘a’ as the first symbol.

• If FIRST(A) contains null production for each terminal ‘b’ in FOLLOW(A),

add this production (A->null) to M[A, b] in the parsing table.
Bottom-up parsing
• Bottom-up parsing starts from the leaf nodes of a tree and works in
upward direction till it reaches the root node.
• Here, we start from a sentence and then apply production rules in
reverse manner in order to reach the start symbol.
 Shift-Reduce Parsing

• Shift-reduce parsing uses two unique steps for bottom-up parsing. These
steps are known as shift-step and reduce-step.
• Shift step: The shift step refers to the advancement of the input pointer to
the next input symbol, which is called the shifted symbol. This symbol is
pushed onto the stack. The shifted symbol is treated as a single node of
the parse tree.
• Reduce step : When the parser finds a complete grammar rule (RHS)
and replaces it to (LHS), it is known as reduce-step. This occurs when the
top of the stack contains a handle. To reduce, a POP function is
performed on the stack which pops off the handle and replaces it with
LHS non-terminal symbol.
LR Parser
 LR Parser

• LR parsing is one type of bottom up parsing.

• It is used to parse the large class of grammars.
• In the LR parsing, "L" stands for left-to-right scanning of the input.
• "R" stands for constructing a right most derivation in reverse.
• "K" is the number of input symbols of the look ahead used to make number of
parsing decision.
Types of LR Parser
• LR parsing is divided into four parts: LR (0) parsing, SLR parsing, CLR parsing
and LALR parsing.
• SLR(1) – Simple LR Parser:
• Works on smallest class of grammar
• Few number of states, hence very small table
• Simple and fast construction
• LR(1) – LR Parser:
• Works on complete set of LR(1) Grammar
• Generates large table and large number of states
• Slow construction
• LALR(1) – Look-Ahead LR Parser:
• Works on intermediate size of grammar
• Number of states are same as in SLR(1)
LR algorithm

• The LR algorithm requires stack, input, output and parsing table. In all
type of LR parsing, input, output and stack are same but parsing table
is different.
• Input buffer is used to indicate end of input and it contains the string to
be parsed followed by a $ Symbol.
• A stack is used to contain a sequence of grammar symbols with a $ at
the bottom of the stack.
• Parsing table is a two dimensional array. It contains two parts: Action
part and Go To part.