University of Arizona, Department of Computer ScienceCSc 453 — Assignment 3 — Due Wed Oct 28, 23.59 — 10%Christian CollbergOctober 11, 20091 IntroductionYour tas k is to write a semantic analyzer for the language Luca. Your program should be named luca sem.luca sem reads a source program, does lexical, syntactic, and semantic analys is and writes semantic errormessages to standard error. A semantically correct program will produce no output.• Your tree-walk evaluator should be programmed in an applicative style. I.e., all information should bepassed around the tree using synthesized, inherited, and threa ded attributes; there should be no globalvariables. In particular, you should use symbol tables and environments to represent scope information,as shown in lectures. The tree-walk evaluator should make exclusive use of recursion; iteration is notallowed. If you do make us e of iteration and global data, points will be deducted.• This assignment can be coded in the language of your choice as long as it can be compiled and run onlectura.• Make sure that your Makefile is working properly, and that luca sem is called exactly as in theexample above.• You should not exit the semantic analyzer after the first error. Rather , you should ge nerate as completeerror messages as poss ible.• You should avoid cascading error messa ges. Consider, for example, the expre ssion x + (y + 3.14) wherex and y are both declared as integers. The subexpression (y + 3.14) should generate a type error sinceintegers can’t be a dded to reals. Howe ver, x + (. . .) should not produce any “extra” messages as aresult of the subexpression being erroneous.• The error messages s hould be of the form<SEMANTIC_ERROR pos="3" message="Identifier expected" argument="X"/>and should be written to standard output.• The syntax is the same as in the previous assignment.2 Semantic rules• Identifiers have to be decla red before they are used.• Identifiers cannot be redeclared in the same scope.• There are four (incompatible) built-in types, INTEGER, REAL, BOOLEAN and CHAR.1• The identifiers TRUE and FALSE are predeclared in the language.• Identifiers are case sensitive.• Here are the type rules for Luca expressions :Left Operators Right ResultInt ‘+’, ‘−’, ‘∗’, ‘/’, ‘%’ Int ⇒ IntReal ‘+’, ‘−’, ‘∗’, ‘/’ Real ⇒ RealInt ‘<’,‘<=’, ‘=’, ‘#’, ‘>=’, ‘>’ Int ⇒ BoolReal ‘<’,‘<=’, ‘=’, ‘#’, ‘>=’, ‘>’ Real ⇒ BoolChar ‘<’,‘<=’, ‘=’, ‘#’, ‘>=’, ‘>’ Char ⇒ BoolBool ‘AND’, ‘OR’ Bool ⇒ Bool‘NOT’ Bool ⇒ Bool‘−’ Int ⇒ Int‘−’ Real ⇒ Real‘TRUNC’ Real ⇒ Int‘FLOAT’ Int ⇒ Real• As seen from the table ab ove, Luca does not allow mixed arithmetic, i.e. there is no implicit conversionof integers to rea ls in an expressio n. For example, if I is an integer and R is real, then R:=I+R is illegal.• Luca instead suppo rts two explicit conversion operators, TRUNC and FLOAT. TRUNC R returns the integerpart of R, and FLOAT I returns a real number representation of I.• Note that % (remainder) is not defined on real number s.• For a constant expression, division by 0 isn’t allowed.• Arithmetic operations on characters are not allowed.• Variables are not allowed in constant expressions.• Only reals, integers, and characters can be read or written.• The left hand side of an assignment statement and the designato r in a READ statement must be writeable(i.e. a n L-value).• EXIT statements can only occur within LOOP statements.• A procedure’s formal parameters and local declarations form one scope, which means tha t it is illegalfor a procedure to have a formal parameter and a loc al variable of the same name. Parameters arepassed by value unless the formal para meter has been declared VAR. Only L-valued expre ssions (suchas ‘A’ and ‘A[5]’) can be passed to a VAR formal.• The assignment A:=B is illegal if A or B are records or arrays.• Procedures can be nested.3 Context ConditionsBelow are the er ror conditions you need to check, organized by AST node. In some cases the order in whichyou check the conditions matters, particularly if you want to generate the same messages as I do! The reasonis that we want to avoid cascading error messages — the test you perform first is more likely to produce anerror message than one you perform later.2• At the end of semantic analysis I sort all my error messages lexicographically. If you do the same we’remore likely to generate the same sequences of errors.DECL:An identifier can only be declared once in ea ch scope. A procedure’s formal parameters and localdeclarations form one scop e . If ID is declared more than once, issue this error message:<SEMANTIC_ERROR pos="..." message="Multiple declaration" argument="ID"/>VARDECL,FIELDDECL,FORMALDECL:1. T he type name must be declared:<SEMANTIC_ERROR pos="..." message="Identifier not declared" argument="TypeName"/>2. And, if the type name is declared, it has to be declared to be a type:<SEMANTIC_ERROR pos="..." message="Type identifier expected" argument="TypeName"/>CONSTDECL:1. T he type name must be declared:<SEMANTIC_ERROR pos="..." message="Identifier not declared" argument="TypeName"/>2. And, if the type name is declared, it has to be declared to be a type:<SEMANTIC_ERROR pos="..." message="Type identifier expected" argument="TypeName"/>3. And, if it’s declare d a type, it has to be declared a scalar type (integer, character, real, boolean):<SEMANTIC_ERROR pos="..." message="Scalar type expected"/>4. I f the declared type is OK, you need to check that the expression is of the s ame type:<SEMANTIC_ERROR pos="..." message="Wrong expression type"/>5. Regardless of the type checks above, the expre ssion has to be constant-valued:<SEMANTIC_ERROR pos="..." message="Constant expression expected"/>ARRAYDECL:1. T he type name must be declared:<SEMANTIC_ERROR pos="..." message="Identifier not declared" argument="TypeName"/>2. And, if the type name is declared, it has to be declared to be a type:<SEMANTIC_ERROR pos="..." message="Type identifier expected" argument="TypeName"/>3. T he array size must be of type integer:<SEMANTIC_ERROR pos="..." message="Integer expression expected"/>4. Regardless, of its type, the array size must be a co nstant expression:<SEMANTIC_ERROR pos="..." message="Constant expression expected"/>3ASSIGN:1. T he left