MuLE/SLam Warm-up Lab[1]
SLam, BNF Grammars, Parsing and
Parse Trees[2]
After completing this lab, one should feel more comfortable
with both the language scheme and the MuLE architecture as well as an
understanding of how parsing works in MuLE's languages.
In this lab, we begin to
experiment with the design and implementation of various programming
languages. The software tool being
used is MuLE, a multiple language
environment. MuLE provides four
interpreters (SLam, SPoc, SOOP, and SLic) that share a common architecture but
represent different language paradigms.
One objective of this lab is to master the general syntax of the system
only once and then use it for all four languages! This lab will introduce the simple functional (applicative)
language, SLam. SLam is implemented as
an interpreter. When we talk about an
interpreter, we say it "acts as an abstract machine that reads a
statement, executes the statement, reads the next statement, executes the
statement, and so forth ... and so on ... in a cycle that continues until the
interpreter is shut down." But, ...
it's not quite that simple.
SLam has two logical components: a
parser and an execute routine. The parser takes an expression and creates a
corresponding parse tree. The execute routine traverses the parse tree
to evaluate the expression. In doing
so, the execute routine uses and
updates the environment. The environment
is the state of the program, i.e. all of the variable bindings made during
interpreter execution. In this lab, our
goal is to explore the relationship of SLam's language design to the
implementation of the parser and the creation of the parse tree.
SLaM is designed to be a simple functional (applicative)
language that uses a prefix format in its expressions. The SLam grammar is defined using BNF
production rules.
|
<slam> |
::= |
<slam_command> |
|
<slam_command> |
::= |
clear |
|
<slam_command> |
::= |
help |
|
<slam_command> |
::= |
list |
|
<slam_command> |
::= |
<slam_stmt_list> |
|
<slam_stmt_list> |
::= |
|
|
<slam_stmt_list> |
::= |
<slam_stmt><slam_stmt_list> |
|
<slam_stmt> |
::= |
(proc
<formals> <slam_stmt>) |
|
<slam_stmt> |
::= |
(assign
<id> <slam_stmt>) |
|
<slam_stmt> |
::= |
(if
<boolean_expr> then <slam_stmt> else <slam_stmt>) |
|
<slam_stmt> |
::= |
(<id> <slam_stmt_list>) |
|
<slam_stmt> |
::= |
<expr> |
|
<formals> |
::= |
|
|
<formals> |
::= |
(<id_list>) |
|
<id_list> |
::= |
|
|
<id_list> |
::= |
<id>
<id_list> |
|
<expr> |
::= |
<boolean_expr> |
|
<expr> |
::= |
<arith_expr> |
|
<expr> |
::= |
<number> |
|
<expr> |
::= |
<id> |
|
<boolean_expr> |
::= |
(<bool_op>
<slam_stmt> <slam_stmt>) |
|
<bool_op> |
::= |
=
| > | < | != | and | or | not |
|
<arith_expr> |
::= |
(<arith_op>
<slam_stmt> <slam_stmt>) |
|
<arith_op> |
::= |
+
| - | * | / |
Part 1. In-lab Exercises (xx pts):
Complete and hand-in before picking up the Lab X assignment
sheet.
1. (a) Note that the nonterminal <slam_command> may be
substituted by any of the following:
ß
list -- instructs the interpreter to print the current
global environment
ß
help -- instructs the interpreter to display the SLam grammar
ß
clear --
instructs the interpreter to delete the current global environment
ß
<slam_stmt_list>
Are the
meta-commands list, help, and clear terminals
or nonterminals?
(b) <slam_stmt_list> is defined "inductively". Explain what this means.
(c) List the terminal symbols in SLam.
(d) Two nonterminals are left undefined in the BNF
productions given for SLam. What are
they and why do you think they were omitted from the table?
(e) A <slam-stmt> is an
acceptable statement/expression in the language. List below the kinds of SLam statements/expressions.
(f) Show a derivation of the function
expression (assign x (+
2 3))
(g) Are the parentheses necessary in the function derived in part (f) above? Explain your answer.
SLam's
parser performs its task by using the production rules of the defined
grammar. The parser receives a scanned
expression. If the expression can be
derived from the grammar, the parser returns a parse tree of the expression. For example, we might expect that when the
parser receives
(assign x (+ 2 3))
the parser
might return a data structure representing the tree
assign
/ \
/ \
/ \
x +
/ \
/ \
/ \
2 3
Before we
take a look at how the parser performs such a task, it would be helpful to
first consider how the data structure for a parse tree is constructed. In SLam, a parse tree is constructed with
nested records. These records are similar to Pascal's
variant records, C's structs, or objects of a class in C++ or Java. Since SLam is implemented in Scheme, which
does not have a pre-defined record data structure, we extend the Scheme
language using define-macro.
2. (a) From <unique at each installation>, copy the
LabX folder to the desktop of your machine.
The LabX folder contains a file named utilities.s Start DrScheme and open the utilities.s
file. Near the beginning of the file,
the documentation indicates that some of the macros in this file are taken
from Essentials of Programming
Languages by Friedman, Wand and Haynes, MIT Press, 1992. This lab uses some materials from the same
book.
(b) Use the menu Edit|Find to locate
the macro definition that defines a record data structure. It begins
(define-macro define-record
...
Based on the macro definition, what
parameters (arguments) do you think are expected when define-record is used
to define a record type?
(c) Scroll to the bottom of the utilities.s file.
List the record types defined here.
(d) Beneath the record types that are already
defined, we'll add our own record type for a tree record structure. We assume a binary tree, defined in BNF as
<tree> ::=
<number> | (<symbol> <tree> <tree>)
Enter the following:
(define-record node
(symbol left right))
Execute.
(Only to confirm an acceptable definition nothing is output to the
screen.) When a record structure is
defined, the macro works behind the scenes to provide some additional
capabilities:
…
make-name
-- a procedure that takes n
arguments and creates a record of type name with n fields.
…
name? a predicate that returns #t when
passed a record of type name.
…
name
-> fieldi -- for 1 <= i <=n, a function that returns the value of the
indicated field.
(e) Now that the node record type has been defined, we can create a tree using node records. Enter the following in the interactions window:
(define atree (make-node 'foo
(make-node 'bar 1 2) 3))
(f) Make a sketch the tree just created.
(g) Now, test it.
In the interactions window, try each of the following and record the
results.
(node? atree)
(node->symbol atree)
(node->right atree)
(node->left atree)
(node->symbol (node->left
atree))
3. (a)
In a parse tree, a distinct record type may be used to
represent each alternative of a BNF production rule. Looking back at the BNF rule for a tree (see 2 (d) above), it is
apparent that we require a second record type to distinguish a tree consisting
of a single leaf.
(b) Enter in the definitions window (i.e. into your newly modified utilities.s):
(define-record leaf (number))
(c)We now have trees that are unions of interior node records and leaf records. When traversing a tree, it is convenient to have some way to branch on the type of record and to fetch values from the fields of that kind of record. Fortunately, utilities.s includes a macro named variant-case that allows us to do just that. The variant-case works in a similar as a scheme cond. To illustrate, enter in the definitions window to modify utilities.s the following:
(define leaf-sum
(lambda (tree)
(variant-case tree
(leaf (number) number)
(node (left right)
(+ (leaf-sum left) (leaf-sum right)))
(else (error "leaf-sum: Invalid tree" tree)))))
(d) Now, define in the interactions window three trees using interior
nodes and leafs.
(define atree (make-node 'a (make-leaf 2) (make-leaf 3)))
(define btree (make-node 'b (make-leaf -1) atree))
(define ctree (make-node 'c btree (make-leaf 4)))
Make a sketch of each tree,
properly labeled.
Execute and then
test with the following. Record the
results.
(leaf-sum atree)
(leaf-sum btree)
(leaf-sum ctree)
4. Save your code as utilities-tree.s on a disk or your account.
Part II. Lab X Assignment (xx pts)
Due: yy
1. Use variant-case to write
a function named max-leaf that
receives a binary tree of numbers, having at least one interior node, and
returns the maximum leaf value. Attach
a printout of your defined function and examples of tests with two different
trees.
2. (a) Start DrScheme and open the file named utilities-parse.s (from the LabX folder <installation
dependent> ). Execute. This file is a composite of the utilities.s file (used previously) and the SLam
parser. Explore the use of the parser
by entering the following.
(parse
'(assign x (+ 2 3)) )
The output should look like this:
#(struct:sbind
x
#(struct:apply
#(struct:prim-proc +)
(#(struct:num 2) #(struct:num 3)))
untyped)
The parser has examined the arguments: the expression '(assign x (+ 2 3)) . The expression was found to be acceptable in the grammar of the language, so the parser created and returned a nested record structure representing the parse tree of the expression.
#(struct:sbind a record representing the binding
of an expression to an identifier
#(struct:apply a record representing the application of
a function
#(struct:prim-proc a record containing a primary operator
#(struct:num a leaf record containing a number
The tree would look something like this
BIND
/ \
/ \
x APPLY
/ | \
/ | \
+ 2 3
(b) Enter each of the following parse expressions
and record the results. For each, make
a sketch of the parse tree.
(parse
'(assign x 5) )
(parse
'(help) )
(parse
'(proc (x y) (< x y)) )
(c) Using the BNF grammar for SLam, write a call to
parse a statement that increments
x
if x is less
than 10 (otherwise, leaves x unchanged). Attach a printout of your parse expression
and the parse tree that is returned along with a sketch of the parse tree.
[For example, if you were to write a call to parse for a statement that assigns
1 to a, the call would look like
(parse '(assign a 1))
.]