Handling Grammar Cycles in the 1997 SML Definition

Elizabeth Scott; Adrian Johnstone

doi:10.1145/3732771.3742709

Handling Grammar Cycles in the 1997 SML Definition

Elizabeth Scott, Adrian Johnstone

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Downloads (Pure)

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 designerspecified
or default disambiguation rules can be applied.

Original language	English
Title of host publication	Proceedings of the 18th ACM SIGPLAN International Conference on Software Language Engineering (SLE '25), June 12--13, 2025, Koblenz, Germany
Publisher	ACM
Pages	3-15
Number of pages	13
DOIs	https://doi.org/10.1145/3732771.3742709
Publication status	Published - 17 Jun 2025

Access to Document

10.1145/3732771.3742709Licence: CC BY

Accepted ManuscriptAccepted author manuscript, 854 KBLicence: CC BY

Cite this

@inproceedings{d65824d5d0804ee984f32bef2bd44ba7,

title = "Handling Grammar Cycles in the 1997 SML Definition",

abstract = "Fully general parsers permit the syntax specification of formallanguages to be unrestricted, allowing language designersto use a syntax specification that supports semanticsspecification, but also permitting ambiguity. Language workbenchesthat support fully general grammars need toolswhich can generate robust default behaviour but also allowexperienced designers to specify particular choices when ambiguityis encountered. The standard longest match approachto ambiguity resolution is not robust when a grammar containscycles. Although cycles can be removed from a grammar,this disrupts the syntax specification. We present analgorithm that safely removes cycles from the shared packedparse forests generated by general parsers and explore theapplication of the algorithm to the 1997 SML Definition. Thealgorithm results in a sub-forest to which further designerspecifiedor default disambiguation rules can be applied.",

author = "Elizabeth Scott and Adrian Johnstone",

year = "2025",

month = jun,

day = "17",

doi = "10.1145/3732771.3742709",

language = "English",

pages = "3--15",

booktitle = "Proceedings of the 18th ACM SIGPLAN International Conference on Software Language Engineering (SLE '25), June 12--13, 2025, Koblenz, Germany",

publisher = "ACM",

}

TY - GEN

T1 - Handling Grammar Cycles in the 1997 SML Definition

AU - Scott, Elizabeth

AU - Johnstone, Adrian

PY - 2025/6/17

Y1 - 2025/6/17

N2 - Fully general parsers permit the syntax specification of formallanguages to be unrestricted, allowing language designersto use a syntax specification that supports semanticsspecification, but also permitting ambiguity. Language workbenchesthat support fully general grammars need toolswhich can generate robust default behaviour but also allowexperienced designers to specify particular choices when ambiguityis encountered. The standard longest match approachto ambiguity resolution is not robust when a grammar containscycles. Although cycles can be removed from a grammar,this disrupts the syntax specification. We present analgorithm that safely removes cycles from the shared packedparse forests generated by general parsers and explore theapplication of the algorithm to the 1997 SML Definition. Thealgorithm results in a sub-forest to which further designerspecifiedor default disambiguation rules can be applied.

AB - Fully general parsers permit the syntax specification of formallanguages to be unrestricted, allowing language designersto use a syntax specification that supports semanticsspecification, but also permitting ambiguity. Language workbenchesthat support fully general grammars need toolswhich can generate robust default behaviour but also allowexperienced designers to specify particular choices when ambiguityis encountered. The standard longest match approachto ambiguity resolution is not robust when a grammar containscycles. Although cycles can be removed from a grammar,this disrupts the syntax specification. We present analgorithm that safely removes cycles from the shared packedparse forests generated by general parsers and explore theapplication of the algorithm to the 1997 SML Definition. Thealgorithm results in a sub-forest to which further designerspecifiedor default disambiguation rules can be applied.

U2 - 10.1145/3732771.3742709

DO - 10.1145/3732771.3742709

M3 - Conference contribution

SP - 3

EP - 15

BT - Proceedings of the 18th ACM SIGPLAN International Conference on Software Language Engineering (SLE '25), June 12--13, 2025, Koblenz, Germany

PB - ACM

ER -