\subsection{Generation of Language-Based Tools}


Much of the functionality of a language-sensitive editor is determined by
the fact that substantial properties of the objects it deals with 
are formally specified by the (attributed) grammar of the language.

Since most of the {\em language independent} functionality of the editor is
``standard'' and can be provided by a set of existing library functions, the
main tasks for the construction of
an editor, namely the specifications of {\em language dependent} features
and actions  can be formalized and supported by a software generating tool.
This tool, the {\em Synthesizer Generator} and the common characteristics of
generated editors are outlined in the following sections.  

\subsubsection{The Synthesizer Generator}
\label{sgen}
\label{sgen-work}
The {\em Synthesizer Generator} (henceforth called {\em sgen}), which was
developed by Thomas Reps and
Tim Teitelbaum at Cornell University, accepts an attributed grammar as input
and constructs a {\em full screen editor} from this grammar. The editor
accepts exactly the words (structured text objects) that can be derived by the given grammar
and executes the semantic checks and actions specified there. The grammar must
be written in a language that has been developed especially for the definition
of attributed grammars, namely the {\em Synthesizer Specification Language\/}
(henceforth abbreviated as {\em SSL}).

In order to process the specification and to construct the editor, the
following actions are taken:
\begin{enumerate}
\item The grammar is parsed whereby completeness (exactly one semantic
	equation must exist for every nonterminal in the affected productions)
	and
	termination (every sequence of derivations must have a terminating
	production) are checked.
\item The generator tests the grammar for ``orderedness'' (see section
	\ref{oag}). This can be done in polynomial time.
\item Lexical definitions (regular expressions) are passed to Lex
	(see \cite{l}), which constructs a finite automata for the lexical
	analysis according to the specified regular expressions.
\item Parsing rules are translated into a form that is suitable as an input
	for the compiler generator Yacc(see \cite{j}). Yacc is then called to
	construct a pushdown automata (which is implemented as a procedure in
	{\em C} source code) according to these rules.
\item Evaluation strategies are computed for every possible situation (see
	page \pageref{oag} for a description of the algorithm) and translated
	into {\em C} procedures.
\item Transformations and {\em unparsing} declarations (see sections
	\ref{ssl} and \ref{ed}) are translated into appropriate sequences of
	function calls.
\item The created {\em C}-program is compiled and the library functions
 supplied by the editor are linked.
\end{enumerate}

                                                  
\label{ssl}
{\em SSL} is a strongly typed language which is free of side effects and is based on
the concept of a {\em term algebra} defining sets of operator-operand trees
(i.e.\ abstract syntax trees). The trees that can be derived from a given
nonterminal are considered as {\em terms}. The operators of these terms denote
nodes of a tree whereas the operands denote subtrees, hence terms again.
Nullary operators are the atomic objects of these trees (hence of the leaves).


Since operators are associated uniquely with a production of the grammar,
the definition of a set of trees may be considered as a type definition for the
nonterminal which generates these trees. Attribute definitions are carried
out in the same way and therefore attribute values are abstract syntax trees
themselves. Simple (predefined)\footnote{ The predefined simple types
are integer, real, bool, char, string, and references.} types are (possibly
infinite) sets of primitive trees (they only consist of the root of a tree).
\\[2mm]
In the following, a few additional properties of the specification language
are given.
The specification of a language is divided into an abstract (concerning the
structure of the defined language) and a concrete (concerning the text itself)
syntax. Structure and text are connected by attributes.
The terminal symbols, which belong to the concrete syntax, are not attributed.
The benefits derived from this separation are that details which belong
to the language representation and are irrelevant for specification purposes
can be suppressed. So we can concentrate on relevant aspects of the language.
Similarly, the accepted input is separated from the output representation.
This enables for example tree oriented transformations of input strings into
an arbitrary representation (a comparable but less powerful formalism is
established by syntax directed translation schemes (see \cite{au72})).  

The separation of an abstract syntax from a concrete one has the following
additional advantages:
\begin{itemize}
\item Parsing problems are separated from the structure of the considered
	language. The only obligation is to describe the abstract structure
	by a grammar which is context free.
\item Common input errors can be handled by relaxing the mapping from the
	input to the abstract syntax.
\item Commands which are independent from the language can be included like
	normal sourcecode and interpreted separately.
\item Tree transformations 		% (see \ref{tree-trans})
	work on abstract trees and
	are hence independent from the concrete language representation.
\end{itemize}

Similar to other grammar description languages (e.g., ALADIN \cite{k1}), SSL
permits non-local attribute references in a limited way: The referenced
attribute must belong to a predecessor of the referencing node in all
possible syntax trees. For noncircularity tests and computations of evaluation
strategies, a non-local reference can be treated as a chain of inherited
attributes (and therefore does not destroy the evaluation order).

As opposed to certain other approaches, the syntactic analysis is completely
independent from the semantic analysis. Syntax tree constructions are never
triggered by means of results of a semantic analysis.Different properties of
a single nonterminal need not be defined in one
place but can be scattered over different files. Furthermore, symbols which
were previously nullary operators can be redefined so that they become roots
of various subtrees. These properties permit the specification, generation
and testing of an editor with respect to partial aspects of
a programming language (e.g., separation of syntactic and semantic aspects).

\vspace{2mm}
In order to extent the editors' functionality (e.g., to generate and store
intermediate code), it is possible to include foreign {\em C}-procedures in an
SSL
specification. An interface to other components of the software development environment
can also be provided by such functions.
As already mentioned, SSL functions do not permit side effects. If side
effects are desired, they must also be supplied by external functions.


