% File: compiler-toolkit.tex
% Title: Using the Tycoon Compiler Toolkit
% Date: 5-JUN-1992 
% Author: Gerald Schr\"oder, Florian Matthes

\documentstyle[tycoon]{article}

\newcommand{\PQ}{{\it P-Quest}}
\newcommand{\TCT}{{\it Tycoon Compiler Toolkit}}

\title{Using the Tycoon Compiler Toolkit}
\titleid{DBIS Tycoon Report 061-92}
\titlestatus{Initial Version}
\date{June 1992}
\author{Gerald Schr\"oder, Florian Matthes}

\titledescription{This document explains the structure and the use of
the Tycoon compiler toolkit, a library of generic modules in the Tycoon 
system library implemented in P-Quest.} 

\titlerelated{\PQ\ Installation and User Manual \cite{Matt91a} \\
\PQ\ User Manual \cite{NMM92} (in German) \\
The Quest Language and System (Tracking Draft) \cite{Card90} \\
}

\begin{document}

\maketitle

\tableofcontents

\newpage


\section{Introduction}

The motivation for the \TCT\ comes from our experience in building and
maintaining compilers and language-sensitive tools for Pascal/R,
Modula-2, Modula/R, DBPL on various software platforms (e.g. see
~\cite{MSS91,Nieb91,ScMa90b,Schr91}). Although the possible approaches
to compiler construction and compiler modularization are well-explored
and widely accepted, many algorithms have to be programmed from scratch
for every new compiler. In particular, a substantial effort in the
development of tools for database environments (schema design tools,
transaction specification tools, proof assistants, or ad-hoc query
interfaces) is devoted to the clerical tasks of scanning, parsing,
unparsing and the recovery from erroneous user-input with precise error
messages.

The \TCT\ supplies tools to construct and change these ``simple'' parts
of compilers in a structured and standardized way within a
strongly-typed polymorphic programming language. It does not rely on
ad-hoc interfaces to external tools (like yacc, lex, bison, rex, ell)
that do not allow to exploit the full power of persistent higher-order
languages.  It also provides a modular framework to reuse and exchange
parts of existing compilers developed with the \TCT\ exploiting the
module mechanisms of \PQ. A standardized approach to the definition of
new compilers is given in this text.

The toolkit is to be understood as a first step in a research programme
where we are going to explore new ways in the usage of compiler toolkits
as extensible language processor components in integrated database
application systems \cite{MaSc91}.  This will be accomplished by using
\e{one} language for the definition of \e{all} compiler components and
by exploiting the language and system support of languages like \PQ\
(like dynamic binding, persistence management, higher-order functions)
to give up the strict separation between language definition, compiler
generation and language utilization time

The toolkit has been designed by Florian Matthes who also programmed the
parser generator. Gerald Schr\"oder programmed the scanner generator and
the demo.

This guide describes the steps required to build a compiler using the
initial version of the toolkit. After a short introduction into the
structure of compilers, a small demo compiler is presented. The source
text of this demo is available in the Tycoon libraries and should be
consulted for a deeper understanding of the examples.

% ------------------------------------------------------------------

\section{Logical compiler structure}


Before it can be judged what a compiler toolkit can afford, the general
structure of a compiler has to be understood first. This description
follows \cite{ASU86}, further details can be found in books on compiler
construction, e.g.~\cite{WaGo85}.

Several \e{logical} compiler \e{passes} can be distinguished. They
successively transform a given source text into a machine-dependent
object code. These passes do not have to correspond to \e{physical
passes} on the source text and its internal representation. It is
possible and usual practice to fold several logical passes into one
physical pass. But for the construction of a compiler the main focus
lies on logical passes.

\begin{figure}[hbt]
\begin{maxipage}\centering
\unitlength=1mm
\begin{picture}(150,10)
\put(10,5){\makebox(0,0)[cc]{Source}}\put(10,5){\oval(15,10)[]}
\put(18,5){\vector(1,0){9}}
\put(28,0){\framebox(20,10)[cc]{Frontend}}
\put(48,5){\vector(1,0){9}}
\put(75,5){\makebox(0,0)[cc]{Intermediate code}}
\put(75,5){\oval(35,10)[]}
\put(93,5){\vector(1,0){9}}
\put(103,0){\framebox(20,10)[cc]{Backend}}
\put(123,5){\vector(1,0){9}}
\put(140,5){\makebox(0,0)[cc]{Code}}
\put(140,5){\oval(15,10)[]}
\end{picture}
%\parbox{150mm}{}
\caption{\label{x1} Overall compiler structure}
\end{maxipage}
\end{figure}

In Figure~\ref{x1} both main passes of a compiler are shown: The
\e{frontend} and the \e{backend}. The frontend transforms the source
text into a compiler dependent, but mostly machine independent,
intermediate language. While this transformation takes place the
compiler checks the source text for errors and reports them. The backend
starts only when the frontend has not found any errors. It transforms
the implicitly error-free intermediate representation into a machine
dependent object code format, possibly enriched by some information for
tools such as a linker, debugger or performance analyser.

The \TCT\ concentrates mainly on building the frontend of a compiler. So
the backend is not mentioned in further detail.

\begin{figure}
\begin{maxipage}\centering
\unitlength=1mm
%
\begin{minipage}[t]{60mm}
\centering
\begin{picture}(40,175)(0,-5)
\put(20,165){\makebox(0,0)[cc]{Character stream}}
\put(20,165){\oval(33,10)[]}
\put(20,160){\vector(0,-1){10}}
\put(11,140){\framebox(18,10)[cc]{Scanner}}
\put(20,140){\vector(0,-1){10}}
%
\put(20,125){\makebox(0,0)[cc]{Symbol stream}}
\put(20,125){\oval(29,10)[]}
\put(20,120){\vector(0,-1){10}}
\put(10,100){\framebox(20,10)[cc]{Parser (1)}}
\put(20,100){\vector(0,-1){10}}
%
\put(20,85){\makebox(0,0)[cc]{Parse tree}}
\put(20,85){\oval(21,10)[]}
\put(20,80){\vector(0,-1){10}}
\put(10,60){\framebox(20,10)[cc]{Parser (2)}}
\put(20,60){\vector(0,-1){10}}
%
\put(20,45){\makebox(0,0)[cc]{Syntax tree}}
\put(20,45){\oval(24,10)[]}
\put(20,40){\vector(0,-1){10}}
\put(3,20){\framebox(34,10)[cc]{Semantic Analyser}}
\put(20,20){\vector(0,-1){10}}
%
\put(20,5){\makebox(0,0)[cc]{Attributed tree}}
\put(20,5){\oval(33,10)[]}
\end{picture}
\par
{a) Passes and data types}
\end{minipage}
%
%\hfill
%
\begin{minipage}[t]{60mm}
\centering
\begin{picture}(40,175)(0,-5)
\put(10,165){\makebox(0,0)[cc]{x}}
\put(20,165){\makebox(0,0)[cc]{+}}
\put(30,165){\makebox(0,0)[cc]{1}}
%
\put(20,160){\thicklines\vector(0,-1){30}}
%
\put(10,125){\makebox(0,0)[cc]{id}}
\put(20,125){\makebox(0,0)[cc]{plus}}
\put(30,125){\makebox(0,0)[cc]{num}}
%
\put(20,120){\thicklines\vector(0,-1){25}}
%
\put(20,90){\makebox(0,0)[cc]{exp}}
\put(15,87){\line(-1,-1){5}}
\put(20,87){\line(0,-1){5}}
\put(25,87){\line(1,-1){5}}
\put(10,80){\makebox(0,0)[cc]{id}}
\put(20,80){\makebox(0,0)[cc]{plus}}
\put(30,80){\makebox(0,0)[cc]{num}}
%
\put(20,75){\thicklines\vector(0,-1){20}}
%
\put(20,50){\makebox(0,0)[cc]{plus}}
\put(15,47){\line(-1,-1){5}}
\put(25,47){\line(1,-1){5}}
\put(10,40){\makebox(0,0)[cc]{id}}
\put(30,40){\makebox(0,0)[cc]{num}}
%
\put(20,35){\thicklines\vector(0,-1){20}}
%
\put(20,10){\makebox(0,0)[cc]{int.plus}}
\put(15,7){\line(-1,-1){5}}
\put(25,7){\line(1,-1){5}}
\put(10,0){\makebox(0,0)[cc]{id.int}}
\put(32,0){\makebox(0,0)[cc]{num.int(1)}}
\end{picture}
\par
{b) Example values}
\end{minipage}
%
%\parbox{120mm}{}
\caption{\label{x2} Components of a compiler frontend}
\end{maxipage}
\end{figure}

