COMPILER DESIGN UNIT - 2

Syntax Analysis
Syntax analysis is a second phase of the compiler design process that comes
after lexical analysis. It analyses the syntactical structure of the given input. It
checks if the given input is in the correct syntax of the programming language in
which the input which has been written. It is known as the Parse Tree or Syntax
Tree.
The Parse Tree is developed with the help of pre-defined grammar of the
language. The syntax analyzer also checks whether a given program fulfills the
rules implied by a context-free grammar. If it satisfies, the parser then creates the
parse tree of that source program. Otherwise, it will display error messages.

Need for Syntax Analyzer:

 Check if the code is valid grammatically
 The syntactical analyzer helps you to apply rules to the code
 Helps us to make sure that each opening brace has a corresponding closing
balance
 Each declaration has a type and that the type must be exists
Department of Computer Science,
Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 1
COMPILER DESIGN UNIT - 2

Terminologies in Syntax Analyzer:

 Sentence: A sentence is a group of character over some alphabet.
 Lexeme: A lexeme is the lowest level syntactic unit of a language (e.g.,
total, start).
 Token: A token is just a category of lexemes.
 Keywords and reserved words: It is an identifier which is used as a fixed
part of the syntax of a statement. It is a reserved word which you can't use as
a variable name or identifier.
 Noise words: Noise words are optional which are inserted in a statement to
enhance the readability of the sentence.
 Comments: It is a very important part of the documentation. It mostly
display by, /* */, or//Blank (spaces)
 Delimiters: It is a syntactic element which marks the start or end of some
syntactic unit. Like a statement or expression, "begin"...''end", or {}.
 Character set: ASCII, Unicode
 Identifiers: It is a restrictions on the length which helps you to reduce the
readability of the sentence.
 Operator symbols: + and – performs two basic arithmetic operations.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 2
COMPILER DESIGN UNIT - 2

Differences b/w Syntax Analyzer & Lexical Analyzer

Syntax Analyzer Lexical Analyzer
The syntax analyzer mainly deals with The lexical analyzer eases the task of
recursive constructs of the language. the syntax analyzer.
The syntax analyzer works on tokens in The lexical analyzer recognizes the
a source program to recognize token in a source program.
meaningful structures in the
programming language.
It receives inputs, in the form of tokens, It is responsible for the validity of a
from lexical analyzers. token supplied by the syntax analyzer

Parsing
A parse also checks that the input string is well-formed, and if not, reject it.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 3
COMPILER DESIGN UNIT - 2

Following are important tasks perform by the parser:

 Helps us to detect all types of Syntax errors
 Find the position at which error has occurred
 Clear & accurate description of the error.
 Recovery from an error to continue and find further errors in the code.
 Should not affect compilation of "correct" programs.
 The parse must reject invalid texts by reporting syntax errors
Derivation
A derivation is basically a sequence of production rules, in order to get the
input string. During parsing, we take two decisions for some sentential form of
input:
 Deciding the non-terminal which is to be replaced.
 Deciding the production rule, by which, the non-terminal will be replaced.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 4
COMPILER DESIGN UNIT - 2

To decide which non-terminal to be replaced with production rule, we can have

two options.
Left-most Derivation
If the sentential form of an input is scanned and replaced from left to right, it
is called left-most derivation. The sentential form derived by the left-most
derivation is called the left-sentential form.
Right-most Derivation
If we scan and replace the input with production rules, from right to left, it is
known as right-most derivation. The sentential form derived from the right-most
derivation is called the right-sentential form.
Example:
Production rules:
E→E+E
E→E*E
E → id
Input string: id + id * id
The left-most derivation is:
E→E*E
E→E+E*E
E → id + E * E
E → id + id * E
E → id + id * id
Notice that the left-most side non-terminal is always processed first.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 5
COMPILER DESIGN UNIT - 2

The right-most derivation is:

