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.

• conditional expressions `e ? e : e`
• operator assignments `x+=e, x-=e`
• assignment to an array position `e[i] = e`