Re: problems with absolute value structure in algebraic grammar

[Hans Aberg]

At 11:25 -0700 2003/06/21, Samad Lotia wrote:
>Here is my grammar from y.output:

Please submit suitable snippets from the .y source file, in case somebody
want to try.


>The purpose of this grammar file is to produce a
>parser which can parse algebraic expressions. The
>purpose of the enclosed_statements rule is to support
>implicit multiplication. For example, the expression:
>
>9acos(0.5)
>
>Really means:
>
>9*acos(0.5)
>
>Or the expression:
>
>8|-2|(2^3)
>
>Really means:
>
>8*abs(-2)*(2^3)

I once worked with this problem, not in Bison, but in a handwritten parser.
My conclusion is that even though it is possible to admit implicit
multiplication and other such mathematical constructs, they are likely to
produce ambiguities if not implemented very carefully. Humans can easily
cope with ambiguities, but computers are poor at that.

So if you can avoid implicit multiplication in your computer language, do
that: any operator with arguments separated with tokens will parse more
easily.

You might also inquire in the newsgroup comp.compilers, if somebody already
has made such a grammar.

Experimenting a bit in Bison, it is possible to make such a grammar by
throwing in some token precedences (see below). But if you want to use this
strategy in a more general mathematical context, I think you will end up
with ambiguities.

The point with the grammar below are the lines:

%right '|'
...
%right NUMBER
...

(I do not know if the associativity is right; also try %left & %nonassoc.)

%token NUMBER
%token ELEMENTARY_FUNCTION
%token IDENTIFIER
%token EXIT

%right '|'
%left '+' '-'
%right ELEMENTARY_FUNCTION
%left '*' '/'
%right '^'
%right IDENTIFIER
%right NUMBER
%right UMINUS

%%
lines:  lines expr '\n'         { printf("%.12g\n", $2.value) }
        |       lines '\n'
        |       lines EXIT '\n'         { return EXIT_SUCCESS; }
        |       /* empty */
        |       error '\n'              { printf("Please re-enter last
line: ");
                                  yyerrok; }
        ;

expr:   expr '+' expr   { $$.value = $1.value + $3.value }
        |       expr '-' expr   { $$.value = $1.value - $3.value }
        |       expr '*' expr   { $$.value = $1.value * $3.value }
        |       NUMBER expr       { $$.value = $1.value * $2.value }
        |       expr '/' expr   { $$.value = $1.value / $3.value }
        |       expr '^' expr   { $$.value = pow($1.value, $3.value) }
        |       '(' expr ')'    { $$.value = $2.value }
        |       '|' expr '|'    { $$.value = $2.value }
        |       '-' expr  %prec UMINUS { $$.value = -$2.value }
        |       IDENTIFIER expr { $$.value = sqrt($2.value) }
        |       ELEMENTARY_FUNCTION expr        { $$.value =
(*$1.f)($2.value) }
        |       NUMBER
        ;
%%

  Hans Aberg