Re: First/Follow sets in Recursive Descent Parsers

Tom Moog <>
8 Aug 2001 01:13:15 -0400

          From comp.compilers

Related articles
First/Follow sets in Recursive Descent Parsers (Dan Haxell) (2001-08-06)
Re: First/Follow sets in Recursive Descent Parsers (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers (Mike Dimmick) (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers (Tom Moog) (2001-08-08)
Re: First/Follow sets in Recursive Descent Parsers (2001-08-08)
| List of all articles for this month |

From: Tom Moog <>
Newsgroups: comp.compilers
Date: 8 Aug 2001 01:13:15 -0400
Organization: Polhode Inc
References: 01-08-029
Keywords: parse
Posted-Date: 08 Aug 2001 01:13:15 EDT

It seems like the best way to know if it is the integration variable
is not to use the prefix 'd' to discriminate, but to use the closing
"}". This seems to imply that you need two tokens of lookahead (or
lookbehind) between the lexer and the parser. If the lexer sees the
"}" it should fix the preceding token before the parser sees it.
Alternatively, you can use a parser with two tokens of lookahead. If
you decide to fix it in the lexer rather than the parser then an added
complication is nested "}" for integration. You'll probably need a
special flex START state to handle this properly.

Tom Moog
Polhode, Inc.

Dan Haxell <> wrote:
>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
>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 = '\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:
>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.

Post a followup to this message

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