E→E+E
E→E+E*E
E → E + E * id
E → E + id * id
E → id + id * id
Parse Tree
A parse tree is a graphical depiction of a derivation. It is convenient to see
how strings are derived from the start symbol. The start symbol of the derivation
becomes the root of the parse tree. Let us see this by an example from the last
topic.
In a parse tree:
 All leaf nodes are terminals.
 All interior nodes are non-terminals.
 In-order traversal gives original input string.
A parse tree depicts associativity and precedence of operators. The deepest
sub-tree is traversed first, therefore the operator in that sub-tree gets precedence
over the operator which is in the parent nodes.
We take the left-most derivation of a + b * c
The left-most derivation is:
E→E*E
E→E+E*E
E → id + E * E
E → id + id * E
E → id + id * id

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 6
COMPILER DESIGN UNIT - 2

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 7
COMPILER DESIGN UNIT - 2

Ambiguity
A grammar G is said to be ambiguous if it has more than one parse tree (left
or right derivation) for at least one string.
Example
E→E+E
E→E–E
E → id
For the string id + id – id, the above grammar generates two parse trees:

The language generated by an ambiguous grammar is said to be inherently

ambiguous. Ambiguity in grammar is not good for a compiler construction. No
method can detect and remove ambiguity automatically, but it can be removed by
either re-writing the whole grammar without ambiguity, or by setting and
following associativity and precedence constraints.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 8
COMPILER DESIGN UNIT - 2

Parsing Techniques
Parsing techniques are divided into two different groups:
1. Top-Down Parsing,
2. Bottom-Up Parsing
Top-Down Parsing:
In the top-down parsing construction of the parse tree starts at the root and
then proceeds towards the leaves.
Two types of Top-down parsing are:
 Predictive Parsing / Non – Recursive Descent Parsing
 Recursive Descent Parsing
Predictive Parsing:
Predictive parse can predict which production should be used to replace the
specific input string. The predictive parser uses look-ahead point, which points
towards next input symbols. Backtracking is not an issue with this parsing
technique. It is known as LL(1) Parser
Recursive Descent Parsing:
This parsing technique recursively parses the input to make a prase tree. It
consists of several small functions, one for each nonterminal in the grammar. It is
also known as Brute force parser or the with backtracking parser. It basically
generates the parse tree by using brute force and backtracking.
Bottom-Up Parsing:
In the bottom-up parsing technique the construction of the parse tree starts
with the leave, and then it processes towards its root. It is also called as shift-
reduce parsing. This type of parsing is created with the help of using some
software tools.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 9
COMPILER DESIGN UNIT - 2

LR parser:
LR parser is the bottom-up parser which generates the parse tree for the
given string by using unambiguous grammar. It follow reverse of right most
derivation. LR parser is of 4 types:
 LR(0)
 SLR(1)
 LALR(1)
 CLR(1)
Operator precedence parser:
It generates the parse tree form given grammar and string but the only
condition is two consecutive non-terminals and epsilon never appear in the right-
hand side of any production.

Recursive Descent Parser:

 It is a kind of Top-Down Parser.
Department of Computer Science,
Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 10
COMPILER DESIGN UNIT - 2

 A top-down parser builds the parse tree from the top to down, starting with
the start non-terminal.
 A Predictive Parser is a special case of Recursive Descent Parser, where no
Back Tracking is required.
 By carefully writing a grammar means eliminating left recursion and left
factoring from it, the resulting grammar will be a grammar that can be
parsed by a recursive descent parser.
Example:

**Here e is Epsilon

Back-tracking

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 11
COMPILER DESIGN UNIT - 2

Top- down parsers start from the root node (start symbol) and match the
input string against the production rules to replace them (if matched). To
understand this, take the following example of CFG:
Consider the grammar G : S → cAd
A → ab | a
and the input string w=cad.
The parse tree can be constructed using the following top-down approach:
Step1: Initially create a tree with single node labeled S. An input pointer points to
‘c’, the first symbol of w. Expand the tree with the production of S.

