4/6

Next Previous Contents Fulltext First Last

Exercises 3: Parsing, syntax-directed translation, type checking

Programming Languages 2010

1. Trace the LR parsing of the statement 

    if (x + y > 4) if (true) {x = y = y - 1 ;} else 8 ;

in the grammar 

    Stm   ::= "if" "(" Exp ")" Stm "else" Stm ;
    Stm   ::= "if" "(" Exp ")" Stm ;
    Stm   ::= "{" [Stm] "}"
    Stm   ::= Exp ";"
    Exp2  ::= Integer
    Exp2  ::= Ident
    Exp1  ::= Exp1 "+" Exp2
    Exp1  ::= Exp1 "-" Exp2
    Exp   ::= Exp1 ">" Exp1
    Exp   ::= Ident "=" Exp
    [Stm] ::= 
    [Stm] ::= Stm [Stm]
    Exp2  ::= "(" Exp ")"
    Exp1  ::= Exp2
    Exp   ::= Exp1

Do this by showing the evolution of the stack and the input, and whether shift or reduce actions are taken.

2. Consider the language 'X'*, i.e. sequences of symbol X. Write two context-free grammars for it: one left-recursive and one right-recursive. With both grammars, trace the LR parsing of the string XXXX. What can you say about the memory consumption of the two processes?

3. Write a calculator for the four floating point operations (+ - * /) by using the semantic actions in one of the standard parser tools (Happy, CUP, Bison). You can start by writing an expression grammar in BNFC and then modify the generated parser file.

To make the usage of the calculator smooth, also accept input without a decimal point, e.g. 3 * 3.14. The usual operator precedences must of course be followed.

4. Semantic actions can be used to make the parser manage languages that are not context-free. Write a Happy/JLex/Cup program that implements a parser for a copy language, where valid expressions are sequences of identifiers (Ident), with any such sequence followed by itself: 

    {x x | x : Ident*}

For instance, foo bar foo foo bar foo is a valid expression, but foo bar foo bar foo isn't. What is the time complexity of the parser?

5. Using the grammar of Question 1, write a syntax-directed thanslator that returns a symbol table indicating the number of occurrences of each identifier that occurs in the program (i.e. a Stm). For instance, in the program 

    {
      x = 3 ;
      x = 2 - x - y ;
      if (x > y) {x = x-1 ;}
    }

the identifier x occurs 6 times and y occurs 2 times.

6. Using the typing rules of lecture 7,, write a derivation of the validity of the statement 

    while (x > 4) {x = x-1 ;}

You will need a context and a couple of extra typing rules.

7. Write typing rules for the following constructs of C/C++, which are not covered by Lab 2.