Re: ITE bison grammar problem

"Andrew Wilson" <>
5 Jun 2005 11:26:46 -0400

          From comp.compilers

Related articles
ITE bison grammar problem (pmatos) (2005-06-04)
Re: ITE bison grammar problem (pmatos) (2005-06-04)
Re: ITE bison grammar problem (Carl Barron) (2005-06-05)
Re: ITE bison grammar problem (Andrew Wilson) (2005-06-05)
| List of all articles for this month |

From: "Andrew Wilson" <>
Newsgroups: comp.compilers
Date: 5 Jun 2005 11:26:46 -0400
Organization: Compilers Central
References: 05-06-028 05-06-032
Keywords: parse, yacc
Posted-Date: 05 Jun 2005 11:26:46 EDT


As it stands this grammar is ambigious.

Is ite(id, id, id) an F or an E?

If you linked the lexical analysis stage to the symbol table, then you
could return id for undefined identifiers, eid for expression type
identifies, and fid for boolean identifiers. Replacing id with fid in
F, and eid with id in E will remove the ambigiouty.

%left '&' '+'
%token id fid eid
%start F
F: "ite" '(' F ',' F ',' F ')'
| F '&' F
| M
| fid
M: E "==" E;
E: "ite" '(' F ',' E ',' E ')'
| E '+' E
| eid

On the other hand as the moderator noted, a better solutution would be
to parse a more general grammar and handle allowable types in the
semantic stages (could even handle it at runtime, but don't).

%nonassoc EQU // I would let the lexer capture the "==" sequence
%left '+'
%left '&' // I would personally give "and" a higher priority than "plus"
%token id
%start A
A: "ite" '(' A ',' A ',' A ')'
| A '&' A
| A '+' A
| id


> However, the real issue remains. There's a reduce/reduce conflict due
> to the ite and identifier. Since I can't syntactically distinguish
> identifiers, what should I do?

>> [My advice would be to treat them the same syntactically and sort
>> them out in the semantics. This lets you produce better error
>> messages like "boolean variable XYZ used for arithmetic" rather
>> than "syntax error". -John]

> How can I do that? Putting id only in F will permit id to be a
> condition in ite, and will make numerical vars impossible. Putting it
> only in E won't allow id to be a condition and won't allow us to have
> boolean variables.
> [Combine E and F, don't try to enforce types in the parser. -John]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.