In figure~\ref{x2}a) a model of the logical passes of the frontend is
shown, while figure~\ref{x2}b) contains an example of the transformation
steps. In the following paragraphs, the model of figure~\ref{x2}a) is
explained with references to the example of figure~\ref{x2}b).

First, the source text, in an abstract view a \e{character stream}, is
transformed by a \e{scanner} into a \e{symbol stream}. The scanner
analyses the character stream and searches for a string, called
\e{lexem}, matching some regular expression. If a lexem was found the
corresponding symbol is put to the symbol stream.

In the example the scanner first finds the lexem ``x'' and puts the
symbol \kw{id} to the symbol stream. Then the lexemes ``+'' resp. ``1''
are found and the symbols \kw{plus} resp. \kw{num} are
returned.\footnote{In reality the scanner would not transform the
\e{whole} source text into symbols \e{before} the next pass is started,
but it would be called to return only the next symbol when this is
needed.}

The symbol stream is input to the \e{parser} which is divided into
two parts. The first part checks if the symbols form a correct sentence
of the language, usually called \e{program} or \e{module}. The
language is described by a grammar, normally a context free grammar. The
parser tries to match the symbol stream with the rules of the grammar.
This process yields a \e{parse tree}, sometimes called \e{concrete
syntax tree}, which shows how the grammar rules have been applied to
form the sentence. The leaves of the parse tree are the input symbols to
the parser.

