COMP2022Assignment2课业解析题意：考察LL（1）文法的相关知识及实现基于预测分析表方法的LL（1）语法分析器解析：
第一题分别要求列出给定文法G的终止符、非终止符、最左推导字符串及构建其语法树；第二题用泵引理证明文法是否非正则；第三题证明给定文法不是LL（1）文法，提示：存在左递归；第四题消除左递归和回溯，构造等价的LL（1）文法；第五题构造预测分析表；第六题编程实现预测分析表表驱动的LL（1）文法分析器；第七部分实现附加功能，判断出一些类型的语法错。符号串的分析流程图：
第一题的最左推导：涉及知识点：LL(1)文法、预测分析表、泵引理更多可加微信讨论
微信号：aaaapple1208pdf
COMP2022: Assignment 2Due: 23:59pm Sunday 20th October 2019 (end week 10)1 The grammar G [10%]Consider the following grammar G, which represents a fragment of a simple programming language:S ! SL j “L ! A; j E; j C;E ! (EBE) j N j VA ! let V =EC ! while E do S j while E do S else SB ! + j – j * j >V ! x j y j zN ! ND j N0 j DD ! 1 j 2 j 3 j 4 j 5 j 6 j 7 j 8 j 9 (you can denote this [1-9])In this assignment, you can ignore whitespace in the strings (i.e. spaces and newlines are not part of thelanguage, but should be used for the sake of readability).i) List the variables of Gii) List the terminals of Giii) Give a leftmost derivation of the string let x=(y-20); while 1 do y;;iv) Draw a parse tree for the string: let x=(y-20); while 1 do y;;2 Prove that L(G) is not regular [5%]Prove that the language generated by G is not a regular language, by contradicting the Pumping Lemma.3 Prove G is not LL(1) [5%]Prove that G is not an LL(1) grammar.4 Find an equivalent LL(1) grammar G′ [10%]Find an equivalent grammar G′ which is LL(1), by using the grammar transformation techniques shownin lectures, or otherwise. Describe the process and show your working.15 LL(1) parse table [15%]Complete the LL(1) parse table for G′. Describe the process and show your working, including:1. FIRST sets for all the production rules of G′2. FOLLOW sets for variables of G′ only if they are needed6 Implementation [25%]Implement a program which parses strings using an LL(1) table driven parser, using the table youdetermined for G′ in the previous exercise. You may use Python, Java, C, C++, or Lisp. If you’d like touse a different language then please check with us frst.• Input:The frst command line argument is the flename of a fle containing the string of characters to test.• Output:1. Print a trace of the execution, showing the steps followed by the program as it performs theleft-most derivation. This should look similar to parsing the string through a PDA. An exampleof this is given in the appendices.2. After parsing the whole input fle, print ACCEPTED or REJECTED, depending on whether or notthe string could be derived by the grammar.3. If there is a symbol in the input string which is not a terminal from the grammar, the programshould output ERROR_INVALID_SYMBOL (This could be during or before trying to parse theinput.)• All whitespace in the input fle should be ignored (line breaks, spaces, etc.). The output will be easierto read if you remove the whitespace before starting the parse.• Examples of the program output syntax are provided in the appendices.7 Extension [30%]You may pick one of the following extensions to improve your parser. Any one of the following ideaswould be sufcient (do not implement more than one). They are listed roughly in order of increasingdifculty/effort, but are worth the same marks:a) Use the FIRST and FOLLOW sets to implement an error recovery feature. This should give the usersuggestions on possible corrections which could change strings which could not be derived in G′ Forthis extension you need to:• Implementation: If a second command line argument error is given, then instead of rejectinga string that is not in the language, it should make suggestions about how to correct it. Theuser chooses one of the options, then the program should continue the parse. Some examplesare provided in the appendices. This should be included in the code you submit to PASTA.• Report: Explain how your error recovery feature uses the FIRST and FOLLOW sets to work,and show some useful examples.b) Extend your program to be able to evaluate the input program, if a second command line argumenteval is given. Some examples are provided in the appendices, and some supplementary material willbe provided on Ed to explain the algorithm needed to build and evaluate the parse tree. This shouldbe included in the code you submit to PASTA.• Implementation:2– Build a parse tree as it performs the leftmost derivation.– Evaluate that parse tree.• Report: Give some examples of usagec) Implement a second parsing algorithm. You could implement:• the CYK algorithm, or• a LR(1) parser• Note: a recursive descent parser would not be sufcient (too easy).You will need to submit your code to PASTA, as well as including some details in your reportcomparing your second parser to the frst one (what are the advantages and disadvantages of thisparser compared to the LL(1) table driven parser.)d) Something else? Check with your tutor to see if they think it’s appropriate.8 Submission detailsDue 23:59pm Sunday 20th October 2019. The late submission policy is detailed in the administrivia lectureslides from week 1. Please notify us if you intend to make a late submission, or if you believe you will notbe able to submit, to make it easier for us to support you.8.1 Canvas submissionYou must submit a report as a single document (.pdf or .docx) to TurnItIn via Canvas. The written partsof the report must be text, not images of hand-writing. Any diagrams can be images, of course. The reportshould include:• Task 1 – 5: Your answers, working, and explanations• Task 6: A description of the testing runs you used, including examples of the output. Show enoughto convince the marker that your testing was comprehensive• Task 7: A description of your extension, including documentation about how to use it and someexamples of input/output8.2 PASTA submissionExact submission details (such as requirements on the name of the program) will be provided next week.• Task 6: submit your source code.• Task 7: submit your source code, if relevantThe visible tests for task 6 (the implementation) will be just enough to show you that you have gotthe input/output syntax correct. It will not test the correctness of your program (you are expected to testthat yourself!)There will be no automatic testing of any extra functionality you added as an extension.8.3 Marking criteriaThe weight of marks for each question are noted next to each question.• Tasks 1 – 5: The marks will be roughly evenly divided between correctness, and on your workingand explanations.• Task 6: The marks will be roughly evenly divided between automatic marking (for correctness) andhand marking (based on your testing, the quality of your explanations, code, etc.)• Task 7: The extension will be hand marked.39 Appendices9.1 Example of string derivationsSuppose we had a program which parsed this grammar fragment (your grammar will be different!):E ! (F ) j T (start variable)F ! +EET ! 0 j 1 j 2 j 3Example 1: For the input:✞ ☎(+12)✝ ✆The output might look like this (note: it doesn’t need to line up neatly):✞ ☎(+12)$ E$(+12)$ (F)$+12)$ F)$+12)$ +EE)$12)$ EE)$12)$ VE)$12)$ 1E)$2)$ E)$2)$ V)$2)$ 2)$)$ )$$ $ACCEPTED✝ ✆Example 2: For the input:✞ ☎( +13 )✝ ✆The output is the same, because we ignore all the whitespace:✞ ☎(+12)$ E$(+12)$ (F)$…ACCEPTED✝ ✆Example 3: For the input:✞ ☎(++3)✝ ✆We get:✞ ☎(++3)$ E$(++3)$ (F)$++3)$ F)$++3)$ +EE)$+3)$ EE)$REJECTED✝ ✆It is rejected because there would be no entry in the parse table for (E; +).49.2 Extension option A (error recovery)Reminder: your code should only run the extension if a second command line argument error is given.Otherwise it should behave normally.This appendix shows a few examples of what using an error recovery feature might look like. Youroutput and features do not need to be identical to these examples, it is only a guideline to give you someideas.Suppose we had a program which parsed this grammar fragment (your grammar will be different!):E ! (F ) j T (start variable)F ! +EET ! 0 j 1 j 2 j 3There are three key steps to implementing error recovery. More marks will be awarded to more useful/sophisticated features.9.2.1 Identifying the errorThe frst step is to be able to describe the error. Examples:✞ ☎(+1+)$ E$(+1+)$ (F)$+1+)$ F)$+1+)$ +EE)$1+)$ EE)$1+)$ VE)$1+)$ 1E)$+)$ E)$Error: got +, but expected {0, 1, 2, 3, (}.REJECTED✝ ✆✞ ☎1)$ E$1)$ T$1)$ 1$)$ $Error: got ), but expected $.REJECTED✝ ✆9.2.2 Recovering with user interventionThe next step would be to give the user the op
tion to correct the error and allow the derivation to continue.For example, you might have an option to delete the next input symbol:✞ ☎(+123)$ E$(+123)$ (F)$+123)$ F)$+123)$ +EE)$123)$ EE)$123)$ VE)$123)$ 1E)$23)$ E)$23)$ V)$23)$ 2)$53)$ )$Error: got 3, but expected {)}.Delete input? Y)$ )$$ $ACCEPTED (+12)✝ ✆It’s a bit more powerful if we also allow the user to insert a symbol:✞ ☎(+12$ E$(+12$ (F)$+12$ F)$+12$ +EE)$12$ EE)$12$ VE)$12$ 1E)$2$ E)$2$ V)$2$ 2)$$ )$Error: got $, but expected {)}.Add input? ))$ )$$ $ACCEPTED (+12)✝ ✆Better still, would be to allow the user to choose to delete or insert (so they can replace a symbol)9.2.3 Making useful suggestionsYou might automatically suggest which is the ‘best’ correction. For example, you might have the programexplore each option automatically, then recommend the correction which leads to an accepted string usinga minimal number of changes. For performance reasons, it would be wise to limit the maximum numberof changes to some fairly small number (e.g. no more than 5 changes).69.3 Extension option B (evaluation)Reminder: your code should only run the extension if a second command line argument eval is given.Otherwise it should behave normally.9.3.1 Semantics of the language:• S := a sequence of one or more commands to execute.• E := an expression to evaluate, possibly including variables• (EBE) := apply the two expressions to some binary operator.– arithmetic is normal integer arithmetic (e.g. 5 – 3 is -2)– > := 1 if the inequality is true, 0 otherwise• N := a strictly positive integer.• V := a variable label.• let V = E; := assign the result of evaluating E, to V• E; := output (print) the result of evaluating E• while E do S; := as long as E evaluates to a non-zero number, do S• while E do S else S; := as long as E evaluates to a non-zero number, do the frst S. If E evaluatesto zero (possibly after some repetitions), do the second S.• If there is more than one expression in the program, they should be evaluated in order. The onlyoutput is the E; statements!9.3.2 Examples of output:Input Output Why(5+3); 8(5-3); -2let x=1; there is no E; statementlet x=1;x; 11;2; 12Statements are evaluated in orderlet x=3;while x do let x=(x-1); x;;2 1let x=3;while x do let x=(x-1); x;else 9;;2 1 9let x=3;while x do let x=(x-1); x;else 9;;4;2 1 9 4let x=5; let y=1;while (x>1) do let y=(x*y); let x=(x-1);;y;120 5! = 120let x=5;while (x>1) do let x=(x-1);;x;1 Variables are not scoped79.3.3 More information:In the resources section on Ed, in the category “Supplementary Material”, there are some resources to helpyou:• Slides explaining the concepts• A worked example of the process of building a parse tree following this algorithm• Some code examples of evaluating a parse tree for a simpler grammar (in Python, Java and C++)8
