Abstract grammar expression tree - Attribute Grammars

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Posts: 1
Joined: Sat Dec 10, 2016 8:37 am UTC

Abstract grammar expression tree - Attribute Grammars

Postby TwelveMoons » 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]


User avatar
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Abstract grammar expression tree - Attribute Grammars

Postby Flumble » Mon Dec 12, 2016 5:03 pm UTC

So how much effort have you put into understanding attribute grammars so far? Have you viewed lecture slides, the chapter in the recommended book for the course, visited the wiki page or any other (more tutoring) sources on the internet?

This question in particular only deals with synthesized attributes, which I believe you've learned and used further along the course too (because it doesn't really make sense to stop a course at the introduction to attribute grammars). Those set a property of each node using a function (usually per alternative) and possibly some properties of child nodes. See for example the attribute grammar on the aforementioned wiki page.

Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 12 guests