In the example of figure~\ref{x2}b) there is a rule saying that an
expression can be an identifier followed by a plus sign followed by a
numerical literal. So, the first part of the parser builds the parse
tree shown in figure~\ref{x2}b).\footnote{In reality the parse tree is
never built explicitly, but exists implicitly in the parser structure.}

The parse tree is input to the second part of the parser which builds an
\e{abstract syntax tree}. This tree contains only the bare syntax
information, but abstracts from superfluous symbols such as parentheses
or keywords as \k{begin}. The construction of the syntax tree is
performed by \e{attributes} and \e{actions} that are attached to the
grammar rules. Therefore, the grammar is called \e{attributed grammar}.
The syntax tree is constructed while parsing a sentence.

In the example above, it is not necessary to know that the source text
matches the rule describing an expression. But the information is
preserved that an operation ``plus'' on two objects, namely an ``id''
and a ``num'', is mentioned in the source text; see figure~\ref{x2}b).

The syntax tree is further analysed by other passes which depend on
the semantic rules of the language. These passes could
check, e.g.,
\begin{itemize}
  \item whether all used identifiers have been declared;
  \item whether the operands of
expressions have compatible types, where ``compatibility'' has to be
defined by the language, e.g. if real and integer operands are
compatible;
  \item whether functions are called with the correct number and type
of arguments.
\end{itemize}

In the example above, it is checked if the identifier ``x'' has been
declared and if it is compatible to the numeric literal ``1'' which
could be defined as an integer or real value.

Summing up, the frontend gives answers to the following questions:
\begin{enumerate}
 \item Is the source text a correct sentence of the language?
 \item What is an (error-free) intermediate representation of the source text?
\end{enumerate}

% ------------------------------------------------------------------------

\section{Compiler toolkits}

In this chapter two aspects of compiler toolkits are discussed:
\begin{enumerate}
 \item Which achievements can be expected from compiler toolkits?
 \item What has to be payed for these achievements?
\end{enumerate}

Normally, compilers are implemented in some programming language and the
programmer is responsible for the correctness of the implementation.
With a compiler toolkit the focus lies on the \e{specification} of the
language the compiler should work on and on the semantics of this
language.  If the specification is correct the toolkit generates a
correct compiler. Thus the language designer has only the responsibility
for the correctness of the specification. The toolkit helps to prove the
correctness, e.g. by defining a language to specify the grammar rules
and by some automatic checks on the rules.

If the language is changed or extended, normally the whole
implementation of the compiler has to be reviewed. Experience teaches
that errors are most likely to happen and are hard to find. With a
toolkit only the specification of the language is changed and the
toolkit guarantees that the newly generated compiler is error-free.

Compilers that have been coded by hand often are not modularized in the
same manner. It is hard to understand which parts of two distinct
compilers do the same things, e.g. which modules form the scanner and
where the interface to the parser can be found. It is almost impossible
to interchange parts of compilers. In a compiler toolkit the interfaces
between the parts are well-defined and constant between all compilers.
Therefore, it is easy to understand which part supplies which service
and it is possible to exchange or reuse a part.

It is not a trivial problem to build a compiler. Compilers are very
complicated tools where algorithms of many domains have to be used. Many
problems have to be solved by any compiler, e.g. efficient reading and
analysing of the source text, which takes most of the compiler runtime,
and error recovery. Solving this problems again and again is time
consuming, tedious and error prone. A compiler toolkit saves time and
enables the language designer to concentrate on the really difficult
task of defining the language, not implementing the compiler. By the
way, hopefully the implementor of the toolkit has solved all common
problems in the most efficient way, leading to fast and small compilers
without bothering about the best algorithms for common problems.

But there are some drawbacks when using compiler toolkits:
\begin{enumerate}
  \item Experience has
shown that many hand-coded compilers are leaner and faster than
automatically generated ones, although there are also counter examples.
  \item Working with a toolkit leads to
