Parsing - Introduction to Parsers

Parsing, also known as syntactic analysis, is the process of analyzing a sequence

of tokens to determine the grammatical structure of a program. It takes the stream of
tokens, which are generated by a lexical analyzer or tokenizer, and organizes them into a
parse tree or syntax tree.

The parse tree visually represents how the tokens fit together according to the rules of the
language's syntax. This tree structure is crucial for understanding the program's structure
and helps in the next stages of processing, such as code generation or execution.
Additionally, parsing ensures that the sequence of tokens follows the syntactic rules of
the programming language, making the program valid and ready for further analysis or
execution.

What is the Role of Parser?

A parser performs syntactic and semantic analysis of source code, converting it into an
intermediate representation while detecting and handling errors.

1. Context-free syntax analysis: The parser checks if the structure of the code
follows the basic rules of the programming language (like grammar rules). It looks
at how words and symbols are arranged.

2. Guides context-sensitive analysis: It helps with deeper checks that depend on

the meaning of the code, like making sure variables are used correctly. For
example, it ensures that a variable used in a mathematical operation, like x + 2, is
a number and not text.

3. Constructs an intermediate representation: The parser creates a simpler

version of your code that’s easier for the computer to understand and work with.
 4. Produces meaningful error messages: If there’s something wrong in your code,
the parser tries to explain the problem clearly so you can fix it.

5. Attempts error correction: Sometimes, the parser tries to fix small mistakes in
your code so it can keep working without breaking completely.

Types of Parsing

The parsing is divided into two types, which are as follows:

• Top-down Parsing

• Bottom-up Parsing

Top-Down Parsing

Top-down parsing is a method of building a parse tree from the start symbol (root) down
to the leaves (end symbols). The parser begins with the highest-level rule and works its
way down, trying to match the input string step by step.

• Process: The parser starts with the start symbol and looks for rules that can help
it rewrite this symbol. It keeps breaking down the symbols (non-terminals) into
smaller parts until it matches the input string.

• Leftmost Derivation: In top-down parsing, the parser always chooses the

leftmost non-terminal to expand first, following what is called leftmost derivation.
This means the parser works on the left side of the string before moving to the
right.
 • Other Names: Top-down parsing is sometimes called recursive parsing or
predictive parsing. It is called recursive because it often uses recursive functions
to process the symbols.

Top-down parsing is useful for simple languages and is often easier to implement.
However, it can have trouble with more complex or ambiguous grammars.

Top-down parsers can be classified into two types based on whether they use
backtracking or not:

1. Top-down Parsing with Backtracking

In this approach, the parser tries different possibilities when it encounters a choice, if one
possibility doesn’t work (i.e., it doesn’t match the input string), the parser backtracks to
the previous decision point and tries another possibility.

Example: If the parser chooses a rule to expand a non-terminal, and it doesn't work, it
will go back, undo the choice, and try a different rule.

Advantage: It can handle grammars where there are multiple possible ways to expand a
non-terminal.

Disadvantage: Backtracking can be slow and inefficient because the parser might have
to try many possibilities before finding the correct one.

2. Top-down Parsing without Backtracking

In this approach, the parser does not backtrack. It tries to find a match with the input
using only the first choice it makes, if it doesn’t match the input, it fails immediately
instead of going back to try another option.

Example: The parser will always stick with its first decision and will not reconsider other
rules once it starts parsing.

Advantage: It is faster because it doesn’t waste time going back to previous steps.

Disadvantage: It can only handle simpler grammars that don’t require trying multiple
choices.

Classification of Top-Down Parsers

Top-down parsing is a way of analyzing a sentence or program by starting with the start
symbol (the root of the parse tree) and working down to the leaves (the actual input
symbols). It tries to match the input string by expanding the start symbol using grammar
rules. The process of constructing the parse tree which starts from the root and goes
down to the leaf is Top-Down Parsing.
In this approach, the parser works from the top of the tree and progressively breaks down
non-terminals into smaller parts, following the leftmost derivation. It's called recursive
because the process often uses recursion to handle different parts of the string.

• Top-down parsers work with grammars that are free from ambiguity and left
recursion.

• They construct the parse tree by following a leftmost derivation, which means they
always expand the leftmost non-terminal first.

• It does not allow Grammar with Common Prefixes.

• Top-Down Parsing is based on Left Most Derivation whereas Bottom-Up Parsing is

dependent on Reverse Right Most Derivation.

Classification of Top-Down Parsing

Recursive Descent Parsing

Recursive Descent Parsing is a top-down parsing technique used to analyze the syntax of
a given input string based on a set of grammar rules. It uses a set of recursive procedures
(or functions) to process each non-terminal in the grammar and try to match the input
string.

Here's how it works:

1. Start with a non-terminal.

2. Check the first possible option (alternative) for the non-terminal and try to match
it with the input string.

3. If it doesn’t match, move to the second option and try again.

 4. Continue this process for each option until you find a match.

5. If at least one option matches the input string, the parsing is successful.

In simple terms, it's like trying different combinations to find the right one that works for
the input string.

Recursive Descent Parser

A recursive descent parser is a top-down parser that processes input based on a set of
recursive functions, where each function corresponds to a grammar rule. It parses the
input from left to right, constructing a parse tree by matching the grammar's production
rules. This parser is simple to implement and is suitable for LL(1) grammars, where
decisions can be made based on a single lookahead token. While straightforward,
recursive descent parsers struggle with left-recursive grammars and may require
grammar transformations to handle such cases effectively.

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:

Before removing left recursion After removing left recursion

