Syntax analysis

Role of parser
● Syntax analysis or parsing is the second phase of a compiler.
● A lexical analyzer can identify tokens with the help of regular expressions and pattern
rules.
● But a lexical analyzer cannot check the syntax of a given sentence due to the
limitations of the regular expressions. Regular expressions cannot check
balancing tokens, such as parenthesis.
● Therefore, this phase uses context-free grammar (CFG), which is recognized by
push-down automata.
● The output of a syntax analyzer is a parse tree.
● For performing the syntax analysis, the grammar of the language has to be specified.
● CFG is used to define the grammar of the language. This process of verifying whether
an input string matches the grammar of the language is called parsing.

● The parser to report any syntax errors in an intelligible fashion and to

recover from commonly occurring errors to continue processing the
remainder of the program.
● There are three general types of parsers for grammars:
1. universal,
2. top-down,
3. bottom-up.
● The methods commonly used in compilers can be classified as being either top-
down or bottom-up.
 ● As implied by their names, top-down methods build parse trees from the
top (root) to the bottom (leaves), while bottom-up methods start from
the leaves and work their way up to the root.
● In either case, the input to the parser is scanned from left to right, one
symbol at a time.

Syntax Error Handling

● If compilers handled only correct programs, design would be simpler.

● But compilers must help programmers locate and fix errors.

● Most languages don’t specify error handling it is left to compiler designer

Common programming errors can occur at many different levels.

1. Lexical errors include misspellings of identifiers, keywords, or operators - e.g.,

the use of an identifier elipseSize instead of ellipseSize - and missing quotes
around text intended as a string.
2. Syntactic errors include misplaced semicolons or extra or missing braces; that
is, { or }.
3. Semantic errors include type mismatches between operators and operands,
e.g., the return of a value in a Java method with result type void.
4. Logical errors can be anything from incorrect reasoning on the part of the
programmer to the use in a C program of the assignment operator = instead of
the comparison operator ==.

Error-Recovery Strategies
When an error is detected, the parser must recover to continue parsing.

● If errors are too many → compiler stops after a limit to avoid spurious errors.

1. Panic-Mode Recovery
● With this method, on discovering an error, the parser discards input symbols
one at a time until one of a designated set of synchronizing tokens is found. The
synchronizing tokens are usually delimiters, such as semicolon or }
● Pros: Simple, avoids infinite loops.
● Cons: May skip large portions of code.
2. Phrase -level recovery
● On discovering an error, a parser may perform local correction on the remaining
input; that is, it may replace a prefix of the remaining input by some string that
allows the parser to continue.
● Atypical local correction is to replace a comma by a semicolon, delete an
extraneous semicolon, or insert a missing semicolon.

● Pros: Can correct any input string.

● Cons: May misinterpret actual error location, risk of infinite loops.
 3. Error Productions
● By anticipating common errors that might be encountered, we can augment the grammar for the
language at hand with productions that generate the erroneous constructs.
● Detects known error patterns and provides specific diagnostics.

4. Global correction
Attempts to transform the erroneous input into a valid program with minimal changes (insertions,
deletions, substitutions).
 Ensures the corrected string is as close as possible to the original input.
 Drawback: Very costly in time and space, so mostly theoretical.

REVIEW OF CONTEXT FREE GRAMMARS

A grammar is defined as a quadruple G= (V, T, P, S)

V = Set of variables, [Link]-Terminals

T = Terminal symbols
P = Set of productions

S = Start symbol

A grammar G = (V, T, P, S) is said to be context free, if all productions in P have the form α→β, where |α | <=
|β| and α is element of V. That is, left-hand side contains only non- terminals. Right hand side is string
of terminals and/or non-terminals

A context-free grammar (grammar for short) consists of terminals, nonterminal, a start

symbol, and productions.
1. Terminals are the basic symbols from which strings are formed. The term "token
name" is a synonym for "terminal" and frequently we will use the word "token" for terminal
when it is clear that we are talking about just the token name.

