From: rcarter@wpi.WPI.EDU (Randolph Carter <Joseph H. Allen>)
Newsgroups: comp.programming
Subject: Re: Lookahead (was: Re: Pascal vs C)
Date: 28 Sep 1992 02:12:14 GMT
Organization: Worcester Polytechnic Institute
NNTP-Posting-Host: wpi.wpi.edu

jos@and.nl (Jos Horsmeier) writes:
>In article <gram.717417205@aim1> gram@aim1.aztec.co.za (Graham Wheeler) writes:
>|Incidentally, C is not in general a difficult language to compile; the most
>|problematic aspect are the type declarations, where a considerable lookahead
>|is needed. The typical approach is to build a tree from the declaration, and
>|then traverse it (so it is done in two stages).

>I beg to differ: there's no need to do any lookahead here. The problem
>is located in the communication between the lexical analyzer and the
>parser. The lexical analyzer doesn't know what to return to the parser
>when it reads an identifier, i.e. it could be a user defined type or
>just the name of a variable (local, global or parameter.) The trick
>is that there are certain `points' in the grammar where the parser
>definitely does or doesn't expect a user defined type name. If the
>parser toggles a switch here, telling the lexical analyzer to return
>a USER_TYPE token when it sees one, all works fine

or equivelently, if you're using a recursive descent parser, have the
scanner always pass the identifier as an identifier and have the parser
check if it's a user defined type at the appropriate points. 

>The only syntactic ambiguous construct where this trick fails is in
>situations like this:

>typedef int t;

>int f(t)
>int t;
>{}

//

>int f(t);

Or to make the problem more interesting, think of it returning a pointer to
a function, and assume that you don't declare the argument:

int (*f(t))()		/* Old-style definition with 't' as int */
{}

//

int (*f(t))();		/* declaration with 't' as a type */

One way of parsing this (assuming a recursive descent parser) is with a
good lexer design.  After the parser gets f(, have the lexer save everything
from there to the balancing parenthasis.  Then continue parsing until you
known whether it's a declaration or old-style definition.  Next have the
lexer take the saved string as the input and parse the arguments/types. 
When that's done, restore the file input to the lexer. 

The parser then looks something like this (assuming you're generating a
parse tree 'NODE *'- you could also have it generate code directly like
bad pascal compilers):

NODE *toplevel()
{
TOKEN *t;
NODE *base, *decl, *args;
LEXSOURCE *inside, *save;

	base=getsimpletype();			/* Gets 'int' */
	decl=getdeclarator(&name,&inside);	/* Gets (* )(),
						   puts 'f' in name and
						   sticks 't' in inside.
						*/


	t=gettoken();
	if(t==';' || t==',')
		{
		/* we have declaration(s) */
		save=curlexsource;
		curlexsource=inside;
		args=declarationlist();	/* Gets 't' as typedef t */
		curlexsource=save;
		...
		}
	
	else if(t=='{')
		{
		/* We have an ansi function definition or an old-style
		   function definition with all args as undeclared integers.
		   To decided which, check if 'inside' is only 0 or more words
		   seperated by commas.  If it is, we have an old-style
		   function definition: Goto below.  If not, we have an ansi
		   function definition:  Process 'inside' as above, but as a
		   function definition */
		   
		}
	else
		{
		/* we have an old-style function definition */
		save=curlexsource;
		curlexsource=inside;
		args=getargs();		/* Gets 't' as identifier 't' */
		curlexsource=save;

		Now: args has function argument names
		     base/decl have function return type
		     name has function name
		}
}
-- 
/*  rcarter@wpi.wpi.edu */      /* Amazing */             /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
Newsgroups: comp.programming,comp.lang.c,comp.lang.pascal,comp.lang.objective-c