Last change 27.11.2019 17:19.
This page change history:
2019-11-22: First public version
2019-11-27: Added description of provided helper code. Changed requirements of interpretation levels 1 and 3 a little.
Using the syntax tree it is now time for semantic checks and running the program. For full credits you DO NOT have to implement everything listed here. One can easily think about dozens of different checks and implementing them all would be too much work for this project.
So select the items you are interested in and concentrate creating a clearly documented, easy to read implementation of them. You might concentrate on hunting semantic errors or running the program.
A fully functional example on how to do semantic checks and a simple interpreter using our syntax tree can be found here.
semantics_common.pyhas utility functions for the symbol table and visiting nodes of the syntax tree (which you can use in your own phase 4, too). The provided function and class are described at the end of this page.
semantics_check.pyhas functions to perform semantic checks by visiting all tree nodes, recognizing node types and checking them. Running this file performs the semantic checks for a given program.
semantics_run.pycontains a simple interpreter which recursively evaluates the syntax tree. Running this file performs semantic checks, prints out the syntax tree and then runs the interpreter.
This section describes the intended semantics (= meaning) of the language constructs. Please note that this is just a description, you don't have to implement all of these! The following sections describe what semantic checks and functionality to implement.
These are just quidelines. You decide the exact semantics yourself (and document them in your submission).
[A..B]creates a tuple with integer values from A to B
[N**M]creates a tuple with N instances of value M
[a, b, c]creates a tuple with values a, b, and c (this is probably obvious)
[2,3,4] | +" results in
[2,3,4] | *" results in
[1,2,3] | Func" means "
Func[1,2,3]". This is a possible semantic check.
Functakes 2 parameters, "
[1,2,3,4] | each:Func" is equal to "
Func[1,2] ++ Func[3,4]". This is a possible semantic check.
select:n[<tuple>]" returns the nth element of the tuple (i.e., "
select:1..." returns the first element). The index of the element must be in range, i.e. 1 <= n <= size-of-tuple. This is a possible semantic check.
In this assigment, semantic checks are performed on the syntax tree (i.e., before running the program, even if you implement the interpreter part). In many programming languages ALL the checks are run and results printed out. However, it's easier to stop at the first semantic error (since recovering from the error and continuing is often quite complicated), so that's what we'll do in this assignment.
In the Semantics of the language section above, ideas for possible semantic checks are marked with "This is a possible semantic check.". However, there are more possible semantic checks that could be performed, so it's ok to also include your own, if you wish. The list below lists the mentioned semantic checks in the estimated order of easiness (the easiness of course depends somewhat on your design choices):
Probably easiest way to implement semantic checking of the syntax tree is to use the provided visitor pattern based function
visit_tree(), as well as provided simple data structure
SemData. The visitor can be used to perform checking passes over the tree, selecting which types of node to act on. The SemData class can be used to store the symbol table as well as other information needed for semantic checking, as well as passing that information along when performing the checks. For more hints on how to implement phase 4, please watch the 26.11. lecture recording, and read the description of the provided helpers at the end of this page.
Semantic errors are reported by returning an error message string instead of
None from the functions provided to the visitor implementation. The provided visitor then prints out this error message and stops the program. If syntax tree nodes contain an attribute called "
lineno", the line number is included in the error message.
After running semantic checks, you now should have a syntax tree (program) which can be executed. We suggest that you write an interpreter which interprets (= runs) the syntax tree. (Alternatively you can generate code from the tree, i.e. write a compiler, but that's probably more complicated than interpretation. If you choose this option, contact the course staff first).
While running the program you don't have to implement any run-time semantic checks, if you don't want to. I.e. you can assume the program is semantically correct, even if you don't write all semantic checks, and you can assume there are no run-time errors which would require error handling in the interpreter.
One way to implement an interpreter is to have an "eval()" method that recursively evaluates the nodes in the syntax tree. You call the topmost eval() and it goes through the tree executing the node statements in the correct order. E.g. before running a plus(+) operation the left and right parts are evaluated first (the value of the evaluated expression can be the return value of eval()). The example Unicode calculator can be used as the basis for your interpreter (or you are welcome to design your own).
Below are different levels of implementing execution. Since levels depend on each other, it's advisable to implement them in order. Also, it's ok if some level is only implemented partially (of course that will be taken into account in grading).
select:" but not including pipes).
Your program must start when executed in python by:
python3 main.py in your submission directory.
You can assume that this python interpreter has PLY installed.
Your program must understand the following command line arguments:
usage: main.py [-h] [--who | -f FILE] -h, --help show this help message and exit --who print out student IDs and NAMEs of authors -f FILE, --file FILE filename to process(See the course snippet on how to implement this using python standard library.)
Your code should be built on top the previous phase (syntax), so the same errors messages from there should be used here also. As mentioned before, you don't have to implement run-time error checking, if writing the interpreter.
In addition to the code, the group submits a text document in either plain text (.txt), markdown (.md) or pdf (.pdf) format. It should document each semantic check / implementation level you've done, explaining how it works. If you implemented any things of your own, explain them also in the document. Also tell what you thought about this assignment? What was difficult? What was easy? Did you learn anything useful?
If you have an idea, feel free to implement it (AND remember to document it)
The file semantics_common.py contains a helper function visit_tree() and classes SemData and SymbolData to help with semantic checks (the classes may be useful also during interpretation).
SemDataclass is meant to be used as a place where you can store all kinds of information required by the semantic checks and interpretation, including the symbol table (which is already included in the class). Create a single object of this class at the beginning, and pass it to every function as a parameter to share data across the checking the interpretation. Examples of possible stuff to keep in SemData (in addition to the symbol table) are call stack (interpretation), what function you are in (semantic checking), etc.
SymbolDataclass is an example of what you could use as a symbol table entry (i.e. store in the .symtbl of SemData). Now it contains the type of the symbol (variable, function, you choose what to put there) and a pointer to the node where the symbol is defined in the tree, but you can choose to put anything there.
visit_treefunction can be used during semantic checking to perform operations on every node of the tree. You give it two functions: one function is called when
visit_treestarts handling a node, and the other when all the children of the node have been handled (visited). In those functions you can choose which nodes you are interested in, collect information to
SemDataor the node itself, and/or check that things are semantically ok.
Nothing at the moment.
General practical questions about the course should be sent to email@example.com.