University of Arizona, Department of Computer ScienceCSc 453 — Assignment 2 — Due Fri Oct 2, 23.59 — 10%Christian CollbergSeptember 26, 20091 IntroductionYour task is to write a syntactic analyzer for the language Luca. Your program should be named luca parse.luca parse reads a source program, writes sy ntactic error messages or (if there are no errors) an abstrac tsyntax tree (in XML format) on standard output.$ luca_parse expr1.luc > expr1.luc.outThe result is a tree in XML format:PROGRAM P;BEGINWRITE a+ b ;END .⇒< block >< PROGRAM name ="P" pos ="1" >< DECLNULL pos ="2" / >< STATS pos =" 3 " >< WRITE pos =" 3 " >< BINARY op = " PL US " pos =" 3" >< VARREF ident =" a " pos = "3 " >< DESNULL pos = "3 " /></ VARREF >< VARREF ident =" b " pos = "3 " >< DESNULL pos = "3 " /></ VARREF ></ BINARY ></ WRITE >< STATNULL pos ="4" / ></ STATS ></ PROGRAM ></ block >For syntactically incorrect Luca programs no abstr act syntax tree is produced, just an error message.Appendix A gives the complete syntax of Luca. Appendix B gives the complete abstract syntax you shouldproduce.2 Luca Syntactic ErrorsInstead of printing error messages in human readable form, lucaparse generates errors in a n XML format:<SYNTAX_ERROR pos="3" expected="]" found=","/><SYNTAX_ERROR pos="2" expected="(,-,FLOAT,NOT,TRUNC,char,identifier,integer,real,string" found="VAR"/>1The list of expected tokens are printed in lexicographically sorted order!You don’t have to do any error recovery. We won’t test any of your output that appears after the firstsyntactic error message.3 Implementation Notes• This assignment can be coded in Java, C, or C++. If you want to use another language, askme first.• Make sur e that your Makefile is working properly. The TA will do the following, a nd nothing else:$ make$ luca_parse test1.luc > test1.luc.outIn other words, if you’re coding in Java you must provide a shell script called lucaparse that callsJava with the appropriate parameters.• You cannot use yacc or any other similar parser generator for this assignment, eitherdirectly or indirectly. I expect you to construct the grammar by hand, compute FIRST sets byhand, and implement the parser by hand.• You should build your parser the way we’ve discussed in class, using a recursive descenttechnique. I f you try a nything else you will get 0 points.• See Sections 4.1.2 and 4.2.4 of the text-book for a description on how to adapt top-down parsers tobuild abstract syntax trees.4 Submission and Assessment• The deadline for this assignment is Fri Oct 2, 23.59. It is worth 10% of your final grade.• You should submit the assignment electronically to d2l.arizona.edu.• You can work alo ne or in tea ms of 2. You must submit a README file that lists the members of yourteam and how much each team member c ontributed to the assig nment.• If you work in a team you should only submit one copy of the assignment.• You can download 58 syntactically corret test cases from the class website: http://www.cs.arizona.edu/~collberg/Teaching/453/2009/Assignments/index.html. Each will give you one point if youget it right and 0 points if you get it wrong. No partial credits. We won’t check for the correctness ofline numbers.• You can download an additional 11 test cases that should generate an er ror. You get 2 points if youget it right and 0 points if you get it wrong. No partial credits. We won’t check for the correctness ofline numbers. We will ignore anything following the first error message.• You can se e some of the test cases in Appendix C You can get an additional 20 points from morecomplicated “secret” test cases, for a total of 100 points.• A large number o f Java classes for building abstract syntax tress have been provided for you. Use themor not, it’s up to you.2• Your electronic submission mu s t contain a working Makefile, and all the files necessary to build thelexer and parser. If your pro gram does not compile “o ut of the box you will receive zero (0) po ints.The TA will n ot try to debug your program or your makefile for you!Don’t show your code to anyone outside your team, don’t read anyone else’s code,don’t discuss the details of your code with anyone. If you need help with the assign-ment see the TA or the instructor.A Luca Syntaxhprogrami ::= ‘PROGRAM’ hidenti ‘;’ hdecl listi hblock i ‘.’hblocki ::= ‘BEGIN’ hstatseqi ‘END’hdecl list i ::= { hdeclarationi ‘;’ }hdeclarationi ::= ‘CONST’ hidenti ‘:’ hidenti ‘=’ hexpressioni |‘VAR’ hidenti ‘:’ hidenti |‘TYPE’ hidenti ‘=’ ‘ARRAY’ hexpressioni ‘OF’ hidenti |‘TYPE’ hidenti ‘=’ ‘RECORD’ ‘[’ [ hfieldlisti ] ‘]’ |‘PROCEDURE’ hidenti ‘(’ [hformal listi] ‘)’ ‘;’ hdecl listi hblockihformallisti ::= hformal parami { ‘;’ hformal parami }hfield list i ::= hfieldi { ‘;’ hfieldi }hformalparami ::= [‘VAR’] hidenti ‘:’ hidentihfieldi ::= hidenti ‘:’ hidentihstatseqi ::= { hstatementi ‘;’ }hstatementi ::= hdesignatori ‘:=’ hexpressioni |hdesignatori ‘(’ [ hactual listi ] ‘)’ |‘IF’ hexpressioni ‘THEN’ hstatseqi ‘ENDIF’ |‘IF’ hexpressioni ‘THEN’ hstat seqi ‘ELSE’ hstat seqi ‘ENDIF’ |‘WHILE’ hexpressioni ‘DO’ hstatseqi ‘ENDDO’ |‘REPEAT’ hstat seqi ‘UNTIL’ hexpressioni|‘LOOP’ hstat seqi ‘ENDLOOP’ |‘EXIT’ |‘WRITE’ hexpressioni | ‘WRITELN’ |‘READ’ hdesignatorihactuallisti ::= hexpressioni { ‘,’ hexpressioni }hexpressioni ::= hexpressioni hbin operatori hexpressioni |hunaryoperatori hexpressioni |‘(’ hexpressioni ‘)’ |hintegerliterali | hchar literali | hreal literali | hstring literali | hdesignatorihdesignatori ::= hidenti { hdesignator’i }hdesignator’i ::= ‘[’ hexpressioni ‘]’ | ‘.’ hidentihbinoperatori ::= ‘+’ | ‘−’ | ‘∗’ | ‘/’ | ‘%’ | ‘AND’ | ‘OR’ | ‘<’ | ‘<=’ | ‘=’ |‘#’ | ‘>=’ |‘>’hunary operatori ::= ‘−’ | ‘NOT’ | ‘TRUNC’ | ‘FLOAT’This grammar is highly ambiguous. Here are the relevant operator precedence rules:3precedence operator arity associativitylow +, - binary left associative*, /, % binary left associativeAND,OR binary left associative<, <=, #, >, >=, = binary left associativehigh NOT, TRUNC, FLOAT, -unaryunary right associative4B Abstract SyntaxBelow are the nodes in the Luca abstract syntax tree , in the format they are generated by luca