From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.8 required=5.0 tests=BAYES_00,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,23f63e0900ada727
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,23f63e0900ada727
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,23f63e0900ada727
X-Google-Attributes: gid1014db,public
X-Google-Thread: 1111a3,23f63e0900ada727
X-Google-Attributes: gid1111a3,public
X-Google-ArrivalTime: 1994-11-12 20:18:05 PST
Newsgroups: comp.lang.objective-c,comp.lang.c++,comp.lang.ada,comp.lang.c
Path: 
 nntp.gmd.de!xlink.net!howland.reston.ans.net!ix.netcom.com!netcom.com!smryan
From: smryan@netcom.com (S M Ryan)
Subject: Re: <<HELP with recursive descent parser>>
Message-ID: <smryanCz6oCA.IEM@netcom.com>
Followup-To: comp.lang.objective-c,comp.lang.c++,comp.lang.ada,comp.lang.c
Organization: Dawn Patrol on the Internet
X-Newsreader: TIN [version 1.2 PL1]
References: <1994Nov12.132726.23824@wmichgw>
Date: Sun, 13 Nov 1994 02:02:33 GMT
Xref: nntp.gmd.de comp.lang.objective-c:2829 comp.lang.c++:78698
 comp.lang.ada:16677 comp.lang.c:68379
Date: 1994-11-13T02:02:33+00:00
List-Id: <comp.lang.ada>

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