Re: Implicit Multiplication

[Hans Aberg]

On 6 Aug 2005, at 03:05, Aaron Hurst wrote:

> I'm trying to parse a simple algebraic (Boolean) expression using  
> the grammar described below.  However, I would like to be able to  
> parse implicit multiplication (i.e. if two expression appear next  
> to each other without an operator, they should be mulitplied).

I once wrote such a grammar, but I concluded that in a computer  
program, the effort of refining the grammr does not seem worth the  
effort.

> For example,
>
> a b + (c + d)g
> should parse the same as
>
> a * b + (c + d) * g
>
> As written below, there are several shift/reduce conflicts caused  
> by the last rule (the implicit multiplication).  I have no idea how  
> to rewrite this unambiguously.
>
> %left '|' '+'
> %left '^'
> %left '&' '*'
> %nonassoc '\''
> %nonassoc '!'
>
> expression:
>   IDENTIFIER
>   | '(' expression ')'
>   | expression '*' expression
>   | expression '&' expression
>   | expression '+' expression
>   | expression '|' expression
>   | expression '^' expression
>   | '!' expression
>   | expression '\''
>
>   | expression expression %prec '*'   /* this rule causes problems */
>   ;

By your last rule, for example a + b c + d becomes ambiguous, as it  
admits the interpretations (a + b) (c + d) and a + (b c) + d.  
Grammatically, implicit multiplication only applies to certain  
situations, where one of the operands is an identifier, a constant,  
or enclosed in parenthesizes. The precedences, %prec '*', only apply  
to tokens, and you have none in that rule.

  Hans Aberg