RE: Ambiguous recursive-descent parsing

Quinn Tyler Jackson <>
30 Mar 2003 00:57:31 -0500

          From comp.compilers

Related articles
RE: Ambiguous recursive-descent parsing (Quinn Tyler Jackson) (2003-03-30)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 30 Mar 2003 00:57:31 -0500
Organization: Compilers Central
Keywords: parse, LL(1)
Posted-Date: 30 Mar 2003 00:57:31 EST
In-reply-to: 03-03-157

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

Quinn Tyler Jackson

Post a followup to this message

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