[q] regarding eliminating a shift/reduce error

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
larry_baker@sdt.com, I'll be assured of getting it.


Thanks in advance,


Larry Baker
SABRE Decision Technologies


(grammar follows this line)


%token SYMBOL
%token VALUE
%token KW_IF
%token KW_THEN
%token KW_ELSE
%token KW_GE
%token KW_LE
%token KW_RETURN


%start begin


%%


begin: stmt_list
;


stmt_list: stmt
| stmt stmt_list
;


stmt:
assign_stmt
| if_stmt
| return_stmt
;


if_stmt: /* else mandatory */
KW_IF '(' b_expr ')'
KW_THEN stmteval KW_ELSE stmteval;


assign_stmt:
';' /* null statement */
| SYMBOL '=' expr ';'
;


return_stmt:
KW_RETURN
expr ';'
;


/*
// boolean expression grammar
*/


b_expr:
b_prod
| b_prod '&' b_expr
| b_prod '|' b_expr
;


b_prod:
b_term
| b_term '#' b_prod
| b_term '=' b_prod
| b_term '>' b_prod
| b_term '<' b_prod


;


b_term:
'(' b_expr ')'
| expr
;


/*
// calculation expression grammar
*/


expr:
prod
| expr '+' prod
| expr '-' prod
;


prod:
term
| prod '*' term
| prod '/' term
;


term:
func
| VALUE


| SYMBOL
| '(' expr ')'
;


/*
// function call grammar
*/


func: SYMBOL '(' arglist ')'
;


arglist:
/* null argument */
| arg
| arg ',' arglist
;


arg: expr;


%%


/* (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 comp.compilers page.
Search the comp.compilers archives again.