RE: Ambiguous recursive-descent parsing

> > I have some ideas for how Tomita-style techniques for managing
> > multiple parse "states" can be combined with LL(1)
> parsing to easily
> > parse languages like C++, but I want to make sure that I am not
> > re-inventing the wheel.


Chris F Clark replied:


> I have to agree with our moderator that I've never heard of anyone
> doing exactly that.


Adaptive(k), the algorithm used in Meta-S is based on LL(k). I was
going to call it ALL(k) (for Adaptive-LL(k)) because the resulting
algorithm is provably Turing-powerful and can thus accept any
acceptable language (thus ALL would have fit), in theory, but felt
that ALL(k) sounded a bit haughty, at which point Stroustrup suggested
calling the algorithm adaptive(k), and that stuck.


Note that adaptive(k) is an algorithm, rather than a class of
languages or grammars. There are possibly more than one algorithm that
could be used to traverse a $-grammar correctly, but adaptive(k) is
the one used in practice by me.


The adaptive(k) algorithm can parse languages such as C++
unambiguously, where k < some large number in practice.


The exact definition of the algorithm is given in the glossary on my
site. It is, to date, an informal definition, but captures the key
points.


--
Quinn Tyler Jackson

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