Le 26 juin 09 à 00:20, Paul Hilfinger a écrit :
Has anyone considered adding extended BNF to Bison? I refer to things
like
A. p : a? ;
B. p : a ( b | c ) d ;
C. p : a ( ',' a )*
D. p : a+
and so forth.
Hi Paul,
Yes, this has been considered several times, but each time tricky
questions, and other patches that need to be completed, made this
dream continuously postponed.
There are numerous questions to answer, mostly involving
semantic actions and including:
Yes, exactly. The grammar side of the question is quite
straightforward, but the actions are very unclear.
1. How do we specify the semantic types of such constructs?
2. How do we refer to, e.g., the values of b and c from example B in
actions?
Presumably this would only be legal inside the parentheses.
Named references have been introduced in Bison, they should help
here. You would use $b and $c, or whatever name you attached to the
symbols:
p[res]: a[x] (b[y] | c[y]) d[z];
3. Assuming we translate * and + into equivalent non-extended
productions, how do we specify left vs. right-recursive lists?
Yep :)
4. How do we specify list constructors for * and +?
5. How do we supply a value for the empty case in A?
6. How do we supply a value for the ( ... ) construct in B?
I have no clear answer for these questions, I just have the same
questions :). But I have some pointers that might provide valuable
ideas.
The SDF/SGLR folks (http://strategoxt.org/Sdf/WebHome) have an
approach that I like when desugaring EBNF into BNF. Constructs like "a
+" or "a?" behave like nonterminal identifiers, and you may well
define "a?" as you wish. But if "a?" is left undefined in the
grammar, *then* the tool adds a default
a -> a?
-> a?
(they write somewhat backwards, apparently because of signatures in
many-sorted algebras. http://homepages.cwi.nl/~daybuild/daily-books/syntax/2-sdf/sdf.html#section.symbols)
They also support a nice construct: {x y}* means zero-or-more x's
separated by y's, and {x y}+ stands for one-or-more.
Menhir (http://cristal.inria.fr/~fpottier/menhir/) supports user-
defined "macros" (parameterized rules) to specify additional grammar
meta-constructs and how to desugar them. I never really looked at it,
but Menhir is certainly a clearer source of inspiration for Bison than
SDF since the former is user-action based, while the later is directly
building the parse-tree (which magically "resolves" all your
questions :).
They also support "inlined" rules, which provides good opportunities
for factoring. For instance, in a grammar of mine, I have (like most
people do):
exp:
exp "+" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "-" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "*" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "**" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "/" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "%" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "^" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "<<" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "bitand" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp "bitor" exp { $$ = ast_call(@$, $1, $2, $3); }
| exp ">>" exp { $$ = ast_call(@$, $1, $2, $3); }
;
They can define a simple "exp: exp op exp" rule, and declare inlined-
rule to define op, and let associativity/prececence do its job.
HTH.
_______________________________________________
help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
