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

Rici Lake <rici@ricilake.net>
4 Nov 2005 14:00:29 -0500

          From comp.compilers

Related articles
What is correct way to describe this in BNF for an LL(1) parser donmackay@optushome.com.au (don) (2005-11-02)
Re: What is correct way to describe this in BNF for an LL(1) parser mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2005-11-04)
What is correct way to describe this in BNF for an LL(1) parser rici@ricilake.net (Rici Lake) (2005-11-04)
Re: What is correct way to describe this in BNF for an LL(1) parser donmackay@optushome.com.au (don) (2005-11-08)
Re: What is correct way to describe this in BNF for an LL(1) parser henry@spsystems.net (2005-11-12)
| List of all articles for this month |

From: Rici Lake <rici@ricilake.net>
Newsgroups: comp.compilers
Date: 4 Nov 2005 14:00:29 -0500
Organization: Compilers Central
References: 05-11-032
Keywords: parse, LL(1)
X-ClientAddr: 200.121.251.2

"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.


Post a followup to this message

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