30 Mar 2003 00:57:31 -0500

Related articles |
---|

RE: Ambiguous recursive-descent parsing qjackson@shaw.ca (Quinn Tyler Jackson) (2003-03-30) |

From: | Quinn Tyler Jackson <qjackson@shaw.ca> |

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

points.

--

Quinn Tyler Jackson

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.