This page is not intended to be used on mobile devices, as it relies on the use of such functions, as the mouse wheel or the mouse hover.

Attribute Grammar Tutor

Attribute
Grammar

X -> X

This exercise can only be solved, after all local dependency graphs have been drawn correctly.

Please finish drawing the local dependency graphs and then click on "Check" for every graph, or click on "Check all" to correct them at once.

X -> X

Cycle found?

yes

R ( X ) =

Iteration stable?

yes

no

yes

Attribute Grammar
Local dependency graphs
Strong acyclicity

Attribute Grammar

Buttons

Apply: Parses the specified attribute grammar and generates two exercises based on it: Local dependency graphs and Strong acyclicity. The editing of the grammar is disabled. If errors were found, they are displayed, and they must be removed, before the exercises can be generated.
Edit: Warning! Clicking on Edit will delete the exercises and any changes you made to them. This cannot be undone.
Afterwards, the attribute grammar can be edited again.
Load attribute grammar: Displays a list of the provided attribute grammars. By clicking on one of them, the selected grammar is loaded into the text area.

Format

Production Rules

One production rule per line.
The first non-terminal is separated from the remaining (non-)terminals by an arrow ->.
EG:S -> A B
(Non-)terminals on the right-hand side of the production rule are separated by a whitespace.
The production rule is separated from its attribute equations by a colon :. The attribute equations are on the same line as the corresponding production rule.
EG:production rule : attribute equations
An empty symbol (ε) is represented by an empty right-hand side of the production rule.
EG:The rule S → ε would be represented as: S -> : …
The name of the (non-)terminals may not contain the characters [, ], ;, =.

Attribute equations

Attribute equations are separated by a semicolon ;.
The format of an attribute equation is: right side = left side.
The left-hand side is composed of just one attribute, whereas the right-hand side can contain several attributes.
An attribute is composed of its name (any letters or digits), followed by the index of the corresponding (non)-terminal in square brackets [].
EG:a[1], attr2[0], 1337[42]
An attribute equation can contain any sort of expression. It will be ignored, when extracting the attributes.
EG:a[0] = max(a[1], a[2]) - the extracted attributes will be a[0], a[1] and a[2].
According to the convention, for example, equation a[0] = b[0] reads as: "Attribute a depends on attribute b." and implies a dependency from b to a.

Local dependency graphs

Buttons

Check: Performs a check of the correctness of the graph representation of the production rule. If any error is found, a list of relevant error messages can be displayed by clicking on the red warning button.
Clear: Completely erases everything on the graph canvas. Cannot be undone!
Draw tree: The syntax tree is automatically drawn on the canvas. This helps you focus on adding the correct attributes and their dependencies. Any changes made to the graph will be erased, before the syntax tree is drawn.
Show solution: Shows the correct graph representation of the production rule, with all the attributes and their dependencies. Any changes made to the graph will be erased, before the solution is drawn.
: Recenters and fits the content to the canvas.

Draw

New syntax tree node

A mouse double click on any empty part of the canvas creates a new syntax tree node.

New attribute node

Hover over the corresponding (non-)terminal. Click on the orange circle with a plus sign, which appears on its right side.

Rename node

Hover over the node and use the mouse wheel scroll to choose the correct name.

Syntax tree: only the (non-)terminal names of the corresponding production rule will be toggled.
Attributes: all attribute names from the whole attribute grammar will be toggled. This is due to the fact, that some attributes may be defined in a different production rule.

Connect nodes

Move the mouse pointer to the border of the node, from which you want the draw the edge. Click and drag the new edge to the other node. Only nodes of the same type can be connected. If you release the mouse button midway, no connection is created.

Reconnect nodes

To move an edge to another node, click and drag the arrow from one node to the other node.

Rearrange edges

To rearrange the path of an edge, click on the edge to create a new vertex.
To move this vertex, click and drag it to any other position.
To delete a vertex, double click on it.

Delete element

Hover over the element and click on the gray circle with a cross.
You can also delete an element by hovering over it and pressing the Del key on the keyboard.
Another option is to middle click on the element to be deleted. This, however, does not work on edges.

Zoom

To zoom in or zoom out, use the mouse wheel over any empty point on the graph canvas.

Pan

Click and drag any blank point on the graph canvas.

Strong acyclicity

Objective: perform the algorithm to find out, whether the attribute grammar is strongly acyclic.
This exercise leads you through the process of establishing the transitive relations and the different iterations, until the algorithm stabilizes.

R (X) [ i ]: Redecorate the relations from previous iterations to the non-terminals in the current production rule.
Draw the redecorated relations using green edges between the correct attributes of the corresponding non-terminal.
⟦ p ⟧^# ( R (X₁), ..., R (X_k) ): Establish the root projection of the transitive closure of the production rule relations.
Draw the root projection using yellow edges between the correct attributes.
R (X): Write down the union of all transitive relations from the production rules of the corresponding non-terminal.
Please use the following format: a relation from attribute a to attribute b is represented as (a, b).