Assignment title: Information

CIS2380: Coursework 2, 2016 Question 1 - 50% This question tests you on the theory side of the module - the creation of a grammar, a shift-reduce parsing table and how to use it to parse strings in a target language. The specification of your target language (MyL) is as follows: The alphabet is four symbols: (1) first letter of your first name (2) the last letter of your last name (3) the first letter of your last name (4) the character $. For example, my name is "thomas leo mccluskey" so, in my case, the alphabet for MyL is (t,y,m,$). Clearly the alphabet for your language is likely to be different1. Strings of your language must satisfy the following constraints. The first is that there is exactly one $ in any correct string, and this is always the last symbol in the string. The string before the $, which must be non-empty, we call a correct expression, defined as follows. Every correct expression is • a sequence of one or more of the letter (3), bracketed by the first (1) and last letter (2), OR • a correct expression bracketed by the first (1) and last letter (2), OR • a sequence of correct expressions. No other strings are allowed. Hence, the first (1) and last (2) letters act like brackets - for every letter (1) in the string, there must be a unique corresponding matching last letter (2). So for my language MyL, examples of correct strings in the language are (separated by semi colons): tmy$ ; tttmyyy$; ttmmmyttmyytmyy$; ttmmmytmyy$; tmytmy$; tttmyttmmyyyy$ Strings of the alphabet which are NOT in the language include: ttmyyty$ (no "m" inside the last "ty"); ttmmy$ missing "y"); tttmyyyyttmmy$ (the fourth "y" does not have a corresponding starting "t"). ASSIGNMENT: You are required to (a) create an unambiguous grammar which generates exactly the language described above using your name (10%); 1If your name is like "nina nolan" and does not give 3 distinct letters, then choose alternative letter(s) in your name, so if you were named as in the example you could use (n,o,a,$) as your alphabet. generate a SR parsing table from the grammar (30%); apply your parsing table to show how it correctly parses a simple correct string of your choice, and how it rejects an incorrect string made up of symbols from the alphabet. (10%). Note that your grammar should be small, consisting of about 6 – 10 production rules. Question 2 - 50% JavaCup is a parser-generator, and works by creating a shift-reduce parsing table using the theory and techniques you use in question 1. In directory on Ouranos: /local/public/cas380/coursework16 you will find the specification of a simple programming language "LPL". This comprises of a syntax scanner and a JavaCup specification with an interpreter in its action code. LPL has integer variables, an assignment statement, a repeat statement, and a print statement. Read through this commented specification and make sure you understand fully how LPL works. Use JavaCup to create an interpreter for LPL in the usual way. In that directory there is an example program "input program1" that can be run using the JavaCupcreated interpreter, as follows: x = 23; repeat x = x-1; y = x*x; print(x,y) until x; print(x) The ";" in LPL acts as a statement separator - that is it separates statements rather than terminates them, unlike the ';" in C,C++,Java etc where it is a statement terminator. LPL is very basic - its scanner is poor in that variable names can only be a single letter x,y, or z, and it will accept mis-spelt keywords etc. Its parser and interpreter are lacking in structured code features and error recovery. ASSIGNMENT: create your own interpreted programming language called MYPL, using LPL as a base. In other words starting from the components of LPL, build up your own language and interpreter. Examples of features that you may add to LPL to create your own MYPL are: (1) long and more varied names for variables (2) more interesting expressions using binary operators such as ==, > and < (3) an 'if' selection statement (4) a 'switch' selection statement (5) a 'while' loop statement (6) a 'for' loop statement (7) block structuring using { .. } or begin .. end (8) better error recovery: for example, if a syntax error occurs in parsing, your code should point out what the nature of the error is and/or where it occurred. This list is not exhaustive - you may add your own features. This coursework must be undertaken individually. The deadline for handing in the work is 4pm May 6th, 2016. You must hand in a HARD COPY of: QUESTION 1. The grammar, 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 final language. ii) print outs of several test programs and screen shots of their execution showing the use of all the new features in your language and showing the correctness of your code. For example, if you have implemented an 'if' statement, the test programs should show that the 'if' branches execute as expected. iii) 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 code you have added to LPL works, any deficiencies of it, and any future extensions you could achieve given more time. iv) Additionally, you must hand in to the digital dropbox the following: your new language's parser.cup, scanner.java and test files. This must allow me to generate an interpreter using JavaCup and validate your tests. 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 parse and documentation. Marking Scheme: pass: you have at least demonstrated you can create a grammar and translate it 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 you produce, (there may be S-R conflicts, and some errors, but the method is sound) and you have made a reasonable attempt at generating a stack trace of the example parse and counter-example. over 60 %: as above, but your grammar is correct, your parsing table is created correctly with respect to the grammar but may have S-R conflicts. You may have some minor errors. over 70 % : as above, but your grammar is correct and leads to a conflict free parsing table. You may have some 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 of the features you have added to LPL; the number and complexity of features you have added to LPL; the comprehensiveness of your testing strategy. 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 at least 2 - 3 of the features (1) - (8), including a statement of achievement and explanation of your method for (iii). over 50%: as above, but with clear documetation addressing (iii), showing a reasonable testing strategy. over 60 %: as above, but you have implemented most of the features (1) - (8), with good, clear documetation addressing (iii), showing a good testing strategy. over 70%: as above, but your work must be distinctive in some way e.g. you will have implemented nearly all the features, your documentation and explanations are excellent etc Extra marks will be given, the more features you implement.