Publications/demaille.08.ldta

Authors

Akim Demaille, Renaud Durlin, Nicolas Pierron, Benoît Sigoure

Where

Proceedings of the 8th workshop on Language DescriptionsTools and Applications (LDTA'08)

Type

inproceedings

Projects

Transformers

Date

2008-02-08

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

• Paper

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}
}