2. Non terminals are syntactic variables that denote sets of strings. The non-terminals
define sets of strings that help define the language generated by the grammar. They also
impose a hierarchical structure on the language that is useful for both syntax analysis and
translation.

3. In a grammar, one nonterminal is distinguished as the start symbol, and the

set of strings it denotes is the language generated by the grammar.
Conventionally, the productions for the start symbol are listed first.
[Link] productions of a grammar specify the manner in which the terminals and non
terminals can be combined to form strings. Each production consists of:

● A nonterminal called the head or left side of the production; this production defines
some of the strings denoted by the head.
● The symbol →. Sometimes : : = has been used in place of the arrow.
 ● A body or right side consisting of zero or more terminals and non-terminals.

All the production rules are of the form X→Y. Production rules are the heart of the
grammar. Consider the production rules

S → aSB, S → aB ,B → b

Here, V= {S, B} , T={a, b} and Starting symbol is S. Using this production rule , we
can derive the string aabb by

S → aSB

→ aaBB

→ aabB

→aabb

Here all the individual steps are called sentential form or Sequential form. All
steps together called Derivation

Eg: Let V= {S, C} , T={a, b} P={S→aCa, C→aCa, C→b}. Generate the string
2 2
a ba from the grammar given above?

S → aCa

→aaCaa

→aabaa
2 2
→ a ba

EXAMPLE:

The grammar with the following productions defines simple arithmetic

expression:
DERIVATION TREES AND PARSE TREES
The construction of a parse tree can be made precise by taking a derivational view, in
which productions are treated as rewriting rules.

Beginning with the start symbol, each rewriting step replaces a nonterminal by the
body of one of its productions.

For example, consider the following grammar, with a single nonterminal E:

E → E + E | E * E | E- E | ( E ) | id

The production E → - E signifies that if E denotes an expression, then – E must also

denote an expression. The replacement of a single E by - E will be described by writing

E => -E which is read, "E derives - E."

The production E -+ ( E ) can be applied to replace any instance of E in any string of

grammar

symbols by (E) , e.g., E * E => (E) * E or E * E => E * (E)

We can take a single E and repeatedly apply productions in any order to get a
sequence of replacements. For example, E => - E => - (E) => - (id)

We call such a sequence of replacements a derivation of - (id) from E. This derivation

provides a proof that the string - (id) is one particular instance of an expression.
Leftmost and Rightmost Derivation of a String

Leftmost derivation − A leftmost derivation is obtained by applying production to

the leftmost variable in each step.

Rightmost derivation − A rightmost derivation is obtained by applying production to

the rightmost variable in each step.

Example

Let any set of production rules in a CFG be

X → X+X | X*X |X| a

over an alphabet {a}.

The leftmost derivation for the string "a+a*a" may be –

X → X+X → a+X → a + X*X → a+a*X → a+a*a

The stepwise derivation of the above string is shown as below –

The rightmost derivation for the above string "a+a*a" may be

X → X*X → X*a → X+X*a → X+a*a → a+a*a

Parse Tree
 Parse tree is a hierarchical structure which represents the derivation of the
grammar to yield input strings.
 Simply it is the graphical representation of derivations.
 Root node of parse tree has the start symbol of the given grammar from where
the derivation proceeds.
 Leaves of parse tree are labelled by non-terminals or terminals.
 Each interior node is labelled by some non -terminals
 If A ->xyz is a production, then the parse tree will have A as interior node
whose children are x, y and z from its left to right.
Yield Of Parse Tree
 The leaves of the parse tree are labelled by non-terminals or terminals and read
from left to right, they constitute a sentential form, called the yield or frontier of
the tree.
 Figure above represents the parse tree for the string id+ id*id. The string id +
id * id, is the yield of parse tree depicted in Figure.

AMBIGUITY
 An ambiguous grammar is one that produces more than one leftmost or more
than one rightmost derivation for the same sentence
 For most parsers, it is desirable that the grammar be made unambiguous, for if
it is not, we cannot uniquely determine which parse tree to select for a
sentence.
 In other cases, it is convenient to use carefully chosen ambiguous grammars,
