CIS2380: Coursework 2, 2021 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 five symbols: (1) first letter of your first name (2) the last letter of your first name (3) the first letter of your last name (4) the last letter of your last name (5) the character $. For example, assuming a name like “thomas leo mccluskey” so, in this case, the alphabet for MyL is (t,s,m,y,$). 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 letters (2) and/or (3) in any order, bracketed by the first (1) and last letter (4), OR • a correct expression bracketed by the first (1) and last letter (4), OR • a sequence of correct expressions. No other strings are allowed. Hence, the first (1) and last (4) letters act like brackets - for every let- ter (1) in the string, there must be a unique cor- responding matching last letter (4). So for the abovementioned language MyL, examples of cor- rect strings in the language are (separated by semi colons): tmssy$; tttsmsyyy$; ttmmsmyttmyytmsyy$; ttmmmytssyy$; tmytmsy$; tttsyttmsmyyyy$ Strings of the alphabet which are NOT in the lan- guage include: ttmyyty$ (no “m” or “s inside the last “ty”); ttmmy$ (missing “y”); tttmyyyyttmmy$ (the fourth “y” does not have a corresponding starting “t”). 1If your name is like “nina nolan” and does not give 4 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,l,$) as your alphabet. ASSIGNMENT: You are required to (i) create an unambiguous context-free grammar which gener- ates exactly the language described above using your name; (ii) use your grammar to generate (a) a derivation sequence and (b) the syntax tree of a chosen string in your language which uses all 5 let- ters of the alphabet; (iii) generate an SR finite state machine and then parsing table from the grammar; (iv) apply your parsing table to show how it cor- rectly parses the chosen string used in part (ii). Note that your grammar should be small, consist- ing of only about 6 – 8 production rules. Question 2 - 50% INTRODUCTION: JavaCup is a parser-generator, and works by creating a shift-reduce parsing table using the theory and techniques you use in Ques- tion 1. In directory on Ouranos: /local/public/cas380/coursework20 you will find the specification of a simple program- ming language TLM (TLM will be available on Brightspace as well). This comprises of a syntax scanner and a JavaCup specification with an inter- preter in its action code. TLM is an extremely sim- ple programming language: it has 3 integer variable names (x, y and z), simple boolean expressions, an assignment statement, a do while statement, a print statement, and a simple user-defined function fa- cility. Study the commented specification and make sure you understand fully how TLM works. Use JavaCup to create an interpreter for TLM in the usual way. In that directory there is an example program “input program1” that can be run using the JavaCup-created interpreter, as follows: start; function; do x = x-1; y = x*x; print(x,y); while x > 10 ; end; x = 23; call; x=15; call; finish; TLM is very basic - its parser and interpreter are lacking in data types, structured code features etc. TLM only checks the first letter of each keyword. ASSIGNMENT: create your own more advanced interpreted programming language called MYPL. You must do this using the already written TLM as a base. In other words starting from the com- ponents of TLM, build up your own language and interpreter. Your language must have the following enhancements. (*i*) Long variable names: rather than only x, y or z, your language should allow a range of variable names to be used. (*ii*) Declarations: your lan- guage must only allow variable names to be used if they have been previously declared (*iii*) Key- words: keywords such as while end etc should be parsed only if they are spelled properly (*iv*) Func- tion: The function declaration structure in TLM is extremely basic: e.g. only one function can be de- clared, it has no name, and it must be declared at the beginning of the program; and the function has no parameters or local variables. Extend the func- tion declaration to overcome some of these limita- tions. Rules: This coursework must be undertaken individually. The deadline for handing in the work is 04-05-2021 23:59 BST. You must hand in for Question 1: The grammar, the derivation sequence, the syntax tree, the derived FSM, the derived shift-reduce parsing table, and proof using a stack trace that the correct example is parsed. You must hand in for Question 2: i) the two files parser.cup and scanner.java defining your final language. This must allow me to gener- ate an interpreter using JavaCup and validate your tests. ii) 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. If you do not include tests with asso- ciated screen shots of the new features of MYPL, they will be assumed not to work, iii) A written report including the following: a statement of WHAT you have achieved in Ques- tion 2; and documentation describing HOW you have upgraded TLM for Question 2. Here you must explain in your own words how the code you have added to TLM works, any deficiencies of it, and any future extensions you could achieve given more time. YOUR SOLUTIONS MUST BE HANDED IN ELECTRONICALLY VIA BRIGHTSPACE. Marking Criteria and Scheme: The coursework assesses the following ability outcomes of the mod- ule: Knowledge (4) and (5), Ability (8). It also, in part, examines outcome Ability (6). It makes up 50 per cent of your 20 credit module. QUESTION 1 Criteria: Correctness of your gram- mar, FSM, parsing table, stack trace of the example parse and documentation. Marking Scheme: i) (10%); ii) (10%); iii) (24%); iv) (6%); To pass: you have at least demonstrated you can create (as well as use) 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 SR 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 SR 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 85%: your grammar is correct and leads to a conflict free parsing table, your parsing table is cor- rect, and the stack traces of the example/counter- example parse are 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 TLM; the num- ber and complexity of features you have added to TLM; the comprehensiveness of your testing strat- egy. If you cannot get anything to work, you may still get marks by explaining your method. Marking Scheme: to pass: you need to imple- ment at least one of (*i*), (*ii*) and (*iii*), submit- ting screen shots proving this, and include a state- ment of achievement and explanation of how you achieved this extension. over 50%: as above, but you have seriously at- tempted all three of (*i*), (*ii*) and (*iii*), with clear documentation, showing a reasonable testing strategy. over 60%: you have implemented all three of (*i*), (*ii*) and (*iii*), with clear documentation, show- ing a reasonable testing strategy. You have at- tempted part (*iv*), and overall have written good, clear documentation, showing a good testing strat- egy. over 70%: as above, you have implemented an en- hanced function feature, and your documentation and explanations are excellent. Extra marks will be given, the more function features you implement.







































































































































































































学霸联盟