### Abstract grammar expression tree - Attribute Grammars

Posted:

**Sat Dec 10, 2016 1:00 pm UTC**I'm studying for my programming languages exam and I missed the lecture relating to the question below. Could somebody please explain to me how to go about this it?

Question 4 (Semantics)

Consider the following simple abstract grammar for expression trees that represent sequences of left or right turns.

M : M "then" M

I M "or" M

I "left"

I "right"

I "forwards"

I "backwards".

A then-construct means to first execute the steps in the left-hand expression, then execute the steps in the right-hand expression. An or-construct means to randomly choose between executing either all of the left-hand side expression or all of the right-hand side expression. For example, the expression left then (right or left) then right will either execute the sequence left, right, right or the sequence left, left, right. (Note that the parentheses are not part of the abstract grammar; they are just used to indicate the grouping of constructs in the abstract tree.)

(a) Write attribute grammar equations for this grammar that calculate the minimum number of steps that could be taken by the steps encoded by an expression. For example, the example above will execute a minimum of three steps. Clearly indicate which grammar rules have which equations. [14 marks]

Thanks.

Question 4 (Semantics)

Consider the following simple abstract grammar for expression trees that represent sequences of left or right turns.

M : M "then" M

I M "or" M

I "left"

I "right"

I "forwards"

I "backwards".

A then-construct means to first execute the steps in the left-hand expression, then execute the steps in the right-hand expression. An or-construct means to randomly choose between executing either all of the left-hand side expression or all of the right-hand side expression. For example, the expression left then (right or left) then right will either execute the sequence left, right, right or the sequence left, left, right. (Note that the parentheses are not part of the abstract grammar; they are just used to indicate the grouping of constructs in the abstract tree.)

(a) Write attribute grammar equations for this grammar that calculate the minimum number of steps that could be taken by the steps encoded by an expression. For example, the example above will execute a minimum of three steps. Clearly indicate which grammar rules have which equations. [14 marks]

Thanks.