together with disambiguating rules that "throw away" undesirable parse trees,
leaving only one tree for each sentence.
Associativity and precedence of operators
1. Operator Precedence

 Precedence decides priority of operators.

 Higher precedence operators are evaluated before lower precedence ones.

 Eg: a + b * c , Here * has higher precedence than +, so it is evaluated as a +

(b * c)

2. Operator Associativity

 Associativity decides order of evaluation when two operators of same

precedence appear in an expression.

 Example: a - b – c , Both - have the same precedence. If associativity is left to

right, it becomes (a - b) - c.
If it were right to left, it would be a - (b - c)

Precedence (High → Associativi

Operators
Low) ty

Left to
1 (), [], . , ->
Right

++, --, + (unary), - Right to

2
(unary), !, ~ Left

3 *, /, % Left to
 Precedence (High → Associativi
Operators
Low) ty

Right

Left to
4 +, -
Right

Left to
5 <<, >>
Right

Left to
6 <, <=, >, >=
Right

Left to
7 ==, !=
Right

Left to
8 & (bitwise AND)
Right

Left to
9 ^ (bitwise XOR)
Right

` (bitwise
10 `
OR)

Left to
11 && (logical AND)
Right

12 `

Right to
13 ?: (ternary)
Left

Right to
14 =, +=, -=, *=, /=, etc.
Left

Left to
15 (Lowest) , (comma)
Right

PARSING
Definition: Parsing is the process of determining if a string of token can be generated
by a grammar.

Mainly 2 parsing approaches:

1. Top-Down Parsing
2. Bottom-Up Parsing
 In top-down parsing, parse tree is constructed from top (root) to the bottom
(leaves).
 In bottom-up parsing, parse tree is constructed from bottom (leaves)) to the top
(root).

 It can be viewed as an attempt to construct a parse tree for the input

starting from the root and creating the nodes of parse tree in preorder.
 Pre-order traversal means: 1. Visit the root 2. Traverse left subtree 3. Traverse
right subtree.

1) TOP -DOWN PARSING

 In top-down parsing, parse tree is constructed from top (root) to the bottom
(leaves).
 Top-down parsing can be viewed as an attempt to find a leftmost derivation for an input string
(that is expanding the leftmost terminal at every step).

RECURSIVE DESCENT PARSING

 It is the most general form of top-down parsing.

 It may involve backtracking, that is making repeated scans of input, to obtain the correct expansion of
 the leftmost non-terminal.

 Unless the grammar is ambiguous or left-recursive, it finds a suitable parse tree

 A recursive-descent parsing program consists of a set of procedures, one for each nonterminal.
 Execution begins with the procedure for the start symbol, which halts and announces success if its
procedure body scans the entire input string.
 General recursive-descent may require backtracking; that is, it may require repeated scans over
the input.
 However, backtracking is rarely needed to parse programming language constructs, so
backtracking parsers are not seen frequently

 To construct a parse tree for this string top down, we initially create a tree consisting
of a single node labelled S.
 An input pointer points to c, the first symbol of w. S has only one production, so
we use it to expand S and obtain the tree as:

 The leftmost leaf, labelled c, matches the first symbol of input w, so we advance
the input pointer to a, the second symbol of w, and consider the next leaf,
labelled A.
 Now, we expand A using the first alternative A → ab to obtain the tree as:
  We have a match for the second input symbol, a, so we advance the input pointer
to d,
the third input symbol, and compare d against the next leaf, labelled b.
 Since b does not match d, we report failure and go back to A to see whether
there is another alternative for A that has not been tried, but that might
produce a match.
 In going back to A, we must reset the input pointer to position 2 , the position
it had when we first came to A, which means that the procedure for A must
store the input pointer in a local variable.
 The second alternative for A produces the tree as:

 The leaf a match the second symbol of w and the leaf d match the third symbol.
Since we have produced a parse tree for w, we halt and announce successful
completion of parsing. (that is the string parsed completely and the parser stops).
 If the grammar is left recursive, the parser falls into infinite recursion (A → A
α | β)

RECURSIVE PREDICTIVE PARSING

A predictive parsing is a special form of recursive-descent parsing, in which the
current input token unambiguously determines the production to be applied at each
step.

The goal of predictive parsing is to construct a top-down parser that never

backtracks. To do so, we must transform a grammar in two ways:
  Eliminate left recursion, and

 Perform left factoring.

These rules eliminate most common causes for backtracking although they do not guarantee a
completely backtrack-free parsing (called LL(1).)

Left Recursion

A grammar is said to be left –recursive if it has a non-terminal A such that there is a derivation
A  A, for some string .
EXAMPLE

Consider the grammar

 It recognizes the regular expression *. The problem is that if we use the first
production for top-down derivation, we will fall into an infinite derivation chain.
This is called left recursion.
 Top–down parsing methods cannot handle left recursive grammars, so a
transformation that eliminates left-recursion is needed. The left-recursive pair of
productions A  A| could be replaced by two non-recursive productions.

Q)
 No matter how many A-productions there are, we can eliminate immediate left recursion from them by
the following technique. First, we group the A productions as

Left Factoring

Left factoring is a grammar transformation that is useful for producing a

grammar suitable for predictive parsing.
The basic idea is that when it is not clear which of two alternative
productions to use to expand a non-terminal A, we may be able to rewrite
the A-productions to defer the decision until we have seen enough of the
input to make the right choice

are two A-productions, and the input begins with a non-empty string derived
from 
we do not know whether to expand A to  1 or  2.
However, we may defer the decision by expanding A to B. Then, after seeing
the input derived from , we may expand B to 1 or 2 .

The left factored original expression becomes:

 FIRST and FOLLOW

 The construction of both top-down and bottom-up parsers is aided by two functions,
FIRST and FOLLOW, associated with a grammar G.

 During top-down parsing, FIRST and FOLLOW allow us to choose which production to
apply, based on the next input symbol.

FIRST()
If 'α' is any string of grammar symbols, then FIRST(α) be the set of terminals that
begin the string derived from α .

If α==*>є then add є to FIRST(α). First is defined for both terminals and non-
terminals.
To Compute First Set
1. If X is a terminal , then FIRST(X) is {X}
2. If X є then add є to FIRST(X)
3. If X is a non-terminal and XY1Y2Y3...Yn , then put 'a' in
FIRST(X) if for some i, a is in FIRST(Yi) and є is in all of
FIRST(Y1),...FIRST(Yi-1).

FOLLOW()
FOLLOW is defined only for non-terminals of the grammar G.
It can be defined as the set of terminals of grammar G , which can
immediately follow the non-terminal in a production rule from start symbol.
In other words, if A is a nonterminal, then FOLLOW(A) is the set of terminals
'a' that can appear immediately to the right of A in some sentential form.
Rules to Compute Follow Set
1. If S is the start symbol, then add $ to the FOLLOW(S).
2. If there is a production rule A αBβ then everything in
 FIRST(β) except for є 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).
Example

LL(1) GRAMMAR

 Predictive parsers, that is, recursive-descent parsers needing no

backtracking, can be constructed for a class of grammars called
LL(1).

 An LL(1) grammar is a context-free grammar that can be parsed

using LL(1) parsing, also known as:

✔ Predictive Parsing
✔ Non-Recursive Descent Parsing
✔ Table-Driven Predictive Parsing

 These parsers read the input Left-to-right (L), produce a Leftmost

derivation (L), and use 1 lookahead symbol for using one input
symbol of lookahead at each step to make parsing action
decisions (which production will choose) — hence the name LL(1).

Characteristics of LL(1) Grammars

It must satisfy the following conditions:

No Left Recursion
The grammar should not have left-recursive rules like −
A→Aα

The left recursion must be eliminated using left factoring or the idea called recursive
transformation.

No Ambiguity
Each nonterminal would have a unique production rule. That production rule can be
determined using a single token of lookahead.

Disjoint FIRST and FOLLOW Sets

The FIRST set of one production should not overlap with the FOLLOW set of another
production. This is to avoid conflicts.

That is

Q)

Check whether the given grammar is LL(1) or not?

Construction of Predictive Parsing Table (LL(1) parsing)
 A parsing table is constructed to help the parser decide which production rule to
apply at each step — without backtracking or guessing.
 A predictive parsing table M[A,a], a two-dimensional array, where “A “is a
nonterminal, and “a” is a terminal or the symbol “$’, the input end marker
 By using a parsing table we can also check whether a grammar is LL(1) or not.
 For every LL(1) grammar, each parsing-table entry uniquely identifies a
production or signals an error
 In parsing table , Rows → Non-terminal , Columns → Terminals + $ and Each
cell contains a production rule or error

Steps to construct a predictive parsing table for a grammar G

is given below:
1. Eliminate Left recursion in Grammar G
2. Perform Left factoring on the Grammar G
3. Find First and Follow on the symbol in Grammar G
4. Construct the predictive parse table
5. Check if the given input string can be accepted by the parser
Algorithm : Construction of a predictive parsing table.

INPUT: Grammar G.

OUTPUT:Parsing table M.

METHOD:For each production A -> α of the grammar, do the following:

If, after performing the above, there is no production at all in M[A,a],

then set M[A,a] to error (which we normally represent by an empty
entry in the table).
NON -RECURSIVE PREDICTIVE PARSER

It is possible to build a non recursive predictive parser by maintaining a stack

explicitly, rather than implicitly via recursive calls.
The key problem during predictive parsing is that of determining the production
to be applied for a nonterminal.
The non recursive parser in looks up the production to be applied in a parsing
table

Requirements

1. Stack
2. Parsing Table
3. Input Buffer
4. Parsing
 Figure : Model of a non recursive predictive parser

Input buffer - contains the string to be parsed, followed by $(used to indicate

end of input string)
Stack – initialized with $, to indicate bottom of stack.
Parsing table - 2 D array M[A,a] where ‘A’ is a nonterminal and ‘a’ is terminal
or the symbol $

Check whether the given input string is accepted by the parser or not
The parser is controlled by a program that behaves as follows. The program
considers X, the symbol on top of the stack, and a current input symbol. These
two symbols determine the action of the parser.
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 nonterminal, the program consults entry M[X, a ] of
the parsing table M. The entry will be either an X-production
of the grammar or an error entry. If, for example, M [X, u ]=
{X  UVW}, the parser replaces X on top of the stack by WVU
(with U on top). As output we shall assume that the parser
just prints the production used; any other code could be
executed here. If M[X, a] = error, the parser calls an error
recovery routine.

Consider grammar we have already seen it’s the parsing Table above. On input
 id + id * id, the non -recursive predictive parser. These moves correspond to a
leftmost derivation (see Fig. 4.12 for the full derivation):

BOTTOM-UP PARSING
 A bottom-up parse starts with the string of terminals itself and
builds from the leaves upward, working backwards to the
start symbol by applying the productions in reverse.
 Along the way, a bottom-up parser searches for substrings of the
working string that match the right side of some production.
 When it finds such a substring, it reduces it, i.e.,
substitutes the left side non-terminal for the
matching right side. The goal is to reduce all the
way up to the start symbol and report a successful
parse
 The Theory behind bottom-up parsing involves
understanding the derivation process in reverse.
 Reductions
 Bottom up parsers begin with the input tokens and try to reduce
them into higher-level constructs.
 bottom-up parsing use the process of reducing" a string w to the
start symbol of the grammar. At each reduction step, a
specific substring matching the body of a production is
replaced by the nonterminal at the head of that
production.
 This continues until the entire input is reduced to the start
symbol.

 By definition, a reduction is the reverse of a step in a derivation

(recall that in a derivation, a nonterminal in a sentential form
is replaced by the body of one of its productions). The goal of
bottom-up parsing is therefore to construct a derivation in reverse.
Example:

Handle and Handle Pruning

Handle is a substring that matches with the right side of the production and
if the substring matches with the right side of the production, it is reduced
with the non- terminal on the left side of the production
EXAMPLE

Consider the grammar E 

E+E

E  E*E E  (E)

E id

And the input string is id1 + id2 * id3 The

rightmost derivation is:

E E + E

E + E * E

 E + E * id3

 E + id2 * id3

 Id1 + id2 * id3

In the above derivation, the underlined substrings are called handles.

HANDLE PRUNING

The process of obtaining rightmost derivation in reverse order is called “handle

pruning”. (Replacement of a handle by its respective non-terminal is called
handle pruning).

SHIFT REDUCE PARSING

Shift reduce parsing attempts to construct a parse tree for an input string
beginning at the leaves (bottom) and working up towards the root (top).
This can be considered as the process of “reducing” a string w to the
start symbol of a grammar.
At each reduction step parser searches for substrings of the working
string that match the right side of some production.
When it finds such a substring, it reduces it, i.e., substitutes the left
side non-terminal for the matching right side. The goal is to reduce all the
way up to the start symbol and report a successful parse.
In Shift-reduce parsing a stack holds grammar symbols and an input
buffer holds the rest of the string to be parsed.
As we shall see, the handle always appears at the top of the stack just
before it is identified as the handle.
We use $ to mark the bottom of the stack and also the right end of the
input. Initially, the stack is empty, and the string w is on the input, as
follows:

STACK INPUT

$ w$
During a left-to-right scan of the input string, the parser shifts zero or
more input symbols onto the stack, until it is ready to reduce a string ‘β’
of grammar symbols on top of the stack.
It then reduces β to the head 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 as follows:
 STACK INPUT
$S $
Upon entering this configuration, the parser halts and announces
successful completion of parsing.
There are actually four possible actions a shift-reduce parser can make:
 Shift
 Reduce
 Accept
 Error

1. Shift: The next input symbol is shifted onto the top of

the stack.
2. Reduce: The parser knows the right end of the string to
be reduced must be at the top of the stack. It must then
locate the left end of the string within the stack and
decide with what nonterminal to replace the string.
3. Accept: Announce successful completion of parsing.
4. Error: Discover a syntax error has occurred and calls an
error recovery routine.
5. EXAMPLE

Example:

Following figure steps through the actions a shift-reduce parser

might take in parsing the input string id1 *id2 according to the
expression grammar.
OPERATOR PRECEDENCE PARSING

 It is a type of shift reduce parsing, that can be applied to a small class

of grammars called operator grammar

 An operator grammar has two characteristics:

 There are no epsilon production in the grammar

 No production would have two adjacent non-terminals at
the right side.
 This property enables the implementation of efficient
operator-precedence parsers.
Precedence Relations

In operator-precedence parsing, use parsing table called-operator

precedence relation table we define three precedence relations
between certain pairs of terminals as follows:
Consider ‘a ‘and ‘b’ are two operators

The intention of the precedence relations is to find the handle of a right

 sentential form,
<. with marking the left end,
=· appearing in the interior of the handle, and
.> marking the right end.
In our input string $a1a2...an$, we insert the precedence relation
between the pairs of terminals.
Example: Consider the string id + id * id and the grammar is:

E→ E+E | E-E | E*E | id

The corresponding precedence relations is

Then the string with the precedence relations inserted is:

$ <. id .> + <. id .> * <. id .> $
<. is inserted between the leftmost $ and id since <. is the entry in row
$ and column id.
Stack implementation of operator precedence parsing:

Operator precedence parsing uses a stack and precedence relation table

for its implementation of above algorithm. It is a shift-reduce parsing containing
all four actions shift, reduce, accept and error.

The initial configuration of an operator precedence parsing is

STACK INPUT

$ w$

where w is the input string to be parsed.

Example:

Consider the grammar E → E+E | E*E | id. Input string is id+id*id .The
implementation is as follows:

STACK INPUT COMMENT

$ <· id +id*id $ shift id
$ id ·> +id*id $ pop the top of the stack id
$ <· +id*id $ shift +
 $+ <· id*id $ shift id
$ +id ·> *id $ pop id
$+ <· *id $ shift *
$+* <· id $ shift id
$ + * id ·> $ pop id
$+* ·> $ pop *
$+ ·> $ pop +
$ $ accept

LR PARSING
LR parsing is most efficient method of bottom-up parsing which can
be used to parse large class of context free grammar.
The technique is called LR(k) parsing; the “L” is for left to right
scanning of input symbol, the “R” for constructing right most
derivation in reverse, and the k for the number of input symbols
of lookahead that are used in making parsing decision.
The cases k =0 or k = 1 are of practical interest, and we shall only
consider LR parsers with k =1 here. When (k) is omitted, k is assumed to
be 1.

There are four types of LR parsing,

 LR(0) -least powerful
 SLR (Simple LR) /SLR(1)
 CLR (Canonical LR)-most powerful
 LALR (Lookahead LR)

 LR(0) and SLR -parsing table is generated with canonical collection of LR(0)
item. For CLR and LALR by canonical collection of LR(1) item
 The input buffer takes one symbol at a time from left to right a1, a2,..., am,$.
 The stack contains the combination of the state symbol and the current input symbol.
 The parsing table is a two-dimensional array containing the Action and Goto tables.

Augmented grammar
G’ is the augmented grammar of G with a new production rule S’→S where S’ is the new starting
symbol i.e,

G’= G  {S’ → S} where S is the start state of G.

The start state of G’ = S’.

This is done to signal to the parser when the parsing should stop to announce acceptance of input.

Items and the LR(0) Automaton

An LR parser makes shift-reduce decisions by maintaining states to keep track
of where we are in a parse.
States represent sets of “items."
An LR(0) item (item for short) of a grammar G is a production of G with a dot at
some position of the body. Thus, production A XYZ yields the four items
 The production A ε generates only one item, A.
Intuitively, an item indicates how much of a production we have seen at a given
point in the parsing process.
the item A .XYZ indicates that we hope to see a string derivable from XYZ next
on the input.
A[Link] indicates that we have just seen on the input a string derivable from X
and that we hope next to see a string derivable from YZ.
Item A XYZ. indicates that we have seen the body XYZ and that it may be time
to reduce XYZ to A.
One collection of sets of LR(0) items, called the canonical LR(0) collection,
provides the basis for constructing a deterministic finite automaton that is used
to make parsing decisions. Such an automaton is called an LR(0)
automaton.
To construct the canonical LR(0) collection for a grammar, we need an
augmented grammar and two functions, CLOSURE and GOTO.

Closure Of Item Sets

If I is a set of LR(0) items for a grammar G, then closure(I) is the set of LR(0) items constructed from I
by the two rules:

1. Initially, every LR(0) item in I is added to closure(I).

2. If A →  .B is in closure(I) and B→ is a production rule of G;
then B→. will be in the closure(I).

We will apply this rule until no more new LR(0) items can be added to closure(I).

Consider the augmented grammar

EE’
GOTO Operation
The GOTO function is used to represent the transitions in the LR(0) automaton for a
grammar. The states of the automaton correspond to sets of items, and GOTO(I;X)
species the transition from the state for I under input X.

If I is a set of LR(0) items and X is a grammar symbol (terminal or non-terminal), then

GOTO(I,X) is defined as follows:
 If A →  . X in I then every item in closure({A →  X. }) will be in
GOTO(I,X).
 If I is the set of items that are valid for some viable prefix , then
GOTO(I,X) is the set of items that are valid for the viable prefix X.

EXAMPLE

I ={ E’ → E., E → E.+T} GOTO(I,+) =

{ E→E+.T,

T→.T*F

T →.F

F →.(E)

F →.id }

Construction of Canonical LR(0) Collection

To create the SLR parsing tables for a grammar G, we will create the canonical LR(0) collection of
the grammar G’.
ALGORITHM

LR(0) Automaton
Constructing SLR parsing table
Constructing SLR Parsing Table
INPUT: An augmented grammar G'.

OUTPUT: The SLR parsing table functions action and goto for G' .

METHOD:

1. Construct C ={I0, I1,…..In}, the collection of sets of LR(0) items

for G'.
2. State i is constructed from Ii . The parsing actions for state i are
determined as follows:

If any conflicting actions are generated by the above rules, we say the
grammar is not SLR (1). The algorithm fails to produce a parser in this case.
3. The goto transitions for state i are constructed for all non-terminals A
using the rule: if GOTO(Ii , A)=Ij then GOTO[I, A]=j .
4. All entries not defined by rules (2) and (3) are made “error”.
5. The initial state of the parser is the one constructed from the set of items
containing [S’  S].
Shift/Reduce and Reduce/Reduce conflicts
If a state does not know whether it will make a shift operation or reduction
for a terminal, we say that there is a shift/reduce conflict.
If a state does not know whether it will make a reduction operation using the
production rule i or j for a terminal, we say that there is a reduce/reduce
conflict.
If the SLR parsing table of a grammar G has a conflict, we say that that
grammar is not SLR grammar.
Stack Implementation

Check whether the given input is valid or not?

1️⃣ Stack: $ 0 | Input: id*id+id$ | Action: shift 5
 First symbol is id
 ACTION[0, id] = shift 5
→ Push id and state 5

2️⃣ Stack: $ 0 id 5 | Input: *id+id$ | Action: reduce 6 goto 3

Rule 6?
Actually based on grammar, this matches:
F → id
 Pop 1 symbol (id, 5)
 GOTO[0, F] = state 3

3️⃣ Stack: $ 0 F 3 | Input: *id+id$ | Action: reduce 4 goto 2

Rule 4:
T→F
 Pop F 3
 GOTO[0, T] = 2

4️⃣ Stack: $ 0 T 2 | Input: *id+id$ | Action: shift 7

Next symbol is *, so:
ACTION[2, *] = shift 7
Push * and state 7

5️⃣ Stack: $ 0 T 2 * 7 | Input: id+id$ | Action: shift 5

Next symbol id, so shift:
Push id 5

6️⃣ Stack: $ 0 T 2 * 7 id 5 | Input: +id$ | Action: reduce 6 goto 10

Reduce F → id
 Pop id 5
 GOTO[7, F] = 10

7️⃣ Stack: $ 0 T 2 * 7 F 10 | Input: +id$ | Action: reduce 3 goto 2

Rule 3:
T→T*F
 Pop F 10, * 7, T 2
 GOTO[0, T] = 2

8️⃣ Stack: $ 0 T 2 | Input: +id$ | Action: reduce 2 goto 1

Rule 2:
E→T
 Pop T 2
 GOTO[0, E] = 1

9️⃣ Stack: $ 0 E 1 | Input: +id$ | Action: shift 6

Next symbol +
 ACTION[1, +] = shift 6

🔟 Stack: $ 0 E 1 + 6 | Input: id$ | Action: shift 5

Next input id → shift to state 5

1️⃣1️⃣ Stack: $ 0 E 1 + 6 id 5 | Input: $ | Action: reduce 6 goto 3

Reduce F → id
Push goto(6,F)=3

1️⃣2️⃣ Stack: $ 0 E 1 + 6 F 3 | Input: $ | Action: reduce 4 goto 9

Rule 4: T → F
 Pop F3
Goto(6,T)=9

1️⃣3️⃣ Stack: $ 0 E 1 + 6 T 9 | Input: $ | Action: reduce 1 goto 1

Rule 1:
E→E+T
 Pop T9, +6, E1
Goto(0, E) = 1

1️⃣4️⃣ Stack: $ 0 E 1 | Input: $ | Action: accept

✔ Grammar fully reduced
✔ Input consumed

✔ State 1 with $ triggers accept

Example:
Find the SLR or LR parsing table for
SAA FOLLOW(S)={$}

AaA/b FOLLOW(A)={a,b,$}