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

"don" <donmackay@optushome.com.au>
8 Nov 2005 23:37:59 -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: "don" <donmackay@optushome.com.au>
Newsgroups: comp.compilers
Date: 8 Nov 2005 23:37:59 -0500
Organization: http://groups.google.com
References: 05-11-032
Keywords: parse
Posted-Date: 08 Nov 2005 23:37:59 EST

Thanks to both of you for your help.


The major problem appears to be in the parser that I'm using. I created
a minimal language :


expression term term-tail
term-tail addition term-tail
term-tail
addition + term
addition term
term name
term | expression |


and then traced what the parser was doing (I'm using this parser and
run-time because I have the sources available to me).


Given the simple input sentence


|a|


the parser tun-time was correctly working until it matched the 'a' with
the first 'term' production. It then looked to see what would match the
second input "|" and decided that the path '1st term-tail, 2nd
addition, 2nd term' productions were the go, thinking that it was the
start of a second term with am implicit operator. It then found the end
of the input and flagged an error.


I think this is because of an 'exception' the parser allows to strict
LL(1) rules (for associative binary operators such as '+' where it
allows the single operator to have more than 2 arguments in the
abstract syntax tree - what it calls "bushy trees"). When it has the
choice of a production with the appropriate head symbol and possibly
passing back through some 'stacked' (partially parsed) productions that
can be empty, it will always choose the non-empty production. In this
case it is where the whole thing is going wrong.


So, thanks again - I guess its back to the debugger and 'thinking cap'
to 'fix' (probably remove) this 'feature'


Regards


Don


Post a followup to this message

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