E –> T E’
E –> E + T | T E’ –> + T E’ | e
T –> T * F | F T –> F T’
F –> (E) | id T’ –> * F T’ | e
F –> (E) | id

LL(1) or Table Driver or Predictive Parser

LL(1) parsing is a way to analyze a sentence in a programming language and check if it

follows the correct structure. The name LL(1) has a meaning:

• The first L means reading the input from Left to Right.

• The second L means creating the Left-most Derivation (building the structure step
by step from the left side).

• The 1 means looking one step ahead in the input to decide what to do next.
Rules for LL(1) Parsing

To work properly, an LL(1) parser needs clear and simple grammar:

• No left recursion (rules must not refer to themselves at the beginning).

• No common prefixes (if two rules start the same way, they should be rewritten to
avoid confusion).

• No ambiguity (there must be only one way to build the sentence).

Because LL(1) parsing is predictable and fast, it is used in compilers and interpreters to
check if code is written correctly.

Construction of LL(1) Parsing Table

Parsing is an essential part of computer science, especially in compilers and interpreters.

From the various parsing techniques, LL(1) parsing is best. It uses a predictive, top-down
approach. This allows efficient parsing without backtracking.

What is LL(1) Parsing?

Here the 1st L represents that the scanning of the Input will be done from the Left to Right
manner and the second L shows that in this parsing technique, we are going to use the
Left most Derivation Tree. And finally, the 1 represents the number of look-ahead, which
means how many symbols you will see when you want to decide.

Conditions for an LL(1) Grammar

To construct a working LL(1) parsing table, a grammar must satisfy these conditions:

• No Left Recursion: Avoid recursive definitions like A -> A + b.

• Unambiguous Grammar: Ensure each string can be derived in only one way.
 • Left Factoring: Make the grammar deterministic, so the parser can proceed
without guessing.

Algorithm to Construct LL (1) Parsing Table

Step 1: First check all the essential conditions mentioned above and go to step 2.

Step 2: Calculate First () and Follow () for all non-terminals.

1. First (): If there is a variable, and from that variable, if we try to drive all the
strings then the beginning Terminal Symbol is called the First.

2. Follow (): What is the Terminal Symbol which follows a variable in the process of
derivation.

Step 3: For each production A --> α. (A tends to alpha)

1. Find First(α) and for each terminal in First(α), make entry A --> α in the table.

2. If First(α) contains ε (epsilon) as terminal, then find the Follow(A) and for each
terminal in Follow(A), make entry A --> ε in the table.

3. If the First(α) contains ε and Follow(A) contains $ as terminal, then make entry A -
-> ε in the table for the $.

To construct the parsing table, we have two functions:

In the table, rows will contain the non-Terminals, and the column will contain the Terminal
Symbols. All the Null Productions of the Grammars will go under the Follow elements,
and the remaining productions will lie under the elements of the First set.

Now, let's understand with an example.

Example 1: Consider the Grammar:

E --> TE'
E' --> +TE' | ε
T --> FT'
T' --> *FT' | ε
F --> id | (E)

*ε denotes epsilon

Step 1: The grammar satisfies all properties in step 1.

Step 2: Calculate first () and follow ().

Find their First and Follow sets:

 First Follow

E --> TE' { id, ( } { $, ) }

E' --> +TE' / ε { +, ε } { $, ) }

T --> FT' { id, ( } { +, $, ) }

T' --> *FT' / ε { *, ε } { +, $, ) }

F --> id/(E) { id, ( } { *, +, $, ) }

Step 3: Make a parser table.

Now, the LL (1) Parsing Table is:

Id + * ( ) $

E E --> TE' E --> TE'

E' E' --> +TE' E' --> ε E' --> ε

T T --> FT' T --> FT'

T' T' --> ε T' --> *FT' T' --> ε T' --> ε

F F --> id F --> (E)

As you can see that all the null productions are put under the Follow set of that symbol
and all the remaining productions lie under the First of that symbol.

Note: Every grammar is not feasible for LL (1) Parsing table. It may be possible that one
cell may contain more than one production.

Let's see an example.

Example 2: Consider the Grammar

S --> A | a
A --> a

Step 1: The grammar does not satisfy all properties in step 1, as the grammar is
ambiguous. Still, let's try to make the parser table and see what happens

Step 2: Calculating first () and follow ()

Find their First and Follow sets:

First Follow

S --> A/a {a} {$}

A -->a {a} {$}

Step 3: Make a parser table.

Parsing Table:

a $

S S --> A, S --> a

A A --> a

Here, we can see that there are two productions in the same cell. Hence, this grammar is
not feasible for LL (1) Parser.

Trick - Above grammar is ambiguous grammar. So, the grammar does not satisfy the
essential conditions. So, we can say that this grammar is not feasible for LL (1) Parser
even without making the parse table.

Example 3: Consider the Grammar

S -> (L) | a
L -> SL'
L' -> )SL' | ε

Step1: The grammar satisfies all properties in step 1

Step 2: Calculating first () and follow ()

First Follow

S (,a $, )

L (,a )

L' ), ε )

Step 3: Making a parser table

Parsing Table:

( ) a $

S S -> (L) S -> a

L L -> SL' L -> SL'

L'->(SL'
L'
L'->ε

Here, we can see that there are two productions in the same cell. Hence, this grammar is
not feasible for LL (1) Parser. Although the grammar satisfies all the essential conditions
in step 1, it is still not feasible for LL (1) Parser. We saw in example 2 that we must have
these essential conditions and in example 3 we saw that those conditions are insufficient
to be a LL (1) parser.

