Disambiguating Context-Free Grammars by Selecting the Minimum-Cost Parse Tree

Abstract A grammar that is ambiguous gives some strings more than one parse tree, but a compiler or interpreter has to work with a single one. The usual remedies each depend on something specific: precedence declarations work inside LR generators, grammar rewriting has to be done by hand, and tree filters act only after parsing. We take a different route and treat disambiguation as an optimisation problem. Each parse tree is given a cost, made up of the number of violated disambiguation patterns, the number of non-terminal nodes, and a canonical tie-breaking key, compared in that order. The cheapest tree is the one we keep. Since violations are penalised and never forbidden outright, every string in the language still receives a tree, and the language itself is untouched. When penalties depend only on a node and its immediate surroundings, the optimum can be found with a CYK-style dynamic program over input spans. For patterns that look further down the tree, such as the dangling else with an optional else-branch, each subtree also reports a small profile of whatever its parent may ask about it. The method works for any context-free grammar, including grammars with ε-rules and cycles, and returns exactly one tree per string of the language. Our implementation runs in O(n⁴·C) time, where C depends only on the grammar and the patterns. We do not suggest replacing linear-time LR parsing in production compilers. The method is meant for general-purpose tools that must cope with arbitrary grammars and still give a reproducible answer. It has clear limits. The chosen tree is only as meaningful as the patterns supplied, and deciding whether a grammar is ambiguous remains undecidable.