dependence on the tools, that is, loss of flexibility.
\end{enumerate}

% -------------------------------------------------------------------

\section{The structure of the \TCT}

The toolkit can be separated into two parts:
\begin{enumerate}
 \item Standardized interfaces between certain parts of a (generated) compiler.
 \item Modules that build implementations for the
 specified interfaces.
\end{enumerate}


\subsection{Interfaces}

The predefined interfaces of a compiler are:
\begin{description}
 \item[Source:] The abstraction of a character stream, giving
 successive access to the characters of a source text.
 \item[Scanner:] The abstraction of a symbol stream, delivering symbols
 scanned from the source character stream.
 \item[Parser:] The abstraction of a syntactic analyser that checks the
 symbol stream for correctness and performs some actions, e.g.
 building a syntax tree.
 \item[ErrorLog:] The abstraction of a log for error messages generated
 by the compiler.
\end{description}

Matching implementations for these interfaces can be implemented in two
ways:
\begin{enumerate}
  \item Using of the toolkit which automatically generates the implementations.
  \item Coding the implementions by hand.
\end{enumerate}


\subsection{Scanner generator}

To build a concrete scanner for a set of symbols,
the following modules can be used:
\begin{description}
 \item[RegExpr:] Building regular expressions.
 \item[Symbol:] Representation of symbol values which can be used optionally.
 \item[LexicalAnalyzer:] The abstraction of a lexical analyser which is
 syntactically equivalent to a scanner but has the semantic difference
 that no ``white spaces'', i.\,e. blank, tab, carriage return, comment,
 are skipped, and that no error recovery is done.
 \item[RegToLex:] This module takes a set of symbols and regular
 expressions defining the corresponding lexems, and produces a lexical
 analyser from these definitions.
\end{description}

Note that there is currently no tool to build a scanner. One or more
lexical analysers are built automatically, but they have to be plugged
together by hand to form a scanner. This will be done automatically
later on but the problem of glueing them together has not been addressed
yet. In the mean time, the module \kw{demoReg.impl} can be used as a
template; see section~\ref{scanner-definition}.


\subsection{Parser generator}

To build a concrete parser for a specific grammar the following modules can be
used:
\begin{description}
 \item[Grammar:] Specification of the grammar rules and attached
 actions, and transformation of the definitions to a parser. Currently, only
 LL(1)-grammars are supported.
 \item[Lexicon:] Mapping of keywords to symbols and grammar rules.
\end{description}


\subsection{Summary}

In contrast to other compiler toolkits, e.g. lex / yacc,
\begin{itemize}
 \item no meta language is used to define scanners and parsers, but all
 definitions are performed in the host language \PQ. This 
 guarantees full type correctness already at language-definition time.

 \item no source code is produced which has to be compiled, but instead
 functions are generated and manipulated as first class language objects
 (flexible naming, dynamic binding, persistent storage, \ldots).
\end{itemize}

Therefore, the opportunity to construct or load parts of the compiler at
\e{runtime} is gained. There is no possibility of type errors at
runtime because \PQ\ can perform all checks at compile time,
especially on the actions attached to the grammar rules.

% --------------------------------------------------------------------

\section{Example: Construction of an expression interpreter}

In this chapter an expression interpreter is constructed using the \TCT.
This example shows which steps you have to take on
building your own compilers or interpreters.


\subsection{Overview}

The result of our effort is an expression interpreter, e.g. an
interpreter that reads and parses expressions, and evaluates them
instead of building a syntax tree.

The following modules are parts of the example:
\begin{description}
 \item[demoMain:] Main program that uses the generated scanner and
 parser to interpret simple expressions.
 \item[demoGen:] Main program that generates a scanner, a parser, and a
lexicon of keywords to save them on disk.
 \item[DemoGram, demoGram:] Top level definition of the parser.
 \item[DemoExp, demoExp:] Definition of expressions for the parser.
 \item[DemoReg, demoReg:] Definition of the scanner and two lexical
 analysers.
 \item[DemoSym, demoSym:] Definition of symbols and keyword lexicon.
 \item[Bindings, bindings:] Representation of values and
 simple mapping of identifiers to values.
\end{description}

To run the demo, follow these steps:
\begin{enumerate}
 \item Compile the modules bottom up, that is, start with
\kw{Binding}, or use \kw{make}.
 \item Start \PQ, import \kw{demoGen} and call \kw{demoGen.go()}. Now the
scanner, parser and lexicon are generated.
 \item Import \kw{demoMain} and call \kw{demoMain.go()}. You can choose the
input from a file, e.g. \kw{demo.txt}, or use interactive mode. In
interactive mode, use {\tt Ctrl-D} to terminate input; you may have to type
{\tt Ctrl-D} more than once.
\end{enumerate}


