Re: Syntax analysis in real time

sanjay@src.dec.com (Sanjay Ghemawat)
23 Jul 1996 23:32:40 -0400

          From comp.compilers

Related articles
Smart textual editors gupta@csc.ti.com (1996-07-15)
Syntax analysis in real time jacob@jacob.remcomp.fr (1996-07-22)
Re: Syntax analysis in real time sanjay@src.dec.com (1996-07-23)
| List of all articles for this month |

From: sanjay@src.dec.com (Sanjay Ghemawat)
Newsgroups: comp.compilers
Date: 23 Jul 1996 23:32:40 -0400
Organization: DEC Systems Research Center
References: 96-07-103 96-07-151
Keywords: parse, tools

> I was looking for smart textual editors. By smart, I mean editors
> which might be doing data flow analysis and such things even while the
> editing is in progress so that they can point out the errors to the
> programmer. (e.g. if certain part of the code is unreachable, then it
> might give hints to the programmer etc.)


The "synthesizer generator" project at Cornell aimed to automate the
process of generating language sensitive editors from language
specifications. (This was in the mid 80's and two of the major
contributers to the project were Tim Teitelbaum and Tom Reps.)


The resulting editors could do usual things like highlighting of
keywords. In addition, they could actually point out type errors as
you were editing the program, and if you added a code generator to the
language specification, you would also see the generated code as you
were editing your program.


To generate a language sensitive editor for a new language, you would
have to specify various things:
1. Parsing rules that would convert fragments in the source language
      into an AST.
2. An attribute grammar specification for various attributes to be
      placed on the AST.


The system generated an editor which would build an AST as you were
typing in the program. As the AST changed, the editor engine would
incrementally reevaluate all of the AST attributes. One of the neat
properties of the system is that the user could open a window to view
any of the attributes of the root of the AST. In fact, the default
editor view just showed a special "unparsed-value" attribute of the
AST.


The power of the system came from the attribute grammar specification.
Unlike yacc, which allows a very limited form of attribute grammars,
the Cornell system would allow you to specify any ordered attribute
grammar. This made it easy to write specifications that propagated
various properties of the program up and down the AST. Using these
facilities, it was easy to propagate expression and variable types,
and therefore flag type errors by placing error messages into the
unparsing attributes.


Here is a snippet from an actual specification Robert Ashcroft and I
wrote for a compiler class. (The full specification contained a
parser, unparser, type-checker, and a code generator for a toy
language.)
expr: IdValue
                                                {
                                                local STR error;
                                                local ENV env;
                                                local BOOL declared;


                                                env = EnvOf($$._block);
                                                declared = with(lookup(id._name, env)) (
                                                        Binding(*, f, *, *, *, *):
                                                                (f==NullFlag ? false :
                                                                                              true)
                                                );
                                                error = declared ? "" : "{<--ID not declared}";
                                                $$._type = declared ?
                                                        with(lookup(id._name, env)) (
                                                                Binding(*, *, t, *, *, *): t
                                                        ) :
                                                        AnyType;
                                                }


This code is evaluated to compute attributes for an identifier that
occurs as an rvalue. The identifier is looked up in the environment
attribute of the expression. The "error" attribute is set to the
empty string if the identifier occurs in the environment. Otherwise,
it is set to "{<--ID not declared}". The unparse attribute (which is
not defined here) is a concatenation of the identifier name and the
"error" attribute. Therefore the user sees an error message whenever
an identifier is used without declaration.


-Sanjay Ghemawat
[Teitelbaum started a little company that produces commercial language
tools, notably Ada editors. I run into them now and then at lunch time,
there being a limited number of places in Ithaca to have lunch. -John]


--


Post a followup to this message

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