28 Jan 2006 15:13:52 -0500

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

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.