Re: Parsing w/ operator precedence

What you are trying to do is called writing a "recursive descent
parser". It is not as hard as it sounds, given a proper LL1 grammar
for the expressions you wish to parse. However, writing a proper LL1
grammar is somewhat difficult until you've versed yourself in the
theory. The naive grammar one naturally writes to express expressions
is not an LL1 grammar. The problems you are encountering are because
you are attempting to start from a naive grammar.


The naive grammar looks something like (in Yacc notation):
E: E * E; // E is expression
E: E / E;
E: E + E;
E: E - E;
E: ( E );
E: number;


A proper LL1 grammar looks more like:
E: F E1; // F is factor
E1: * E; // E1 is "rest of expression"
E1: / E;
E1: ; // this is an empty rule
// for the case when nothing follows the factor
F: T F1; // T is term
F1: + F; // F1 is "rest of factor"
F1: - F;
F1: ;
T: ( E );
T: number;


The result is five mutually recursive routines (E, E1, F, F1, and T)
that create the parse tree. Note the resulting parse tree does not
look like the one that matches the naive grammar. Note, I will not go
into more detail, because I am not an LL parsing expert.


I would recommend you find yourself a textbook on compiler
construction that covers the topic. I'm certain you can find some
recommendations if you look at the comp.compilers FAQ. Most parsing
questions are best addressed in that newsgroup.


Also, aside from the learning experience, I do not recommend
writing parsers by hand. It seems like a trivial task, but the
resulting parsers often fail to implement the language the author
intended.


Finally, if you want a parse tree that matches your naive grammar, I
would recommend you use an LR parser generator. Most of them
(e.g. all the yacc derivatives), allow the naive grammar when
accompanied by "precedence" directives.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)
------------------------------------------------------------------------------

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