Step2: The leftmost leaf ‘c’ matches the first symbol of w, so advance the input
pointer to the second symbol of w ‘a’ and consider the next leaf ‘A’. Expand A
using the first alternative.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 12
COMPILER DESIGN UNIT - 2

Step 3: The second symbol ‘a’ of w also matches with second leaf of tree. So
advance the input pointer to third symbol of w‘d’. But the third leaf of tree is b
which does not match with the input symbol d. Hence discard the chosen
production and reset the pointer to second position. This is called backtracking.
Step 4: Now try the second alternative for A.

Now we can halt and announce the successful completion of parsing.

In recursive descent parsing, the parser may have more than one
production to choose from for a single instance of input, whereas in predictive
parser, each step has at most one production to choose. There might be instances
where there is no production matching the input string, making the parsing
procedure to fail.
Example for recursive decent parsing:
A left-recursive grammar can cause a recursive-descent parser to go into an infinite
loop.
Hence, elimination of left-recursion must be done before parsing.
Consider the grammar for arithmetic expressions
E → E+T | T
T → T*F | F
F → (E) | id
Department of Computer Science,
Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 13
COMPILER DESIGN UNIT - 2

After eliminating the left-recursion the grammar becomes,

E → TE’
E’ → +TE’ | ε
T → FT’
T’ → *FT’ | ε
F → (E) | id
Now we can write the procedure for grammar as follows:
Recursive procedure:
Procedure E()
begin
T( );
EPRIME( );
end
Procedure EPRIME( )
begin
If input_symbol=’+’ then
ADVANCE( );
T( );
EPRIME( );
end

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 14
COMPILER DESIGN UNIT - 2

Procedure T( )
begin
F( );
TPRIME( );
End
begin
If input_symbol=’*’ then
ADVANCE( );
F( );
TPRIME( );
end
Procedure F( )
If input-symbol=’id’ then
ADVANCE( );
else if input-symbol=’(‘ then
begin
ADVANCE( );
E( );
else if input-symbol=’)’ then
ADVANCE( );
else ERROR()
end
else ERROR( )

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 15
COMPILER DESIGN UNIT - 2

Stack implementation:

Predictive Parser
Predictive parser is a recursive descent parser, which 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.
 Predictive parsing is a special case of recursive descent parsing where no
backtracking is required.
 The key problem of predictive parsing is to determine the production to be
applied for a non terminal in case of alternatives.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 16
COMPILER DESIGN UNIT - 2

Predictive parsing uses a stack and a parsing table to parse the input and generate a
parse tree. Both the stack and the input contains an end symbol $ to denote that the
stack is empty and the input is consumed.
The parser refers to the parsing table to take
any decision on the input and stack element
combination.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 17
COMPILER DESIGN UNIT - 2

A predictive parser looks like:

• Rather than writing code, we build tables.

• Building tables can be automated!.

The table-driven predictive parser has an input buffer, stack, a parsing table and an
output stream.
Input buffer: It consists of strings to be parsed, followed by $ to indicate the end of
the input string.
Stack: It contains a sequence of grammar symbols preceded by $ to indicate the
bottom of the stack. Initially, the stack contains the start symbol on top of $.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 18
COMPILER DESIGN UNIT - 2

Parsing table: It is a two-dimensional array M[A, a], where ‘A’ is a non-terminal

and ‘a’ is a terminal.
Predictive parsing program: The parser is controlled by a program that considers
X, the symbol on top of stack, and a, the current input symbol. These two symbols
determine the parser action. There are three possibilities:
1. If X = a = $, the parser halts and announces successful completion of parsing.
2. If X = a ≠ $, the parser pops X off the stack and advances the input pointer to the
next input symbol.
3. If X is a non-terminal , the program consults entry M[X, a] of the parsing table
M.
Algorithm for nonrecursive predictive parsing:
Input : A string w and a parsing table M for grammar G.
Output : If w is in L(G), a leftmost derivation of w; otherwise, an error indication.
Method : Initially, the parser has $S on the stack with S, the start symbol of G on
top, and w$ in the input buffer.
Predictive parsing table construction:
The construction of a predictive parser is aided by two functions associated with a
grammar G :
1. FIRST
2. FOLLOW

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 19
COMPILER DESIGN UNIT - 2

