% -*- Mode:TeX -*-

\chapter{Front-end}
The front-end of the Id compiler is organized as shown in figure~\ref{fig:front-end-ov}:

\begin{figure}
  \illustration{d1}
  \caption{Id compiler front-end}
  \label{fig:front-end-ov}
\end{figure}

The front-end currently consist of the following modules:
\begin{itemize}
  \item file-parser
  \item pre-scope-analysis-desugaring
  \item scope-analysis  
  \item type-checking
  \item overloading-translation
  \item lambda-lift
\end{itemize}



The first module, file-parse, reads in the source code and performs
lexical analysis and parses the input.  The output from the lexer is a
stream of tokens or lexemes, which is fed into the parser.  The parser
outputs a parse tree, which is the data-structure that the rest of the
front-end modules operate upon.  The file-parser can be called
repeatedly on the same input file to obtain several parse trees if the
input file contains the code for more than one parse trees. The
functions of the other modules in front-end are described in the next
chapter.  

The lexical token and parse tree data structures are discussed in
great detail in Chapter 3 of {\em DFCS: Dataflow Compiler Substrate
Manual}\cite{DFCS}.  Note that parse trees are slightly different from
syntax trees.  They represent the same information in a more compact
form by suppressing syntax tree nodes that do not contain any
additional information.  The differences and motivations for doing
this are again described in Chapter 3 of {\em DFCS: Dataflow Compiler
Substrate Manual}\cite{DFCS}.  In the following sections, we will
first describe the tools used in building the lexer and the parser,
give some examples, and proceed with the description of the rest of
the modules in the Id compiler.

\section{PAGEN}

PAGEN is a lexer and LALR parser generator for Common Lisp\cite{Steele90}.
Given a definition of a grammar, PAGEN generates the tables used by the
table driven lexer and parser.  In addition, it also generates the
\term{defgrammar} and \term{defproduction} code for the input grammar.  For
more details about \term{defgrammar} and \term{defproduction}, please refer
to Chapter 4 of {\em DFCS: Dataflow Compiler Substrate Manual}\cite{DFCS}.
Both PAGEN itself and the lexer/parser are written in Common Lisp.

\subsection{PAGEN Input}

 A PAGEN grammar definition is a Backus-Nauer Format (BNF) definition
with a few extensions for common cases.  The PAGEN input file must
have a filename ending with a \term{.Pagen} suffix.  It consists of a
series of statements that do such things as tell what machines to
generate scanners for, what package the resulting file should be in,
\etc It is interesting to note that the grammar for the PAGEN input
language itself is defined by a PAGEN file, and PAGEN generated the
parser for the PAGEN input language.

In this document, we will give the grammar for PAGEN in BNF.
Appendix {pagen-pagen} contains the PAGEN file for the grammar of PAGEN's input 
language. Terminals will be written as \term{terminal}.

\subsection{Grammar}

 A PAGEN grammar definition consists of a series of statements.  Each
