RE: LL Parser problem

Quinn Tyler Jackson <>
7 Sep 2004 23:31:24 -0400

          From comp.compilers

Related articles
Re: LL Parser problem (2004-09-03)
RE: LL Parser problem (Quinn Tyler Jackson) (2004-09-07)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 7 Sep 2004 23:31:24 -0400
Organization: Compilers Central
References: 04-09-006
Keywords: LL(1), parse, tools
Posted-Date: 07 Sep 2004 23:31:24 EDT

DoDi said:

> My strongest argument for really context free grammars, best LL(1), is
> the chance for a complete separation of the grammar and parser from
> any implementation language. Nowadays grammars require the insertion
> of syntactic and semantic code into the mere grammar, when a parser
> for a language shall be created. When instead a parser could be
> constructed from a grammar without any additional code, the separate
> maintenance of the grammar and the intended application (compiler...)
> would be much easier. Then the parser could create an parse tree, or
> some other suitable meta data structure, based on nothing but the
> grammar, and the application only had to deal with that well defined
> and language independent information.

One of my long-term goals with the $-calculus has been to arrive at a
formalism that will allow for the formalism-only specification of languages.

This was achieved with promise in [Jackson 2003] on XML, and reported with a
toy language in [Jackson 2002]. I've just finished a paper (under
pre-review), where it has also been achieved with C++ and Perl. (O(n)
results on test data.)

Efficient Context-Sensitive Parsing Using the -Calculus
Quinn Tyler Jackson

The parsing of context-sensitive languages has application in the fields of
bioinformatics, mathematics, formal and computational linguistics, and
programming language implementation. To date, however, efficient
context-sensitive parsing has remained an elusive goal in terms of both
notation and practice, and especially in the area of programming language
implementation, has been effected largely by ad hoc methods. We present
difficult to parse context-sensitive constructions occurring in these fields
and supply $-grammars that accept these languages in better-than-cubic time,
demonstrating that the $-Calculus and the algorithms used to effect parsing
against $-grammars are strong contenders in this arena. Theory cannot be
entirely separated from practice, and so, sufficient background of the
$-Calculus is presented to facilitate discussion of the results.

Because of the scope of the above -- it's being given the thrice-over before

[Jackson 2003] Quinn Tyler Jackson, "Efficient Formalism-Only Parsing of
XML/HTML Using the -Calculus," SIGPLAN Notices, 38(2), pp. 29-35, Feb.

[Jackson 2002] Quinn Tyler Jackson, "Some Theoretical and Practical Results
in Context-Sensitive and Adaptive Parsing," Progress in Complexity,
Information, and Design, Vol. 1 No. 4, Dec. 2002.

Quinn Tyler Jackson

"Never express yourself more clearly than you think."
-- Niels Bohr

Post a followup to this message

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