Parse forest disambiguation
LJ Bram Sanden, van der · TU/e Research Portal · 2014
Context-free grammars are the most widely used formalism to express the concrete syntax of general-purpose and domain-specific languages. Generalized parsers are able to handle any context-free grammar, which allows grammar engineers to write grammars in a natural way. A consequence of supporting the whole class of context-free grammars is that also ambiguous grammars are supported. This means that parsing an input sentence may lead to multiple derivations rather than a unique derivation. In generalized parsing, the set of all parse trees of a given input sentence is embedded in a parse forest. By using disambiguation rules and disambiguation filters, undesired derivations can be removed. In this thesis we will define a set of parser-technology independent parse forest filters, that allows the removal of undesired parse trees from a shared packed parse forest. These filters remove all parse trees from a parse forest that contain some construct, such as an invalid path. Given declarative disambiguation rules expressing the associativity, and precedence of operators, we can create filters that specify the constructs that should be removed. We will describe a new filter based on precede and follow restrictions, that allows the disambiguation of expression grammars containing mixfix operators with respect to associativities and precedences of operators. As a case study we will look into the disambiguation of the mCRL2 language, where also other disambiguation filters like keyword restriction and prefer filtering are used. Often disambiguation filtering can be partially applied on parse time, avoiding the creation of undesired parse trees in the first place. We will show how our disambiguation filters for expression grammars can be incorporated into the GLL algorithm. This integration leads to a substantial decrease in the total time needed for parsing and disambiguation of input sentences containing many ambiguities.