Verifiable Composition of Deterministic Grammars

Loading...
Thumbnail Image

Persistent link to this item

Statistics
View Statistics

Journal Title

Journal ISSN

Volume Title

Title

Verifiable Composition of Deterministic Grammars

Published Date

2009

Publisher

ACM Press

Type

Report

Abstract

There is an increasing interest in domain-specific and extensible languages, and frameworks for developing extensions to them. One challenge is to develop tools that allow non-expert programmers to add an eclectic set of language extensions to a host language. In this paper we describe mechanisms for composing and analyzing syntactic specifications of a host language and extensions. These specifications consist of context-free grammars with each terminal symbol mapped to a regular expression, from which a slightly-modified LR parser and context-aware scanner are generated. Conflicts are detected in a composed grammar when its parser is generated, but this comes too late since the non-expert programmer performs the compilation after composing the independently developed extensions with the host language. The primary contribution of this paper is a modular analysis that is performed independently by each extension designer on her extension (composed alone with the host language). If each extension passes this modular analysis, then the language composed later by the programmer will compile with no conflicts or lexical ambiguities. Thus, extension writers can verify that their extension will safely compose with others and, if not, fix the specification so that it will. This is possible due to the context-aware scanner's lexical disambiguation and a set of reasonable restrictions limiting the sort of constructs that can be introduced by a language extension. The restrictions ensure that the states in the parse table can be partitioned so that each state can be attributed to the host language or a single language extension.

Keywords

Description

Associated research group: Minnesota Extensible Language Tools

Related to

Replaces

License

Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other identifiers

Suggested citation

Schwerdfeger, August; Van Wyk, Eric. (2009). Verifiable Composition of Deterministic Grammars. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/217427.

Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.