4 Nov 2005 14:00:29 -0500

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) |

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.