\subsection{The grammar}
\label{grammar}

The expression interpreter accepts the following syntax (see
section~\ref{parser-definition} for examples how these rules are implemented):
\begin{tt}
\begin{description}
 \item[top] ::= \{ 'let' id '=' exp 'in'  |  exp \} ';'\\
 {\rm At top level we can perform binding of expressions to identifiers
 or evaluate expressions.}
 \item[exp] ::= term \{ ('+'|'-') term \}\\
 {\rm An expression is a term optionally plus or minus other terms. Evaluation
order
 is left to right.}
 \item[term] ::= factor \{ ('*'|'/') factor \}\\
 {\rm A term is a factor optionally multiplied with or divided by other
 terms. Evaluation order is left to right.}
 \item[factor] ::= '(' exp ')'  |  int  |  real  |  id\\
 {\rm A factor is an expression put in parentheses or an integer literal or a
 real literal or an identifier.}
\end{description}
\end{tt}

For example, this is a correct top level input:
\begin{xple}
  \k{let} a = 2 \k{in}
  \k{let} b = a * 2 \k{in}
  \k{let} c = b - 2 \k{in}
  a * ( b - c + 2 ) / 8 ;
\end{xple}

The result is ``1''.


\subsection{Scanner definiton}
\label{scanner-definition}

The scanner is defined by \kw{demoReg} and it is generated by \kw{demoGen}. It
is composed of two lexical analysers: The first one skips
whitespaces like blanks, tabs and carriage returns, the second one
recognizes the symbols of the language. Each symbol is accompanied with
a regular expression defining the lexem. Here is a list of symbols and
regular expressions:
\begin{center}
\begin{tabular}{c|c}
 symbol     & regular expression\\
 \hline
 point      & '.'\\
 equal      & '='\\
 plus       & '+'\\
 minus      & '--'\\
 times      & '*'\\
 div        & '/'\\
 leftparen  & '('\\
 rightparen & ')'\\
 int        & \{'0'..'9'\}$^+$\\
 real       & \{'0'..'9'\}$^+$\,'.'\,\{'0'..'9'\}$^+$\\
 id         & \{'A'..'Z', 'a'..'z'\}\,\{'A'..'Z', 'a'..'z', '0'..'9',
 '\_'\}$^+$\\
 \hline
 wrong      & \e{predefined}\\
 endOfInput & \e{predefined}\\
 \hline
 \end{tabular}
 \end{center}

The symbols \kw{wrong} and \kw{endOfInput} are predefined by
the module \kw{Symbol}. The keywords \k{let} and \k{in} are
recognized as symbol \kw{id} and have to be separated from identifiers
by using the keyword lexicon defined in \kw{DemoSym}.

To define a scanner, take the following steps:
\begin{enumerate}

 \item Find the symbols and their description by regular expressions. The
symbol that matches the longest possible input is returned, i.\,e. ``1.0'' is
\kw{real} and not \kw{int}, \kw{point}, \kw{int}. Ambiguous definitions
are not permitted, i.\,e. it is not possible to define keywords if they are
matching the regular expression defining identifiers.\footnote{Some
lookup in a hash table might be more space and time efficient than a
lexical analyser distinguishing dozens of keywords.} It is not possible
to declare a right context, i.\,e. that ``1..'' should be treated as \kw{int}
and \kw{ellipsis} instead of \kw{real} and \kw{point}.

 For example, the following lines (taken from \kw{demoReg}) describe the lexem
of the symbols \kw{int} and \kw{real}, using the
previously generated object \kw{lexGen}:
\begin{xple}
  \k{let} lexGen =
  regToLex.new(:DemoSym\_T
    symbol.wrong
    symbol.endOfInput
  )
    (* get generator for lexical analyser (object)*)

  \k{let} digitR = regExpr.range('0' '9')
    (* digit in the range from 0 to 9 *)
  \k{let} digitsR = regExpr.rep(digitR)
    (* repetition of digits, at least one *)

  lexGen.setSymbol(digitsR demoSym.int)
    (* one or more digits form an integer number *)

  \k{let} realR =
    regExpr.seq \k{of}
      digitsR
      regExpr.string(".")
      digitsR
    \k{end}

  lexGen.setSymbol(realR demoSym.real)
    (* a sequence of digits, dot, digits forms a real number *)
\end{xple}

  \item Find strategies for scanning the input. I.\,e.
whether  white\-spaces should be skipped; whether nested comments, which cannot
be described by regular expressions, are allowed; how the scanner recovers
from errors; \dots

 \item Define one or more lexical analysers with the modules \kw{RegToLex} and