Rules for first( ):

1. If X is terminal, then FIRST(X) is {X}.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X is non-terminal and X → aα is a production then add a to FIRST(X).
4. If X is non-terminal and X → Y1 Y2…Yk is a production, then place a in
FIRST(X) if for some
i, a is in FIRST(Yi), and ε is in all of FIRST(Y1),…,FIRST(Yi-1); that is, Y1,
….Yi-1=> ε. If ε
is in FIRST(Yj) for all j=1,2,..,k, then add ε to FIRST(X).
Rules for follow( ):
1. If S is a start symbol, then FOLLOW(S) contains $.
2. If there is a production A → αBβ, then everything in FIRST(β) except ε is
placed in follow(B).
3. If there is a production A → αB, or a production A → αBβ where FIRST(β)
contains ε, then everything in FOLLOW(A) is in FOLLOW(B
Algorithm for construction of predictive parsing table:
Input : Grammar G
Output : Parsing table M
Method :
1. For each production A → α of the grammar, do steps 2 and 3.
2. For each terminal a in FIRST(α), add A → α to M[A, a].
3. If ε is in FIRST(α), add A → α to M[A, b] for each terminal b in FOLLOW(A).
If ε is in FIRST(α) and $ is in FOLLOW(A) , add A → α to M[A, $].
4. Make each undefined entry of M be error.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 20
COMPILER DESIGN UNIT - 2

LL(1) grammar:
The parsing table entries are single entries. So each location has not more than
one entry. This type of grammar is called LL(1) grammar.
Consider this following grammar:
S → iEtS | iEtSeS | a
E→b

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 21
COMPILER DESIGN UNIT - 2

After eliminating left factoring, we have

S → iEtSS’ | a
S’→ eS | ε
E→b
To construct a parsing table, we need FIRST() and FOLLOW() for all the non-
terminals.
FIRST(S) = { i, a }
FIRST(S’) = {e, ε }
FIRST(E) = { b}
FOLLOW(S) = { $ ,e }
FOLLOW(S’) = { $ ,e }
FOLLOW(E) = {t}

Since there are more than one production, the grammar is not LL(1) grammar.
Actions performed in predictive parsing:
1. Shift
2. Reduce
3. Accept
4. Error

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 22
COMPILER DESIGN UNIT - 2

Implementation of predictive parser:

1. Elimination of left recursion, left factoring and ambiguous grammar.
2. Construct FIRST() and FOLLOW() for all non-terminals.
3. Construct predictive parsing table.
4. Parse the given input string using stack and parsing table.
LL Parser
An LL Parser accepts LL grammar. LL grammar is a subset of context-free
grammar but with some restrictions to get the simplified version, in order to
achieve easy implementation. LL grammar can be implemented by means of both
algorithms namely, recursive-descent or table-driven.
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).

LL Parsing Algorithm
We may stick to deterministic LL(1) for parser explanation, as the size of
table grows exponentially with the value of k. Secondly, if a given grammar is not
LL(1), then usually, it is not LL(k), for any given k.
Given below is an algorithm for LL(1) Parsing:

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 23
COMPILER DESIGN UNIT - 2

Input:
string ω
parsing table M for grammar G
Output:
If ω is in L(G) then left-most derivation of ω,
error otherwise.
This is true for both top-down (LL) and bottom-up (LR) parsers.
BOTTOM-UP PARSING
 Bottom-up parsers construct parse trees starting from the leaves and work up
to the root.
 Bottom-up syntax analysis is also termed as shift-reduce parsing.
 The common method of shift-reduce parsing is called LR parsing.
 Operator precedence parsing is an easy-to-implement shift-reduce parser.
 Shift-reduce parsing try to build a parse tree for an input string beginning at
the leaves (the bottom) and working up towards the root (the top).
 At each and every step of reduction, the right side of a production which