Advantages of Construction of LL(1) Parsing Table

• Clear Decision-Making: With an LL(1) parsing table, the parser can decide what
to do by looking at just one symbol ahead. This makes it easy to choose the right
rule without confusion or guessing.

• Fast Parsing: Since there’s no need to go back and forth or guess the next step,
LL(1) parsing is quick and efficient. This is useful for applications like compilers
where speed is important.
 • Easy to Spot Errors: The table helps identify errors right away. If the current
symbol doesn’t match any rule in the table, the parser knows there’s an error and
can handle it immediately.

• Simple to Implement: Once the table is set up, the parsing process is
straightforward. You just follow the instructions in the table, making it easier to
build and maintain.

• Good for Predictive Parsing: LL(1) parsing is often called “predictive parsing”
because the table lets you predict the next steps based on the input. This makes
it reliable for parsing programming languages and structured data.

Important Notes

1. If a grammar contains left factoring, then it cannot be LL (1).

Eg - S -> aS | a ---- both productions go in a

2. If a grammar contains left recursion, it cannot be LL (1)

Eg - S -> Sa | b
S -> Sa goes to FIRST(S) = b
S -> b goes to b; thus, b has 2 entries hence not LL (1)

3. If the grammar is ambiguous then it cannot be LL (1).

Every regular grammar need not be LL (1) because regular grammar may contain left
factoring, left recursion or ambiguity.

Bottom-Up Parsing

Bottom-up parsing is a method of building a parse tree starting from the leaf nodes (the
input symbols) and working towards the root node (the start symbol). The goal is to
reduce the input string step by step until we reach the start symbol, which represents the
entire language.

• Process: The parser begins with the input symbols and looks for patterns that can
be reduced to non-terminals based on the grammar rules. It keeps reducing parts
of the string until it forms the start symbol.

• Rightmost Derivation in Reverse: In bottom-up parsing, the parser traces the

rightmost derivation of the string but works backwards, starting from the input
string and moving towards the start symbol.

• Shift-Reduce Parsing: Bottom-up parsers are often called shift-reduce parsers

because they shift (move symbols) and reduce (apply rules to replace symbols) to
build the parse tree.
Bottom-up parsing is efficient for handling more complex grammars and is commonly
used in compilers. However, it can be more challenging to implement compared to top-
down parsing.

Generally, bottom-up parsing is categorized into the following types:

1. LR parsing/Shift Reduce Parsing: Shift reduce Parsing is a process of parsing a string

to obtain the start symbol of the grammar.

• LR (0)

• SLR (1)

• LALR

• CLR

2. Operator Precedence Parsing: The grammar defined using operator grammar is

known as operator precedence parsing. In operator precedence parsing there should be
no null production, and two non-terminals should not be adjacent to each other.

Shift Reduce Parser in Compiler

Shift-reduce parsing is a popular bottom-up technique used in syntax analysis, where the
goal is to create a parse tree for a given input based on grammar rules. The process works
by reading a stream of tokens (the input) and then working backwards through the
grammar rules to discover how the input can be generated.

1. Input Buffer: This stores the string or sequence of tokens that needs to be parsed.

2. Stack: The parser uses a stack to keep track of which symbols or parts of the parse
it has already processed. As it processes the input, symbols are pushed onto and
popped off the stack.

3. Parsing Table: Like a predictive parser, a parsing table helps the parser decide
what action to take next.

Shift-reduce parsing works by processing the input left to right and gradually building up
a parse tree by shifting tokens onto the stack and reducing them using grammar rules,
until it reaches the start symbol of the grammar.

Four Main Operations of Shift Reduce Parser

Shift: Move the next input symbol onto the stack when no reduction is possible.

Reduce: Replace a sequence of symbols at the top of the stack with the left-hand side of
a grammar rule.

Accept: Successfully complete parsing when the entire input is processed and the stack
contains only the start symbol.
Error: Handle unexpected or invalid input when no shift or reduce action is possible.

Working of Shift Reduce Parser

Shift-reduce parsers use a Deterministic Finite Automaton (DFA) to help recognize these
handles. The DFA helps track what symbols are on the stack and decides when to shift or
reduce by following a set of rules. Instead of directly analyzing the structure, the DFA
helps the parser determine when reductions should occur based on the stack's contents.

The shift-reduce parser is a bottom-up parsing technique that breaks down a string into
two parts: the undigested part and the semi-digested part. Here’s how it works:

1. Undigested Part: This part contains the remaining tokens that still need to be
processed. It is the input that hasn’t been handled yet.

2. Semi-Digested Part: This part is on a stack. It's where tokens or parts of the string
that have been processed are stored.

Parsing Process

At the beginning, the input string is entirely undigested, and the stack is empty.

The parser performs one of three actions at each step:

1. Shift

• When the parser can’t reduce the sequence on the stack (because the stack
doesn’t match any production rule), it shifts the next token from the input to the
stack.

• This means the parser takes one token from the undigested part (the input) and
places it on the stack.

• The stack keeps growing as tokens are added until a valid reduction is possible.

2. Reduce

• If the sequence of tokens on the stack matches the right side of a production rule,
the parser can reduce it. This means the sequence of tokens on the stack is
replaced with a non-terminal symbol (the left side of the production rule).

• For example, if the stack has id, and there’s a production rule T → id, the stack will
change from id to T.

• This process is like reversing the rule. It’s called a reduction.

• The reduction continues until the stack is reduced all the way to the start symbol
of the grammar, which indicates that the input has been successfully parsed.
 o There’s one special case of reduction: If the entire stack contains the start
