|[q] regarding eliminating a shift/reduce error email@example.com (Larry Baker) (1997-01-30)|
|From:||Larry Baker <firstname.lastname@example.org>|
|Date:||30 Jan 1997 22:19:29 -0500|
|Organization:||SABRE Decision Technologies|
I am developing a parser/compiler for an interpreted scripting
language, to be used in a business application. The grammar for part
of that language (actually, most of it) appears below. I'm reasonably
satisfied with where I am at the moment, but I have one nagging
question that I'm hoping someone on the net will be kind enough to
help me with.
Yacc still complains about 1 shift/reduce error, which I traced down
to a conflict between "b_expr" (binary-result expressions) and "expr"
(numerical-result expressions). The conflict is due to ambiguity
between parenthetically-isolated expressions. For example ((a+b)>c)
and ((a>b)) are ambiguous; if you start as a b_expr with the first (,
the grammar can interpret the 2nd ( as a b_expr or an expr.
My question is the following: how do I eliminate the shift/reduce
ambiguity in this situation?
I've considered the following options, and rejected them:
1/ change the language to allow "expr"s to return binary results, a la
Pascal or C. I'd prefer not to do this, as the scripting language is
intended to encapsulate calculations that are generally limited to a
few lines of code, and there will probably not ever be a situation
where I will need that kind of sophistication. It will also
necessitate a semantic check to make sure that the result of an
expression is binary (true/false) in a binary context, which is a
development overhead I'd rather not deal with at the moment.
2/ duplicate the "expr" grammar tree under "b_expr," so that the same
functionality is supported. This strikes me as ugly, and
difficult-to-maintain (duplicated code everywhere).
I realize that by constraining "expr"s to numerical calculations, and
"b_expr"s to binary results, then allowing "expr"s to be mixed with
"b_expr"s in an IF statement, I've created this situation for myself,
but I'm not terribly unhappy with the parser that yacc generates from
my grammar. The default behavior is acceptable. My main concern is
to learn what to do in a situation like this, in order to "clean up"
the grammar, if that proves practical.
Note that this is work-in-progress, so if the language itself seems a
little fuddled, it is, and I'm still trying to decide how I want to
extend it to defuddle it.
Our net connection for netnews got very flaky today (just when I need
it!), so if you could CC: any responses to this message via e-mail to
email@example.com, I'll be assured of getting it.
Thanks in advance,
SABRE Decision Technologies
(grammar follows this line)
| stmt stmt_list
if_stmt: /* else mandatory */
KW_IF '(' b_expr ')'
KW_THEN stmteval KW_ELSE stmteval;
';' /* null statement */
| SYMBOL '=' expr ';'
// boolean expression grammar
| b_prod '&' b_expr
| b_prod '|' b_expr
| b_term '#' b_prod
| b_term '=' b_prod
| b_term '>' b_prod
| b_term '<' b_prod
'(' b_expr ')'
// calculation expression grammar
| expr '+' prod
| expr '-' prod
| prod '*' term
| prod '/' term
| '(' expr ')'
// function call grammar
func: SYMBOL '(' arglist ')'
/* null argument */
| arg ',' arglist
/* (end of posting) */
[I suggested a variant of option 1, make one type of expression
syntactically, and enforce the boolean vs. arithmetic dichotomy
semantically. This isn't all that hard, and as a bonus lets you emit
better error messages, e.g. "boolean value found where arithmetic
expected" rather than "syntax error" -John]
Return to the
Search the comp.compilers archives again.