Test: Parsing Techniques- 2 - Computer Science Engineering (CSE) MCQ

To recover from an error actions taken by operator precedence parser:
1. Insert symbols onto stack.
2. Delete symbols from the stack.
3. Insert or delete symbols from the input.

In shift-reduce parsing "the handle will always appear inside the stack and reversor top”.

II. LALR parser is more powerful than an SLR parser: True, Canonical LR is the most powerful parser as compared to other LR parsers. Order: LR(0)< SLR < LALR < CLR.

III. Recursive descent parsing is an example of top-down parsing: True, Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking.

Hence the correct answer is II and III.

• LALR is less powerful than CLR but more costly than any parser.
• Every SLR grammar is unambigous but every unambigous grammar need not be SLR i.e. may be LALR but not SLR. 
• LR(K) grammar never using backtracking.

Definition of Follow (A) as per question “The set of terminals that can appears immediately to the right of non-terminal A in same sentential form”. If the above definition is changed to replace “ sentential” with “ left-most sentential” for L FOLLOW (A) and “right-most sentential” for R FOLLOW (A)

We are still considering the terminal symbol to the right of A ’ .
Hence all three sets would be identical

LR(1) parsing is sufficient for deterministic context-free languages: True, LR(k) grammars (also known as deterministic context-free grammars) allow parsing (string recognition) with deterministic pushdown automata (PDA), they can only define deterministic context-free languages.

An ambiguous grammar have more than one leftmost or rightmost derivation tree.

E→ number \ E' + E' \ E' x E'

Then YACC compiler detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action.
Consider the following configuration where shift- reduce conflict occurs

Stack Input

.... E + E x . E . . $

A handle may be described as the sentencial form given by the bottom up parser from left to right in reverse order.

LALR(1) parser for a grammar, G can have shift- reduce ( S - R) conflicts if and only if there is a S - R conflict in its immediate sub-parsers (e.g. LR(1)). If LR(0) has S - R conflicts then they may get removed in LR (1), hence there will be no S - R conflict in LALR(1).

So, parsing table must not contain entry 

 since Y→a production not present in grammar.

Some possible stack contents are aaS, ab, b, etc.

So E + E x E is not a handle for the expression.

Given grammar can be parsed using both Top- down and bottom up parsing methods for the input string “ccbca"