statement starts with a PAGEN keyword, and may be on more than one
line.  Keywords in PAGEN start with a `\$' sign and are
case-insensitive. PAGEN statements can be divided into 2 categories.
Those used for specifying the lexemes, and those used for specifying
the parse trees.  Note however that in PAGEN, both go into the same
input file.  (In contrast, in C/UNIX, LEX handles the former while
YACC the latter.)  We will first describe those used for specifying
lexemes and give some examples, before going on to those used for
specifying parse trees.  In the course of the description,
non-terminals productions of the PAGEN input language will be written
in small-caps fonts, \eg {\sc target-statment}.

\subsection{Lexical Analyzer}

The lexical analyzer, or lexer, is defined by a series of lexical statements.

\subsubsection{Target Statement}

The {\tt target} statement specifies what target system to make lexers
for.  Some targets have different character sets from others, and a
mapping from native character codes to internal character codes will
be made for each target.  In addition, characters that are
indistinguishable in the grammar (\eg whitespace characters) will be
mapped to the same internal code in order to compact the scanner
tables.

\begin{defines}
target-statement \is \term{\$target} \term{identifier} \\
\end{defines}

Currently the available targets are: {\tt lispm} and {\tt unix}.

\subsubsection{Let Statements}

A {\tt let} statement maps an identifier to a regular expression for
use in definition of lexical tokens.  

\begin{defines}
let-statement \is \term{\$let} \term{identifier} = regular-expression \\
\end{defines}

The identifier defined is a meta-variable used in other lexical
statements, i.e. the identifier is a variable of the input to PAGEN.

\subsubsection{Regular Expressions}

Lexical tokens are defined by regular expressions.  The lexer reads
the input stream, finds the longest string that matches one of the
regular expressions, and then returns the corresponding lexical token.
If the longest string matching any regular expression matches more
than one regular expression, the regular expression appearing earliest
in the {\tt .PAGEN} file takes priority.



Regular expression specification in the PAGEN input language is
defined by the following grammar (The following is an ambiguous
grammar that specifies the same language as the unambiguous grammar
used by PAGEN, but is easier to read):

\begin{defines}
regular-expression \is regular-expression "\Or" regular-expression \\
regular-expression \is regular-expression  regular-expression \\
regular-expression \is regular-expression "*" \\
regular-expression \is regular-expression "+" \\
regular-expression \is primary-regular-expression \\
\\
primary-regular-expression \is {\tt identifier} \\
primary-regular-expression \is {\tt set} \\
primary-regular-expression \is {\tt string} \\
primary-regular-expression \is {\tt caseless-string} \\
primary-regular-expression \is "\verb+~+" primary-regular-expression \\
primary-regular-expression \is "(" primary-regular-expression ")" \\
\end{defines}

\noindent
where {\tt identifier}, {\tt set}, {\tt string}, and {\tt caseless-string} are
defined as:

\begin{defines}
\term{identifier} \equals alpha \arbno{(alpha \Or digit)} \\
\term{set} \equals ``\{'' \arbno{(set-contents \Or ``\bslash'' any)} ``\}'' \\
\term{string} \equals ``\verb|"|'' \arbno{(string-contents \Or ``\bslash'' any)} ``\verb|"|'' \\
\term{caseless-string} \equals ``\verb|`|'' \arbno{(caseless-string-contents \Or ``\bslash'' any)} ``\verb|'|'' \\
\end{defines}

As in BNF, ``{\tt *}'' means zero or more occurences of the preceding
regular expression (Kleene recursion), and ``{\tt +}'' means at least
one occurence of the preceding regular expression.  The definitions of
{\sc alpha}, and {\sc digit} are self explanatory.  {\sc Any\/} means
any character in the character set.  {\sc Set-contents} is any
character except right brace (\verb"}") and backslash, unless these
are preceded by the escapes character, backslash.  {\sc
String-contents} is any character except double-quotes and backslash.
Again, these charaters can be included by preceding them with the
backslash escape character.{\sc Caseless-string-contents} is any
character except close-quote and backslash.  As before, a preceding
backslash allows us to include these characters in {\sc
Caseless-string-contents}. A few examples will make the meaning of
these terminals clear.

\smallskip
\noindent
{\bf Examples}

\noindent
1) An \term{identifier} is a meta-variable defined in a \term{\$let} statement.  
When used on the RHS, the corresponding expression that the {\tt identifier}
denotes is substituted in its place. For example, if we have
\begin{example}
     \$let digit = {0123456789}
\end{example}
then the regular expression for number is 
\begin{example}
     ${\tt digit}^*$
\end{example}
and is equivalent to 
\begin{example}
     $\{0123456789\}^*$
\end{example}

\noindent
2) A \term{set} represents any single character string within the set. An 
   example of a \term{set} is 
\begin{verbatim}
     {abc} 
\end{verbatim}
and is equivalent to 
\begin{verbatim}
     "a"|"b"|"c"
\end{verbatim}

\noindent
3) A \term{string} is any sequence of characters enclosed by double
quotes.  An example is:
\begin{verbatim}
     "aBc"
