First/Follow sets in Recursive Descent Parsers

"Dan Haxell" <Dan.Haxell@btinternet.com>6 Aug 2001 04:04:20 -0400

From comp.compilers

Related articles
First/Follow sets in Recursive Descent Parsers Dan.Haxell@btinternet.com (Dan Haxell) (2001-08-06)
Re: First/Follow sets in Recursive Descent Parsers ralph@inputplus.demon.co.uk (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers mike@dimmick.demon.co.uk (Mike Dimmick) (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers tmoog@polhode.com (Tom Moog) (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers therabbit@hole.com (2001-08-08)
| List of all articles for this month |

 From: "Dan Haxell" Newsgroups: comp.compilers Date: 6 Aug 2001 04:04:20 -0400 Organization: BT Internet Keywords: parse, question Posted-Date: 06 Aug 2001 04:04:20 EDT

I am currently writing a utility to translate LaTeX math expressions
into Maple syntax. So far I have been using Flex to generate the
lexical analyser and then hand-coding a recursive descent parser (in
C++).

It is based on the following grammar expressed in EBNF:

expression = ['+' | '-'] term { ('+' | '-') term }.
term = factor ( { ('*' | '/') factor } | { factor } ).
factor = entity [ '^' '{' expression '}' ].
entity = NUMBER | VARIABLE [ '(' expression ')' ] | '(' expression ')' |
integral.
integral = '\int' [subscript superscript] '{' expression 'd' VARIABLE '}'.
subscript = '_' ( '{' expression '}' | (VARIABLE | NUMBER) ).
superscript = '^' ( '{' expression '}' | (VARIABLE | NUMBER) ).

Using this, strings of letters such as 'abc' are translated as products:
'a*b*c'.

Each non-terminal is implemented as a void function that returns a
string containing the Maple translation, e.g. string factor(void).

The problem I have is when parsing an integral: during the parse, I
want the letter 'd' to have a new meaning, namely to designate the end
of the expression and indicate the variable to integrate. This should
only be the case when parsing an integral and normally it should be
treated as a simple variable.

However, when parsing the expression 2x dx, the 'dx' is not recognised
as being special since the program is still in the Expression()
function and thus parses as 2*x*d*x.

Would passing First/Follow sets (stop sets??) to each function allow
for situations such as this? Many of the examples of RDPs use void
functions as well.

Thanks,

Dan.

Post a followup to this message