Avoiding right-recursion

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]
--

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