Project3: Parse Tree Output Format For SL Programs

This is an explanation of the format of the sample parse trees given along with the assignment.

In theory, the leaf nodes of a parse tree include every input token. In practice, many input tokens are redundant and can be omitted. Similarly, the redundant internal (non-terminal) nodes may also be omitted. Such nodes do not contribute to interpretations or execution. (See the class notes on parsing.)

In SL, we need not have explicit nodes in the parse tree for most delimiters, keywords, and even some non terminals. Terminals (tokens) and non terminals that are typically omitted from the parse tree are:

    (  )  {  }  ;  ,  =
    function call break if else let read write return while
    PARAMLIST PARAMREST STATEMENT ARGLIST ARGREST BINOP UNOP

Here are some explanatory notes, though not comprehensive, on the parse tree output for some of the more confusing situations.

FUNCTION: The parse subtree printed for the non terminal FUNCTION looks something like this (refer to the online examples):
```
    [function
        [ident (function-name)]
        [ident (parameter-1)]
        [ident (parameter-2)]
        [ident (parameter-3)]
        ... for each of the function parameters (0 or more)
        [block ....]
    ]
```
That is, the FUNCTION node has several children. The first is an identifier (the function name). It can be followed by zero or more children that are also identifiers (formal parameter names). The last child is the subtree for a BLOCK (see below).
Note that various delimiter tokens (parentheses and commas) have been eliminated from the parse tree. There is no explicit node in the parse tree for non terminals PARAMLIST and PARAMREST.

BLOCK and STATEMENT: There is no explicit parse tree node for the non-terminal STATEMENT. Instead, the children of a BLOCK are the individual statements themselves. E.g., for:
```
    {let x = y; let z = a;}
```
the parse tree output is:
```
    [block 
        [let 
            [ident (x)]
            [expr [ident (y)]]
        ]
        [let 
            [ident (z)]
            [expr [ident (a)]]
        ]
    ]
```
(Note the omission of all the delimiters from the parse tree.)

CALL: A function call can occur either alone as a statement or as the right hand side of a LET statement. In either case, the subtree rooted at the call-node is printed like this:

    [call 
        [ident (function-name)]
        [expr .... argument expression 1]
        [expr .... argument expression 2]
        [expr .... argument expression 3]
        ... expressions for each of the arguments (0 or more)
    ]

The parse tree for a LET statement whose right hand side is a function call is printed as follows:

    [let
        [ident (variable on lefthand side of assignment)]
        [call 
            [ident (function-name)]
            [expr .... argument expression 1]
            [expr .... argument expression 2]
            [expr .... argument expression 3]
            ... expressions for each of the arguments (0 or more)
        ]
    ]

LET: The right hand side of a LET statement can be an expression or a function call. The parse tree for the latter has already been mentioned above. For the former, the output is:
```
    [let
        [ident (variable on lefthand side of assignment)]
        [expr ....... expression being assigned (see below)]
    ]
```
That is, the two forms are distinguished by whether the second child of the let node is an EXPR or a CALL node.

EXPR: An expression node has one, two, or three children nodes. If it is a simple number, identifier, or a parenthesized expression, it has one child. E.g., for an identifier:
```
    [expr [ident (identifer-name)]]
```
If the expression involves a unary operator, it has two chilren: the operator and the operand expression. E.g., for the expression ~1:
```
    [expr ~
        [expr [number (1)]]
```
If the expression involves a binary operator, it has three children: the operator, and the two operand expressions. E.g., for the expression (* 2 3):
```
    [expr *
        [expr [number (2)]]
        [expr [number (3)]]
    ]
```
Note that the trees for expressions that differ only in the number of enclosing parentheses are identical. For example, the tree printed for both (* 2 3) and ((( (* 2 3) ))) is the same one shown above.

The tree output format for the remaining should be fairly obvious from the given examples.

Ravishankar Mosur

Last modified: Wed Mar 18 10:03:54 EST 1998