Re: Do I need to invent a new type of parser?

anton@mips.complang.tuwien.ac.at (Anton Martin Ertl) writes:


>|[Not to throw cold water on your plans, but 15-20 years ago there were quite
>|a few languages which allowed to you define syntax on the fly. They all
>|died. Makes you wonder, huh? -John]


>Some are alive and kicking:
> [..]


Indeed:


The Syntax Definition Formalism (SDF) developed by the Programming
Research Groups of the University of Amsterdam and the Center of
Mathematics and Computer Science (CWI) at Amsterdam is a formalism to
specify context free grammars. It is used in combination with the
Algebraic Specification Formalism (ASF) to define the syntax of the
signatures of the algebras specified in ASF.


The ASF+SDF system uses specifications to generate interactive programming
environments for the languages defined by the specifications. For the
syntax defined in the specification the system generates a parser. This
parser is used also to parse the equations by which the semantics of the
language are defined.


A small example is the specification of the language of booleans:


module Booleans
    exports
        sorts BOOL
        lexical syntax
            true -> BOOL
            false -> BOOL
        context-free syntax
            "~" BOOL -> BOOL
            BOOL "&" BOOL -> BOOL
            BOOL "|" BOOL -> BOOL
            "(" BOOL ")" -> BOOL {bracket}
        variables
            b[0-9']* -> BOOL
    equations
        [0] ~ false = true
        [1] ~ true = false
        [2] true & b = b
        [3] false & b = false
        [4] true | b = true
        [5] false | b = b
end module Booleans


The lines under the heading 'context-free syntax' may be viewed in two
ways; as grammar rules read the other way around (read "~" BOOL -> BOOL as
BOOL ::= "~" BOOL) and as function signature definitions. The syntax
defined in the first part of the module is needed to parse the equations;
the parser is extended at run time.


In the the environment generated by the system one can instantiate an
editor for this syntax. In this editor a term of sort (type) BOOL can be
entered. The term is parsed and can then be reduced by applying the
reduction rules derived from the equations by interpreting them from left
to right. For example the term


true & (~ true | ~ false)


would be reduced to true.


The formalism is designed to make formal descriptions of syntax and
semantics of (programming) languages from which tools to process texts in
the defined language can be generated. Several such despriptions have been
made (including a typechecker for Pascal, an interpreter for SQL). I am
presently writing a specification of the syntax and static semantics of
Eiffel.


Further reading:


@article{HHKR89,
    key = {HHKR89},
    author = {J. Heering and P.R.H. Hendriks and P. Klint and J. Rekers},
    title = {{T}he syntax definition formalism {SDF} - reference manual},
    journal = {SIGPLAN Notices},
    volume = {24},
    number = {11},
    pages = {43-75},
    year = {1989}}


@book{BHK89,
    key = {BHK89},
    editor = {J.A. Bergstra and J. Heering and P. Klint},
    title = {{A}lgebraic {S}pecification},
    series = {ACM Press Frontier Series},
    publisher = {The ACM Press in co-operation with Addison-Wesley},
    year = {1989}}






groet


Eelco Visser


--
Eelco Visser
student - Department of Computer Science - University of Amsterdam
e-mail: visser@fwi.uva.nl
--

Return to the comp.compilers page.
Search the comp.compilers archives again.