The Meta-Environment - SDF

Skip to main content.

SDF (Syntax Definition Formalism)

Note

The primary reference for SDF is now http://www.syntax-definition.org

The Meta-Environment team has always made SDF available as a separately distributable and usable product. Due to this policy, SDF is now used by many different projects and people. Now, we also present SDF on its own website.

Description

SDF is a Syntax Definition Formalism with the following features:

This implies that if you have a grammar for some programming language (say COBOL or Java) and you want to combine it with the grammar of some embedded language (say, SQL) then you can just combine the two grammars without further ado. Shift/reduce conflicts are a matter of the past!

SDF is implemented in two parts:

An SDF definition consists of a grammar and some disambiguation constructs. These are used to generate a parsetable that the SGLR tool uses to parse an input file to a parse forest. Optionally, it may be needed to filter the result of SGLR such that a unique parse tree is obtained. SGLR outputs parse trees in the ATerm format. This parse architecture is thus as follows:

parse-architecture.png

Experiment with SDF using the Online SDF Demo.

The Meta-Environment ships with a grammar library containing various languages (C, Java, COBOL, ...). Other online sources for SDF grammars are:

After parsing, you can manipulate parse trees in any language:

The Meta-Environment includes the latest release of SDF. It offers:

Online documentation

Publications

%BIBTEX{ @phdthesis{Vis97.thesis, author = {Visser, E.}, title = {Syntax Definition for Language Prototyping}, year = {1997}, month = {September}, school = {University of Amsterdam}, url = {http://homepages.cwi.nl/~paulk/dissertations/Visser.pdf } } @INPROCEEDINGS{KV94, author = "P. Klint and E. Visser", title = "Using Filters for the Disambiguation of Context-free Grammars", editor = "G. Pighizzini and P. San Pietro", booktitle = "Proceedings ASMICS Workshop on Parsing Theory", year = 1994, pages = {1--20}, note = "Published as Technical Report 126--1994, Computer Science Department, University of Milan", url = {http://homepages.cwi.nl/~paulk/publications/ASMICS94.pdf} } @article{HKR90, author = {J. Heering and P. Klint and J. Rekers}, title = {{I}ncremental generation of parsers}, journal = {IEEE Transactions on Software Engineering}, volume = "SE-16", pages = {1344--1351}, year = {1990}, url = {http://doi.acm.org/10.1145/73141.74834} } @article{HKR92.igls, author = {J. Heering and P. Klint and J. Rekers}, title = {Incremental generation of lexical scanners}, journal = {ACM Transactions on Programming Languages and Systems}, volume = {14}, year = {1992}, pages = {490--520}, url = {http://www.acm.org/pubs/citations/journals/toplas/1992-14-4/p490-heering/} } @phdthesis{Rek92, author = {J. Rekers}, title = {Parser Generation for Interactive Environments}, school = {University of Amsterdam}, year = {1992}, url = {http://homepages.cwi.nl/~paulk/dissertations/Rekers.pdf} } @article{HHKR89, author = {J. Heering and P.R.H. Hendriks and P. Klint and J. Rekers}, title = {{T}he syntax definition formalism {SDF} --- {R}eference manual}, journal = {SIGPLAN Notices}, volume = {24}, number = {11}, pages = {43--75}, year = {1989} } @InProceedings{Moonen:2002:LIA, author = "L. Moonen", title = "Lightweight Impact Analysis using Island Grammars", booktitle = "Proceedings of the 10th International Workshop on Program Comprehension (IWPC 2002)", publisher = "IEEE Computer Society Press", month = jun, year = 2002, url = "http://www.cwi.nl/~leon/papers/iwpc2002/", } @InProceedings{Moonen:2001:RPGa, author = "L. Moonen", title = {Generating Robust Parsers using Island Grammars}, booktitle = "Proceedings of the 8th Working Conference on Reverse Engineering", publisher = "IEEE Computer Society Press", year = 2001, month = oct, pages = "13--22", url = "http://www.cwi.nl/~leon/papers/wcre2001/", }

@INPROCEEDINGS{ JV2000, author = "Jonge, M. de and J. Visser", title = {Grammars as Contracts}, booktitle = {Generative and Component-Based Software Engineering, Second International Symposion, GCSE 2000}, address = "Erfurt, Germany", year = "2001", series = "Lecture Notes in Computer Science", volume = "2177", publisher = "Springer", editor = "Greg Butler and Stan Jarzabek", pages = "85--99" }

@inproceedings{BSVV02, author = "Brand, {M.G.J. van den} and J. Scheerder and J.J. Vinju and E. Visser", title = "Disambiguation Filters for Scannerless Generalized {LR} Parsers", booktitle = "Compiler Construction 2002 (CC 2002)", series = "LNCS", editor = "N. Horspool", volume = {2304}, pages = {143--158}, year ="2002", url = {"/pub/Meta-Environment/SDF/BSVV02.pdf"} } @inproceedings{vandenbrand01parsing, author = "Brand, {M.G.J. van den} and C. Ringeissen", title = "{ASF}+{SDF} parsing tools applied to {ELAN}", booktitle = "Electronic Notes in Theoretical Computer Science", volume = "36", publisher = "Elsevier Science Publishers", editor = "Kokichi Futatsugi", year = "2001" }

@inproceedings{BJ00, author = "Brand, {M.G.J. van den} and J. Scheerder", title = "{D}evelopment of {P}arsing {T}ools for {C}{A}{S}{L} using {G}eneric {L}anguage {T}echnology", editor = {D. Bert and C. Choppy}, booktitle = {Workshop on Algebraic Development Techniques (WADT'99)}, series = {LNCS}, volume = {1827}, pages = {89--105}, year = {2000} } }%