This chapter explains the creation of an attribute gammar from a given
yacc grammar and how to use Torero's tools. An attribute grammar for calculating
the decimal value of a binary floating point number is used as example. Basic
knowledge about Attribute Gammars is expected to understand the following
steps. Being familiar with the ox notation for attribute references is also
required because Torero is using the same syntax.
The example is also available as download under:
During the workflow a given yacc file is extended to an Attribute Grammar.
After this is done it can be exported to the ox format for further processing.
Begin by loading the yacc file specifying the grammar of a binary floating point number. Click File | Import Yacc Grammar to open a file chooser dialog. Then select the yacc file ag_bsp1.y from the tutorial folder and push the open button in the file chooser dialog.
If the given yacc file is accurate, Torero shows an appropriate status message in the status line (Parsing and building ag_bsp1.y in 40 msec). If the yacc grammar contains some harmless faults, a parser log window will appear to inform about it. Torero tries to be as fault-tolerant as possible but has some limitations in comparison with yacc.
After loading the grammar it can be browsed by means of derivations. Explore the grammar by building some derivations. To start a new derivation click Derivations | <New Derivation>. This brings up a dialog for selecting a production as the root of the new derivation. Select the Production
S -> L '.' L
(This should be the last entry in the list).
Press the Create Derivation button to move on. A new maximized derivation window appears on the screen. Now the previously selected production is visualized as a tree. It can be expanded easily. The tree is a graphical representation of a derivation in the current grammar. Now try to build a derivation for the word L101,01.
There are two kinds of nodes. The red nodes (with the little T on the right side) represent terminal symbols. The blue nodes (with the N) represent non-terminal symbols. This type of symbols can be used to extend the derivation. By pressing the right mouse button on it, a popup menu of productions which can be used to extend this non-terminal appears.
For the tutorial expand the non-terminal L on the left side of the tree with the production L -> L B. Apply the same production two times more on the leftmost non-terminal. Now try to apply productions standalone and build the derivation tree shown below.
Now define the attributes needed for calculating the decimal value from a parse tree representing the derivation of a word in the grammar of binary floating point decimals. For this two attributes are needed. One for calculating the decimal value of the binary number part of the binary float. Name it val. One more attribute for getting the information how often to shift-right (divide by two) the binary number part after the comma is needed. Name it q.
The Attribute Tool is designed
to assist this procedure. Select the tool from the toolbar by clicking
on it. (The one with the big A on it). Now click on the Symbol
in the tree view you want to add an attribute. Klick now on the non-terminal
S (which is the root Symbol in our Derivation Tree) to bring up
the Attribute Tool Dialog.
Press the New button to create a new attribute. The text New appears in the textfield. Change it to val and commit it with enter. You just created a new Attribute named val. Now assign it to the non-terminal S by selecting val from the Defined Attributes List to the right and click on the add button. This assignment is immediately reflected in the active derivation window. Now select one of the other Symbols that need the val attribute in the derivation window. The active Nonterminal Combobox always shows the currently selected Symbol of the tree. Try to add the val attribute also to the symbols L and B. Finally add the q attribute to L. After having executed correctly all these commands, the derivation tree should look like this:
After this is done it's time to save the work. Do this by selecting File | Save AG. Use .torero or .trr as file extension for easy lookup at loading.
After having assigned all the neccessary attributes, connect them to each other with the Connect Tool. It's also neccessary to specify the mathematical relations between them using the Function Tool .
Begin by connecting the val attribute from the symbol B up to the symbol L. The tree in front shows two places where this connection can be declared. It doesn't matter which place is used for the next step, because it results in the same modification of the attibute grammar.
Select the Connect Tool from the toolbar. Now select the attribute
which should be the source of your connection. Click on the
val attribute of the B symbol which is under the L symbol.
Notice that the mouse cursor changed it's state. This indicates to select
the destination attribute of the connection. Do this by clicking
on the val symbol above. The derivation tree immediately shows
the connection everywhere this kind of production is used. At this moment
the derivation tree should look like the one below. Notice that the little
function icon at the left of the destination attribute has changed from
grey to black. This means that the function which exactly defines the
connection is defined and valid.
For this connection there is no need to edit the function. Whenever connections like this (exactly on source connected to one destination) are made, the representing function is generated automatically. However this doesn't mean that such functions cannot be changed.
Now use the function tool from the toolbar to make some attribute initializations. Select the tool from the toolbar and klick on the attribute val of a B symbol above an '0' symbol. Thus the function dialog appears and the little function icon shows that the function has become invalid. Now you can enter code for making the val attribute well defined on this location. Enter
@B.val@ = 0
into the function text field and press OK. If correctly entered the function state changes from invalid to valid. Now define
@B.val@ = 1
for the production
B -> '1'
@L.q@ = 2
for the production
L -> B
The picture below is a brief instruction for the steps just explained.
Now complete the information flow of the val attribute in the production
L -> L B
Therefore connect the val attributes from the symbols L and B to the val attribute on the L symbol above them. This time the corresponding function can't be generated automatically. It must exactly defined with the function tool:
@L.0.val@ = @L.1.val@ * 2 + @B.val@
Complete the information flow on the same production for the q attribute so that the relation between the q above and the q below is
@L.0.q@ = @L.1.q@ * 2
These operations will lead to a tree view like this:
Keep in mind that the tree view is completely dynamic. This means that changing the tree structure is allowed at any time. It's even possible to open a new derivation window at any time. Do so for completing the attribute connections. Just open a new Derivation Window via the Menubar and choose
S -> L '.' L
as root once again.
On this view define the last function as:
@S.val@ = @L.0.val@ + @L.1.val@ / @L.1.q@
All done. Familiarize with this treeview and see that regardless which
structure the tree has the connections always make sense.
There is finally one thing to do. Because a executable binary is made from this example a facility to inform the user about the result of the calculated value must be provided. This can be done by defining a traversal (name it print). It has to be added to the root production. This is reflected in the treeview with an "attribute like" entry on the symbol belonging to the left hand side of the production (it's the S symbol) the traversal is added to. All these procedures can be done with the Traversal Tool. To make the val attribute available in print connect the attibute to the traversal with the Connect Tool. Finally enter the source code with the Function tool:
/* Print the calculated value to stdout */
These modifications make the previously shown picture look like this:
Now export the attribute grammar to the ox file format.
Until now the previously defined attributes have no data type. To provide this information a file named attribute_types.h have to be created . For this example it should contain:
#define T_VAL float
#define T_Q float
because the used attributes have to be float values.
There is already a Makefile for building the example. Use it to get the binary from the source. The binary is named calcdec and can be tested with:
echo "110.001" | calcdec