Description
Over the course of the next three programming assignments (HW03, 04, and 05) we will be implementing a programming language. We will call this language, SBML.
For this assignment we will be constructing an expression evaluator. The evaluator will take an expression as input, evaluate the expression, and then print the result to standard output.
Your program must construct an abstract syntax tree representing the input expression during parsing. Semantic analysis and expression evaluation will then be done through recursive operation on the contents of the syntax tree starting at the root. This will be discussed with examples in class. Doing so will make the next stage of this assignment more manageable.
The code written for this assignment will be reused in future assignments. Please keep that in mind when working. Keep your code clean, neat, and modular so that it will be easy to update and extend in future assignments.
We will use the parser generator PLY – Python Lex and Yacc – to specify and implement the SBML language.
Installation Instructions for PLY:
- Using PIP:
> pip3 install ply –-user
or
> python3 -m pip install ply –-user
- Manual Installation Using setuptools
-Download the ply archive; https://www.dabeaz.com/ply/
-Unzip the archive.
-From command-line, navigate to the ply directory.
-Run the command: python3 setup.py install –-user
SBML description:
SBML Datatypes:
Numbers: Integers and Reals – implement as Python integers          and floats.
Booleans: True and False – implement as Python Booleans.
Strings: Sequences of characters enclosed within matching          single or double quotes in a single line. Strings          should be implemented using the equivalent Python
String type.
List:    Finite, ordered sequence of elements separated by          commas and enclosed within matching square          brackets. Elements of the list need not be of the          same type. Implement as Python list.
Tuple:   Finite, ordered sequence of elements separated by          commas and enclosed within matching parentheses.          Elements of the tuple need not be of the same          type.
SBML Literal Representation of Data Types:
Integer: Positive (no sign) or negative (unary -) whole         numbers in base-10 representation (decimal         representation). An integer literal is one or more         digits, 0-9.
Examples: 57, -18, 235
Real:Â Â Â A real value is represented by 0 or more digits
(0-9), followed by a decimal point, “.”, followed         by 0 or more digits (0-9), except that a decimal         point by itself with no leading or trailing digit         is not a real.
Examples: 3.14159, 0.7, .892, 32787.
A real can also contain exponents as in scientific         notation. In this case, a real value, as defined         above, is followed by an “e” character and then a         positive or negative integer, as defined above.
Examples: 6.02e-23, 17.0e4
Boolean: True, False (just as in Python)
String: A string literal begins with a single or double         quote, followed by zero or more non-quote         characters, and ends with a matching quote. The         value of the string literal does not include the         starting and ending quotes.
Examples: “Hello World!”, “867-5309”
List:   A list literal is composed by a left square         bracket, followed by a comma-separated sequence of         zero or more expressions, followed by a right         square bracket.
Examples: [“a”, “b”], [1, 2], [307, “307”, 304+3]
SBML Operators:
Operator precedence and associativity is given below.
- ( expression ) – A parenthesized expression
- ( expression1, expression2, … ) – Tuple constructor
A singleton tuple can be constructed by including a comma after the expression. E.g., ( expression1, ) There are no empty tuples
- #i(tuple) – returns the argument at index i in the Indices start at 1 as in SML.
- a[b] – Indexing Operation. b can be any expression.
- a ** b – Exponentiation. base a raised to the power b.
right associative: 2**3**4 == 2**(3**4)
- a * b – Multiplication. Overloaded for integers and
- a / b – Division. Overloaded for integers and reals, but result is always a real value.
- a div b – Integer Division. Returns just the quotient.
a and b are integers.
- a mod b – Modulus. Divides a by b and returns just the a and b are integers.
- a + b – Addition. Overloaded for integers, reals,       strings, and lists.
- a – b – Subtraction. Overloaded for integers and reals.
- a in b – Membership. Evaluates to True if it finds the value of a inside the string or list             represented by b.
- a::b – Cons. Adds operand a to the front of the list referred to by operand b.
- not a – Boolean negation.
- a andalso b – Boolean Conjunction (AND)
- a orelse b – Boolean Disjunction (OR)
- a < b – Less than. Comparison.
- a <= b – Less than or equal to. Comparison.
- a == b – Equal to. Comparison.
- a <> b – Not equal to. Comparison.
- a >= b – Greater than or equal to. Comparison.
- a > b – Greater than. Comparison.
SBML Operator Precedence:
Operator Precedence for SBML (ordered from lowest to highest):
All operators are left-associative, except for exponentiation (**) and
cons (::), which are right-associative
Operators on the same line have the same precedence.
- orelse Boolean Disjunction
- andalso Boolean Conjunction
- not Boolean Negation
- <, <=, ==, <>, >=, > Comparison Operators (for                             numbers and strings)
- h::t Cons operator
- in Membership test
- +, – Addition and Subtraction                             (Overloaded for numbers,                              strings, lists)
- *, /, div, mod Multiplication, Division,                             Integer Division, Modulus
- ** Exponentiation 10. a[b]                   Indexing
- #i(tuple) Tuple Indexing
- (exp1, exp2,…) Tuple Creation
- (exp) Parenthetical Expression
SMBL Operator Semantics:
Indexing: Operand a must be either a string or a list.          Operand b must be an integer. If a is a string,          then return the b-th character as a string. If a          is a list, then return the b-th element as an          instance of whatever type it is. The index is          0-based. If the index is out of bounds, then this          is a semantic error.
Addition: Operands must either both be numbers, or both be          strings, or both be lists. If they are integers          or reals, then addition with standard (Python)          semantics is performed. If a and b are both          strings, then string concatenation is performed.          If a and b are both lists, then list          concatenation is performed.
Subtraction: Operands must both be integers or reals.
Performed using standard subtraction             semantics.
Multiplication: Operands must both be integers or reals.
Performed using standard multiplication                semantics.
Division: Operands must both be integers or reals. Operand          b cannot be 0. Performed using standard division          semantics.
Booleans: Operands for Boolean operations (not, andalso,          orelse) must be Boolean values.
Comparisons: Operands must either both be numbers or both             be strings. Comparison of numbers (integers             and strings) should follow standard semantics.             Comparison of strings should follow the Python             semantics. Returns True if comparison is true,             and False if comparison is False.
Program Behavior:
-Your program will be called with a single command-line argument. This argument will name an input file. The input file will contain a list of expressions, one per line.
Like So: python3 sbml.py <input_file_name.txt>
-Your program should process each expression one-by-one, and produce one of the following three outputs, printed to
STDOUT:
- If the line contains a syntax error, then print:
“SYNTAX ERROR”.
- If the line contains a semantic error, then print:
“SEMANTIC ERROR”.
- Otherwise, evaluate the expression and print the result.
Example: | |
Input File:
1 – 2 + 3 1 2 42 + “Red” 1 – (2 + 3) “Hello” + ” ” + “SBML.” [[1], 2, 3][0][0] + 40 |
Output:
2 SYNTAX ERROR SEMANTIC ERROR -4 Hello SBML. 41 |
–