Re: <<HELP with recursive descent parser>>

[smryan@netcom.com (S M Ryan)]

:  The grammar I am following is...
:       E  ==>	E + T
: 	E  ==>  T
: 	T  ==> 	T * F
: 	T  ==>	F
: 	F  ==>	(E)
: 	F  ==>	NUMBER
: 		Procedure T
: 		Begin
: 		  If F() == TRUE then return TRUE
: 		else begin
: 		If T()==TRUE the do begin
this will cause infinite recursion.
: 		Symbol := lex();
check the value of the next symbol before you consume it.
It's possible the next symbol is '+', in which case you
have to push it back on lex or keep it in a global. 
: 		If symbol == '*' then
: 		   If F() == TRUE return TRUE
- don't forget to embed your semantics or translation unless
  all you want is a recogniser.
- if the interior F() fails, you have a parse error and
  do some kind of error and/or recovery.
: 		else return FALSE

You can't use this grammar. For recursive descent, you need right
recursion, and you must be able to choose a production based on 
the next k symbols:

	E  ==>  t E'
	E' ==>  <empty> | + T E'
	T  ==>  F T'
	T' ==>  <empty> | * F T'
	F  ==>  ( E )   | <number>

boolean function F;
    begin
	if lookahead=lpar then			// F ==> ( E )
	    if not E then error;
	    if lookahead=rpar
		then consume input
		else error;
	    return true
	else if lookahead=number then		// F ==> <number>
	    stash number
	    consume input
	    return true
	else
	    return false
    end

boolean function T;
    boolean function T';
	begin
	    if lookahead=star then		// T' ==> * F T'
		consume input;
		if not F then error
		multiply stashed values
		if not T' then error
		return true
	   else					// T  ==> <empty>
		return true
	end;
    begin
	if F then				// T ==> F T'
	    if not T' then error;
	    return true
	else
	    return false
    end;

boolean function E;
	basically the same as T.

T' and E' are tail recursive and can be transformed into
	boolean function T';
	    begin
		while lookahead=star do
		    consume input
		    if not F then error
		    multiply stashed values
		return true
	    end

And because T' and E' always return true
boolean function T;
    procedure T';
	begin
	    while lookahead=star do
		consume input
		if not F then error
		multiply stashed values
	end
    begin
	if F then
	    T';
	    return true
	else
	    return false

And finally inlining gives
boolean function T;
    begin
	if F then
	    while lookahead=star do
		consume input;
		if not F then error;
		multiply stashed values
	    return true
	else
	    return false


In an extended grammar this language is
	E  ==>  T [ '+' T ] *
	T  ==>  F [ '*' F ] *
	F  ==>  ( E )   | <number>
in which the final form of function T is read off directly from
production T.

-- 
 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ __________________________________
| | | | | | | | | | | | | | | | | | | | | smryan@netcom.com	PO Box 1563
| | | | | | |G|A|T|E| |1| | | | | | | | |             Cupertino, California
|Electricians use gate 2| | | | | | | | |_(xxx)xxx-xxxx_______________95013
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|____(coming soon: a new signature)