ATTRIBUTE GRAMMAR FOR PL/0
                                     --------------------------


               This attribute grammar contructs an environment and a  syntax  tree  for  a
          PL/0  program.  The  environment  corresponds  to a symbol table of records with
          fields for identifier name and type. Types are themselves a variant  record-like
          structure  with three discriminants: 1) const with a value field, 2) var, and 3)
          procedure with fields to represent the local environment and syntax tree of that
          procedure.  There is no type checking in this attribute grammar, so the environ-
          ment is not actually referenced.


          Attributes
          ----------

          (1)  env - environment as a list of declared  variables  with  their  associated
               type (e.g. const (value), var, procedure (env, tree))

          (2)  tree - syntax tree representation of program and procedures

          (3)  lexeme - the lexeme of a token

          (4)  value - the value of a numeric constant


          Functions
          ---------

          (1)  list - return a list containing its argument

          (2)  append - accept a set of arguments and return a list of those arguments

          (3)  tuple - accept a set of arguments and return a tuple of those arguments

          (4)  tree - accept a set of arguments and return a tree with the first  argument
               as the root and the remaining arguments as children


          Grammar
          -------

          <program> ::= <block> .
              <program> . tree <-- <block> . tree

          <block> ::= <const-decl> <var-decl> <proc-decl> <statement>
              <block> . env <--
                append (<const-decl> . env, <var-decl> . env, <proc-decl> . env)
              <statement> . env <-- <block> . env
              <block> . tree <-- <statement> . tree

          <const-decl> ::= const <const-assignment-list> ;
              <const-decl> . env <-- <const-assignment-list> . env

            | e
              <const-decl> . env <-- nil








                                                 2


          <const-assignment-list> ::= <ident> = <number>
              <const-assignment-list> . env <--
                list (tuple (<ident> . lexeme, const (<number> . value)))

            | <const-assignment-list>[1] , <ident> = <number>
              <const-assignment-list> . env <--
                append (<const-assignment-list>[1] . env,
                  list (tuple (<ident> . lexeme, const (<number> . value))))

          <var-decl> ::= var <ident-list> ;
              <var-decl> . env <-- <ident-list> . env

            | e
              <var-decl> . env <-- nil

          <ident-list> ::= <ident>
              <ident-list> . env <-- list (tuple (<ident> . lexeme, var))

            | <ident-list>[1] , <ident>
              <ident-list> . env <-- append (<ident-list>[1] . env,
                list (tuple (<ident> . lexeme, var)))

          <proc-decl> ::= <proc-decl>[1] procedure <ident> ; <block> ;
              <proc-decl> . env <--
                append (<proc-decl>[1] . env,
                  list (tuple (<ident> . lexeme,
                  procedure (<block> . env, <block> . tree))))

            | e
              <proc-decl> . env <-- nil

          <statement> ::= <ident> := <expression>
              <expression> . env <-- <statement> . env
              <statement> . tree <--
                tree (":=", <ident> . lexeme, <expression> . tree)

            | call <ident>
              <statement> . tree <-- tree ("call", <ident> . lexeme)

            | begin <statement-list> end
              <statement-list> . env <-- <statement> . env
              <statement> . tree <-- <statement-list> . tree

            | if <condition> then <statement>[1]
              <condition> . env <-- <statement> . env
              <statement>[1] . env <-- <statement> . env
              <statement> . tree <--
                tree ("if-then", <condition> . tree, <statement>[1] . tree)

            | while <condition> do <statement>[1]
              <condition> . env <-- <statement> . env
              <statement>[1] . env <-- <statement> . env
              <statement> . tree <--
                tree ("while-do", <condition> . tree, <statement>[1] . tree)

            | e
              <statement> . tree <-- nil






                                                 3


          <statement-list> ::= <statement>
              <statement> . env <-- <statement-list> . env
              <statement-list> . tree <-- <statement> . tree

            | <statement-list>[1] ; <statement>
              <statement-list>[1] . env <-- <statement-list> . env
              <statement> . env <-- <statement-list> . env
              <statement-list> . tree <--
                tree (";", <statement-list>[1] . tree, <statement> . tree)

          <condition> ::= odd <expression>
              <expression> . env <-- <condition> . env
              <condition> . tree <-- tree ("odd", <expression> . tree)

            | <expression>[1] <relation> <expression>[2]
              <expression>[1] . env <-- <condition> . env
              <expression>[2] . env <-- <condition> . env
              <condition> . tree <-- tree (<relation> . lexeme,
                <expression>[1] . tree, <expression>[2] . tree)

          <relation> ::= = | <> | < | > | <= | >=

          <expression> ::= <term>
              <term> . env <-- <expression> . env
              <expression> . tree <-- <term> . tree

            | <adding-operator> <term>
              <term> . env <-- <expression> . env
              <expression> . tree <--
                tree (<adding-operator> . lexeme, <term> . tree)

            | <expression>[1] <adding-operator> <term>
              <expression>[1] . env <-- <expression> . env
              <term> . env <-- <expression> . env
              <expression> . tree <-- tree (<adding-operator> . lexeme,
                <expression>[1] . tree, <term> . tree)

          <adding-operator> ::= + | -

          <term> ::= <factor>
              <factor> . env <-- <term> . env
              <term> . tree <-- <factor> . tree

            | <term>[1] <multiplying-operator> <factor>
              <term>[1] . env <-- <term> . env
              <factor> . env <-- <term> . env
              <term> . tree <-- tree (<multiplying-operator> . lexeme,
                <term>[1] . tree, <factor> . tree)

          <multiplying-operator> ::= * | /

          <factor> ::= <ident>
              <factor> . tree <-- tree (<ident> . lexeme)

            | <number>
              <factor> . tree <-- tree (<number> . lexeme)

            | ( <expression> )
              <expression> . env <-- <factor> . env
              <factor> . tree <-- <expression> . tree