Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Parser?
3.
LR Parsers
3.1.
Advantages of LR Parsing
3.2.
Types of LR Parsing Methods
4.
SLR(1) Parser
4.1.
Working of SLR(1) Parser
5.
Frequently Asked Questions
5.1.
What is the limitation of the SLR parser?
5.2.
What is a symbol table?
5.3.
What is bootstrapping in compiler design?
6.
Conclusion
Last Updated: Mar 27, 2024

SLR Parser in Compiler Design

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

LR Parsing is a bottom-up parsing method. It is used to parse context-free grammar, which is primarily used by compilers. Shift-Reduce Parsing (SLR Parsing) is a type of LR Parsing that is used to examine the syntax of a given input string. Head over to the below blog to get a better understanding of SLR Parser.

SLR Parser in Compiler Design

The article thoroughly covers the key elements of the Shift-Reduce Parsing (SLR Parsing) algorithm. It describes how the algorithm works, constructing a parsing table from the input symbols along with the stack implementation of a test input.

What is a Parser?

A parser is a piece of software that typically comes with a compiler. It receives input using defined interfaces such as markup tags, interactive online commands, and sequential source program instructions. The information that parsers receive is divided into components such as nouns (things), verbs (methods), and their characteristics or alternatives. A parser may additionally verify that all required input has been supplied. There are two types of parsers in compiler technology; top-down parsers and bottom-up parsers.

When parsing is done top-down, the input symbol is first transformed into the start symbol. The bottom-up method of parsing builds the parse tree from the input symbol to the start symbol by reversing the rightmost string derivations.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

LR Parsers

The LR parser is a bottom-up, shift-reduced, non-recursive parser. It employs a broad class of context-free grammar, making it the most effective syntax analysis tool. LR parsers are also referred to as LR(k) parsers, where L stands for left-to-right scanning of the input stream, R for building the right-most derivation backward, and k is the number of lookahead symbols to be used for decision-making. Programming languages of all kinds can be handled by LR parsers, which are strong and effective. They are utilized by a number of well-known interpreters and compilers, including the Python interpreter and the GCC compiler.

Advantages of LR Parsing

Some of the significant advantages of LR parsing are given as follows:

  • LR parsers can parse a strictly larger class of grammars than (top-down) predictive parsers.
     
  • LR parsers can usually recognize all programming language constructs specified by a context-free grammar.
     
  • It understands almost every programming construct that CFG may be expressed in.
     
  • LR parsers detect errors quickly.

Types of LR Parsing Methods

LR parsing contains three types of methods which are discussed below:

  • Simple LR(SLR): Execution is relatively simple and inexpensive. But for particular classes of grammar, it is unable to create a parsing table. It creates parsing tables that aid in performing input string parsing. SLR Parsing is possible with the provision of context-free grammar.
     
  • Canonical LR(CLR): The CLR (1) parsing table is built using the canonical set of LR (1) entries. Compared to SLR (1) parsing, the CLR (1) parsing table creates more states. It can only find the reduction node in the lookahead symbols in the CLR (1).
     
  • Look-Ahead LR(LALR): it has a medium level of power as compared to SLR and CLR parsers. The tables that result from this will be smaller than those from the CLR Parser because it is compacted.

SLR(1) Parser

SLR (1) refers to simple LR Parsing. It is similar to LR(0) parsing because LR(0) parsing requires just the canonical items for the construction of a parsing table, The only thing that differentiates the LR(0) parser from the SLR parser is the possibility of a shift reduced conflict because we are entering reduce corresponding to all terminal states in the LR(0) parsing table. This issue can be resolved by entering "reduce" in the terminating state, which corresponds to the FOLLOW of the LHS of production. This collection of items is known as SLR(1). A collection of rules is used to create the table using the provided grammar in order to determine the closure and goto operations for each state. The SLR parsing algorithm is reasonably easy to use and effective.

The various steps involved in the SLR (1) Parsing are shown in the given flowgraph:

Flowgraph for Steps of SLR

Working of SLR(1) Parser

An SLR (Simple LR) parser is a bottom-up parsing technique that uses a deterministic finite automaton (DFA) to recognize the valid syntax of a language. A parse table is produced by this parser from a collection of grammar rules and the DFA. The grammar rule to apply at each stage of the parsing process is subsequently determined using the parse table.

Let's look at an example to better understand how the SLR parser functions.

Implement SLR Parser for the given grammar:

1. E→E + T

2. E→T 

3. T→T * F 

4. T→F 

5. F→(E) 

6. F→id 

Step 1: Create augmented grammar using the provided grammar.

Augmented grammar: 

E'→E

E→E + T 

