RE: LL Parser problem

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


Abstract
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
submission.


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


[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


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


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

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