30 Jan 1997 22:19:29 -0500

Related articles |
---|

[q] regarding eliminating a shift/reduce error larry_baker@sdt.com (Larry Baker) (1997-01-30) |

From: | Larry Baker <larry_baker@sdt.com> |

Newsgroups: | comp.compilers |

Date: | 30 Jan 1997 22:19:29 -0500 |

Organization: | SABRE Decision Technologies |

Keywords: | yacc, question |

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]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.