Parsing in Compiler Design Notes for GATE

Parsing is an important topic belonging to the Computer Science family. And, when you want to attempt any competitive examinations like the GATE Exam, you need to have a complete idea about the parsing in compiler design.

This article will help you to understand and get deep information about parsing in compiler design. We hope that the information contained in the GATE notes for the CSE topics will help you understand this topic in a better way.

What is Parsing in Compiler Design?

The process of transforming the data from one format to another is called Parsing. This process can be accomplished by the parser. The parser is a component of the translator that helps to organise linear text structure following the set of defined rules which is known as grammar.

Types of Parsing:

Types of Parsing

There are two types of Parsing:

  • The Top-down Parsing
  • The Bottom-up Parsing

Parsing Types

  • Top-down Parsing: When the parser generates a parse with top-down expansion to the first trace, the left-most derivation of input is called top-down parsing. The top-down parsing initiates with the start symbol and ends on the terminals. Such parsing is also known as predictive parsing.

Top- Down Parsing

      • Recursive Descent Parsing: Recursive descent parsing is a type of top-down parsing technique. This technique follows the process for every terminal and non-terminal entity. It reads the input from left to right and constructs the parse tree from right to left. As the technique works recursively, it is called recursive descent parsing.
      • Back-tracking: The parsing technique that starts from the initial pointer, the root node. If the derivation fails, then it restarts the process with different rules.
  • Bottom-up Parsing: The bottom-up parsing works just the reverse of the top-down parsing. It first traces the rightmost derivation of the input until it reaches the start symbol.

Bottom-up parsing

      • Shift-Reduce Parsing: Shift-reduce parsing works on two steps: Shift step and Reduce step.
        • Shift step: The shift step indicates the increment of the input pointer to the next input symbol that is shifted.
        • Reduce Step: When the parser has a complete grammar rule on the right-hand side and replaces it with RHS.
      • LR Parsing: LR parser is one of the most efficient syntax analysis techniques as it works with context-free grammar. In LR parsing L stands for the left to right tracing, and R stands for the right to left tracing.

Video on Parsing in Compiler Design

Why is parsing useful in compiler designing?

In the world of software, every different entity has its criteria for the data to be processed. So parsing is the process that transforms the data in such a way so that it can be understood by any specific software.

The Technologies Use Parsers:

  • The programming languages like Java.
  • The database languages like SQL.
  • The Scripting languages.
  • The protocols like HTTP.
  • The XML and HTML.

Practice Problem Related To Parsing in Compiler Design

Q. Which one of the following kinds of derivation is used by LR parsers?

  • (A) Leftmost
  • (B) Leftmost in reverse
  • (C) Rightmost
  • (D) Rightmost in reverse

Q. Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR

II. SLR is more powerful than LALR.

III. SLR is more powerful than Canonical LR.

  • (A) I only
  • (B) II only
  • (C) III only
  • (D) II and III only

Frequently Asked Questions on Parsing in Compiler Design

What is LR Parsing?

LR parser is one of the most efficient syntax analysis techniques as it works with context-free grammar. In LR parsing L stands for the left to right tracing, and R stands for the right to left tracing.

What is parsing and its types?

Parser is a compiler that is used to break the data into smaller elements coming from lexical analysis phase.

What is parsing in programming?

To parse, in computer science, is where a string of commands – usually a program – is separated into more easily processed components, which are analyzed for correct syntax and then attached to tags that define each component.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility CriteriaGATE 2023GATE Admit CardGATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Also Explore,

Leave a Comment

Your Mobile number and Email id will not be published.