RE: Detecting endless recursion?

Quinn Tyler Jackson <>
4 Feb 2004 21:24:36 -0500

          From comp.compilers

Related articles
RE: Detecting endless recursion? (Quinn Tyler Jackson) (2004-01-17)
Re: Detecting endless recursion? (Joachim Durchholz) (2004-02-01)
RE: Detecting endless recursion? (Quinn Tyler Jackson) (2004-02-04)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 4 Feb 2004 21:24:36 -0500
Organization: Compilers Central
References: 04-02-025
Keywords: parse
Posted-Date: 04 Feb 2004 21:24:36 EST

Joachim Durchholz said:

> The next more general class is context-sensitive grammars; these can
> express things like type constraints, but there is no widely-known
> technique for writing parsers for them, so in practice, they aren't
> used except in research.

Meta-S allows grammars of from Type 3 to Type 0 to be expressed in an
A-BNF[1] grammar specification. Type 0 langauges cannot be expressed without
using both tries and predicates in the same grammar, and therefore it is
quite a simple matter to know that a grammar is not TP: if the grammar does
not contain both predicates and tries, it must be non-TP. If it contains
both -- it *may* be TP.[2]

The adaptive(k)[3] subset Type 0 remains Type 0 because it retains tries and
predicates, while at the same time, the adpative(k) algorithm used to effect
a parse on input against a Meta-S grammar tends to be almost as time
efficient as LR(0). (Sure, it's quite possible to write terribly inefficient
grammars, but the use of predicates can make even some of these more

Because Type 1 and Type 0 langauges can behave in many ways like computer
programs rather than grammars, the Meta-S IDE allows them to be debugged,
profiled, tested against sample input, et cetera.

Meta-S has been around in some form not unlike its current form since late
1998. It has been beta-tested by parsing practioners and specialists.

If anyone wants to know anything else about it, please ask.

Quinn Tyler Jackson

[1] URL:
[2] URL:
[3] URL:

Post a followup to this message

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