Handling Grammar Cycles in the 1997 SML Definition

Abstract

Fully general parsers permit the syntax specification of formal languages to be unrestricted, allowing language designers to use a syntax specification that supports semantics specification, but also permitting ambiguity. Language workbenches that support fully general grammars need tools which can generate robust default behaviour but also allow experienced designers to specify particular choices when ambiguity is encountered. The standard longest match approach to ambiguity resolution is not robust when a grammar contains cycles. Although cycles can be removed from a grammar, this disrupts the syntax specification. We present an algorithm that safely removes cycles from the shared packed parse forests generated by general parsers and explore the application of the algorithm to the 1997 SML Definition. The algorithm results in a sub-forest to which further designer-specified or default disambiguation rules can be applied.