Once a production rule has recognized a stream of tokens, its tree building partner constructs a piece of the abstract syntax tree with the instantiated non-terminals and terminals that appear on the right hand side of the production rule. A tree must be constructed according to the arity of its associated operator: fixed, list, or atomic.
For example, in the case of addition, the tree to be constructed will have the associated fixed arity operator plus. This tree will have two descendents, the two arithmetic sub-expressions. To build the tree, we simple indicate the name of the associated operator and the list of descendent trees. The descendents are constructed during recursive phases of parsing. Thus, for addition, we have:
<exp> ::= <exp> "+" <exp> ;
plus (<exp>.1, <exp>.2)
N.B. The ``dotted'' notation allows Metal to assign
different values to the two
To construct a tree with an associated list operator, the name of the operator is followed by a keyword that indicates how to construct the list. The keyword list means construct the list from scratch. The keywords pre and post mean add an element to the beginning or end of an existing list. For example, the first rule below:
<exp_s> ::= <exp> ;
exp_s-list ((<exp>))
<exp_s> ::= <exp_s> ";" <exp> ;
exp_s-post (<exp_s>, <exp>)
tells the parser to construct a tree whose operator is exp_s and whose list of descendents contains only one expression (note the two levels of parentheses to construct a list!). The second rule, when a list of expressions has been recognized, constructs the first part of the list recursively, then adds the last expression to the end of the list. Combined, these rules specify how to parse any list of expressions containing at least one expression and to construct a tree with these expressions as descendents. This corresponds to our abstract syntax specification the an exp_s list may not be empty.
To construct a tree with an associated atomic operator, the name of the operator in the tree building part is followed by the keyword atom and in parenthesis, a lexical variable name in capital letters. This variable is the name assigned within Metal to the atomic value as recognized by the lexer.
Consider the abstract syntax rule for an Exp variable:
variable -> implemented as IDENTIFIER ;
In the corresponding concrete syntax rule, we first tell the parser to recognize a token, which we name %ID. Then, we build a tree with the atomic operator variable. The atomic value for the operator is the %ID token.
<variable> ::= %ID ;
variable-atom (%ID)
N.B. The symbols and keywords of the concrete syntax enable parsing but do not appear in the constructed abstract syntax tree.