Introduction
In this project, you will be implementing a simple interpreter for a new programming language, called Brewin. Brewin is an object-oriented variant of the LISP language. You guessed it – that means there are lots of parentheses! :^) You¡¯ll be implementing your interpreter in Python. This project is the first of three – in the later CS131 projects, you¡¯ll be adding new features to your interpreter based on the concepts we learn in class.
Once you successfully complete this project, your interpreter should be able to run simple Brewin programs and produce a result, for instance it should be able to run a program that computes the factorial of a number the user enters (see below).
Brewin v1 Language Introduction
In Brewin, all functions and data are contained in classes – there are no stand-alone functions or variables. Every Brewin program must have a special class called “main”, and this class must hold a special method called “main” where execution of your program begins.
Here is a simple program in the Brewin language. You can see our main class, with two fields (num, result) and two methods (main, factorial). Line numbers have been added for clarity:
000 # Our first Brewin program!
001 (class main
002 # private member fields
003 (field num 0)
004 (field result 1)
006 # public methods
007 (method main ()
008 (begin
009 (print “Enter a number: “)
010 (inputi num)
011 (print num ” factorial is ” (call me factorial num))
014 (method factorial (n)
015 (begin
016 (set result 1)
017 (while (> n 0)
018 (begin
019 (set result (* n result))
020 (set n (- n 1))
023 (return result)
Here¡¯s a description of the above program:
¡ñ 000: This line has a comment on it, indicated by the #
¡ñ 001: Defines a class called main; all Brewin programs must have a main class. When the
Brewin interpreter runs a program, it first instantiates an object of the main class’s type and then executes the main method within this object.
¡ñ 003: This defines a member variable (a “field”) named num whose initial value is 0. In Brewin v1, fields are not given fixed types, like in C++. A given field may thus refer to values of different types over time.
¡ñ 004: This defines a member variable (a “field”) named result whose initial value is 1. All Brewin fields must have an initial value specified for them.
¡ñ 007: This defines the “main” method of our main class. Execution of a Brewin program starts with main method in the main class.
¡ñ 008: This is a begin statement. A begin statement allows you to sequence one or more nested statements (e.g., those on lines 9-11). By default, all Brewin methods are made up of a single, high-level statement, so if you want a function to execute multiple statements, a method’s high-level statement must be a begin statement, which then may contain one or more embedded statements to execute.
¡ñ 009: This statement prints data to the screen.
¡ñ 010: This statement inputs an integer (hence “inputi”) from the keyboard and stores it
into the member variable named num.
¡ñ 011: This statement prints something like “5 factorial is 120” to the screen. To get the
factorial result, it makes a method call to the factorial method within the “me” object. “me” is like “this” in C++ or “self” in Python – it refers to the current object, so this method call invokes the factorial method in the current object.
¡ñ 014: This defines the “factorial” method in our main class. You can see that the factorial method accepts one parameter called n. Parameters in Brewin v1 don’t have types specified for them, meaning that n could refer to different types of values depending on what values are passed in over time.
¡ñ 015: The begin statement lets us run multiple statements in the factorial function.
¡ñ 016: The set command sets the value of the member variable result to 1.
¡ñ 017: This is a while loop which will continue running while n > 0.
¡ñ 018: The begin statement lets us run multiple statements in the while loop. The body of a
while loop must be a single statement, so adding a begin statement lets us run multiple
sub-statements in the while loop.
¡ñ 019: Sets the value of the result member variable to n * result.
¡ñ 020: Decrements the value of the member variable n.
¡ñ 023: Returns the value of the result member variable as the result of the factorial
Let¡¯s distill some interesting facts about the Brewin v1 language that we can glean from our program:
¡ñ Formatting:
¡ð Brewin requires that statements be enclosed in parentheses like LISP. You must
have the right number of parentheses or your program won’t work! Too many or
too few can cause problems, so be careful!
¡ð Comments in Brewin begin with a # sign.
¡ð Spaces and newlines are used as separators – there are no parentheses,
commas, semicolons, etc.
Code Help, Add WeChat: cstutorcs
¡ñ Classes:
¡ð Our program contains a single class called “main” (which is mandatory in all
Brewin programs), but a Brewin program can have additional classes if you like.
¡ð Before execution begins, the Interpreter instantiates a “main” object based on the
definition of the main class.
¡ð Once the main object has been instantiated, the Interpreter then asks that object
to run the statement(s) in its main method – this executes the program. ¡ñ Variables:
¡ð There are two types of variables in Brewin v1 – member variables (aka fields) in classes, and parameters of functions. There are no local variables in Brewin v1, other than parameters.
¡ð Fields (aka member variables)
¡ö Fields are defined with a “field” keyword in a class.
¡ö You don¡¯t specify types for field variables. So field variables don’t have
fixed types, but the values they refer to do have types. Thus a member variable may refer to values of different types over time, just like in Python.
¡ö Fields can have their value changed.
¡ö All fields must have a constant value specified for their initial value.
¡ö All fields in an object are private and may only be accessed by methods in
the same object
¡ð Parameter variables
¡ö Parameter variables are defined in a method’s prototype.
¡ö Parameter variables are typeless (so you can pass different types of values each time you call the function if you like), just like in Python.
¡ö Parameter variables can have their value changed.
¡ð All variables are assigned via the ¡°set¡± statement.
¡ñ Methods:
¡ð All methods within a class are defined via the ¡°method¡± keyword.
¡ð All methods in a class are public.
¡ð The main method, within the main class, is a special method where execution of
a Brewin v1 program begins.
¡ð Methods may have zero or more parameters, which are specified in parentheses
right after the method name. So the main method has no parameters, and the
factorial method has a single parameter called n.
¡ð Every method must have a single top-level statement as its body, e.g., (print
“hello world”). If you want to run more than one statement in a method, you must make the top-level statement in the method a “begin” statement which can have one or more sequenced sub-statements, e.g.:
# every method has a single statement
(method talk () (print “hi there”))
(method greeting ()
(begin # the method’s single statement is a begin statement # we can then sequence multiple sub-statements in the begin (print “hello “)
(print “world”)
¡ð All methods are called with the “call” keyword. When you use the call keyword, you must specify what object the call is being directed to, then the method to be called in that object, then any parameters that are to be passed to the method. So the code:
(call me factorial num)
calls the factorial method within the me object (the current object – think of “me” like the “this” pointer in C++), passing a parameter value of num to the method. As you can see, methods may modify parameters.
¡ð As you can see, a method may optionally return a value. ¡ñ Expressions:
¡ð Expressions are written in prefix notation, e.g., (+ 5 (* 6 3)), or (== n 1).
¡ð An expression may refer to constants, variables and other sub-expressions, and
it may call methods within the current object or other objects.
¡ð An expression may also be used to instantiate a new object (we’ll see this later)
¡ñ Control Flow:
¡ð A while loop has a boolean expression as its condition (which it uses to decide
whether to run its body) and a single statement as its body. To sequence multiple
statements in a while loop, wrap them in a top-level ¡°begin¡± statement.
¡ð The begin statement lets you run one or more sub-statements in order.
¡ð The return statement lets a method return a value to its caller, and immediately
terminates the current method.
Now that you have a flavor for the language, let¡¯s dive into the details.
How To Build an Interpreter
When you build an interpreter, you have to represent all of the elements of the interpreted language (e.g., Brewin) using classes/objects in the “host” language that you’re using to build the interpreter (e.g., Python). For instance, if our interpreted language:
¡ñ has variables, we’ll need to have a class in the host language to represent variables (their name, their current value).
¡ñ has values, we’ll need to have a class in the host language to represent a value (its type and the current value it’s set to)
¡ñ has functions, we’ll likely have a class in the host language to represent a function (its name, parameter variables, and statement(s) that make up its body).
¡ñ has statements, then we may want to have class(es) in the host language to represent the different types of statements in the interpreted language (“while” statements, “if” statements, “set” statements, “return” statements, etc.)
¡ñ has classes, then we’ll likely have a class in the host language to represent a class in the interpreted language (holding the class’s name, its fields and their initial values and its methods).
¡ñ has objects (instantiated from classes), then we’ll likely have a class in the host language to represent instantiated objects (e.g., what fields/member variables the object has and what their current values are, what methods does the object have, etc.).
As your interpreter interprets a Brewin program, if the interpreted program defines a new Brewin class, then your python program will need to create a new python object to represent/track that class. If a statement in your interpreted program instantiates a new Brewin object, then your python program will need to create and track a new python object that represents that Brewin object and the methods/fields it holds. If a statement in your interpreted program defines a new variable, then your python program will need to create and track a new python object that represents that Brewin variable. And so on.
We’ll also need to have an overall Interpreter class in the host language (python) that can use all of the classes above to implement the interpreter. For this project, you MUST create a new class called Interpreter and derive it from our InterpreterBase class (found in our provided intbase.py). Your Interpreter class MUST implement at least the constructor and the run() method that is used to interpret a Brewin program, so we can test your interpreter (more details on this later in the spec). You may add any other public or private members that you like to your Interpreter class.
How should your Interpreter class’s run() method work? Here’s some pseudocode:
class Interpreter(InterpreterBase):
def run(self, program):
# parse the program into a more easily processed form
result, parsed_program = BParser.parse(program_source)
if result == False:
return # error
self.__discover_all_classes_and_track_them(parsed_program)
class_def = self.__find_definition_for_class(“main”)
obj = class_def.instantiate_object()
obj.run_method(“main”)
And what might a ClassDefinition class (which represents a Brewin class) look like?
class ClassDefinition:
# constructor for a ClassDefinition def __init__(self, …):
# uses the definition of a class to create and return an instance of it
def instantiate_object(self):
obj = ObjectDefinition()
for method in self.my_methods:
obj.add_method(method)
for field in self.my_fields:
obj.add_field(field.name(), field.initial_value())
return obj
And what might an ObjectDefinition class (which represents a Brewin object, which may be instantiated from a Brewin class during interpretation of a Brewin program) look like?
class ObjectDefinition: def __init__(self, …):
# Interpret the specified method using the provided parameters
def call_method(self, method_name, parameters):
method = self.__find_method(method_name)
statement = method.get_top_level_statement()
result = self.__run_statement(statement)
return result
# runs/interprets the passed-in statement until completion and
# gets the result, if any
def __run_statement(self, statement):
if is_a_print_statement(statement):
result = self.__execute_print_statement(statement)
elif is_an_input_statement(statement):
result = self.__execute_input_statement(statement)
elif is_a_call_statement(statement):
result = self.__execute_call_statement(statement)
elif is_a_while_statement(statement):
result = self.__execute_while_statement(statement)
elif is_an_if_statement(statement):
result = self.__execute_if_statement(statement)
elif is_a_return_statement(statement):
result = self.__execute_return_statement(statement)
elif is_a_begin_statement(statement):
result = self.__execute_all_sub_statements_of_begin_statement(statement)
return result
The above examples will hopefully help you to get started on your implementation. These are just suggestions – you may implement your interpreter in any way you like so long as it is capable of passing our test cases and meets the explicit requirements stated in this spec.
Our Parser Class
To make things easier for you, we’re going to provide you with a simple class, called BParser, that can take Brewin source code, passed in as a Python list of strings, and output a fully-parsed list of strings. This will eliminate the need for you to write your own parsing logic and let you focus on the logic of the interpreter. Here’s how our parser class may be used:
from bparser import BParser # imports BParser class from bparser.py
def main():
# all programs will be provided to your interpreter as a list of
# python strings, just as shown here.
program_source = [‘(class main’,
‘ (method main ()’,
‘ (print “hello world!”)’,
‘ ) # end of method’,
‘) # end of class’]
# this is how you use our BParser class to parse a valid
# Brewin program into python list format.
result, parsed_program = BParser.parse(program_source)
if result == True:
print(parsed_program)
print(‘Parsing failed. There must have been a mismatched
parenthesis.’)
The above program would print the following out:
[[‘class’, ‘main’, [‘method’, ‘main’, [], [‘print’, ‘”hello world!”‘]]]]
Notice that our parser removes extraneous spaces and newlines, and eliminates comments. You’re left with a simple python list of lists that can be easily processed to build your interpreter. e.g.,
for class_def in parsed_program: for item in class_def:
if item[0] == ‘field’: # handle a field
elif item[0] == ‘method’: # handle a method
In addition, our parser attaches a new member variable to every string in the output list called line_num. You can use this to determine what line number each token was found on in the input program. For example, here’s a function that prints the line numbers of all the tokens in the above program:
def print_line_nums(parsed_program):
for item in parsed_program:
if type(item) is not list:
print(f'{item} was found on line {item.line_num}’)
print_line_nums(item)
For our above program, this would print out:
class was found on line 0
main was found on line 0
method was found on line 1
main was found on line 1
print was found on line 2
“hello world!” was found on line 2
You can use the line_num field to output specific error messages (e.g., “trying to dereference a null object reference on line 5.”) which will help with debugging.
Brewin v1 Language Spec
The following sections provide detailed requirements for the Brewin v1 language so you can implement your interpreter correctly.
Formatting
¡ñ You need not worry about program formatting (spacing, etc.) since:
¡ð You will use our BParser class to parse all Brewin programs
¡ð All Brewin programs are guaranteed to be formatted correctly and syntactically
correct Classes
Every Brewin program consists of one or more classes. This section describes the syntax of defining a class as well as the requirements you must fulfill in supporting classes in your interpreter.
Overall Class Definition
Class Definition Syntax
Here’s the syntax for defining a class:
(class classname (field …) (method …)
# specific syntax will follow later in this doc
# specific syntax will follow later in this doc
# end of class definition
(field …) …
(method …)
Class Definition Requirements
You must meet the following requirements when supporting classes in your interpreter.
¡ñ Every Brewin program must have at least one class called main, with at least one method named main in that class. This is where execution of your Brewin program begins.
程序代写 CS代考 加微信: cstutorcs
¡ñ Brewin programs may have zero or more additional classes beyond the main class
¡ñ Every Brewin class must have at least one method defined within it
¡ñ Every Brewin class may have zero or more fields defined within it
¡ñ Class names are case sensitive, and must start with an underscore or letter, and may
have underscores, letters and numbers
¡ñ Classes may be defined in any order within your source file; all classes are visible to all
other classes (e.g., for instantiating a new object) regardless of whether they’re define
above or below the location of instantiation
¡ñ Methods and fields may be defined in any order within the class; all methods and fields
are visible to all other methods inside the class regardless of the order they are defined
¡ñ There are no official constructors or destructors in Brewin. If you want to define and call
your own methods in a class to perform initialization or destruction you may.
¡ñ Duplicate class names are not allowed. If a program defines two or more classes with
the same name you must generate an error of type ErrorType.TYPE_ERROR by calling InterpreterBase.error().
Class Definition Examples
Here are a few examples showing how to define valid Brewin classes:
(class person
(field name “”)
(field age 0)
(method init (n a)
(set name n)
(set age a)
(method talk (to_whom)
(print name ” says hello to ” to_whom)
(class main
(field p null)
(method tell_joke (to_whom)
(print “Hey ” to_whom “, knock knock!”)
(method main ()
(call me tell_joke “Matt”) # call tell_joke in current object
(set p (new person)) # allocate a new person obj, point p at it
(call p init “Siddarth” 25) # call init in object pointed to by p
(call p talk “Paul”) # call talk in object pointed to by p
Class Fields
This section details how to define fields (i.e., member variables) inside of classes.
Field Syntax
Here’s the syntax for defining a field:
(field field_name initial_value)
Field Requirements
¡ñ Field names are case sensitive and must start with an underscore or letter, and contain letters, underscores and numbers.
¡ñ All fields in Brewin are private by default and may only be accessed by methods in the same object. An object cannot access the fields of another object, even if the objects are both of the same type/class.
¡ñ Fields are visible to all methods within the current object, whether those methods are defined above or below the field’s definition, just like in C++.
¡ñ Fields do not have a particular type – they can be assigned to a value of any type, and may be reassigned to values of different types over time.
¡ñ All field definitions must specify an initial value for the field. Valid initial values must be constants: integers like 10 or -20, true, false, null, and “strings” in double quotation marks. Expressions are not allowed to be used for the initial value of a field.
¡ñ When an object is instantiated in your program from a class, the object gets a copy of each of the fields defined in the class, with each field’s value initialized to the specified initial value for that field.
¡ñ If a given class has two or more fields with the same name, you must generate an error of type ErrorType.NAME_ERROR by calling InterpreterBase.error().
¡ñ None of the programs we test you with will use ¡°me¡± as the name of a field. You can treat that as undefined behavior.
Field Examples
Here are some examples of field definitions:
(field foo_123 10)
(field name “unknown”)
(field _awesome true)
(field obj_ref_field_puppy null)
Class Methods
This section details how to define methods (i.e., member functions) inside of classes.
Defining Methods Method Definition Syntax
Here is the syntax for defining a method within a class:
(method method_name (param_name1 param_name2 … param_namen) (statement_to_execute)
) # end of method
Where there may be zero or more parameters to a function. Notice that in Brewin v1, you do not specify the types of the parameters or the return type of the method. Each method has a single high-level statement that it runs.
Method Definition Requirements
¡ñ Every class must have at least one method
¡ñ Each method definition specifies the method’s name, its list of parameters – if any, and a
single, top-level statement to run for the method
¡ñ All formal parameters to a function must have unique names, i.e. two parameters to a
function cannot have the same name. You can treat this as undefined behavior.
¡ñ We will not test you on methods with formal parameters named ¡°me¡±. You can treat this
as undefined behavior.
¡ñ Methods in Brewin v1 do not have types for the parameters nor do they have return
types. So any type of variable can be passed to a method’s parameter, and any type of
value may be returned (including no value at all).
¡ñ All methods are public in Bruin – there are no private methods
¡ñ Methods may optionally return a value
¡ñ If a method wishes to run multiple statements, then you must specify a begin statement
as the method’s top-level statement. You may then have any number of sub-statements run as part of the begin statement.
¡ñ If a method has a parameter whose name is the same as the name of a field in the class, then all references to the name of that variable during the execution of that method will refer to the parameter rather than the field (i.e., the parameter hides the field within that method). This is called shadowing. For example:
(class main
(field x 10)
(method bar (x) (print x)) # prints 5
(method main () (call me bar 5))
¡ñ If a given class has two or more methods with the same name, you must generate an error of type ErrorType.NAME_ERROR by calling InterpreterBase.error().
Method Definition Examples
Here are a few example method definitions:
(method say_hello () (print “hello!”)) # takes no parameters (method say_hi_to (name) (print “hello ” name)) # takes 1 parameter (method square (val) (return (* val val))) # returns a result
(method do_several_things ()
(print “hi”)
(print “bye”)
# begin with multiple statements
(method two_params (a b) (return (+ a b)))
Calling Methods Syntax
Method calls use the following syntax:
(call target_object method_name param1 … paramn)
where target_object can be a member variable that holds an object reference or the “me” keyword, which indicates that the call should be directed to a method in the current object that’s making the call.
Requirements
¡ñ You may pass any variable, constant or expression as parameters to a method call. For example, this would be a valid function call if some_method accepts a single parameter:
(call some_object some_method (* 3 (+ 5 6))) # 33 passed as 1st arg
¡ñ If the called method returned a value, then you may use this return value within a statement or expression, e.g.:
# use the result of the method call to update field_x
(set field_x (call some_object some_method (* 3 (+ 5 6))))
¡ñ Brewin v1 does not support overloaded methods (e.g., two methods with a different set of parameters). You are NOT responsible for supporting overloading or detecting invalid use of overloading, and will not be provided with any test cases that use overloaded methods.
¡ñ If a call is made to an undefined method, you must report an error by calling the InterpreterBase.error() method with an error type of ErrorType.NAME_ERROR.
¡ñ If a call is made to a method with the wrong number of parameters, you must report an error by calling the InterpreterBase.error() method with an error type of ErrorType.TYPE_ERROR.
The following code shows several method calls within the same and to different objects:
(class person
(field name “”)
(field age 0)
(method init (n a) (begin (set name n) (set age a)))
(method talk (to_whom) (print name ” says hello to ” to_whom))
(method get_age () (return age))
(class main
(field p null)
(method tell_joke (to_whom) (print “Hey ” to_whom “, knock knock!”))
(method main ()
(call me tell_joke “Leia”) # calling method in the current obj
(set p (new person))
(call p init “Siddarth” 25) # calling method in other object
(call p talk “Boyan”) # calling method in other object
(print “Siddarth’s age is ” (call p get_age))
Constants in Brewin are just like those in other languages.
¡ñ You can have integer constants, string constants enclosed in ¡°double quotes¡±, boolean constants (true/false), and null (which is used to designate an invalid object reference). There are no floating-point numbers.
¡ñ Integer constants may be positive or negative (e.g., -5 with no spacing between the minus sign and the first digit), and have any valid integer value representable by a python integer.
Here are some example constants:
¡ñ “this is a test”
¡ñ -12345678901234
¡ñ null ¡ñ0
Programming Help
Expressions
An expression is made up of constants, variables, and operations (e.g., +, -, <, ==, function calls, object instantiation) which yield a result/output value. An expression may have nested sub-expressions. An expression is NOT a statement! For example:
(+ 5 variable)
(> str “foobar”)
(== some_int (+ (* 3 5) 6))
Expressions may be any of the following:
¡ñ A constant (e.g., 5, “foobar”, true/false, null)
¡ñ A variable name (e.g., years_old)
¡ñ An arithmetic expression, with any of the following operators: +, -, *, /, %, e.g.:
¡ð (setvar(+var15))
The arithmetic operators must yield an integer result
¡ñ A comparison expression that compares integers with any of the following operators: <, >, <=, >=, !=, ==:
¡ð (if(>some_int_var15)(print”bigger”)) The comparison operators must yield a boolean result
¡ñ A concatenation expression that concatenates two strings and results in a new string, using the + operator:
¡ð (setvar(+”foo”some_var_that_refers_to_a_string))
¡ñ A comparison expression that compares strings, with any of the following operators: ==,
!=, <, >, <=, >=, e.g.:
¡ð (if(>=string_var1″foobar”)(print”biggerorequal”))
All comparison operators compare strings lexicographically
The comparison operators must yield a boolean result
¡ñ A comparison expression that compares booleans, with any of the following operators:
!=, ==, & (logical AND), | (logical OR), e.g.:
¡ð (if(==boolean_var1true)(print”it’strue”))
The comparison operators must yield a boolean result
¡ñ A comparison expression that compares objects with null, with the following operators:
==, !=, e.g.:
¡ð (if(==xnull)(print¡°it¡¯strue¡±))
We will always compare with null, not another object.
¡ñ A boolean unary NOT expression, with the ! operator, e.g.:
¡ð (if(!boolean_var1)(print”thevariableisfalse”)) The unary NOT operator must yield a boolean result
¡ñ A method call expression that calls a method in the current object or another object, e.g.: ¡ð (setresult(callmefactorialnum))
¡ð (setresult(callsome_other_objsome_other_member_func10))
¡ñ A new expression which instantiates a new object of the specified class’s type and returns an object reference to that new object, e.g.:
¡ð (setsome_field(newClassName))
Note: In Brewin, there is no delete command like in C++. Brewin may rely upon Python’s garbage collection feature to automatically reclaim objects that are no longer referenced, so there’s no need to implement your own garbage collection.
Here are requirements for expressions:
¡ñ All expressions are represented in prefix notation with spaces separating each token in the expression, e.g., (+ 5 6), (> a 10) or (call target_object method_name param)
¡ñ The types of all values used in an expres