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?
• Types of Parsing
• Video on Parsing in Compiler Design
• Top-down Parsing
  • Recursive Descent Parsing
  • Back-Tracking Parsing

• Bottom-up Parsing
  • Shift-Reduce Parsing
  • LR Parsing

• Why is Parsing useful
• Technologies that use Parsers
• Practice Question Related to Parsing in Compiler Design
• FAQ Related to Parsing in Compiler Design

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:

There are two types of Parsing:

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

• 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.

• • • 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.

• • • 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

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

Also Explore,

• Introduction to Compiler Design
• Code Optimization in Compiler Design
• Intermediate Code Generation in Compiler Design
• Runtime Environment in Compiler Design
• Lexical Analysis
• Logical Operators in C
• Operators in C
• Relational Operators in C
• Comma Operator in C