An Imperative Interpreter written with a Functional Interpreter
ART-C Interpreter Description
You must write an interpreter for a toy imperative language named ART-C (which is shorthand for Another Rhetorical Toy-C). The interpreter must be written in Scheme and must use none of the imperative features of Scheme. A code-base is provided that you must build on. This code-base consists of several files that must be downloaded and then referenced by the file that you must create. These files are available at
artc-ast.rkt artc-semantic-domain.rkt utils.rkt
You should download these files into the same folder and then create another file in that folder named artc.rkt . The first lines of
artc.rkt must be as shown below. These lines are similar to the import statements you will find in most Java programs and grant access
to the functions contained in the code-base.
(require “./artc-ast.rkt”)
(require “./utils.rkt”)
(require “./artc-semantic-domain.rkt”)
Syntax
ART-C is an imperative language that supports only the boolean and int data types along with basic arithmetic and logical operators. There are no function calls, arrays, or complex data types. While strings can occur in an ART-C program in the context of an sprint, the string data type is not supported.
The syntax of ART-C is given by the implied EBNF grammar below where the last three productions are informally defined and the starting non-terminal is
::= {
Semantics
This section informally defines the semantics of each program element. Since this specification is not formal, it is likely to be ambiguous and/or incomplete but should nonetheless convey a reasonable specification of the expected meaning of each program element. Seek clarification of any part of the specification that you believe is unclear.
PROGRAM
Execution of a program means execute the body in the context of the state imposed by the DECLARATIONS . The meaning of the program is the state that results from executing the body.
BLOCK
Executing a block means execute each statement in the body of the block in the context of the state imposed by the DECLARATIONS . Each STATEMENT is executed in the order it occurs and the meaning of the BLOCK is the state produced by
the final statement in the BLOCK . If there is no final statement in the block (i.e. the block has no statements), the meaning of the
block is the state in which the block was executed.
CS 421 : Programming Languages ý Kenny Hunt
)tkr.slitu/esab-edoc( )tkr.niamod-citnames-ctra/esab-edoc(
)tkr.tsa-ctra/esab-edoc(
DECLARATIONS
Executing a DECLARATIONS means execute each DECLARATION in the order that they occur. The meaning of the DECLARATIONS is the state that results after execution of the last DECLARATION .
DECLARATION
The meaning of a DECLARATION is the state that results from adding the declared variable to the state and assigning it a value that denotes the notion of not initialized. Note, that the scope of a single declaration extends only to the BODY of the associated BLOCK or PROGRAM .
ASSIGN
Binds the value the expression to the named variable. The type of the variable and the type of the expression must be identical; otherwise there is an error.
IF
The meaning is the meaning of the first statement if the conditional expression evaluates to true. Otherwise, the meaning is the meaning of the second statement if it is present. Otherwise, the meaning is the state in which the IF is executed.
WHILE
Execution of a while first evaluates the expression and then executes the associated statement if the expression is true after which this process repeats.
EXPRESSION
Evaluation of an expression produces the value of the expression.
BINARY
A binary expression represents either a logical or arithmetic operation. See Figure 1 for details. Each operator is defined as that of the corresponding Java operator. Pay attention to overflow and error conditions.
UNARY
There are two unary expressions. See Figure 1 for details. Each operator is defined as that of the corresponding Java operator.
SPRINT
Prints the string (this is for labeling an output) followed by the value of the expression to the interpreter window and then prints a newline. If the expression is not provided, this function will print the state (a list of all variables that are presently in scope and their corresponding values).
Operator Arity Meaning Operand Type Expression Type
+
2
addition
int
int
–
2
subtraction
int
int
*
2
multiplication
int
int
/
2
division
int
int
@
2
exponentiation
int
int
?
2
remainder
int
int
< 2 less than intboolean>
2
greater than
int
boolean
=
2
equal to
int
boolean
<= 2 less than or equal to intboolean>=
2
greater than or equal to
int
boolean
&
2
logical and
boolean
boolean
%
2
logical or
boolean
boolean
~
1
logical negation
boolean
boolean
–
1
arithmetic negation
int
int
Figure 1. Operators
Validity Function (30 Points)
You must write a function (is-program-valid? pgm) that accepts a program and returns true (#t) if the program is valid and false (#f) otherwise. The intent of this function is to ensure that the program is strongly and statically typed. Note that the input program is assumed to be syntactically correct. Each of the following rules must be checked such that if any one of them is violated, the program is not valid.
1. Reserved words are not valid variable names. For example, variable names ¡°true¡±, ¡°while¡± and ¡°int¡± are not allowed. 2. Block scoping rules are enforced.
a. Duplicate variables declared in the same scope (block) are not allowed.
b. Variables of inner scopes (blocks) hide variables of outer scopes (blocks).
c. All variables that are referenced must have been previously declared and are in scope.
3. Enforce constraints in the literals such that every INT literal must be a valid Java int literal. 4. Ensure that the expression of an IF is a boolean
5. Ensure that the expression of a WHILE is a boolean
6. Ensure that the types of the VARIABLE and EXPRESSION of each assignment are identical. 7. Ensure that the operands of all operators are of the correct type.
CS 421 : Programming Languages
ý Kenny Hunt
Additional Rule
One other rule must also be checked: the rule that all variables must be initialized prior to use. You have the option of performing this check statically or dynamically.
Interpreter Function (50 Points)
You must write a function (interpret-program pgm) that accepts a single valid program object and returns the resulting state. The interpret-program function will also accept programs for which (is-program-valid? pgm) is false and will execute them correctly until
the very moment that an invalid action is invoked. At that moment, rather than performing an invalid action, an error will be raised.
Parallelism (521 MSE Students Only: 25 Points)
Extend the ART-C language by adding a parallel statement. A parallel construct is a tagged list of statements as given by example below. Semantically (not necessarily in real-time), the statements in the parallel construct will be executed simultaneously; each starting from the same state. The resulting state will be the union of the states generated by each statement. If there are conflicting values in any of the resulting states, then an error occurs. In order to complete this excercise you must
1. Modify the EBNF syntax wherever necessary to include a parallel construct.
2. Extend the interpreter by writing an interpret-parallel function.
3. Extend the static type-checking function to include type-checking a parallel element.
An example of a valid parallel construct is shown below. Of course, variables x, y, and q must already exist int the enclosing typemap for this to be valid.
(parallel
(:= n 5)
(while (> x 0)
(block
(declare int z)
(:= z 3)
(:= x (- x 1))
(:= y (+ y x))))
(:= q 2))
Examples
(interpret-program ‘(program
(declare int n)
(declare boolean error)
(declare int result)
(block
(:= error false)
(:= result 1)
(block
(declare int local)
(:= n 5)
(:= local n)
(while (> local 0)
(block
(:= result (* result local))
(:= local (- local 1)))))
(sprint “result: ” result)
(if (~ error) (sprint “a”) (sprint “b”))))) ==> ((result 120) (error #f) (n 5))
Grammars Overview
Consider an expression language with two binary operators “$” and “#” and two unary prefix operators “*” and “@”. It also includes a single alphabetic symbol “X” along with parenthesis “(” and “)”. An EBNF expression grammar is given below where the starting non-terminal is
$ #
@*X()
BNF Grammar (9 Points)
1. Give an equivalent unambiguous BNF grammar for this expression language.
CS 422. 1G:ivPerothgeramssmoicnigatLivaitnygoufatghestwo binary operators and a precedence table for all four operators in your BNF grammar.
ý Kenny Hunt
) >rpxe< | (] | [=::>rotcaf< }>rotcaf< { >rotcaf< =:: >mret< }>mret< { >mret< =:: >rpxe< 3. Using your BNF specification, provide a parse tree for the expression *X$X$@((*X)#X#*X) .Syntax Charts and BNF (6 Points)For each of the two syntax charts in Figure 2, provide an equivalent grammar that describes exactly the same language (where the alphabet is given as {0, 1}) and informally justify your answer. Chart AChart BSyntactic Ambiguity (5 Points)Prove that the following BNF grammar is ambiguous.Figure 2. Syntax Charts N = { , , }
T = {a, b, c, x}
P = { ::=
::= x
::=
::= a
::= b
::= c}
S =
Submission
1. You must submit all your work using using a project named cs421 with a folder named hw3. 2. The scheme code must be placed in a single file named artc.rkt.
GitLab
CS 421 : Programming Languages ý Kenny Hunt
)34491:ude.xalwu.sc//:sptth(
Reviews
There are no reviews yet.