PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q6(b)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Lexical Analysis with DFA; Top-Down & Bottom-Up Parsing

Question

Construct the parse tree for the following.

Solution

Context-Free Grammar for Expressions with Precedence: The standard unambiguous expression grammar enforcing operator precedence (parentheses first, then and , then ) is:

Given statement: with identifier tokens .

Derivation and Parse Tree Construction: Derivation:

Hierarchical Parse Tree:

                 S
             /   |   \
           id    =     E
           (r)       / | \
                    E  +  T
                    |    /|\
                    T   T / F
                    |  /|\   /|\
                    F T * F ( E )
                    | |   |   |
                    a F   c   T
                      |      /|\
                      b     T * F
                            |   |
                            F   e
                            |
                            d

Yield: .

Answer:

Using standard expression grammar , , , the parse tree correctly nests under parentheses , groups multiplication and division with left-associativity , and adds at the top level.

All past exam questions for Theory of Computation