\kw{RegExpr}. Note that a lexical analyser does no error-reporting or
error-recovery, but delivers the symbol \kw{wrong} instead. A lexical
analyser is generated by calling the method \kw{generate} which raises
an exception if the definition is erroneous.

 See module \kw{demoReg} for the definition of two lexical analysers. One
lexical analyser skips whitespaces, the other
recognizes the symbols of the language. Note that the generation of an
analyser could take place at compile-time if it would be declared
in the body of the module, i.\,e.
\begin{xple}
  \k{let} analyser = lexGenObject.generate(\dots)
\end{xple}
In this example the analysers are generated at run-time when the function
\kw{demoReg.generator} is called.

\item Plug the lexical analysers
together according to your strategies. In the example this is done
in the module \kw{demoReg} locally in the function \kw{generator}.
The following strategies are implemented: Whitespaces are skipped, no comments
are allowed, errors are reported and error recovery is simply repetition of
skipping and scanning until a valid symbol or end-of-input is found. Note that
there is a problem recognizing end-of-input because the module \kw{Source} only
reports \e{once} that end-of-input is reached. So only one lexical analyser
recognizes end of input but maybe delivers a valid symbol if the previous read
characters formed a correct lexem.

 The full source text of the scanner generator function is listed in
 figure~\ref{scannerf}.

\begin{figure}[hbtp]
\longhrule
\begin{xple}
  \k{let} generator :Scanner\_Generator(DemoSym\_T) =
    \k{fun}(wrong, endOfInput :DemoSym\_T) :Scanner\_Binder(DemoSym\_T)
  \k{begin}
    \k{let} skipBinder :LexicalAnalyzer\_Binder(DemoSym\_T) =
      skipGen.generate(wrong endOfInput)
    \k{let} lexBinder :LexicalAnalyzer\_Binder(DemoSym\_T) =
      lexGen.generate(wrong endOfInput)
    \k{fun}(src :Source\_T err :Scanner\_ErrorReport) :Scanner\_T(DemoSym\_T)
    \k{begin}
      \k{let} lex = lexBinder(src)
      \k{let} skip = skipBinder(src)
      \k{let} local =
      \k{tuple}
        \k{let} \k{var} sym = wrong
        \k{let} \k{var} eof = \k{false}
      \k{end}
      \k{let} nextSym() :\k{Ok} =
      \k{begin}
        \k{if} \k{not}(local.eof) \k{then}
          skip.next()
          local.eof := skip.sym() \k{is} endOfInput
          \k{if} \k{not}(local.eof) \k{then}
            lex.next()
            local.eof := lex.sym() \k{is} endOfInput
          \k{end}
        \k{end}
      \k{end}
      \k{tuple}
        \k{let} sym() :DemoSym\_T = local.sym
        \k{let} string = lex.string
        \k{let} position = lex.position
        \k{let} next() :\k{Ok} =
        \k{begin}
          nextSym()
          \k{while} \k{not}(local.eof) \k{andif} \{lex.sym() \k{is} symbol.wrong\} \k{do}
            err(src.current() src.position())
            \k{try}
              src.next()
            \k{else} (* source.endOfInput *)
              local.eof := \k{true}
            \k{end}
            nextSym()
          \k{end} (* \k{while} *)
          local.sym := \k{if} local.eof \k{then} endOfInput \k{else} lex.sym() \k{end}
          \k{ok}
        \k{end} (* next *)
      \k{end} (* \k{tuple} *)
    \k{end} (* \k{fun} *)
  \k{end} (* generator *)
\end{xple}
\caption{\label{scannerf} Scanner generator function}
\longhrule
\end{figure}

 \item \kw{demoReg.generator} returns a scanner function that needs a concrete
source text and a concrete error report function to become a concrete
scanner fulfilling the definition of delivering a symbol stream. In
\kw{demoReg} this function is declared locally to the function \kw{generator};
it is an unnamed function that is returned as result of the function
\kw{generator}.


\end{enumerate}


In this process there are many possibilities to save something to
reuse it later on:
\begin{itemize}
 \item Save the \e{definition of a lexical analyser} and extend it
 later on to recognize more symbols:
\begin{xple}
    \k{let} lexGen =
      regToLex.new(:Symbol\_T
        symbol.wrong
        symbol.endOfInput
      )

    dynamic.extern(
      writer.file("lexGen")
      dynamic.new(lexGen)
      dynamic.fast)
\end{xple}

 \item Save the \e{generated lexical analyser} to use it in another
 scanner that needs the same functionality:
\begin{xple}
    \k{let} analyser = lexGen.generate(symbol.wrong symbol.endOfInput)

    dynamic.extern(
      writer.file("analyser")
      dynamic.new(analyser)
      dynamic.fast)
