Mike.Spivey@prg.oxford.ac.uk (Mike Spivey) (01/23/91)
This is partly a stylistic and partly a practical question about lists
and yacc parsers. If I want to recognise a long (and non-empty) list
of items and build a linked list from them, the obvious approach ...
list : item { $$ = cons($1, nil); }
| item ',' list { $$ = cons($1, $3); }
;
... is weak because the parser's stack will grow linearly with the
length of the list. (Is it one state stacked per item or two?). This
is a general problem with right recursion in LR parsers.
A better approach in some ways is to use left recursion but do extra
work to build the list:
list : item { $$ = cons($1, nil); }
| list ',' item { $$ = snoc($1, $3); }
;
with snoc defined, perhaps, by (a well-typed version of)
/* snoc -- destructively add an item to the end of a list */
list snoc(list a, val y)
{
if (a == nil)
return cons(y, nil);
else {
list b = a;
while (tail(b) != nil)
b = tail(b);
tail(b) = cons(y, nil);
return a;
}
}
But this approach uses time quadratic in the length of the list.
I also stumbled on the following yacc-hack:
list : head body { $$ = $1; }
;
head : item { $$ = cons($1, nil); }
;
body : /* empty */ { $$ = $0; }
| body ',' item { $$ = tail($1) = cons($3, nil); }
;
The trick here is that the value of a 'body' is the last item in the
list, and the hideous $0 reaches over and grabs the first item as the
last when the body is empty.
Other approaches suggest themselves: build the list backwards then
nreverse it, for example. My question is this: what do you, dear
reader, do in these circumstances? And, misguided though the
yacc-hack may be, is it portable?
-- Mike Spivey, Programming Research Group, Oxford, England
[The hack is probably portable, but it's hardly a good idea since there are
easier ways to do the job. I make the list a structure with two pointers,
one to the head and one to the tail, so updates can be hooked directly to the
tail without scanning the list. Another approach is to create the list
linked backwards, pushing each new item on to the list, and then when the
whole thing is made reverse the pointers in one pass down the list. -John]
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.mareb@lux.sait.edu.au (Buckley) (01/30/91)
>From: Mike.Spivey@prg.oxford.ac.uk (Mike Spivey) >A better approach in some ways is to use left recursion but do extra >work to build the list: I like to use a cyclically linked list - the tail of the list points back to the head. The list pointer points to the tail (or nil for an empty list). It is very easy to append to this list and when you are done it is very easy to convert it to a conventional list. And you still only need one pointer. I guess this would look something like this: list : CLlist { $$ = tail($1); tail($1) = nil; } ; CLlist : item { $$ = tail($1) = $1; } | CLlist ',' item { tail($3) = tail($1); $$ = tail($1) = $3; } ; b++ __ Bob Buckley Phone: (08) 343 3465 School of Mathematics & Computer Studies Fax: (08) 349 4367 University of South Australia The Levels SA 5095 email: mareb@lux.sait.edu.au Australia -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.