\end{verbatim}
which only matches the string
\begin{verbatim}
     "aBc"
\end{verbatim}


\noindent
4) A \term{caseless-string} on the other hand ignores the case of the letters.
   So
\begin{verbatim}
     `aBc'
\end{verbatim}
matches any one of the following strings:
\begin{verbatim}
     "abc"|"ABC"|"Abc"|"aBc"|"abC"|"ABc"|"aBC"|"AbC"
\end{verbatim}

The productions of {\sc regular-expression} are self-explanatory and
similar to BNF grammar.  The only exception is that involving
\verb+~+.  This is only used for \verb+~+{\tt exp} where {\tt exp}
must match only single characters. \verb+~+{\tt exp} matches any
character other than those in {\tt exp}.  

\subsubsection{Lexical Tokens}

There are three kinds of lexical tokens in Pagen, {\em terminals},
{\em pseudo-terminals}, and {\em discards} and they are defined by
their respective statements:

\begin{defines}
terminal-statement \is \term{\$terminal} \term{identifier} = regular-expression \\
pseudo-terminal-statement \is \term{\$pseudo} \term{identifier} = regular-expression \\
discard-statement \is \term{\$discard} \term{identifier} = regular-expression \\
\end{defines}

A {\em terminal} is a lexical token used by the parser.  No ptnode is
built by the parser for a terminal lexical token.  The string making
up a terminal is not saved.  {\em Discard} tokens are recognized by
the lexer and discarded.  They are not passed on to the parser.  A
{\em pseudo-terminal}, like a {\em terminal}, is used by the parser,
but also becomes a ptnode itself.  During lexical analysis, the string
making up a pseudo-terminal is saved, and subsequently used by the
parser.  For instance, identifiers in an input program are
pseudo-terminals --- the {\tt ptnode-value} of an identifier is the
string of characters that names the identifier.  Pseudo-terminals have
values that are used during the static-analysis phase of compilation.

\smallskip
Before proceeding with the description of those parts of PAGEN
concerned with parsing, we give a complete example of an input file to
PAGEN specifying a lexer.

\subsubsection{Example}
The following is a specification of a lexer for mathematical
expressions:
\begin{verbatim}
   $let            alpha = {ABCDEFGHIJKLMNOPQRSTUVWXYZ}|
                           {abcdefghijklmnopqrstuvwxyz_-}
   $let            digit = {0123456789}

   $terminal       left-parenthesis = "("
   $terminal       right-parenthesis = ")"
   $terminal       plus = "+"
   $terminal       minus = "-"
   $terminal       times = "*"
   $terminal       divide = "/"
   $terminal       semicolon = ";"
   $terminal       equal = "="

   $pseudo         id = alpha (alpha | digit)*
   $pseudo         number = digit+

   $discard        whitespace = (space | newline | tab | return | page)+
\end{verbatim}

\noindent
Given the input: \verb# offset = 3 + index #, 

the above lexer recognizes a pseudo-terminal {\tt id} with value {\tt
offset}, the {\tt terminal '='}, another pseudo-terminal {\tt number}
with value {\tt 3}, followed by another {\tt terminal '+'}, and
finally a last pseudo-terminal {\tt id} with value {\tt index}.


\subsection{The Parser}

The parser is defined by a series of grammar statements.  There are
five kinds of grammar statements:


\subsubsection{Acceptance Statement}

The acceptance statement tells the parser what to return as a parse
tree.  When the parser is called, it will parse until it processes the
accept production, and return the parse tree.  There are two forms: {\em
accept} and {\em accept-each}.  The {\em identifier} below names a
non-terminal in the grammar being defined.

\begin{defines}
accept-statement \is \term{accept} {\em identifier} \\
accept-each-statement \is \term{accept-each} {\em identifier} \\
\end{defines}

The {\em accept} form means that the whole file or stream must parse
into exactly one parse-tree.  The {\em accept-each} form means that the
parser can be called repeatedly until the file is empty.  Each time the
parser is called, it will parse and return one parse-tree.

\subsubsection{significant}
 This defines a normal production.  When the parser reduces this
production it makes a ptnode whose tag is derived from the name of this
production, and leaves the new ptnode on the stack.

\subsubsection{no-node}
 This defines a {\em linear} production, that is, the right hand side
contains only one non-terminal.  It is used for parsing, but it really
conveys no useful information beyond the parser, so no ptnode is made
for this production.  For example:
\begin{verbatim}
     $no-node primary-regular-expression -> identifier
\end{verbatim}
 When the parser reduces the identifier to a primary-regular-expression,
it just leaves the identifier on the stack instead of making a
primary-regular-expression ptnode out of it.

\subsubsection{n-ary}
 This is an extension to the normal syntax of context-free grammars.
For example, the statement
\begin{verbatim}
     $n-ary   tuple-expression -> expression $separated-by ","
\end{verbatim}
 defines {\em tuple-expression} to be any number of {\em expressions}
separated-by commas.  This production takes the place of a number of
simpler productions.  The ptnode formed will have as its children a list
of all the child ptnodes that were separated by the separator tokens.

 To specify a number of non-terminals separated by whitespace, use the
following format.
 \begin{verbatim}
     $n-ary   production-rhs -> production-rhs-primary $separated-by
\end{verbatim}

\subsubsection{n-ary-1}
 The {\tt n-ary-1} is a combination of {\tt n-ary} and {\tt no-node}.
If there is at least one separator token, then it behaves like an {\tt
n-ary} production.  If there is no separator, then it behaves like a
{\tt no-node} production.  This is what we use for {\em
tuple-expressions} if we allow a single expression to be considered a
degenrate case of {\em tuple-expression}:
\begin{verbatim}
     $n-ary-1  tuple-expression -> expression $separated-by ","
\end{verbatim}


\subsubsection{Example}
The following is a grammar specification for a parser, where {\tt id}
and {\tt number} are as defined in the lexer example:

\begin{verbatim}
   $significant	        proc -> "def" id id "=" expr ";

   $no-node             expr -> add-expr

   $no-node             add-expr -> mul-expr
   $significant	        add-expr -> add-expr "+" mul-expr
   $significant	        add-expr -> add-expr "-" mul-expr

   $no-node             mul-expr -> primary-expr
   $significant	        mul-expr -> mul-expr "*" primary-expr
   $significant	        mul-expr -> mul-expr "/" primary-expr

   $no-node             primary-expr -> "(" expr ")"
   $no-node             primary-expr -> block-expr
   $no-node             primary-expr -> id
   $no-node             primary-expr -> number

   $significant         block-expr -> "{" blist in expr "}"

   $n-ary               blist -> binding $separated-by ";"

   $significant         binding ->
   $significant	        binding -> id "=" expr

   $accept              proc
\end{verbatim}

\noindent
Given the input file:

\begin{verbatim}
  def double n = 2 * n;
\end{verbatim}

\noindent
the parser produces the parse tree shown in figure~\ref{fig:def-double-parse-tree}

\begin{figure}
  \illustration{d2}
  \caption{Parse tree for: def double n = 2 * n;}
  \label{fig:def-double-parse-tree}
\end{figure}

\subsection{Running Pagen}

First, make a grammar definition, in a pagen file (with suffix {\tt
".pagen"}).  Next bring up a LISP process and do the following to load
PAGEN:
\begin{verbatim}
  (load "/df/id-world/utilities/011/loop")
  (load "/df/id-world/utilities/011/out-file-system")
  (load "/df/id-world/utilities/011/defprogram")
  (load "/df/id-world/csg/registry/021/registry")
  (make-program :pagen :noconfirm)
\end{verbatim}

\noindent
Finally:
\begin{example}
    (pagen:pagen \i{file})
\end{example}
 will generate a file with the extension {\tt ".pagen-output"} that
contains the tables for the scanner and parser. The functions that
perform the shifts and reductions in the parser resides in {\tt
parser.lisp} in the PAGEN directory and need to be added manually.
The {\tt ".pagen-output"} file will include an {\tt in-package}
statement naming the package specified by the package-statement in the
PAGEN file.

\subsubsection{Using the Parser}

 The parser should be in a package that {\em uses} the Lisp and DFCS
package.  See the {\em DFCS: Dataflow Compiler Substrate Manual}\cite{DFCS}
for support manipulating parse trees.  Some examples are given in the next
section.


\section{Working with parse tree data structures}
 Selectors, constructors and mutators for working with parse tree data
structures are defined in DFCS and documented in {\em DFCS: Dataflow
Compiler Substrate Manual}\cite{DFCS}.  We will not repeat the
definitions here, but will instead give some examples which illustrate
use.

\subsection{Examples}
\subsubsection{Example 1}
In the first example, we make use of the DFCS functions:
\verb+ block-place, ptnode-tag, ptnode-child, ptnode-value,
 ptnode-children, ptnode-place, ptnode-line, parse-tree-root+.
The example operates on a block-structured language and prints out
the place where each variable binding occurs.  The place in this case
refers to the line number of the beginning of the enclosing block.
Both {\tt :identifier} and {\tt :block-expr/1} are tags associated
with productions.

\begin{verbatim}
   ;; top level function.
   (defun print-binding-occurences (parse-tree)
      (pbo-expr (parse-tree-root parse-tree) nil))


   ;; pbo-expr recrusively walks down a parse tree from the root.
   ;; If the current node is an :identifier, we reach a base case.
   ;;   Nothing is done in the base case as there no binding takes place.
   ;; If the current node is a :block-expr/1, the 0th child of the 
   ;;   node is a subtree of bindings, while the 1st child is a subtree
   ;;   containing the body of the block.  pho-expr calls pbo-blist to
   ;;   print out the binding-occurences and recursively calls itself on
   ;;   the body of the block.
   ;; For any other internal ptnodes, pbo-expr calls itself recursively
   ;;   on every subtree.
   (defun pbo-expr (ptnode block-place)
      (case (ptnode-tag ptnode)
        (:identifier
         nil)
        (:block-expr/1
         (let ((blist (ptnode-child 0 ptnode))
               (in-expr (ptnode-child 1 ptnode)))
            ;; process bindings
            (pbo-blist blist (ptnode-place ptnode))
            ;; process "in" expr
            (pbo-expr in-expr block-place)))
        (otherwise
         (dolist (child (ptnode-children ptnode))
            (pbo-expr child block-place)))))	


   ;; blist is a list of bindings.  
   ;; block-place is the 'place' where these bindings occur.
   ;; pbo-blist prints out the information that the bindings in
   ;;   in blist occurs at block-place.
   (defun pbo-blist (blist block-place)
      (dolist (binding (ptnode-children blist))
         (pbo-binding binding block-place)))

   ;; binding is a the ptnode of a single binding.
   ;; block-place is the 'place' where the binding occurs.
   ;; pbo-binding prints out the information that the binding
   ;;   occurs at block-place.
   (defun pho-binding (binding block-place)
      (let ((lhs (ptnode-child 0 binding))
            (rhs (ptnode-child 1 binding)))
         ;; print this identifier
         (format t "Block at ~a; identifier ~a~%"
                 (ptnode-line block-place)
                 (ptnode-value lhs))
         ;; process the rhs
         (pbo-expr rhs block-place)))
\end{verbatim}

\noindent
When the above is run on the following input:
\begin{verbatim}
   def examp x =
     {y = x + 3;
      z = {q = y + 7;
           r = q + 3;
           in
             r};
      in
        w}
\end{verbatim}
we get the output:
\begin{verbatim}
   Block at 2; identifier y
   Block at 2; identifier z
   Block at 3; identifier q
   Block at 3; identifier r
\end{verbatim}

\subsubsection{Example 2}

The definition of {\tt pbo-expr} can be recoded as follows using {\tt
grammarcase}.  {\tt Grammarcase},{\tt grammarbind}, and {\tt
gramarcasebind} used in this and the following example are described
in chaper 4 of DFCS.  

\begin{verbatim}
   (defun pbo-expr (ptnode block-place)
      (grammarcase ptnode
        (:identifier
         nil)

        ((block-expr -> "{" blist in expr "}")
         (let ((blist (ptnode-child 0 ptnode))
               (in-expr (ptnode-child 1 ptnode)))
            ;; process bindings
            (pbo-blist blist (ptnode-place ptnode))
            ;; process "in" expr
            (pbo-expr in-expr block-place)))

        (otherwise
         (dolist (child (ptnode-children ptnode))
            (pbo-expr child block-place)))))	

\end{verbatim}
{\tt Grammarcase} allows us to use the prodspec instead of the
tag.  It also takes care of taking the tag of ptnode.  A prodspec is a
representation of a production.  In the above example, 
\begin{verbatim}
     block-expr -> "{" blist in expr "}"
\end{verbatim} 
is a prodspec.  It is possible to give a list of prodspec in place of
one prodspec if the same code is excuted for all of them.  Note that
we can still use keyword tags (such as {\tt :identifier}) within a
grammarcase statement.


\subsubsection{Example 3}
The definition of {\tt pbo-binding} can be recoded to use {\tt grammarbind}:

\begin{verbatim}
   (defun pho-binding (in-binding block-place)
      (grammarbind (binding -> id "=" expr)
                   in-binding
         ;; print this identifier
         (format t "Block at ~a; identifier ~a~%"
                 (ptnode-line block-place)
                 (ptnode-value (ptnode id))) ; (ptnode id) returns the child
                                             ; of in-binding corresponding to id.
                             
         ;; process the rhs
         (pbo-expr (ptnode expr) block-place))) ; (ptnode expr) is similar to
                                                ; (ptnode id)

\end{verbatim}

In cases where a production has repeated occurence of the same 
non-terminal, we need to explicitly name
prodspec components.  For instance, if we have the following production:
\begin{verbatim}
   add-expr -> add-expr "+" mul-expr
\end{verbatim}

\noindent
and we use it in {\tt grammarbind}, \verb+(ptnode add-expr)+ is ambiguous.
The way to get around it is to explicitly name the components.  We can use
\begin{verbatim}
   add-expr -> (add-expr op1) "+" (mul-expr op2)
\end{verbatim}
in a {\tt grammarbind} expression, and use {\tt (ptnode op1)} to obtain the
ptnode for the add-expr on the RHS.

\subsubsection{Example 4}
The last example here illustrates the use of {\tt grammarcasebind} which
combines the functionality of {\tt grammarcase} and {\tt grammarbind}:
\begin{verbatim}
   (defun pbo-expr (ptnode block-place)
      (grammarcasebind ptnode
        (:identifier
         nil)

        ((block-expr -> "{" blist in expr "}")
         ;; process bindings
         (pbo-blist (ptnode blist) 
                    (ptnode-place ptnode))
         ;; process "in" expr
         (pbo-expr (ptnode expr) 
                   block-place))

        (otherwise
         (dolist (child (ptnode-children ptnode))
            (pbo-expr child block-place)))))	

\end{verbatim}

Multiple prodspec's can be used as a pattern for {\tt grammarcasebind} 
matching.  Note however that they must have the same number of ptnodes on the
RHS, and syntactically identical names must be used for corresponding 
components.  Explicit naming as explained in the previous example can be used
obtain identical names.  For instance, the following list can be used as
multiple prodspec.  Access to ptnode will be through {\tt (ptnode lb)}
and {\tt (ptnode e)}.

\begin{verbatim}
    (((block-binding lb) -> call (expression e))
     ((block-binding lb) -> (keyword-expression e))
     ((loop-binding lb) -> call (expression e))
     ((loop-binding lb) -> (keyword-expression e)))
\end{verbatim}

\subsection{Attribute Grammar}

 In the course of working with parse trees, we often want to associate
information with each ptnode. Attribute grammar provides a simple way
of doing this when the information can be computed in a structured way
from other ptnodes of the production.  With an attribute grammar, we
associate with each production rules for computing an attribute of the
ptnodes related by the production.  For example, we can associate an
attribute {\em free} with each ptnode that denodes the free variables
in the subtree of the syntax tree rooted at that ptnode.  Then the
rule for computing the {\em free} attribute for a production such as:
\begin{verbatim}
   add-expr1 -> add-expr2 "*" mul-expr
\end{verbatim}
is
\begin{example}
   {\em free}(add-expr1) = {\em free}(add-expr2) $\cup$ {\em free}(mul-expr)
\end{example}

Attributes are either {\em synthesized} or {\em inherited}.  An
attribute is {\em synthesized} if all definitions of the attribute are
for LHS of productions.  In term of the parse tree, the attribute of a
ptnode is calculated from the attributes of the children of that
ptnode.  One the other hand, an attribute is {\em inherited} if all
definitions of the attribute are for RHS of productions.  The
attribute of a ptnode in a parse tree is, in this case, calculated
from the attributes of its parent, hence the name inherited.

The tools for working with attribute grammars are defined in DFCS and
documented in Chapter 4 of {\em DFCS: Dataflow Compiler Substrate
Manual}\cite{DFCS}.  Again as in previous sections, we will only give
examples of their use.  The reader should refer to the DFCS document
for details.  In particular, the reader should look at the 3 different
storage methods for attributes, {\tt :ephemeral, :memoized, and
:permanent}, which are discussed in detail there.

\subsubsection{Example 1}
The following example defines the rules for 5 attributes for the
default production.  Default production refers to the special
production 
\begin{verbatim}
      $lhs -> $rhs-component $separated-by)
\end{verbatim}
that PAGEN matches to any production. The attribute {\tt
ptnode-non-generic-frame} is an inherited attribute, while all the
others, {\tt ptnode-type}, {\tt ptnode-defined-type-env}, {\tt
ptnode-idnodes}, and {\tt ptnode-nexified-variables}, are synthesized
attributes.

\begin{verbatim}
   (defattributes ($lhs -> $rhs-component $separated-by)
      ((ptnode-type $lhs)       ; defining attribute ptnode-type for $lhs
       (ptnode-type (ptnode $rhs-component 0)))  
                                ; <ptnode $rhs-component 0> returns the
                                ; 0th ptnode on the RHS.

      ((ptnode-defined-type-env $lhs) 
       nil)

      ((ptnode-idnodes $lhs) 
       nil)

      ((ptnode-non-generic-frame $rhs-component i)
                                ; defining attribute ptnode-non-generic-frame
                                ; for ith component of the RHS
       (ptnode-non-generic-frame (ptnode $rhs))
                                ; <ptnode $rhs> returns the ptnode on the RHS.

      ((ptnode-nexified-varibales $lhs) 
       nil))
\end{verbatim}

Our attribute system computes attributes in a lazy fashion, and can
handle any attribute not defined circularly.  In addition, it also
invalidates {\tt :ephemeral} attributes when the structure of the
parse tree changes in such a way as to affect the value of that
attribute.

\subsubsection{Example 2}
We can also define rules that apply to a specific set of productions.
In this case, all the productions have to have the same number of
children.  In addition, the LHS and RHS must be renamed in the same
way as when we use multiple prodspec's in {\tt grammarcasebind}
(Example 4 of the previous section).

\begin{verbatim}
  (defattributes (((block-binding lb) -> call (expression e))
                  ((block-binding lb) -> (keyword-expression e))
                  ((loop-binding lb) -> call (expression e))
                  ((loop-binding lb) -> (keyword-expression e)))

     ((ptnode-idnodes lb)
      (let ((lb-node (ptnode lb)))
        (make-idnode-list nil (ptnode-free lb-node) lb-node))))
\end{verbatim}

\bigskip
This concludes the description of PAGEN and the attribute grammar tools in
DFCS.  The next chapter will describe the other front-end modules.