\end{xple}

 \item Save the \e{scanner function} to use it in a compiler for
 arbitrary source input.
\begin{xple}
    \k{let} scanner = demoReg.generator(symbol.wrong symbol.endOfInput)

    dynamic.extern(
      writer.file("scanner")
      dynamic.new(scanner)
      dynamic.fast)
\end{xple}

\end{itemize}


\subsection{Keywords}

Keywords require a special handling because they are terminal symbols but
normally also match the regular expression for identifiers. So the lexical
analyser recognizes an identifier and the scanner has to look up a keyword
lexicon whether the identifier found is a keyword.

These steps are taken to handle keywords:
\begin{enumerate}

 \item Generate a keyword lexicon with the module \kw{Lexicon}, e.g. when
defining the symbols of the language. In the example this is done in the module
\kw{demoSym} by this line:
\begin{xple}
  \k{let} keywordLexicon = lexicon.new(nextsym())
  (* 'nextsym()' returns the first symbol that can be used for keywords *)
\end{xple}

 \item Insert the appropriate keywords in the lexicon, e.g. while defining
the grammar of the language. This is done in the module \kw{demoGram}:
\begin{xple}
  \k{let} letKW = lexicon.insert(demoSym.keywordLexicon "let")
  \k{let} inKW = lexicon.insert(demoSym.keywordLexicon "in")
\end{xple}

 Save the keyword lexicon; see \kw{demoGen}:
\begin{xple}
    dynamic.extern(
      writer.file("lexicon")
      dynamic.new(demoSym.keywordLexicon)
      dynamic.fast)
\end{xple}


 \item Define a new layer between scanner and parser which looks up the
keyword lexicon if an identifier is found. Therefore the lexicon has to be
loaded at runtime, i.\,e. in  \kw{demoMain}:
\begin{xple}
    \k{let} keywordLexicon =
      dynamic.be(
        :lexicon.T
        dynamic.intern(reader.file("lexicon") dynamic.fast))

    \k{let} scanner =
    \k{tuple}
      \k{let} sym() :DemoSym\_T =
        \k{if} scanner.sym() \k{is} demoSym.id \k{then}
          \k{try}
            lexicon.lookupSymbol(keywordLexicon)(scanner.string())
          \k{else}
            demoSym.id
          \k{end}
        \k{else}
          scanner.sym()
        \k{end}
        \k{let} string = scanner.string
        \k{let} position = scanner.position
        \k{let} next = scanner.next
    \k{end}
\end{xple}

\end{enumerate}


\subsection{Parser definition}
\label{parser-definition}

Parsers are defined and generated by \kw{Grammar}. Attributed grammars
are used to define actions that are executed while a sentence of the
language is parsed for correctness. Normally, these actions build an
abstract syntax tree.

In the example two modules define the grammar and attached actions:
\kw{DemoGram} and \kw{DemoExp}. Instead of building a syntax tree the
parser binds identifiers to values and evaluates expressions. It also
checks if all used identifiers have been declared and if the types are
compatible.

Follow these instructions to build a parser:
\begin{enumerate}

 \item Define the grammar with attached actions using \kw{Grammar}. Currently
only LL(1)-grammars can be used.

Figure~\ref{grammarf} shows an example for the definition of the grammar
rule \kw{factor} (see section~\ref{grammar} for the complete grammar).
It is taken from \kw{demoExp}. \kw{grammar.alt} describes alternative
clauses; note that all sub-clauses of the alternative clause have to
take inherited attributes und deliver derived attributes of the same
type, what is checked by the \PQ\ compiler. \kw{grammar.seq}
describes sequence clauses, which have an attached action (see
section~\ref{action-definition}). In this case, the action takes an
inherited attribute and the derived attributes of the three parts, and
simply hands through one derived attribute, while the others are
dismissed.

\begin{figure}[hbtp]
\longhrule
\begin{xple}
 (* -- factor ::= '(' exp ')'  $|$  int  $|$  real  $|$  id  *)

  \k{let} factor =
    grammar.alt \k{of}

      grammar.seq3(leftparenS exp rightparenS
        \k{fun}(:bindings.T
              :Source\_Position
            v :Value
              :Source\_Position)
              :Value
          v)

      intS

      realS

      idS

    \k{end}
\end{xple}
\caption{\label{grammarf} Grammar rule \kw{factor}}
\longhrule
\end{figure}

 \item Generate the parser by calling the method \kw{newParser}. While the
generation takes place it is checked whether the grammar is of the correct
(LL(1)-)form.

This is done in \kw{demoGen}:
\begin{xple}
    \k{let} parser = grammar.newParser(demoGram.top)
\end{xple}

 \item The result is a parser function that takes a concrete scanner as