\subsubsection{The Editing Paradigm}

DBPL-USE and AM-USE utilize up-to-date interface technology based on window and menue
systems\footnote{E.g., X-Windows (X11) and SunView.} supported by UNIX\footnote{
SUN OS 4.0.}.

They can be invoked either without parameters or with an arbitrary number
of them.
The parameter list designates the files which are loaded into edit-buffers of
the same name. They can open multiple windows, whereby every window is associated
with a buffer. Changing the ``active'' window is triggered by a pointing
device (mouse). The actual cursor position in the edited text is changed
similarly. Standard operations like the deletion and replication of regions
as well as file insertions
and search functions are incorporated. Command names and key bindings
follow the EMACS text editor \cite{sta}. As usual, the bindings are
described by means of a keyboard description files and can be modified easily.
\\[2mm]
As opposed to common editors, the editors presented here have {\em knowledge} about 
their languages and
supply functions which are based on the {\em structure} and the {\em meaning}
of language constructs. The creation of design objects takes place in a
{\em structural} manner to enforce a view of design objects as hierarchical
objects generated by grammars. 

Following the structural editing paradigm, design objects are created in a top-down
fashion, starting with the root of the syntax tree. Patterns are inserted
by selecting one of the currently enabled tree expansions from a menue (i.e.,
one of the righthand sides of the nonterminal labelling the current
``active'' node of the syntax tree). 

Following this style of working, syntax errors cannot be made. In case of
an update,
the user always has to select a {\em node} (and {\em not} any arbitrary
position in the text). Consequently, structural editing consists in inserting,
pasting or deleting of whole subtrees. In order to enter the required text 
(at least
the identifiers), the {\em text cursor} is positioned automatically on the
first position within the selected subtree where text input is enabled. 
Semantic errors (according to the semantics decribed in
section~\ref{pl-semantik}) are detected and displayed. They are inserted
as comments at appropriate positions of the displayed program text.

Most language sensitive editors developed up to now either work {\em
structurally\/} (e.g MENTOR \cite{don} and IPE \cite{mef}), i.e.\ by means
of tree manipulations like pruning, grafting and deriving or they work {\em
textually\/} by means of a separate parser.
The editors presented here are {\em hybrid\/}, i.e., they combine both
principles. The structural editing paradigma is not abandoned but subtrees
containing no keywords may be inserted textually as well as by selecting
menue items\footnote{ Self defined intentifiers and constants obviously
{\em have} to be inserted textually.}. During the input of text, an occurring
syntax
error is indicated at once (if the user tries to leave the current node) and
further input is disabled until the error is corrected.

Due to the combination of both principles, design objects can be stored
alternatively as texts or as preordered trees. The latter facilitates the
revision of design objects by means of the editor and reusing by other tree oriented
tools. Attribute values can be stored in the same fashion (i.e.\ as preordered trees
or represented as texts). This feature is utilized in interfacing the GKBMS with 
appropriate representations of design objects as discussed in section \ref{alse}.

Semantic errors are only displayed if no syntax error occurs (leaving
the current node). The editor does not enforce semantic correctness; design objects
can be stored {\em with} semantic errors. The same applies for a syntactic
incompleteness, i.e., not all syntactically obligatory
constructs are required in order to leave the editor\footnote{ In this case
the program should not be stored textually since
the placeholders do not belong to the language and the program cannot be
parsed again.}. 

\paragraph{Operating Mode}
\label{ed-work}
An editor consists of a kernel furnishing an appropriate data type for
the maintenance of attributed trees and a driver for their manipulation.
The editor constructs and updates the attributed trees, it holds
one of them in each of its buffers. 

Editor-operations are replacements of a subtrees. More complex operations
are implemented as sequences of subtree replacements:
deletion is achieved through replacing a subtree by an empty production;
insertion of a pasted subtree by expanding an empty production, whereby
the label of the insert node and the root of the subtree must match;
alternations are sequences of deletions and insertions.

Consequently, every editing session is a sequence of subtree replacements.
Thereby, an inserted subtree is considered as ``free standing'' and fully
attributed whereas the inherited attributes of the root are undefined.

The parser is called for every text input. If parse-errors occur then the cursor
is positioned on the first unrecognized token. A {\em concrete} syntax
tree is constructed from the input and mapped to an abstract tree. If
necessary, attribute values are updated accordingly (see section~\ref{ssl}).
Updates are carried out by means of an incremental version of the evaluation
algorithm for {\em ordered} grammars invented by Kastens (see section~\ref{oag}
and \cite{k})\footnote{ In case of an update, semantic equations are treated as
assignments.}. The generated concrete syntax tree and the input itself are
not needed any further. The resulting abstract tree is inserted at the
appropriate position in the tree which holds the currently edited object
and displayed according to the {\em unparsing} rules incorporated in the editor.

Summarizing, the editor transforms every input to an attributed tree and inserts
this tree into the main tree according to the construction rules of the
abstract grammar.

As opposed to compilers based on attribute grammars, for an editor it is
necessary to maintain a consistently attributed tree, even in case of uncomplete
design objects. Therefore, nonterminals that have not been unexpanded must obtain
attributes and
corresponding empty productions. From the editor's point of view, the
attributed tree is complete and consistent after every user action.

The representation of attributed trees mentioned above includes the display
of error attributes. Error attributes are defined as strings whose values
evaluate to the empty string if no error occurs and to the appropriate error
message otherwise. 