matches with the substring is replaced by the left side symbol of the
production.
 If the substring is chosen correctly at each step, a rightmost derivation is
traced out in reverse.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 24
COMPILER DESIGN UNIT - 2

Handles
A handle of a string is a substring that matches the right side of a production
and whose reduction to the non-terminal on the left side of the production
represents one step along the reverse of a rightmost derivation.
Precise definition of a handle
A handle of a right-sentential form ɣ is a production A -->βand a position of
ɣ where the string βmay be found and replaced by A to produce the previous right-
sentential form in a rightmost derivation of ɣ.

The string w to the right of the handle contains only terminal symbols.

(eg.) Consider the grammar

Department of Computer Science,
Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 25
COMPILER DESIGN UNIT - 2

S -->αABe
A --> Abc I b
B --> d
The sentence abbcde can be reduced to S by the following steps.
abbcde
aAbcde
aAde
aABe
s
These reductions trace out the following rightmost derivation in reverse.

Handle Pruning
 If A -->β is a production then reducing βto A by the given production is
called handle pruning i.e., removing the children of A from the parse tree.
 A rightmost derivation in reverse can be obtained by handle pruning.
Start with a string of terminals ω that is to parse. If ω is a sentence of the
grammar at hand, then ω= ɣn where ɣn is the nth right sentential form of some as
yet unknown rightmost derivation.

Example for right sentential form and handle for grammar

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 26
COMPILER DESIGN UNIT - 2

E --> E+E
E --> E*E
E --> (E)
E --> id

Shift-reduce Parsing
 Shift Reduce parsing is a bottom-up parsing that reduces a string w to the
start symbol of grammar.
 It scans and parses the input text in one forward pass without backtracking.
Stack implementation of shift-reduce parsing
 Handle pruning must solve the following two problems to perform parsing:
o Locating the substring to be reduced in a right sentential form.
o Determining what production to choose in case there is more than one
productions with that substring on the right side.
 The type of data structure to use in a shift-reduce parser.
Implementation of shift-reduce parser

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 27
COMPILER DESIGN UNIT - 2

Shift-reduce parser can be implemented by using the following components:

• Stack is used to hold grammar symbols.
• An input buffer is used to hold the string w to be parsed.
• $ is used to mark the bottom of the stack and also the right end of the input.
• Initially the stack is empty and the string ωis on the input, as follows:
Stack Input
$ ω$
• The parser processes by shifting zero or more input symbols onto the stack until a
handle β is on top of the stack.
• The parser then reduces β to the left side of the appropriate production.
• The parser repeats this cycle until it has detected an error or until the stack
contains the start symbol and the input is empty.
Stack Input
$S $
• When the input buffer reaches the end marker symbol $ and the stack contains the
start symbol, the parser halts and announces successful completion of parsing.
Actions in shift-reduce parser
A shift-reduce parser can make four possible actions viz:
1) shift
2) reduce
3) accept
4) error.

• A shift action, shifts the next symbol onto the top of the stack.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 28
COMPILER DESIGN UNIT - 2

• A reduce action, replaces the symbol on the right side of production by the
symbol on left side of the production concerned.
To perform reduction, the parser must know the right end of the handle
which is at the top of the stack. Then the left end of the handle within the stack is
located and the non-terminal to replace the handle is decided.
• An accept action, initiates the parser to announce successful completion of
parsing.
• An error action, discovers that a syntax error has occurred and calls an error
recovery routine.
Note:
An important fact that justifies the use of a stack in shift-reduce parsing is
that the handle will always appear on top of the stack and never inside.
(eg.) Consider the grammar
E --> E+E
E --> E*E
E --> (E)
E --> id
and the input string id1+ id2 * id3. Use the shift-reduce parser to check
whether the input string is accepted by the above grammar.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 29
COMPILER DESIGN UNIT - 2