symbol and there’s no more input left, the parse is successful (the input is
valid).

o The sequence being reduced (e.g., id in the rule T → id) is called a handle.
Identifying the handle is one of the most important tasks of a shift-reduce
parser.

3. Error

• If neither shift nor reduce actions are possible, the parser encounters an error.

• An error happens when:

1. The sequence on the stack doesn't match any rule in the grammar (so no
reduction can be made).

2. If shifting a token would create a sequence on the stack that cannot

eventually be reduced to the start symbol, continuing the shift would be
pointless.

1. For example, if the parser has E + on the stack and the next input token is ),
no reduction is possible and shifting ) would result in an invalid sequence.

Example 1 - Consider the grammar

S --> S + S
S --> S * S
S --> id

Perform Shift Reduce parsing for input string "id + id + id".

Example 2 - Consider the grammar
E --> 2E2
E --> 3E3
E --> 4
Perform Shift Reduce parsing for input string "32423".

Example 3 - Consider the grammar

S --> ( L ) | a
L --> L , S | S
Perform Shift Reduce parsing for input string "( a, ( a, a ) ) ".

Input Parsing
Stack Buffer Action

$ (a,(a,a))$ Shift

$( a,(a,a))$ Shift

$(a ,(a,a))$ Reduce S → a

 Input Parsing
Stack Buffer Action

$(S ,(a,a))$ Reduce L → S

$(L ,(a,a))$ Shift

$(L, (a,a))$ Shift

$(L,( a,a))$ Shift

$(L,(a ,a))$ Reduce S → a

$(L,(S ,a))$ Reduce L → S

$(L,(L ,a))$ Shift

$(L,(L, a))$ Shift

$(L,(L,a ))$ Reduce S → a

$ ( L, ( L, S ))$ Reduce L →L, S

$ ( L, ( L ))$ Shift

$ ( L, ( L ) )$ Reduce S → (L)

$ ( L, S )$ Reduce L → L, S
 Input Parsing
Stack Buffer Action

$(L )$ Shift

$(L) $ Reduce S → (L)

$S $ Accept

LR Parser

LR parser is a bottom-up parser for context-free grammar that is very generally used by
computer programming language compiler and other associated tools. LR parser reads
their input from left to right and produces a right-most derivation. It is called a Bottom-up
parser because it attempts to reduce the top-level grammar productions by building up
from the leaves. LR parsers are the most powerful parser of all deterministic parsers in
practice.

Description of LR parser: The term parser LR(k) parser, here the L refers to the left-to-
right scanning, R refers to the rightmost derivation in reverse and k refers to the number
of unconsumed "look ahead" input symbols that are used in making parser decisions.
Typically, k is 1 and is often omitted. A context-free grammar is called LR (k) if the LR (k)
parser exists for it. This first reduces the sequence of tokens to the left. But when we read
from above, the derivation order first extends to non-terminal.
 1. The stack is empty, and we are looking to reduce the rule by S'→S$.

2. Using a “.” in the rule represents how many of the rules are already on the stack.

3. A dotted item, or simply, the item is a production rule with a dot indicating how
much RHS has so far been recognized. Closing an item is used to see what
production rules can be used to expand the current structure. It is calculated as
follows:

Rules for LR parser: The rules of LR parser as follows.

1. The first item from the given grammar rules adds itself as the first closed set.

2. If an object is present in the closure of the form A→ α. β. γ, where the next symbol
after the symbol is non-terminal, add the symbol's production rules where the dot
precedes the first item.

3. Repeat steps (B) and (C) for new items added under (B).

LR parser algorithm: LR Parsing algorithm is the same for all the parser, but the parsing
table is different for each parser. It consists following components as follows.

1. Input Buffer - It contains the given string, and it ends with a $ symbol.
Stack - The combination of state symbol and current input symbol is used to refer
to the parsing table to take the parsing decisions.

Parsing Table: Parsing table is divided into two parts- Action table and Go-To table.
The action table gives a grammar rule to implement the given current state and current
terminal in the input stream. There are four cases used in action table as follows.

1. Shift Action- In shift action the present terminal is removed from the input stream
and the state n is pushed onto the stack, and it becomes the new present state.

2. Reduce Action- The number m is written to the output stream.

3. The symbol m mentioned in the left-hand side of rule m says that state is removed
from the stack.

4. The symbol m mentioned in the left-hand side of rule m says that a new state is
looked up in the goto table and made the new current state by pushing it onto the
stack.

An accept - the string is accepted

No action - a syntax error is reported

Note -
The go-to table indicates which state should proceed.
LR parser diagram:

Problem on LR (0) parser

Prerequisite: LR Parser.

The LR parser is an efficient bottom-up syntax analysis technique that can be used for a
large class of context-free grammar. This technique is also called LR (0) parsing.
L stands for the left to right scanning
R stands for rightmost derivation in reverse
0 stands for no. of input symbols of lookahead.

Augmented grammar: If G is a grammar with starting symbol S, then G' (augmented

grammar for G) is a grammar with a new starting symbol S' and productions S'-> .S . The
purpose of this new starting production is to indicate to the parser when it should stop
parsing. The ' . ' Before S indicates the left side of ' . ‘ has been read by a compiler and the
right side of ' . ' is yet to be read by a compiler.

Steps for constructing the LR parsing table:

1. Writing augmented grammar

2. LR(0) collection of items to be found

3. Defining 2 functions: goto (list of non-terminals) and action (list of terminals) in

the parsing table.

