Computational aspects of M-grammars

Abstract

In this paper M-grammars that are used in the Rosetta translation system will be looked at as the specification of attribute grammars. We will show that the attribute evaluation order is such that instead of the special-purpose parsing and generation algorithms introduced for M-grammars in Appelo et al.(1987), also Earley-like context-free parsing and ordinary generation strategies can be used. Furthermore, it is illustrated that the attribute grammar approach gives an insight into the weak generative capacity of M-grammars and into the computational complexity of the parsing and generation process. Finally, the attribute grammar approach will be used to reformulate the concept of isomorphic grammars.

Related Papers

• Attribute Grammars, Applications and Systems: International Summer School Saga Prague, Czechoslovakia, June 4-13, 1991 Proceedings(1991)
• → An LR parsing technique for extended context-free grammars(1981)5 cited
• → Effective natural language parsing with probabilistic grammars(2010)4 cited
• A Special Kind of Context Free Grammars and Their Parsing(1998)
• → Algorithm of parsing context-free grammars(2022)