Re: Implicit Multiplication
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
___
Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Implicit Multiplication
On Fri, 5 Aug 2005, Aaron Hurst wrote: > [...] 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). [...] >| expression expression %prec '*' /* this rule causes problems */ This is an excerpt from the 'parser.output' file generated by Bison from the GNU 3DLDF grammar: 886 numeric_secondary: numeric_primary 887 | numeric_secondary TIMES numeric_variable 888 | numeric_secondary numeric_variable | ... State 888 corresponds to the rule for what you're calling implicit multiplication. In my grammar, there are no conflicts associated with this state. In order for this to work, you will need to use an expression hierarchy, i.e., 'expression' is not enough. The general pattern is: type_variable: ... type_primary: type_variable | ... type_secondary: type_primary | ... type_tertiary: type_secondary | ... type_expression: type_tertiary | ... For 'numerics' I have a couple more stages, but you may not need them. I've described this technique in previous postings to this mailing list. Hans Aberg has also published an article on a similar but more general technique. Laurence Finston http://www.gnu.org/software/3dldf/LDF.html ___ Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
Re: Implicit Multiplication
On 6 Aug 2005, at 03:05, Aaron Hurst wrote:
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).
Here is a variation:
%token IDENTIFIER
%left '|' '+'
%left '^'
%left '&' '*' IDENTIFIER '(' ')'
%%
expression:
IDENTIFIER
| '(' expression ')'
| expression '*' expression
| expression '&' expression
| expression '+' expression
| expression '|' expression
| expression '^' expression
| IDENTIFIER IDENTIFIER
| IDENTIFIER '(' expression ')'
| '(' expression ')' IDENTIFIER
| '(' expression ')' '(' expression ')'
;
Hans Aberg
___
Help-bison@gnu.org http://lists.gnu.org/mailman/listinfo/help-bison
