Computer Science Department Colloquium
Thursday, December 1, 1994
210 MacLean Hall
4:00-5:00pm

MULTI-AXIOM GRAMMARS REVISITED
by
James S. Jones
Graceland College

The Multi-axiom Grammar (MAG) was introduced by Rus and LePeau as an alternative to the single-axiom Context Free Grammar (CFG) and the all-axiom Algebraic Grammar (AG) for programming language specification. MAGs are unique in that the language designer can identify which nonterminals are non-axioms. However, the only use for non-axioms which was considered was in the specification of the lexicon of the language. Other uses played havoc with previous definitions and algorithms. In this talk I will revisit basic definitions of Multi-axiom Grammar, Subgrammar, Primitive Subgrammar, Quotient Grammar, and Grammar/Language Layer which address this problem and which give additional flexibility to the language designer. I have developed a system which allows non-axioms to exist at any grammar/language layer and which treats non-axioms as local variables in a given layer. I will also show the relation between language classes specified by MAGs, CFGs, and AGs, in order to suggest a preference for MAGs. Finally, I will show how this theory has application for pipeline parallel LR parsing based on a tokenization process occurring between the language layers.


Return to Jim Jones's faculty homepage