tailieunhanh - Báo cáo khoa học: "Computational Aspects of M-grammars"

In this paper M-grammars t h a t are used in the Rosetta translation system will be looked at as the specification of a t t r i b u t e grammars. We will show t h a t the a t t r i b u t e evaluation order is such t h a t 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 t h a t the a t t r i. | Computational Aspects of M-grammars Joep Rous Philips Research Laboratories . Box 5600 J A Eindhoven The Netherlands E-mail rous@ uucp 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-bee 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. M-grammars In this section we will introduce very globally the grammars that are used in the Rosetta machine translation system which is being developed at Philips Research Laboratories in Eindhoven. The original Rosetta grammar formalism called M-grammars was a computational variant of Montague grammar. The formalism was introduced in Landsbergen 1981 . Whereas rules in Montague grammar operate on strings M-grammar rules M-rules operate on labelled ordered trees called S-trees. The nodes of S-trees are labelled with syntactic categories and attribute-value pairs. Because of the reversibility of M-rules it is possible to define two algorithms M-Parser and M-Generator . The M-Parser algorithm starts with a surface structure in the form of an S-tree and breaks it down into basic expressions by recursive application of reversed M-rules. The result of the M-Parser algorithm is a syntactic derivation tree which reflects the history of the analysis process. The leaves of the derivation tree are names of basic expressions. The M-Generator algorithm generates a set of S-trees by bottom-up application of .