Implement an expression evaluator in Python Program
Python program
The Program will be calledSeawolf. For this assignment, implement an expression evaluator. This takes an expression as input, evaluates it to a result, and prints the result to standard output.
The Language:
* Data Types: our language has three data types:
** Integer = should be implemented using the equivalent Python integer type.
** Real = should be implemented using the equivalent Python integer real.
** List = can be implemented using a Python list.
** String = should be implemented using the equivalent Python String type.
Each type has a literal representation:
- Integer. An integer is represented by one or more digits (0-9). For example, 42 is an integer literal.
- Real. A real is represented by zero or more digits (0-9) followed by the decimal point "." and zero or more digits (0-9). For example, 3.14159 is a real literal.
- String. A string literal starts with a double quote. This may be followed by zero or more non-double-quote characters. The string ends with a double-quote. The value of the string literal should not include the starting and ending quotes. An example string literal is "Hello SeaWolf.".
- List. A list literal consists of a square bracket, followed by a comma-separated list of zero or more expressions. For example, [ 307, 130, 100+3 ] is a list literal.
* Operators: the following operators are listed in precedence order, from highest to lowest (all associative operators are left-associative):
Operator Description
literal The literals given above.
( expression ) A parenthesized expression.
a [ b ] Indexing. B may be any expression.
a * b, a / b operand and returns remainder).
a ** b Exponent Performs exponential (power) calculation on operators = a to the power b.
a // b Floor Division - The division of operands where the result is the quotient in which the digits after the decimal point are removed.
a + b, a - b Addition and subtraction.
a in b Evaluates to true if it finds a variable in the specified sequence and false otherwise.
a < b, a <= b, a == b, a <> b, a > b, a >= b Comparison.
not a Boolean NOT.
a and b Boolean AND.
a or b Boolean OR.
The operators have the following semantics:
- Indexing: B must be an integer, a must be either a string or a list. If a is a string, returns the b-th character of the string as a string. If a is a list, returns the b-th element of the list (whatever type it has). The index is zero-based, so the first element is at index 0. If the index is out of bounds, it is a semantic error.
- Addition: A and B must be either both integers, both reals, both strings or both lists. If they are integers or reals, then addition (with standard semantics) is performed. If they are both strings, than string concatenation is performed. If they are both lists, then concatenation of the lists is performed.
- Multiplication, Division and Subtraction: A and B must be integers or reals. For division only, B must not be 0. These are performed using standard multiplication semantics.
- Comparison: A and B must be integers. The two integers are compared, and the result is 1 if the comparison is true, and 0 if the comparison is false.
- Boolean AND, OR, NOT: A and, if present, B must be integers. If the integer is 0, then it is considered false. All other integers are true. The boolean operation is performed. If its true, the result of the expression is the integer 1, otherwise it is the integer 0.
Your program will be called with a single argument. This argument will be a file containing expressions, with one expression per line. You should process each expression and print one of three possible outputs:
- If the line contains a syntax error, you should print out: SYNTAX ERROR.
- A semantic error occurs when the line does not contain a syntax error, but one of the "must" conditions given above is violated when evaluating it. If the line contains a semantic error, you should print out: SEMANTIC ERROR.
Otherwise, you should evalute the expression, and print the result using Python's repr function.
An example input file might look like:
1 - 2 + 3
1 2 3
42 + "Red"
1 - (2 + 3)
"Hello" + " " + "SeaWolf."
[1, 2, 3][0] + 40
The output from this file should look like:
2
SYNTAX ERROR
SEMANTIC ERROR
-4
'Hello SeaWolf'
41
To get you started, we've created a framework that handles multiplication and division of integer literals, including parenthesization. You may use it, or start with your own code.
You should download the tpg.py parser. Documentation for TPG can be found at http://christophe.delord.free.fr/tpg
This will be the first of several projects that uses this code, so it will do you well to make sure your code is reusable. You should create an abstract syntax tree, and use that, rather than using parser actions to evaluate expressions directly. Future projects will require you to add to your parser and your abstract syntax tree.
Your program will be run with a command like:
python.exe hw.py input1.txt
Blue Print
import sys
import tpg
class SemanticError(Exception):
"""
This is the class of the exception that is raised when a semantic error
&occurs.
"""
# These are the nodes of our abstract syntax tree.
class Node(object):
"""
A base class for nodes. Might come in handy in the future.
"""
def evaluate(self):
"""
Called on children of Node to evaluate that child.
"""
raise Exception("Not implemented.")
class IntLiteral(Node):
"""
A node representing integer literals.
"""
def __init__(self, value):
self.value = int(value)
def evaluate(self):
return self.value
class Multiply(Node):
"""
A node representing multiplication.
"""
def __init__(self, left, right):
# The nodes representing the left and right sides of this
# operation.
self.left = left
self.right = right
def evaluate(self):
left = self.left.evaluate()
right = self.right.evaluate()
if not isinstance(left, int):
raise SemanticError()
if not isinstance(right, int):
raise SemanticError()
return left * right
class Divide(Node):
"""
A node representing division.
"""
def __init__(self, left, right):
# The nodes representing the left and right sides of this
# operation.
self.left = left
self.right = right
def evaluate(self):
left = self.left.evaluate()
right = self.right.evaluate()
if not isinstance(left, int):
raise SemanticError()
if not isinstance(right, int):
raise SemanticError()
if right == 0:
raise SemanticError()
return left / right
# This is the TPG Parser that is responsible for turning our language into
# an abstract syntax tree.
class Parser(tpg.Parser):
"""
token int "\d+" IntLiteral;
separator space "\s";
START/a -> expression/a
;
expression/a -> muldiv/a
;
;
muldiv/a -> parens/a
( "\*" parens/b $ a = Multiply(a, b) $
| "/" parens/b $ a = Divide(a, b) $
)* ;
parens/a -> "\(" expression/a "\)" | literal/a
;
literal/a -> int/a;
"""
# Make an instance of the parser. This acts like a function.
parse = Parser()
# This is the driver code, that reads in lines, deals with errors, and
# prints the output if no error occurs.
# Open the file containing the input.
try:
f = open(sys.argv[1], "r")
except(IndexError, IOError):
f = open("input1.txt", "r")
# For each line in f
for l in f:
try:
# Try to parse the expression.
node = parse(l)
# Try to get a result.
result = node.evaluate()
# Print the representation of the result.
print(repr(result))
# If an exception is thrown, print the appropriate error.
except tpg.Error:
print("SYNTAX ERROR")
# Uncomment the next line to re-raise the syntax error,
# displaying where it occurs. Comment it for submission.
# raise
except SemanticError:
print("SEMANTIC ERROR")
# Uncomment the next line to re-raise the semantic error,
# displaying where it occurs. Comment it for submission.
# raise
f.close()
