Chapter 1

Front-end

The front-end of the Id compiler is organized as shown in figure 1.1:

The front-end currently consist of the following modules:

• file-parser

• pre-scope-analysis-desugaring

• scope-analysis

• type-checking

• overloading-translation

• lambda-lift

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 DFCS: Dataflow Compiler Substrate Manual[2]. 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 DFCS: Dataflow Compiler Substrate Manual[2]. 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.

1.1 PAGEN

PAGEN is a lexer and LALR parser generator for Common Lisp[1]. Given a definition of a grammar, PAGEN generates the tables used by the table driven lexer and parser. In addition, it also generates the defgrammer and defproduction code for the input grammer. For more details about defgrammer and defproduction, please refer to Chapter 4 of DFCS: Dataflow Compiler Substrate Manual[2]. Both PAGEN itself and the lexer/parser are written in Common Lisp.

Figure 1.1: Id compiler front-end 2

1.1.1 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 .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 grammer of PAGEN’s input language. Terminals will be written as

terminal.

1.1.2 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, e.g.,target-statment.

1.1.3 Lexical Analyzer

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

Target Statement

The 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 (e.g.,whitespace characters) will be mapped to the same internal code in order to compact the scanner tables.

target-statement → $target identifier

Currently the available targets are: lispm and unix.

Let Statements

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

let-statement → $let identifier = regular-expression

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

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 .PAGEN file takes priority.

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

regular-expression  → regular-expression ”| ” regular-expression
regular-expression  → regular-expression regular-expression
regular-expression  → regular-expression ”*”
regular-expression  → regular-expression ”+”
regular-expression  → primary-regular-expression
primary-regular-expression → identifier
primary-regular-expression → set
primary-regular-expression → string
primary-regular-expression → caseless-string
primary-regular-expression → ”~” primary-regular-expression
primary-regular-expression → ”(” primary-regular-expression ”)”

where identifier, set, string, and caseless-string are defined as:

identifier  = alpha {(alpha | digit)}^{∗}
set  = “{” {(set-contents | “\” any)}^{∗} “}”
string  = “"” {(string-contents | “\” any)}^{∗} “"”
caseless-string = “`” {(caseless-string-contents | “\” any)}^{∗} “'”

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

1) An identifier is a meta-variable defined in a $let statement. When used on the RHS, the corresponding expression that the identifier denotes is substituted in its place. For example, if we have

     $let digit = 0123456789

then the regular expression for number is

      digit^{∗}

and is equivalent to

{0123456789}^{∗}

2) A set represents any single character string within the set. An example of a set is

     {abc}

and is equivalent to

     "a"|"b"|"c"

3) A string is any sequence of characters enclosed by double quotes. An example is:

     "aBc"

which only matches the string

     "aBc"

4) A caseless-string on the other hand ignores the case of the letters. So

     `aBc'

matches any one of the following strings:

     "abc"|"ABC"|"Abc"|"aBc"|"abC"|"ABc"|"aBC"|"AbC"

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

Lexical Tokens

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

terminal-statement  → $terminal identifier = regular-expression
pseudo-terminal-statement → $pseudo identifier = regular-expression
discard-statement  → $discard identifier = regular-expression

A 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. Discard tokens are recognized by the lexer and discarded. They are not passed on to the parser. A pseudo-terminal, like a 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 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.

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.

Example

The following is a specification of a lexer for mathematical expressions:

   $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)+

Given the input: offset = 3 + index ,

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

1.1.4 The Parser

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

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: accept and accept-each. The identifier below names a non-terminal in the grammar being defined.

accept-statement  → accept identifier
accept-each-statement → accept-each identifier

The accept form means that the whole file or stream must parse into exactly one parse-tree. The 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.

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. no-node

This defines a 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:

     $no-node primary-regular-expression -> identifier

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.

n-ary

This is an extension to the normal syntax of context-free grammars. For example, the statement

     $n-ary   tuple-expression -> expression $separated-by ","

defines tuple-expression to be any number of 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.

     $n-ary   production-rhs -> production-rhs-primary $separated-by

n-ary-1

The n-ary-1 is a combination of n-ary and no-node. If there is at least one separator token, then it behaves like an n-ary production. If there is no separator, then it behaves like a no-node production. This is what we use for tuple-expressions if we allow a single expression to be considered a degenrate case of tuple-expression:

     $n-ary-1  tuple-expression -> expression $separated-by ","

