Semantics driven disambiguation: A comparison of different approaches

From LRDE

Revision as of 15:20, 5 January 2018 by Bot (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Abstract

Context-sensitive languages such as langC or Cxx 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, extensibilityscalability and expressiveness. We evaluate three approaches to write disambiguation filters for sdf grammars: algebraic equations with asf, rewrite-rules with programmable traversals for stratego, and attribute grammars with tag, our system. To this end we introduce phenix, a highly ambiguous language. Its “standard” grammar exhibits ambiguities inspired by those found in the langC and Cxx 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.

Documents

Bibtex (lrde.bib)

@InProceedings{	  demaille.08.ldta,
  oldkeys	= {durlin.08.seminar},
  author	= {Akim Demaille and Renaud Durlin and Nicolas Pierron and
		  Beno\^it Sigoure},
  title		= {{Semantics driven disambiguation: A comparison of
		  different approaches}},
  booktitle	= {Proceedings of the 8th workshop on Language Descriptions,
		  Tools and Applications (LDTA'08)},
  year		= 2008,
  abstract	= {Context-sensitive languages such as \langC or \Cxx 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 \acs{sdf}
		  grammars: algebraic equations with \acs{asf}, rewrite-rules
		  with programmable traversals for \stratego, and attribute
		  grammars with \acr{tag}, our system. To this end we
		  introduce \phenix, a highly ambiguous language. Its
		  ``standard'' grammar exhibits ambiguities inspired by those
		  found in the \langC and \Cxx 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.},
  keywords	= {Transformers, context-free grammar, attribute grammar,
		  Stratego, ASF, SDF, disambiguation, parsing, program
		  transformation, term rewriting}
}