RE: Detecting endless recursion?

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
efficient.)


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


http://members.shaw.ca/qjackson/


[1] URL:
http://members.shaw.ca/qjackson/cs/glossary/adaptive_backus_naur.html
[2] URL: http://citeseer.nj.nec.com/jackson02some.html
[3] URL: http://members.shaw.ca/qjackson/cs/glossary/adaptive_k.html

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