PLC Nick

Question 1

Describe what it means for a grammar to be ambiguous

Answer 1

A grammar is ambiguous if two or more parse trees can be derived for a given string

Question 2

In the exam, how should you show ambiguity?

Answer 2

Do parse trees, or much easier is to select a part of the grammar and double it, such that it’s not clear what’s first or not. Like selecting the rule E;E, put down (E;E);E, E;(E;E). Make sure to replace E with actual values

Question 3

In a layered grammar, how do you show binding?

Answer 3

Loosest at the top, Tightest at the bottom

Question 4

In a grammar, how do you show left/right association?

Answer 4

F::= F;G|G, F is forced to left of ; so ; is left associated. F::= G;F|G, F is forced to right of ; so ; is right associated.

Question 5

E ::= xD | D | if (E < D)then E | E:=E +E |E;E |(E)
D::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Answer 5

E ::= if (E<D) then E | F
F ::= F;G | G
G ::= H := E + G | H
H ::= xD | D | (E)