Viable prefixes
The set of prefixes of right sentential forms that can appear on the stack of a
shift-reduce parser are called viable prefixes.
Conflicts during shift-reduce parsing
• Shift-reduce parsing cannot be used in context free grammar.
• For every shift-reduce parser, such grammar can reach a configuration in which
the parser cannot decide whether to shift or to reduce (a shift-reduce conflict), or
cannot decide which of the several reductions to make (a reduce/reduce conflict),
by knowing the entire stack contents and the next input symbol.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 30
COMPILER DESIGN UNIT - 2

(eg.)
• An ambiguous grammar can never be LR. Consider dangling-else grammar,
Stmt-->if expr then stmt
I if expr then stmt else stmt
I other
• In this grammar a shift/reduce conflict occurs for some input string.
• So this grammer is not LR(l) grammar.
Operator Parsing
Operator precedence grammar is kinds of shift reduce parsing method. It is
applied to a small class of operator grammars.
A grammar is said to be operator precedence grammar if it has two
properties:
No R.H.S. of any production has a∈.
No two non-terminals are adjacent.
Operator precedence can only established between the terminals of the grammar. It
ignores the non-terminal.
There are the three operator precedence relations:
 a ⋗ b means that terminal "a" has the higher precedence than terminal "b".
 a ⋖ b means that terminal "a" has the lower precedence than terminal "b".
 a ≐ b means that the terminal "a" and "b" both have same precedence.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 31
COMPILER DESIGN UNIT - 2

Precedence table:

Parsing Action
 Both end of the given input string, add the $ symbol.
 Now scan the input string from left right until the ⋗ is encountered.
 Scan towards left over all the equal precedence until the first left most ⋖ is
encountered.
 Everything between left most ⋖ and right most ⋗ is a handle.
 $ on $ means parsing is successful.
Example
Grammar:
E → E+T/T
T → T*F/F
F → id
Given string:
w = id + id * id
Let us consider a parse tree for it as follows:

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 32
COMPILER DESIGN UNIT - 2

On the basis of above tree, we can design following operator precedence table:

Now let us process the string with the help of the above precedence table:

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 33
COMPILER DESIGN UNIT - 2

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.
 LR parsing is divided into four parts: LR (0) parsing, SLR parsing, CLR
parsing and LALR parsing.

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.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 34
COMPILER DESIGN UNIT - 2

 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.
LR (1) Parsing
Various steps involved in the LR (1) Parsing:
 For the given input string write a context free grammar.
 Check the ambiguity of the grammar.
 Add Augment production in the given grammar.
 Create Canonical collection of LR (0) items.
 Draw a data flow diagram (DFA).
 Construct a LR (1) parsing table.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 35
COMPILER DESIGN UNIT - 2

Augment Grammar
Augmented grammar G` will be generated if we add one more production in
the given grammar G. It helps the parser to identify when to stop the parsing and
announce the acceptance of the input.
Example
Given grammar
S → AA
A → aA | b
The Augment grammar G` is represented by
S`→ S
S → AA
A → aA | b
Parser Generator
YACC is an automatic tool that generates the parser program.
YACC
 YACC stands for Yet Another Compiler Compiler.
 YACC provides a tool to produce a parser for a given grammar.
 YACC is a program designed to compile a LALR (1) grammar.
 It is used to produce the source code of the syntactic analyzer of the
language produced by LALR (1) grammar.
 The input of YACC is the rule or grammar and the output is a C program.
These are some points about YACC:
Input: A CFG- file.y
Output: A parser y.tab.c (yacc)

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 36
COMPILER DESIGN UNIT - 2

The output file "file.output" contains the parsing tables.

The file "file.tab.h" contains declarations.
The parser called the yyparse ().
Parser expects to use a function called yylex () to get tokens.
The basic operational sequence is as follows:

This file contains the desired grammar in YACC format.

It shows the YACC program.

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 37
COMPILER DESIGN UNIT - 2

It is the c source program created by YACC.

C Compiler

Executable file that will parse grammar given in gram.Y

Department of Computer Science,

Sri Lakshmi College of Arts & Science,
Kallakurichi
Page | 38