Example

The following is a grammer specification for a parser, where id and number are as defined in the lexer example:

   $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

Figure 1.2: Parse tree for: def double n = 2 * n;

$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

Given the input file:

def double n = 2 * n;

the parser produces the parse tree shown in figure 1.2

1.1.5 Running Pagen

First, make a grammar definition, in a pagen file (with suffix ".pagen"). Next bring up a LISP process and do the following to load PAGEN:

  (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)

Finally:

    (pagen:pagen file)

will generate a file with the extension ".pagen-output" that contains the tables for the scanner and parser. The functions that perform the shifts and reductions in the parser resides in parser.lisp in the PAGEN directory and need to be added manually. The ".pagen-output" file will include an in-package statement naming the package specified by the package-statement in the PAGEN file.

Using the Parser

The parser should be in a package that uses the Lisp and DFCS package. See the DFCS: Dataflow Compiler Substrate Manual[2] for support manipulating parse trees. Some examples are given in the next section.

1.2 Working with parse tree data structures

Selectors, constructors and mutators for working with parse tree data structures are defined in DFCS and documented in DFCS: Dataflow Compiler Substrate Manual[2]. We will not repeat the definitions here, but will instead give some examples which illustrate use.

1.2.1 Examples

Example 1

In the first example, we will make use of the DFCS functions: block-place, ptnode-tag,

ptnode-child, ptnode-value,  ptnode-children, ptnode-place, ptnode-line, parse-tree-root.

This 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 :identifier and :block-expr/1 are tags associated with productions.

   ;; 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)))

When the above is run on the following input:

def examp x =
  {y = x + 3;
   z = {q = y + 7;
        r = q + 3;
        in

             r};
      in
        w}

we get the following output:

   Block at 2; identifier y
   Block at 2; identifier z
   Block at 3; identifier q
   Block at 3; identifier r

Example 2

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

   (defun pbo-expr (ptnode block-place)
      (grammercase 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)))))

Grammercase 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,

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

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 :identifier) within a grammarcase statement.

Example 3

The definition of pbo-binding can be recoded to use grammarbind:

   (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)

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:

   add-expr -> add-expr "+" mul-expr

and we use it in grammerbind, (ptnode add-expr) is ambiguous. The way to get around it is to explicitly name the components. We can use

   add-expr -> (add-expr op1) "+" (mul-expr op2)

in a grammerbind expression, and use (ptnode op1) to obtain the ptnode for the add-expr on the RHS.

Example 4

The last example here illustrates the use of grammarcasebind which combines the functionality of

grammarcase and grammarbind:
   (defun pbo-expr (ptnode block-place)
      (grammercasebind 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)))))

Multiple prodspec’s can be used as a pattern for 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 (ptnode lb) and (ptnode e).

    (((block-binding lb) -> call (expression e))
     ((block-binding lb) -> (keyword-expression e))
     ((loop-binding lb) -> call (expression e))
     ((loop-binding lb) -> (keyword-expression e)))

1.2.2 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 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 free attribute for a production such as:

   add-expr1 -> add-expr2 "*" mul-expr

is

    free(add-expr1) = free(add-expr2) ∪ free(mul-expr)

Attributes are either synthesized or inherited. An attribute is 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 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 DFCS: Dataflow Compiler Substrate Manual[2]. 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, :ephemeral, :memoized, and :permanent, which are discussed in detail there.

Example 1

The following example defines the rules for 5 attributes for the default production. Default production refers to the special production

      $lhs -> $rhs-component $separated-by)

that PAGEN matches to any production. The attribute ptnode-non-generic-frame is an inherited

attribute, while all the others, ptnode-type, ptnode-defined-type-env, ptnode-idnodes, and

ptnode-nexified-variables, are synthesized attributes.

   (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))

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

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 grammarcasebind (Example 4 of the previous section).

  (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))))

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

Bibliography

[1] Guy L. Steele Jr. Common Lisp, The Language. Second Edition. Digital Press, 1990.

[2] K. R. Traub. A Dataflow Compiler Substrate. Revised by Jamey Hicks and Shail Aditya. CSG Memo 261. MIT Laboratory for Computer Science, Cambridge, MA, January 1991.

[3] K. R. Traub. A Compiler for the MIT Tagged-Token Dataflow Architecture. Technical Report LCS TR-370, MIT Laboratory for Computer Science, Cambridge, MA, August 1986.