E→T 

T→T * F 

T→F 

F→(E) 

F→id 

Step 2: Find LR(0) canonical Items

GOTO (I0, E)

l1: E’->E.

     E->E.+T
 

GOTO (I0, T)

l2: E->T.

     T->T.*F
 

GOTO (I0, F)

l3: T->F.
 

GOTO (I0, ( )

I4: F->(.E)

     E->.E+T

     E->.T

     T->.T*F

     T->.F

     F->.(E)

     F->.id
 

GOTO (I0, id)

I5: F->id.
 

GOTO (I1, +)

I6: E->E+.T

     T->.T*F

     T->.F

    F->.(E)

    F->.id
 

GOTO(I2, *)

I7: T->T*.F

     F->.(E)

     F->.id
 

GOTO(I4, E)

I8: F->(E.)

     E->E.+T
 

GOTO(I4, T)

I2: E->T.

     T->T.*F
 

GOTO(I4, F)

I3: T->F.
 

GOTO(I4, ( )

I4: F->(.E)

     E->.E+T

     E->.T

     T->.T*F

     T->.F

     F->.(E)

     F->.id
 

GOTO(I4, id)

I5: F->id.
 

GOTO(I6, T)

I9: E->E+T.

T->T.*F
 

GOTO(I6, F)

I3: T->F.
 

GOTO(I6, ( )

I4: F->(.E)
 

GOTO(I6, id)

I5: F->id.
 

GOTO(I7, F)

I10: T->T*F.
 

GOTO(I7, ( )

I4: F->(.E)

     E->.E+T

     E->.T

     T->.T*F

     T->.F

     F->.(E)

     F->.id
 

GOTO(I7, id)

I5: F->id.
 

GOTO(I8, ) )

I11: F->(E).
 

GOTO(I8, +)

I6: E->E+.T

     T->.T*F

     T->.F

     F->.(E)

     F->.id
 

GOTO(I9, *)

I7: T->T*.F

     F->.(E)

     F->.id

Step 3: Construct the Parsing table

To fill the reduction action in the ACTION section of the table, computation of FOLLOW is necessary. 

Follow(E): {$, ), +}

Follow(T): {$, +, ), *}

Follow(F): {*, +, ), $}

Parsing Table

In the above parsing table:

  • si means to shift and stack state i.
     
  • rj means reduce by production numbered j.
     
  • acc means accept.
     
  • Blank means error.
     

Step 4: Parse the given input. Parse the string id*id+id using stack implementation.

Stack  Input Action
0 id*id+id$ s5 Shift 5
0 id 5 *id+id$ r6 Reduce by F->id
0 F 3 *id+id$ r4 Reduce by T->F
0 T 2 *id+id$ s7 Shift 7
0 T 2 * 7 id+id$ s5 Shift 5
0 T 2 * 7 id 5 +id$ r6 Reduce by F->id
0 T 2 * 7 F 10 +id$ r3 Reduce by T->T*F
0 T 2 +id$ r2 Reduce by E->T
0 E 1 +id$ s6 Shift 6
0 E 1 + 6 id$ s5 Shift 5
0 E 1 + 6 id 5 $ r6 Reduce by F->id
0 E 1 + 6 F 3 $ r4 Reduce by T->F
0 E 1 + 6 T 9 $ r1 Reduce by E->E+T
0 E 1 $ Accept

Using the SLR parser, the given input string has been fully parsed as shown in the table above.

Frequently Asked Questions

What is the limitation of the SLR parser?

One of the key limitations of SLR is that it can only handle grammars that fall under the SLR(1) class, which implies that the grammar must be straightforward and have only one lookahead symbol.

What is a symbol table?

The Symbol Table is an essential data structure that the compiler creates and maintains to keep track of the semantics of variables, which means, it keeps the information about the scope and binding of names, information about instances of various things, etc.

What is bootstrapping in compiler design?

Bootstrapping is the process of translating more complex programs into basic language, which may then be used to manage more complex programs. This complex program can manage still more complex programs, and so on.

Conclusion

This article explains the concepts of LR parsers, their advantages, and a complete working of SLR parsers using an example. We sincerely hope you enjoyed reading the article and learned a lot about this topic. For a better understanding of the subject, you can further refer to the Recursive Descent ParserBottom-Up Parsing, and LR Parsing.

For more information, refer to our Guided Path on Coding Ninjas Studio to upskill yourself in PythonData Structures and Algorithms, Competitive ProgrammingSystem Design, and many more! 

Head over to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more! 

Happy Learning Ninja!

Previous article
Polish Notation in Compiler Design
Next article
Symbol Tables in Compiler Design
Live masterclass