Re: Arithmetic expressions w. recursive descent parser?

RobertSzefler <NOSPAMrszeflerNOSPAM@murator.com.pl>
28 Jan 2006 15:13:52 -0500

          From comp.compilers

Related articles
Arithmetic expressions w. recursive descent parser? bmildh@linuxmail.org (2006-01-26)
Re: Arithmetic expressions w. recursive descent parser? Juergen.Kahrs@vr-web.de (=?ISO-8859-1?Q?J=FCrgen_Kahrs?=) (2006-01-28)
Re: Arithmetic expressions w. recursive descent parser? torbenm@app-2.diku.dk (2006-01-28)
Re: Arithmetic expressions w. recursive descent parser? NOSPAMrszeflerNOSPAM@murator.com.pl (RobertSzefler) (2006-01-28)
| List of all articles for this month |

From: RobertSzefler <NOSPAMrszeflerNOSPAM@murator.com.pl>
Newsgroups: comp.compilers
Date: 28 Jan 2006 15:13:52 -0500
Organization: Internet Partners
References: 06-01-078
Keywords: arithmetic, parse

bmildh@linuxmail.org wrote:
> The problem is that I cant get the implementation right with +,- in
> combination w. numbers starting w. + or -, eg. -45, +3, etc.
> I would appreciate any help, pointers, tips, on how to get the + and -
> operator correctly implemented with numbers that could start with + or
> - .


<snip code>


You might want to look into parsing expression grammars (and packrat
parsing, which is a simple and powerful technique) which can indeed
handle a much broader class of grammars than what you start with:


http://en.wikipedia.org/wiki/Parsing_expression_grammar
http://pdos.csail.mit.edu/~baford/packrat/
http://pdos.csail.mit.edu/~baford/packrat/popl04/peg-popl04.pdf


If you don't want to enter this relatively unexplored territory, I
suggest acquainting yourself with operator precedence parsing and the
simple "shunting yard" algorithm (which btw might be seen as a stackless
version of an extended RD parser):


http://en.wikipedia.org/wiki/Operator-precedence_parser
http://en.wikipedia.org/wiki/Reverse_Polish_notation


Back to your problem: I have a feeling that parsing your type of
grammars is impossible with a finite-lookahead recursive descent parser,
I might be wrong, though. What you might want to add to your code is
some sort of state tracking along the descent, which would bring the
method closer to traditional LL/LR parsing.


Anyway, why not just use ANTLR or any other LR parser construction toolkit?


regards,


Robert


Post a followup to this message

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