Adapting to Babel

"Quinn Tyler Jackson" <>
Thu, 23 Apr 2009 08:17:34 -0700

          From comp.compilers

Related articles
Adapting to Babel (Quinn Tyler Jackson) (2009-04-23)
Adapting to Babel (Quinn Jackson) (2013-08-07)
| List of all articles for this month |

From: "Quinn Tyler Jackson" <>
Newsgroups: comp.compilers
Date: Thu, 23 Apr 2009 08:17:34 -0700
Organization: Compilers Central
Keywords: books, question
Posted-Date: 24 Apr 2009 06:49:50 EDT

Would anyone care to review this:

I can email the PDF directly.

It is written in the dry dissertation style. (Yawn.)


Since the time of Noam Chomsky's introduction of phrase structure grammars
in 1956-1957, it has been known that formal methods can be applied to the
parsing of an infinite variety of input. In practice, however, grammars of
sufficient formal power to generate context-sensitive languages in their
various forms have lacked efficient generalizable algorithms, or have been
of such cumbersome notation and implementation that practitioners in various
fields that could otherwise greatly benefit from applied language theory
have been shackled to much less powerful underlying parsing engines.

The $-Calculus (pronounced: meta-ess calculus), an adaptive grammar
formal-ism, and the corresponding adaptive(k) parsing algorithm are shown to
have theoretical and practical utility in the fields of classical formal
language, combinatorics, computational linguistics, bioinformatics, data
mining, and programming language semantics, making tractable many previously
difficult to parse languages.

This is demonstrated by first building a formal foundation around the
septuple of the $-Calculus, and then introducing the predicated pushdown
automaton augmented with name-indexed tries (PDA-Ts), a new computational
machine built upon the classical single stack PDA. After the formal model is
established, implementation issues and their time complexity are examined in
terms of optimizations used in practice to reduce time complexity.

After this framework is established, each of the areas benefited by the
$-Calculus and its corresponding automata and algorithms is examined in turn
using empirical methods.

Quinn Tyler Jackson

Post a followup to this message

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