Semantics driven disambiguation: A comparison of different approaches
In Proceedings of the 8th workshop on language descriptions, tools and applications (LDTA’08)
Abstract
Context-sensitive languages such as or can be parsed using a context-free but ambiguous grammar, which requires another stage, disambiguation, in order to select the single parse tree that complies with the language’s semantical rules. Naturally, large and complex languages induce large and complex disambiguation stages. If, in addition, the parser should be extensible, for instance to enable the embedding of domain specific languages, the disambiguation techniques should feature traditional software-engineering qualities: modularity, extensibility, scalability and expressiveness. We evaluate three approaches to write disambiguation filters for sdf grammars: algebraic equations with asf, rewrite-rules with programmable traversals for , and attribute grammars with , our system. To this end we introduce , a highly ambiguous language. Its “standard” grammar exhibits ambiguities inspired by those found in the and standard grammars. To evaluate modularity, the grammar is layered: it starts with a small core language, and several layers add new features, new production rules, and new ambiguities.