Q. Construct an LR parsing table for the given context-free grammar -

S-->AA
A-->aA|b
Solution:
STEP 1- Find augmented grammar -

The augmented grammar of the given grammar is: -

S'-->.S [0th production]

S-->.AA [1st production]
A-->.aA [2nd production]
A-->.b [3rd production]

STEP 2 - Find LR (0) collection of items

Below is the figure showing the LR (0) collection of items. We will understand everything
one by one.

The terminals of this grammar are {a,b}

The non-terminals of this grammar are {S,A}

RULE - if any nonterminal has ' . ' preceding it, we must write all its production and add '
. ' preceding each of its-production.

RULE - from each state to the next state, the ' . ' shifts to one place to the right.

• In the figure, I0 consists of augmented grammar.

• Io goes to I1 when ' . ' of 0th production is shifted towards the right of S(S'->S.).
This state is the accepted state. S is seen by the compiler
 • Io goes to I2 when ' . ' of 1st production is shifted towards the right (S->A.A) . A is
seen by the compiler

• I0 goes to I3 when ' . ' of the 2nd production is shifted towards the right (A->a.A) .
a is seen by the compiler.

• I0 goes to I4 when ' . ' of the 3rd production is shifted towards the right (A->b.) . b
is seen by the compiler.

• I2 goes to I5 when ' . ' of 1st production is shifted towards the right (S->AA.) . A is
seen by the compiler

• I2 goes to I4 when ' . ' of 3rd production is shifted towards the right (A->b.) . b is
seen by the compiler.

• I2 goes to I3 when ' . ' of the 2nd production is shifted towards the right (A->a.A) .
a is seen by the compiler.

• I3 goes to I4 when ' . ' of the 3rd production is shifted towards the right (A->b.) . b
is seen by the compiler.

• I3 goes to I6 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler

• I3 goes to I3 when ' . ' of the 2nd production is shifted towards the right (A->a.A) .
a is seen by the compiler.

STEP3 - defining 2 functions: goto[list of non-terminals] and action[list of terminals] in

the parsing table

• $ is by default a terminal that takes the accepting state.

• 0,1,2,3,4,5,6 denotes I0,I1,I2,I3,I4,I5,I6

• I0 gives A in I2, so 2 is added to the A column and 0 rows.

• I0 gives S in I1, so 1 is added to the S column and 1 row.

• similarly, 5 is written in A column and 2nd row, 6 is written in A column and 3 rows.

• I0 gives an in I3 to .so S3(shift 3) is added to a column and 0 rows.

• I0 gives b in I4, so S4(shift 4) is added to the b column and 0 rows.

• Similarly, S3(shift 3) is added on a column and 2,3 rows, S4(shift 4) is added on b

column and 2,3 rows.

• I4 is reduced state as ' . ' is at the end. I4 is the 3rd production of grammar. So write
r3(reduce 3) in terminals.
 • I5 is reduced state as ' . ' is at the end. I5 is the 1st production of grammar. So write
r1(reduce 1) in terminals.

• I6 is reduced state as ' . ' is at the end. I6 is the 2nd production of grammar. So
write r2(reduce 2) in terminals.

As each cell has only 1 value in it, hence, the given grammar is LR (0).

SLR Parser (with Examples)

LR parsers is an efficient bottom-up syntax analysis technique that can be used to

parse large classes of context-free grammar is called LR(k) parsing.
L stands for left-to-right scanning
R stands for rightmost derivation in reverse
k is several input symbols. when k is omitted, k is assumed to be 1.

Advantages of LR parsing

• LR parsers handle context-free grammars. These grammars describe the structure

of programming languages-how statements, expressions, and other language
constructs fit together.

• LR parsers ensure that your code adheres to these rules.

• It can detect syntactic errors

• It is an efficient non-backtracking shift shift-reducing parsing method.

Types of LR Parsing Methods

• SLR parser

• LALR parser

• Canonical LR parser

SLR Parser

• it is weakest of the three methods but easier to implement

• a grammar for which SLR parser can be constructed is called SLR grammar
Steps for constructing the SLR parsing table

1. Writing augmented grammar

2. LR (0) collection of items to be found

3. Find FOLLOW of LHS of production

4. Defining 2 functions: goto [list of terminals] and action [list of non-terminals] in

the parsing table

EXAMPLE - Construct LR parsing table for the given context-free grammar

S-->AA
A-->aA|b

Solution:

STEP1: Find augmented grammar. The augmented grammar of the given grammar is:-

S'-->.S [0th production]

S-->.AA [1st production]
A-->.aA [2nd production]
A-->.b [3rd production]

STEP2: Find LR (0) collection of items

Below is the figure showing the LR (0) collection of items. We will understand everything
one by one.

The terminals of this grammar are {a,b}.

The non-terminals of this grammar are {S,A}

RULE - If any non-terminal has ' . ' preceding it, we have to write all its production and add
' . ' preceding each of its production.
RULE - from each state to the next state, the ' . ' shifts to one place to the right.

• In the figure, I0 consists of augmented grammar.

• Io goes to I1 when ' . ' of 0th production is shifted towards the right of S(S'->S.).
this state is the accepted state. S is seen by the compiler.

• Io goes to I2 when ' . ' of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler

• I0 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.

• I0 goes to I4 when ' . ' of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler.

• I2 goes to I5 when ' . ' of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler

• I2 goes to I4 when ' . ' of 3rd production is shifted towards right (A->b.) . b is seen
by the compiler.

• I2 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.

• I3 goes to I4 when ' . ' of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler.

• I3 goes to I6 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler

• I3 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler.

STEP3: Find FOLLOW of LHS of production

FOLLOW(S)=$
FOLLOW(A)=a,b,$

STEP 4: Defining 2 functions:goto[list of non-terminals] and action[list of terminals] in the

parsing table. Below is the SLR parsing table.
 • $ is by default a nonterminal that takes accepting state.

• 0,1,2,3,4,5,6 denotes I0,I1,I2,I3,I4,I5,I6

• I0 gives A in I2, so 2 is added to the A column and 0 rows.

• I0 gives S in I1,so 1 is added to the S column and 1 row.

• similarly 5 is written in A column and 2 row, 6 is written in A column and 3 row.

• I0 gives a in I3 .so S3(shift 3) is added to a column and 0 row.

• I0 gives b in I4 .so S4(shift 4) is added to the b column and 0 row.

• Similarly, S3(shift 3) is added on a column and 2,3 row ,S4(shift 4) is added on b

column and 2,3 rows.

• I4 is reduced state as ' . ' is at the end. I4 is the 3rd production of grammar(A--
>.b).LHS of this production is A. FOLLOW(A)=a,b,$ . write r3(reduced 3) in the
columns of a,b,$ and 4th row

• I5 is reduced state as ' . ' is at the end. I5 is the 1st production of grammar(S-->.AA).
LHS of this production is S. FOLLOW(S)=$ . write r1(reduced 1) in the column of $
and 5th row

• I6 is a reduced state as ' . ' is at the end. I6 is the 2nd production of grammar( A--
>.aA). The LHS of this production is A. FOLLOW(A)=a,b,$ . write r2(reduced 2) in
the columns of a,b,$ and 6th row

LALR Parser (with Examples)

LALR Parser: LALR Parser is lookahead LR parser. It is the most powerful parser which
can handle large classes of grammar. The size of CLR parsing table is quite large as
compared to another parsing table. LALR reduces the size of this table. LALR works
similar to CLR. The only difference is, it combines the similar states of CLR parsing table
into one single state.
The general syntax becomes [A->∝.B, a ] where A->∝.B is production and a is a terminal
or right end marker $ LR(1) items=LR(0) items + look ahead

How to add lookahead with the production?

CASE 1 - A->∝.BC, a

Suppose this is the 0th production. Now, since ' . ' precedes B, so we have to write B's
productions as well.

B->.D [1st production]

Suppose this is B's production. The look ahead of this production is given as- we look at
previous production i.e. - 0th production. Whatever is after B, we find FIRST (of that value)
, that is the lookahead of 1st production. So, here in 0th production, after B, C is there.
Assume FIRST(C)=d, then 1st production becomes.

B->.D, d

CASE 2 - Now if the 0th production was like this,

A->∝.B, a

Here, we can see there's nothing after B. So the lookahead of 0th production will be the
lookahead of 1st production. i.e.-

B->.D, a

CASE 3 - Assume a production A->a|b

A->a,$ [0th production]

A->b,$ [1st production]

Here, the 1st production is a part of the previous production, so the lookahead will be the
same as that of its previous production.

Steps for constructing the LALR parsing table:

1. Writing augmented grammar

2. LR (1) collection of items to be found

3. Defining 2 functions: goto [list of terminals] and action [list of non-terminals] in

the LALR parsing table

EXAMPLE Construct CLR parsing table for the given context free grammar

S-->AA

A-->aA|b
Solution:

STEP1- Find augmented grammar: The augmented grammar of the given grammar is: -

S'-->.S ,$ [0th production]

S-->.AA ,$ [1st production]

A-->.aA ,a|b [2nd production]

A-->.b ,a|b [3rd production]

Let's apply the rule of lookahead to the above productions.

• The initial look ahead is always $

• Now, the 1st production came into existence because of ' . ' before 'S' in 0th
production. There is nothing after 'S', so the lookahead of 0th production will be
the lookahead of 1st production. i.e. : S-->.AA ,$

• Now, the 2nd production came into existence because of ' . ' before 'A' in the 1st
production.
After 'A', there's 'A'. So, FIRST(A) is a,b. Therefore, the lookahead of the 2nd
production becomes a|b.

• Now, the 3rd production is a part of the 2nd production. So, the look ahead will be
the same.

STEP2 - Find LR (0) collection of items. Below is the figure showing the LR(0) collection of
items. We will understand everything one by one.

The terminals of this grammar are {a,b}

The non-terminals of this grammar are {S,A}
RULES -

1. If any non-terminal has ' . ' preceding it, we have to write all its production and add
' . ' preceding each of its production.

2. from each state to the next state, the ' . ' shifts to one place to the right.

• In the figure, I0 consists of augmented grammar.

• Io goes to I1 when ' . ' of 0th production is shifted towards the right of S(S'->S.).
This state is the accept state . S is seen by the compiler. Since I1 is a part of the
0th production, the lookahead is same i.e. $

• Io goes to I2 when ' . ' of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler. Since I2 is a part of the 1st production, the lookahead is same i.e.
$.

• I0 goes to I3 when ' . ' of 2nd production is shifted towards the right (A->a.A) . a is
seen by the [Link] I3 is a part of 2nd production, the lookahead is same
i.e. a|b.

• I0 goes to I4 when ' . ' of 3rd production is shifted towards right (A->b.) . b is seen
by the compiler. Since I4 is a part of 3rd production, the lookahead is same i.e. a|b.

• I2 goes to I5 when ' . ' of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler. Since I5 is a part of the 1st production, the lookahead is same i.e.
$.

• I2 goes to I6 when ' . ' of 2nd production is shifted towards the right (A->a.A) . A is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is
same i.e. $.

• I2 goes to I7 when ' . ' of 3rd production is shifted towards right (A->b.) . A is seen
by the compiler. Since I6 is a part of the 3rd production, the lookahead is same i.e.
$.

• I3 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is
same i.e. a|b.

• I3 goes to I8 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I8 is a part of the 2nd production, the lookahead is
same i.e. a|b.

• I6 goes to I9 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I9 is a part of the 2nd production, the lookahead is
same i.e. $.
 • I6 goes to I6 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is
same i.e. $.

• I6 goes to I7 when ' . ' of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler. Since I6 is a part of the 3rd production, the lookahead is
same i.e. $.

STEP 3 - Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in

the parsing [Link] is the CLR parsing table

Once we make a CLR parsing table, we can easily make a LALR parsing table from it.

In the step2 diagram, we can see that

• I3 and I6 are similar except their lookaheads.

• I4 and I7 are similar except their lookaheads.

• I8 and I9 are similar except their lookaheads.

In LALR parsing table construction , we merge these similar states.

• Wherever there is 3 or 6, make it 36(combined form)

• Wherever there is 4 or 7, make it 47(combined form)

• Wherever there is 8 or 9, make it 89(combined form)

Below is the LALR parsing table.

Now we must remove the unwanted rows

• As we can see, 36 row has same data twice, so we delete 1 row.

• We combine two 47 row into one by combining each value in the single 47 row.

• We combine two 89 row into one by combining each value in the single 89 row.

The final LALR table looks like the below.

CLR Parser: The CLR parser stands for canonical LR parser. It is a more powerful LR
parser. It makes use of lookahead symbols. This method uses a large set of items called
LR (1) items. The main difference between LR (0) and LR (1) items is that, in LR (1) items,
it is possible to carry more information in a state, which will rule out useless reduction
states. This extra information is incorporated into the state by the lookahead symbol. The
general syntax becomes [A->∝.B, a ] where A->∝. B is the production and a is a terminal
or right end marker $ LR (1) items=LR (0) items + look ahead

How to add lookahead with the production?

CASE 1 - A->∝.BC, a
Suppose this is the 0th production. Now, since ' . ' precedes B, so we have to write B's
productions as well.

B->.D [1st production]

Suppose this is B's production. The look ahead of this production is given as we look at
previous productions i.e. 0th production. Whatever is after B, we find FIRST(of that value)
, that is the lookahead of 1st production. So, here in 0th production, after B, C is there.
assume FIRST(C)=d, then 1st production becomes

B->.D, d

CASE 2 - Now if the 0th production was like this,

A->∝.B, a

Here, we can see there's nothing after B. So the lookahead of 0th production will be the
lookahead of 1st production. ie-

B->.D, a

CASE 3 - Assume a production A->a|b

A->a,$ [0th production]

A->b,$ [1st production]

Here, the 1st production is a part of the previous production, so the lookahead will be the
same as that of its previous production.

These are the 2 rules of look ahead.

Steps for constructing CLR parsing table :

1. Writing augmented grammar

2. LR(1) collection of items to be found

3. Defining 2 functions: goto[list of terminals] and action[list of non-terminals] in the

CLR parsing table

EXAMPLE
Construct a CLR parsing table for the given context-free grammar

S-->AA

A-->aA|b

Solution: STEP 1 - Find augmented grammar

The augmented grammar of the given grammar is:-

S'-->.S ,$ [0th production]

S-->.AA ,$ [1st production]

A-->.aA ,a|b [2nd production]

A-->.b ,a|b [3rd production]

Let's apply the rule of lookahead to the above productions

• The initial look ahead is always $

• Now, the 1st production came into existence because of ' . ' Before 'S' in 0th
production. There is nothing after 'S', so the lookahead of 0th production will be
the lookahead of 1st production. ie: S-->.AA ,$

• Now, the 2nd production came into existence because of ' . ' Before 'A' in the 1st
production. After 'A', there's 'A'. So, FIRST(A) is a,b. Therefore, the look ahead for
the 2nd production becomes a|b.

• Now, the 3rd production is a part of the 2nd production. So, the look ahead will be
the same.

STEP 2 - Find LR(1) collection of items Below is the figure showing the LR(1) collection of
items. We will understand everything one by one.

The terminals of this grammar are {a,b}

The non-terminals of this grammar are {S,A}

RULE-

1. If any non-terminal has ' . ' preceding it, we have to write all its production and add
' . ' preceding each of its production.

2. from each state to the next state, the ' . ' shifts to one place to the right.

3. All the rules of lookahead apply here.

• In the figure, I0 consists of augmented grammar.

• Io goes to I1 when ' . ' of 0th production is shifted towards the right of S(S'->S.).
This state is the accept state . S is seen by the compiler. Since I1 is a part of the
0th production, the lookahead is the same ie $

• Io goes to I2 when ' . ' of 1st production is shifted towards right (S->A.A) . A is seen
by the compiler. Since I2 is a part of the 1st production, the lookahead is the same
i.e. $.

• I0 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is the
same ie a|b.

• I0 goes to I4 when ' . ' of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler. Since I4 is a part of the 3rd production, the lookahead is the
same i.e. a | b.

• I2 goes to I5 when ' . ' of 1st production is shifted towards right (S->AA.) . A is seen
by the compiler. Since I5 is a part of the 1st production, the lookahead is the same
i.e. $.

• I2 goes to I6 when ' . ' of 2nd production is shifted towards the right (A->a.A) . A is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is the
same i.e. $.

• I2 goes to I7 when ' . ' of 3rd production is shifted towards right (A->b.) . A is seen
by the compiler. Since I6 is a part of the 3rd production, the lookahead is the same
i.e. $.

• I3 goes to I3 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I3 is a part of the 2nd production, the lookahead is the
same i.e. a|b.

• I3 goes to I8 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I8 is a part of the 2nd production, the lookahead is the
same i.e. a|b.
 • I6 goes to I9 when ' . ' of 2nd production is shifted towards the right (A->aA.) . A is
seen by the compiler. Since I9 is a part of the 2nd production, the lookahead is the
same i.e. $.

• I6 goes to I6 when ' . ' of the 2nd production is shifted towards right (A->a.A) . a is
seen by the compiler. Since I6 is a part of the 2nd production, the lookahead is the
same i.e. $.

• I6 goes to I7 when ' . ' of the 3rd production is shifted towards right (A->b.) . b is
seen by the compiler. Since I6 is a part of the 3rd production, the lookahead is the
same ie $.

STEP 3- defining 2 functions:goto[list of terminals] and action[list of non-terminals] in

the parsing table. Below is the CLR parsing table

• $ is by default a non terminal which takes accepting state.

• 0,1,2,3,4,5,6,7,8,9 denotes I0,I1,I2,I3,I4,I5,I6,I7,I8,I9

• I0 gives A in I2, so 2 is added to the A column and 0 row.

• I0 gives S in I1,so 1 is added to the S column and 1st row.

• similarly 5 is written in A column and 2nd row, 8 is written in A column and 3rd
row, 9 is written in A column and 6th row.

• I0 gives a in I3, so S3(shift 3) is added to a column and 0 row.

• I0 gives b in I4, so S4(shift 4) is added to the b column and 0 row.

• Similarly, S6(shift 6) is added on 'a' column and 2,6 row, S7(shift 7) is added on b
column and 2,6 row, S3(shift 3) is added on 'a' column and 3 row, S4(shift 4) is
added on b column and 3 row.
 • I4 is reduced as ' . ' is at the end. I4 is the 3rd production of grammar. So write
r3(reduce 3) in lookahead columns. The lookahead of I4 are a and b, so write R3 in
a and b column.

• I5 is reduced as ' . ' is at the end. I5 is the 1st production of grammar. So write
r1(reduce 1) in lookahead columns. The lookahead of I5 is $ so write R1 in $
column.

• Similarly, write R2 in a,b column and 8th row, write R2 in $ column and 9th row.

Role of Operator Precedence Parser

Introduction: Operator Precedence Parser constructed for operator precedence

grammar. Operator precedence grammar is a grammar that doesn't contain epsilon
productions and does not contain two adjacent non-terminals on R.H.S. of any
production. Operator precedence grammar is provided with precedence rules. Operator
Precedence grammar could be either ambiguous or unambiguous.
Operator Precedence Parser Algorithm:

1. If the front of input $ and top of stack both have $, it's done

else

2. compare front of input b with ⋗

if b! = '⋗'

then push b

scan the next input symbol

3. if b == '⋗'

then pop till ⋖ and store it in a string S

pop ⋖ also

reduce the popped string

if (top of stack) ⋖ (front of input)

then push ⋖ S

if (top of stack) ⋗ (front of input)

then push S and goto 3

Components Operator Diagram:

Components Operator

Example -
Let's take an example to understand the role of operator precedence as follows.

E-> E+T/T

T-> T*V/V
V->a/b/c/d

string= "a+b*c*d"

Implementation of the above algorithm for the string "a+b*c*d" as follows.

Stack Input Stack Top Current Input Action

$ a+b*c*d$ $ a shift a

$a +b*c*d$ a + reduce using V->a

$V +b*c*d$ V + reduce using T->V

$T +b*c*d$ T + reduce using E->T

$E +b*c*d$ E + shift +

$E+ b*c*d$ b * reduce using V->b

$E+V b*c*d$ V * reduce using T->V

$E+T *c*d$ T * shift *

$E+T* c*d$ * c shift c

$E+T*c *d$ c * reduce using V->c

$E+T*V *d$ V * reduce using T->T*V

$E+T *d$ T * shift *

Stack Input Stack Top Current Input Action

$E+T* d$ * d shift d

$E+T*d $ d $ reduce using V->d

$E+T*V $ V $ reduce using T->T*v

$E+T $ T $ reduce using E->E+T

$T $ E $ accept

Algorithm for construction of Precedence function:

1. Generate a function Xa for each grammar terminal a and for the end of the string
symbol.

2. Partition the symbol in groups so that Xa and Yb are the same groups if a ≐ b.

3. Generate a directed graph whose nodes are in the groups, for each symbol a and
b, do place an edge from the group of Yb to the group of Xa if a ⋖ b, otherwise if a
⋗ b place an edge from the group of Xa to that of Yb.

4. If the constructed graph has a cycle then no procedure functions exist. When
there are no cycles collect the length of the longest paths from the groups of Xa
and yb respectively.
Difference Between Bottom-Up and Top-Down Parser

Feature Top-down Parsing Bottom-up Parsing

Direction Builds tree from root to leaves. Builds tree from leaves to root.

Uses rightmost derivation in

Derivation Uses leftmost derivation.
reverse.

Can be slower, especially with More efficient for complex

Efficiency
backtracking. grammars.

Example
Recursive descent, LL parser. Shift-reduce, LR parser.
Parsers