(Aktu Btech) Compiler Design Important Unit-2 Basic Parsing Techniques

With B.Tech AKTU Quantum Book, you can delve into the complexities of Compiler Design. Access key notes, frequently asked questions, and helpful insights for understanding this critical area. Unit-2 Basic Parsing Techniques

Dudes 🤔.. You want more useful details regarding this subject. Please keep in mind this as well.

Important Questions For Compiler Design:
*Quantum               *B.tech-Syllabus
*Circulars                *B.tech AKTU RESULT
* Btech 3rd Year     * Aktu Solved Question Paper

Q1. Explain about basie parsing techniques. What is top-down parsing? Explain in detail.

Ans. A parser for any grammar is a program that takes as input string w and produces as output a parse tree for ω.

Role of parser: 

• 1. The role of parsing is to determine the syntactic validity of a source string. 
• 2. Parser helps to report any syntax errors and recover from those errors. 
• 3. Parser helps to construct parse tree and passes it to rest of phases of compiler.  

There are basically two type of parsing techniques: 

• 1. Top-down parsing: 
  • a. Top-down parsing attempts to find the left-most derivation for an input string ω, that start from the root (or start symbol), and create the nodes in pre-defined order. 
  • b. In top-down parsing, the input string ω is scanned by the parser from left to right, one symbol token at a time. 
  • c. The left-most derivation generates the leaves of parse tree in left to right order, which matches to the input scan order. 
  • d. In the top-down parsing, parsing decisions are based on the lookahead symbol (or sequence of symbols). 
• 2 Bottom-up parsing: 
  • a. Bottom-up parsing can be defined as an attempt to reduce the input string ω to the start symbol of a grammar by finding out the right most derivation of ω in reverse. 
  • b. Parsing involves searching for the substring that matches the right side of any of the productions of the grammar. 
  • c. This substring is replaced by the left hand side non-terminal of the production
  • d. Process of replacing the right side of the production by the left side non-terminal is called “reduction”. 

Q2. What are the common conflicts that can be encountered in shift-reduce parser ?

Ans. There are two most common conflict encountered in shift-reduce parser:

• 1. Shift-reduce conflict: 
  • a. The shift-reduce conflict is the most common type of conflict found in grammars. 
  • b. This conflict occurs because some production rule in the grammar is shifted and reduced for the particular token at the same time.
  • c. This error is often caused by recursive grammar definitions where the system cannot determine when one rule is complete and another is just started.
• 2. Reduce-reduce conflict: 
  • a. A reduce-reduce conflict is caused when a grammar allows two or more different rules to be reduced at the same time, for the same token. 
  • b. When this happens, the grammar becomes ambiguous since a program can be interpreted more than one way. 
  • c. This error can be caused when the same rule is reached by more than one path.

Q3. Eliminate left recursion from the following grammar

Ans. 

The production after left recursion is

Q4. Differentiate between top-down and bottom-up parser. Under which conditions predictive parsing can be constructed fora grammar ? 

Ans. 

Predictive parsing can be constructed if the following condition holds: 

• 1. Every grammar must be recursive in nature. 
• 2. Each grammar must be left factored. 

Q5. Construct an SLR(1) parsing table for the following grammar:

Ans. The augmented grammar G’ for the above grammar G is:

The canonical collection of sets of LR(0) item for grammar are as follows:

Q6. Eliminate left recursion from the following grammar S → (L) |aL → L, S|S

i. (a,(a, a))                                          ii. (a,a) 

Ans. i. 

ii. 

Compiler Design Btech Quantum PDF, Syllabus, Important Questions

Compiler Design Quantum PDF | AKTU Quantum PDF:

AKTU Important Links | Btech Syllabus

Important Links-Btech (AKTU)