Can anyone explain what attribute grammars are?
Author Message
Can anyone explain what attribute grammars are?

On Tue, 6 Feb 2001 20:57:32 -0600, "Kyle Wayne Kelly"

Quote:

>Can anyone explain what attribute grammars are?

Attributed grammars are mostly used for constukting parsers that do
more than just building a syntax tree. With attributed grammars its
possible to directly evaluate some parsed elements.

Here is an simple grammar example for parsing polynimal expressions of
the form ax^n + bx^m + ... (from the pcctsbk.pdf by Terence J. Parr):

poly
: term ( "\+" term )*
;
term
: coefficient { reg { "^" exp } }
| reg { "^" exp }
;
coefficient
: FLOAT
;
reg : ID
;
exp : reg
| FLOAT
;

This grammar can only be used to generate a syntax tree, but not for
more. Now the same as attributed grammar:

poly > [float r]
: <<float f;>>
term>[\$r] ( "\+" term>[f] <<\$r += f;>> )*
;

This means that the rule 'poly' is treated as a method that returns an
float, that can bee accessed as variable 'r' within the method.
<<float f;>> declares a variable 'f' of type float. term>[\$r] stores
the result of the parsing of the rule 'term' within r. Than for each
additional term the result is stored in 'f' and the added to r with
( "\+" term>[f] <<\$r += f;>> )*

The rest looks like this:

term > [float r]
: <<float f=0.0, e=0.0, c=0.0, v=0.0;>>
coefficient > [c]
( reg > [v]
( "^" exp>[e]<<\$r = c*pow(v,e);>>
| <<\$r = c*v;>>
)
| <<\$r = c;>>
)
| reg > [f]
( "^" exp > [e]<<\$r = pow(f,e);>>
| <<\$r = f;>>
)
;
coefficient > [float r]
: flt:FLOAT<<\$r = atof(\$flt->getText());>>
;
reg > [float r]
: id:ID <<\$r = value(\$id->getText());>>
;
exp > [float r]
: reg > [\$r]
| flt:FLOAT<<\$r = atof(\$flt->getText());>>
;

Quote:
}

Some explanations to \$flt->getText(): This example is from an object
oriented parser generator that treats every token as an object, so
\$flt->getText() calls the method getText() of the token object wich
returns the parsed text.

Another use are semantic predicates, wich control wich rule is used
for parsing. Maybe you would like to use different rules for arrays
and functions, but the syntax should look the same for both. Without
semantic predicates its impossible because how should the parser
choose the rule to take? With them its simple. A functions with
boolean result is called that tells the parser if it should choose the
rule or not:
arrayOrFunction: array | function;
array: <<isarray(current_text)>>? ID "(" expression_list ")";
function: <<isprocedure(current_text)>>? ID "(" expression_list ")";
The <<blabla>>? construct is a guard for the rule that must be
fullfilled to match the rule.

also the yacc manual if you have access to a linux computer. It may be
also found at www.gnu.org

Philipp Wojke

Mon, 28 Jul 2003 22:13:07 GMT

 Page 1 of 1 [ 1 post ]

Relevant Pages