What is correct way to describe this in BNF for an LL(1) parser

"don" asks:


> I can do everything I've needed to so far except for the absolute value
> function (eg | expression |). The problem is that the expression can
> expand back to this definition and, as it is simply stated now, the
> parser does not appear to tell the difference between closing '|' and
> the start of a nested expression. If I change the trailing "|" to
> something like '@' then the whole thing works OK.
>
> Is there a 'proper' way in BNF form to express this?


I suspect that the problem is that you are allowing implicit
multiplication, so you have somewhere rules like:


mult-expr ::= pow-expr '/' mult-expr
                          | pow-expr '*' mult-expr
                          | pow-expr mult-expr ;; implicit multiplication


term ::= '|' expr '|'
                | '(' expr ')'
                | VAR
                | NUMBER


(I don't know what tool you are using or any details of your grammar;
this is just a guess. Make appropriate substitutions, or ignore me if
I'm guessing wrong.)


If it were not for implicit multiplication, the use of |x| for abs(x)
is unambiguous (providing you're not using | for other things as well,
of course). However, if implicit multiplication is allowed, then the
expression:


        |a| |b| |c|


could be parsed as:


        abs(a) * abs(b) * abs(c)
or
        abs(a * abs(abs(b)) * c)




So any self-respecting parser generator will complain, whether it is
LL, LR or whatever.


If this is the case, you could try to restrict implicit multiplication,
although I suspect that this wouldn't be what you wanted (that is, if
you insist on implicit multipication, you would probably want "|a| |b|
|c|" to be valid), or you could try to deal with the issue lexically,
as Fortress does (see http://research.sun.com/projects/plrg/), which is
to disambiguate '|' based on surrounding whitespace.

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