parameter and checks the symbol stream of this scanner for correctness.

\end{enumerate}

In this process there are two possibilities to save something:
\begin{enumerate}
  \item Save the definition of the grammar to extend it later on:
\begin{xple}
    dynamic.extern(
      writer.file("grammar")
      dynamic.new(demoGram.top)
      dynamic.fast)
\end{xple}
  \item Save the generated parser function to use it in a compiler.
\begin{xple}
    dynamic.extern(
      writer.file("parser")
      dynamic.new(parser)
      dynamic.fast)
\end{xple}
\end{enumerate}


\subsection{Action definition}
\label{action-definition}

Actions that for example build a syntax tree are defined along with the
grammar that describes the language. Each rule (terminal or
non-terminal) takes an inherited attribute, performs actions and
delivers a derived attribute. Further information about attribute
grammars can be found, for example, in \cite{WaGo85,ReTe88,ReTe89}.

Figure~\ref{actionf} shows an example taken from \kw{demoExp} that
describes the actions that have to be performed when an identifier is
expected. See Figure~\ref{node} for a graphical representation of the
example. The type of the inherited attribute is \kw{bindings.T}, the
type of the derived attribute is \kw{bindings.Value}. The action has to
transform the inherited to the derived attribute. If an identifier is
found the value it has been bound to is looked up in the (inherited)
bindings. If the identifier has been declared, the associated value is
returned.  Otherwise the value \kw{unknown} is returned. If no
identifier has been found also the value \kw{unknown} is returned.

\begin{figure}[hbt]
\begin{maxipage}\centering
\unitlength=1mm
\begin{picture}(120,50)
\put(40,40){\makebox(0,0)[r]{inherited attribute:}}
\put(40,35){\makebox(0,0)[r]{\kw{bindings}}}
\put(42,45){\vector(0,-1){14}}
\put(78,30){\vector(0,1){15}}
\put(80,40){\makebox(0,0)[l]{derived attribute:}}
\put(80,35){\makebox(0,0)[l]{\kw{value}}}
\put(38,15){\framebox(45,15){}}
\put(60,25){\makebox(0,0)[c]{action: find \kw{id} in \kw{bindings}}}
\put(60,20){\makebox(0,0)[c]{return \kw{value} or \kw{unknown}}}
\put(60,8){\vector(0,1){6}}
\put(82,5){\makebox(0,0)[cc]{\kw{id} (taken from symbol stream)}}
\end{picture}
\caption{\label{node} Node of parse tree for \kw{idS}}
\end{maxipage}
\end{figure}

\begin{figure}[hbtp]
\longhrule
\begin{xple}
  \k{let} idS =
    grammar.terminal(
      :bindings.T  \hfill (* -- type of inherited attribute *)
      :bindings.Value  \hfill (* -- type of derived attribute *)
      demoSym.id  \hfill (* -- symbol: 'identifier' *)
      \k{fun}(b :bindings.T  \hfill (* -- normal action: takes bindings *)
          s :Parser\_ScannerState)  \hfill (* -- and the scanner state *)
        :Bindings\_Value  \hfill (* -- returning a value *)
        \k{try}  \hfill (* -- install exception handler *)
          bindings.lookup(b s.string())  \hfill (* -- lookup identifier in binding *)
        \k{else}  \hfill (* -- not found *)
          (* error report *)
          unknown  \hfill (* -- value unknown *)
        \k{end}
      \k{fun}(b :bindings.T  \hfill (* -- action in error case *)
          s :Parser\_ScannerState)  \hfill (* -- (id expected, but not found) *)
        :Bindings\_Value
      \k{begin}
        (* error report *)
        unknown
      \k{end}
    )
\end{xple}
\caption{\label{actionf} Action definition for \kw{idS}}
\longhrule
\end{figure}


\subsection{Generating the scanner and the parser}

Scanner, parser, and lexicon are generated by \kw{demoGen}. While the
generation process takes place status information is reported. This can
be suppressed by setting flags in \kw{grammar} and \kw{regToLex}.

The generated scanner, parser and lexicon are saved into the files
\kw{scanner}, \kw{parser} and \kw{lexicon}. Strictly speaking,
two \e{functions} are saved, a scanner function that, given a
source and an error report function, returns a scanner, and a parser
function that, given a scanner and a error report/recovery function,
parses a symbol stream.


\subsection{Running the demo}

The main ``compiler-interpreter'' is \kw{demoMain}. It defines the functions
for error reporting and recovery, asks the user for input, opens
the input source, loads the
scanner and parser functions and the lexicon, generates the
concrete scanner, and starts the parser.


\bibliographystyle{florian}
\bibliography{../bib/florian}

\end{document}



