A long time back, I was considering mixfix parsing. I have mixed (pardon the
pun) feelings about it, but the immediate concern was making it work in the
context of something like bison, which doesn't have a notion of dynamically
alterable operator precedence.
This morning, it occurred to me that there is a dreadfully obvious solution.
First, note that mixfix occurs only in expressions. We introduce a set of
Bison productions:
mixexpr: mixsequence {
$0 = ResolveMixFixSequence($1);
}
mixsequence: PreFixToken mixexpr;
mixsequence: mixexpr PostFixToken;
mixsequence: mixexpr InfixToken mixexpr;
where the semantic actions of mixsequence simply build a concatenated list
of the constituent mixfix keywords, identifiers, and literals. We then run
ResolveMixFixSequence on this list as a post-pass, which converts the
initially parsed sequential AST into the expression AST intended by the
prevailing mixfix syntax rules.
Note that the Bison rules desribe low-level mechanics. A mixfix rule of the
form _ '[' _ ']' would be entered for lexical purposes as a InfixToken '['
and a PostfixToken ']'. This is sufficient to get the token stream captured;
resolution happens later.
I spoke about this with Paul Snively, who identified another possible
approach. We could use GLR parsing, and use a hand-constructed merge rule to
resolve the resulting shift/reduce errors according to the mixfix table. At
the moment, my sense is that I like the idea but I'm not (yet) certain about
the practice. In particular, if the resolution of precedence is left-context
dependent in an LR parser, then I'm not sure we always have enough
information at the point of merge to know what to do. We *may* have it, but
I haven't yet thought it through. A second issue here is that the GLR
strategy would seem to need to know all of the legal "shapes" of mixfix
syntax in advance so that it can build correct trees. Perhaps some variant
of my original thought can avoid this; it may be that the implementation of
ResolveMixFixSequence could be encoded successfully in GLR merge rules. It
would sure be nice if this worked.
Anybody feel like taking the time to play around with one approach or the
other to help move BitC forward?
shap
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
