PRINCIPLES OF COMPILER DESIGN,TWO MARKS ,UNIT II

1. Define CFG.

The context free grammar consists of terminals, non terminals, a start symbol, and productions.

            G = (V, T, P, S)

            V-> variables or non terminals (uppercase letters)

            T-> terminals (lowercase letters, operator symbols, digits)

S-> start symbol

P-> productions.

                        Ex:

                                    E->E+E / id

2. What is an ambiguous grammar? Give an example.

·         A grammar that produces more than one parse tree for the same sentence.

·         An ambiguous grammar produces more than one leftmost or more than one rightmost derivation for the same sentence.

Ex:

            E->E+E / E*E / E-E / id

            Input string is id + id * id

3.    What is handle pruning?

->A rightmost derivation in reverse can be obtained by “handle-pruning.”

->The process of discovering a handle & reducing it to the appropriate    left-hand side is called handle pruning.

->Handle pruning forms the basis for a bottom-up parsing method.

Ex:

S ® aABe

A ® Abc | b

B ® d

abbcde

Find the handle = b at loc. 2

aAbcde

b at loc. 3 is not a handle:

aAAcde

... blocked.

4. Define left factoring.

Left factoring is a grammar transformation that is useful for producing a grammar suitable for predictive parsing. Two alternative productions to use to expand a nonterminal A.

            A-> αβ₁ / αβ₂

 After applying left factoring

            A-> α A^’

                A-> β₁ / β₂

                        For example consider the following grammar: –

                        S-> iEtS  |  iEtSeS  |  a

                        E -> b

The left factored grammar becomes

S->iEtSS’ | a

S ‘->eS | ε

E ->b

5. What are the properties of operator precedence parsing?

The operator precedence grammar, no production rule can have:

àe at the right side

     àTwo adjacent non-terminals at the right side.

Ex:

      E®AB                                   E®E+E |

                  A®a                                 E*E |

                  B®b                                 E/E | id

       not operator grammar       operator grammar 

6. Define viable prefixes.

The set of prefixes of right sentential forms that can be appearing on the stack of a shift reduce parser. It is a prefix of right sentential form that does not continue past the right end of the rightmost handle of that sentential form.

7. List out the actions involved in shift-reduce parsing.

                                                              i.      Shift -> The next input symbol is shifted onto the top of the stack.

                                                            ii.      Reduce-> It must locate the left end of the handle within the stack and decide with non terminals to replace the handle.

                                                          iii.      Accept-> The parser announces successful completion of parsing.

                                                          iv.      Error-> The parser discovers that a syntax error has occurred and calls an error recovery routine.

8. What are the different types of conflicts occurs in shift reduce parsing?

                                                              i.      shift/reduce conflict -> parser cannot decide whether to shift or to reduce

                                                            ii.      reduce/reduce conflictàparser cannot decide which of several reductions to make

9. What are the recovery strategies in a parser?

                                                              i.      Panic mode recovery

                                                            ii.      Phrase level.

                                                          iii.      Error productions.

                                                          iv.      Global correction

10. Eliminate the left recursion for the given grammar:

E->E+T/T

T->T*F/F

F->(E) / id.

After eliminating the left recursion

            E->TE’

            E’->+TE’ / ε

            T->FT’

            T’->*FT’ / ε

            F->(E) / id

11. Write a rule to construct precedence function table.

Ø  For each production A-> α of the grammar do step 2 and 3.

Ø  For each terminal a in FIRST (α), add A-> α to M [A, a].

Ø  If ε is in FIRST (α), add A-> α to M [A, b] for each terminal b in FOLLOW (A). If ε is in FIRST (α) and $ is in FOLLOW (A), add A-> α to M[A, $].

Ø  All the remaining entries in table M are marked as SYNTAX ERROR

12. Write down the rules for left recursion.

                                    To eliminate left recursion we need to modify the grammar having

a production rule with left recursion.

                              A        Aα  / β

Then we eliminate left recursion by re-writing the production rule as:

                        A         βA ‘

                        A’         αA ‘  /  ε

13. What are the goals of error handler in a parser?

1.      It should report the presence of errors clearly and accurately.

2.      It should recover from each error quickly enough to be able to detect subsequent errors.

3.      It should not significantly slow down the processing of correct programs.

14. Differentiate Top down and bottom up approach with an example.

Sl.No	Top down parsing (LL(1), recursive descent)	Bottom up parsing (LR(k), operator precedence and shift reduce parsing)
1	Start at the root of the parse tree from the start symbol and grow toward leaves (similar to a derivation)	Start at the leaves and grow towards the root.
2	Pick a production and try to match the input	We can think of the process as reducing the input string to the start symbol
3	Bad “pick” Þ may need to backtrack	At each reduction step a particular substring matching the right-side of a production is replaced by the symbol on the left-side of the production
4	Some grammars are backtrack-free  (predictive parsing)	Bottom-up parsers handle a large class of grammars
5.	Ex: E->E+E /E * E / id Top down: E=>E+E E=>E+E*E E=>id+E*E E=>id+id*E E=>id+id*id	E->E+E / E* E / id Bottom up: =>id+id*id =>E+id*id =>E+E*id =>E+E*E =>E+E =>E

15. Eliminate the left recursion from the following grammar

A->Ac / Aad / bd / c

After eliminating the left recursion

A->bdA’ / A’

A’->cA’ / adA’ / ε

16. Differentiate SLR, CLR, and LALR parser.

S.NO	SLR	CLR	LALR
	Small in parser size	Larger than SLR	Same as SLR in Size
	Less powerful than CLR	More powerful than SLR	Less powerful than CLR.But the Syntactic features can be expressed in the grammar of LALR.
	Time and space complexity is less	More time and space complexity	Intermediate time and space complexity.
	Error detection is not immediate in SLR	Error detection is immediate in LR	Error detection is not immediate in LALR
	Its not applicable in all Ambiguous grammar	Its applicable to ambiguous grammar than SLR	Its Applicable to all ambiguous grammar.

17. What are kernel and non-kernel items?

Kernel items:

            It is the collection of item S’-> .S and all the items whose dots are at the leftmost end of RHS of the rule.

Non – Kernel items:

            It is the collection of all the items   in which ‘ . ‘ are at the leftmost and  RHS of the rule.

18. What are the disadvantages of operator precedence parsing?
1. It cannot handle the unary minus (the lexical analyzer should handle   the unary minus).
2. Small class of grammars.
3. Difficult to decide which language is recognized by the grammar.

19. Define LR (k).

A grammar that can be parsed by an LR parser examining to up k input symbols on each move is called LR (k) grammar. We must be able to recognize the occurrence of the right side with k input symbols. We must be able to recognize the use of a production seeing only the first k symbols of what its right side derives.

            L-> denotes that input sequence is processed from left to right.

            R-> denotes that the right most derivation is performed.

            k-> denotes that at most k symbols of the sequence are used to make a decision.

20. Define SLR.

SLR-> Simple LR (LR (0))

            The idea is construction of a DFA from the grammar.

A grammar for which an SLR parser can be constructed is said to be SLR grammar.

            An LR (0) of a grammar G is a production of G with a dot operator at some position of the right side.

            Ex: A->XYZ yields four items.

                        A->.XYZ

                        A->X.YZ

                        A->XY.Z

                        A->XYZ.