本次为Python代写之 CSCI3136 Assignment 7
Instructor: Alex Brodsky Due: 9:00am, Friday, July 12, 2019
Consider the grammar for the Splat programming language in Figure 1, where the terminal int denotes an integer, the terminal symbol, and the terminal string denotes a quoted string.
→ VALUEFTAIL → ε
→ ′∗′ FACT
→ ′/′ FACT
→ ′(′ EXPR ′)′
→ ′[′ ARGS ′]′
→ ′−′ VALUE
→ ′!′ VALUE
→ EXPR A LIST → ε
→ ′ ,′ EXPR A LIST → symbol
→ ′ false ′
E LIST → E TAIL →
EXPR E TAIL
→ E LIST
EXPR → S EXPR → S TAIL →
S EXPR ANDOP S TAIL ε
→ ′|′ S EXPR
ANDOP → A TAIL →
RELOP A TAIL
RELOP → R TAIL →
TERM R TAIL
→ ′ &′ ANDOP
→ ′ >′ RELOP
→ ′ =′ RELOP
→ ′ #′ RELOP
TERM → T TAIL →
FACT T TAIL
→ ′ +′ TERM
→ ′ −′ TERM
Figure 1: A grammar for the Splat language.
Splat, is a functional language where all programs consist of one or more expressions. For now, an expression can be one of:
CSCI3136 Summer 2019 Assignment 7
arithmetic expressions such as 1 + 2 * 3
boolean expressions such as 1 < 2 & 3 > 2
string expressions such as “Hello ” + “world!”
list expressions such as [“a”, “b”, “c”] and [3, 1, 2] + [4, 5, 6]
Expressions in Splat are evaluated in the standard way. For example,
1 + 2 * 3 evaluatesto7
1 < 2 & 3 > 2 evaluatestotrue
“Hello ” + “world!” evaluates to “Hello world”
[3, 1, 2] + [4, 5, 6] evaluatesto[3, 1, 2, 4, 5, 6]
Formally, an expression is either a literal
integer such as 42,
boolean such as true
string such as ”Hello”
list of constants such as [1,2,3]
or a composition of subexpressions and operators such as above. The expression is evaluated by applying the operators just like in most programming languages. The operators in Splat are:
add two integers
concatenate two strings
concatenate two lists
subtract one integer expression from another integer expression, e.g., 3 – 2 negate an integer expression, e.g., -42
multiply and divide integer expressions
<, >, =, # compare two expressions: less than, greater than, equals, not equals
&, |, !
combine boolean expressions with and, or, and not Table 1: Operators in Splat.
All expressions are evaluated in the same way as in most other languages such as Java or Python. The list expression is evaluated by evaluating each of the elements of the list. E.g., the evaluation of [1+2, 3+4, “Hello”] is [3, 7 “Hello”].
[50 marks] A recursive descent parser, called splat.1.py, (written in Python) that parses Splat programs using the context-free grammar specified in Assignment 5 is provided as part of this assignment. Using this parser, or your own version of the parser (implemented in a language of your choice) implement an evaluator that evaluates parsed expressions.
Note: The provided solution automatically builds an abstract syntax tree (AST) as it parses the input. Each node in the AST contains a field called atoms which is the list of its children. The AST differs from the parse tree in that all the right-recursive parts of the parse tree are flattened. For example, The parse tree, rooted at TERM for the expression 1 + 2 + 3 is shown in Figure 2, where as the corresponding AST is shown in Figure 3.
To evaluate the expressions, your evaluator will need either a parse tree, or an abstract syntax tree. Note: it is impossible to evaluate the expressions without a tree representation. The output of your evaluator should evaluate the expressions and print out the results.
CSCI3136 Summer 2019 Assignment 7
Figure 2: Parse tree for 1−2+3 Figure 3: Abstract syntax tree for 1−2+3 The following evaluation rules apply:
• The evaluation of a literal or a symbol is just the literal or symbol.
• The evaluation of a list is a list with each element evaluated.
• The evaluation of an expression is the application of the operator to the subexpressions, e.g.,
1 − 2 + 3 should result in 2 being the output.
• If an operator cannot be applied to a subexpression, the message Evaluation Error is out-
putted and the evaluator should exit.
All operators and their precedence in the grammar in Figure 1 should be implemented.
The evaluator should print out the result of each of the the top-level evaluations (one per line),
in the same format as the input. See the provided tests for examples.
You may implement your evaluator in any language that you wish, but it must be runnable on
the bluenose server. The evaluator should take input from stdin and output to stdout.
A set of test cases is provided for you to test your evaluator. A test script test.sh is provided to run the tests. Since the choice of language is up to you, you must provide a standard script
called runme.sh to run your evaluator. For example the script for a Python solution looks like:
# Command to run your program
To submit this part of the assignment please use Brightspace. Remember, you need to include a script called runme.sh that will let the marker run your code.
CSCI3136: Assignment 7
Assignments are due by 9:00am on the due date. Assignments must be submitted electronically via Brightspace. Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the authors named above declare that its content is their original work and that they did not use any sources for its preparation other than the class notes, the textbook, and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported to the Facultys Academic Integrity Officer and possibly to the Senate Discipline Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipdue