CIS2380: Coursework 2, 2017 The coursework is concerned with parsing and interpreting expressions in a simple data type called 3-valued logic. This data type has 3 values - true, false and unknown. The data type is similar to propositional logic, in that it has similar operators such as \and" and \or". 3-valued logic is often used in areas of computer science such as artificial intelligence and databases. Question 1 - 40% : This question tests you on the theory side of the module - the construction of a grammar, a shift-reduce parsing table and how to use it to parse strings in the target language of 3-valued logic expressions. Consider the following grammar for the language: W -> W & P | W + P | ! W | P P -> 0 | 1 | ? | V Here W,P, and V are non terminals, & (and), + (or), ! (not), 0 (false) , 1 (true), ? (unknown) are terminals. V represents a set of propositional variables (like variables in programming). You need to complete a concrete version of the grammar above, tailored to yourself, by stating two more rules which define V by naming exactly 2 propositional variables. These 2 variable names must be the characters taken from the first 2 distinct letters of your surname. For example, my surname is \mccluskey" hence the final 2 rules in my 3-valued logic grammar would be: V -> m | c Add your final 2 rules to the grammar, making 10 rules altogether. Now carry out the following tasks using the methods shown in the lectures: (i) use your grammar to generate (a) a derivation sequence and (b) the parse tree of a chosen string in your language which has at least 5 characters and contains both your propositional variables. For example, such a string in *my* language might be \1 & m + ! c" as it has 6 characters and contains m and c; (ii) translate your grammar into a shift reduce parsing table; (iii) apply your parsing table to show how it correctly parses your chosen string in part (i). Choose another string with characters from the alphabet of your grammar, which is not in the language, and show how a parse for that string would fail. In each case the answer consists of a stack trace of your parser. Question 2 - 60% : JavaCup is a parser-generator that works by creating an S-R parsing table, using the theory and techniques you use in Question 1. (i) Encode the same concrete grammar as you used in Question 1 into the implementation of Javacup on the Department’s Linux machines. Thismeans you must produce scanner.java and parser.cup files (note in particular the grammar’s syntax must be turned into JavaCup’s syntax). Your scanner.java and parser.cup files must implement a parser that inputs a string W and builds up a parse tree of W. It outputs the tree if the string is correct syntax, or outputs the phrase \syntax error" otherwise. Show its correct operation by running it on a file containing your chosen string from question 1(i). Also, show its correct operation by running it on a file containing you string not in the language, from Question 1(iii). (ii) Build on your answer to 2(i) by turning your parser into an \expression language" interpreter as follows. A program in your expression language (denoted by non-terminal E below) must consist of a sequence of either of two types of statements - assignment (denoted by non-terminal AS below) and write (denoted by non-terminal WS below). To specify the concrete syntax, your grammar in Question 1 would be augmented with the new rules: E -> WS | AS | WS ; E | AS ; E WS -> write W AS -> V = W Here new terminal symbols are \;" , \=", and \write". The \;" in the language acts as a statement separator - that is it separates statements rather than terminates them. The \=" is the assignment symbol. The \write" statement has the effect of writing out the value of the expression following it to the output (the terminal). A concrete, example program in the language (from the grammar generated using my name) is as follows: m = ? & 1 + 1 ; c = m + ? ; write 1 & m + ! c You must create the expression language interpreter by using java commands to build up the parse tree within the grammar, as you did in Question 2(i), then by passing the tree to a simple interpreter written in Java’s action code which interprets the program. Hence if the program above is input, it would output \true" (i.e. the value 1 in the grammar’s syntax). To interpret each expression W in 3-valued logic, you must use the following truth table axioms in your simple interpreter: 1 & 1 = 1 1 & ? = ? 1 & 0 = 0 ? & 1 = ? ? & ? = ? ? & 0 = 0 0 & 1 = 0 0 & ? = 0 0 & 0 = 0 1 + 1 = 1 1 + ? = 1 1 + 0 = 1 ? + 1 = 1 ? + ? = ? ? + 0 = ? 0 + 1 = 1 0 + ? = ? 0 + 0 = 0 !1 = 0 !? = ? !0 = 1as well as using left associativity to dissambiguate the interpretation of expressions such as \1 & m + !c " (iii) Add extra features to your language, such as more variable names, bracketed expressions \( W ) ", more logical operators such as "implies", and an error detector that gives a helpful error message when errors are spotted. This coursework must be undertaken individually. The deadline for handing in the work is published on your online coursework schedule. You must hand in a HARD COPY of: QUESTION 1. The grammar, the derivation sequence and parse tree, the derived FSM, the derived shift-reduce parsing table, and proof using a stack trace that the correct example is parsed, and the incorrect example does not. QUESTION 2. i) print outs of parser.cup and scanner.java defining your parser for part (i) ii) print outs of parser.cup and scanner.java defining your interpreter for parts (ii) / (iii) iii) print outs of several test programs (similar to the example program in my language above) and screen shots of their execution. The examples should show that the correct operation of the parser for part (i), and the correct operation of the interpreter in parts (ii) / (iii). iv) A short written report including SECTION 1: a statement of WHAT you have achieved in Question 2; and SECTION 2: documentation describing HOW you have achieved it. Here you must explain in your own words how the interpreter code you have written works, any deficiencies of it, and any future extensions you could achieve given more time. v) Additionally, you must hand in to the digital dropbox the following: your two versions of parser.cup and scanner.java, and the test files. This must allow me to generate an interpreter using JavaCup and validate your tests. NOTE: You must use the version of Javacup shown in the tutorials, and base your solution on the examples given out in the lecture / tutorials. Marking Criteria and Scheme: The coursework assesses the following ability outcomes of the module: Knowledge (4) and (5), Ability (8). It also, in part, examines outcome Ablity (6). It makes up 50 per cent of your 20 credit module. QUESTION 1 Criteria: Correctness of your grammar, FSM, parsing table, stack trace of the example parses and documentation. Marking Scheme: pass: you have at least demonstrated you can translate a grammar into a FSM and then a parsing table, though you may have made some major mistakes. over 50 %: your parsing table creation is faithful with respect to the grammar, (there are some errors in what you have produced, but the method is sound) and you have made a reasonable attempt at generating a stack traceof the example parse and counter-example. over 60 %: as above, but your parsing table is created correctly with respect to the grammar. You have made several minor errors. over 70 % : as above, but your grammar is correct and leads to a conflict free parsing table. You may have made one or two minor errors. over 90 %: your grammar is correct and leads to a conflict free parsing table, your parsing table is correct, and the stack trace of the example/counterexample parse is correct, and everything is clear and excellently documented. QUESTION 2 Criteria: the correctness and clarity of your code and explanations; the appropriateness and amount of the features you have implemented in your expression language interpreter; the comprehensiveness of your testing strategy. (NB If you cannot get something to work, you may still get marks by explaining your method.) Marking Scheme: to pass: you need to implement and test successfully the parser, and have made an attempt at the interpreter, and included a statement of achievement and explanation of your method for (iii). over 50%: as above, but with clear documetation, and a good attempt at implementing the interpreter, showing a reasonable testing strategy. over 60 %: as above, but you have implemented the interpreter correctly, with good, clear documetation addressing, showing a good testing strategy. over 70%: as above, but your work must be distinctive in some way e.g. you will have implemented most / all the features in 2(iii), your documentation and explanations are excellent etc Extra marks will be given, the more extra features you implement.