Scala Assignment - Syntax Analysis for HasLang (comp3000-haslang.zip) using build.sbt. Please read the Assignment Instructions.pdf carefully and Work on SyntaxAnalysis.scala & SyntaxAnalysisTests.scala files inside the src folder. You will see //FIXME commands in those two files. There is 42 tests need to be passed (Already 5 tests have been passed, so 37 left). Solve the code inside SyntaxAnalysis.scala file and also have to write my own tests inside the SyntaxAnalysisTests.scala file. Please use VS Code to do the assignment. I have also attached a zip file (Errors - VS Code Terminal.zip) which contains all the screenshots of the failed tests after running the code bundle on VS Code Terminal.
Assignment Instructions Syntax Analysis Marks breakdown: • Code: 90% • Your unit tests: 10% Overview This assignment asks you to develop a lexical analyser, parser and tree builder for a simple functional programming language called HasLang. We will build on these components in assignment three to complete a full implementation of a subset of this language. Building this implementation will give you insight into the way that programming language implementations work in general, as well as specific experience with how functional language programs are written, how they are compiled, and how they are executed. This kind of task often arises in programming situations other than language implementation. For example, many applications have configuration files that are written in simple languages. The application must be able to read these files reliably and understand their structure, just as a compiler must read program files and understand them. HasLang HasLang is a language that contains elements from lazy functional languages such as Haskell, Clean and Miranda; it uses a Haskell-like syntax. The description here is a brief overview of the HasLang language. Aspects such as checking the validity of names or types and translating the program into an executable form are beyond the scope of syntax analysis and hence are not considered in this assignment. We will address some of this in Assignment Three. The basic unit of a HasLang program is the expression; there are no statements. In fact, a program is just a single expression. For example, here is a simple program that returns the result of a simple arithmetic operation: 2 + 3 * 4 When this program is run it will print the value of the expression: the number 14. Let expressions are used to build programs out of smaller expressions. A let expression is the let keyword followed by one or more definitions, followed by the in keyword and a single expression. The idea is that the definitions can give names to values and functions. The value of a let expression is given by its final expression, which can use the defined names. For example, here is a program consisting of a let expression that uses two values: let a :: Int = 5; b :: Int = a + 1 in a * b The definitions in a let expression are separated by semicolons. This means the last definition and the body expression are not terminated by semicolons. This program will print the result of multiplying a by b, so 30 will be printed. (The name a can be used in the definition of b since b is defined later, but that is a name analysis issue, so we don't need to worry about it here.) There are no assignment statements, so the value bound to a particular occurrence of a name cannot be changed. All variable declarations (which are also called "bindings") must include their type. In the example above they are both integers (using :: to specify type). Some of the types are Int, Bool, and the type of a function which takes a value and returns a value (for example, the type of a function that takes an integer and returns a boolean is Int -> Bool). Definitions can also define functions. For example, here is a program that defines a value and a function, and calls the function passing the value as a parameter: let x :: Int = 100; inc :: Int -> Int = \a :: Int -> a + 1 in inc x } This program will print 101. Parameter passing is not done with parenthesis as in C/C++/Java/Scala, it is done simply by putting the parameter to the right of the function name as above. Functions in HasLang are defined in the very same way as variables, in fact it is best to think of them as variables which contain functions rather than primitive values. In the example above, inc's value is an anonymous function; the notation for this is a lambda (\) followed by the single argument parameter (with type), then an arrow and the body of the function. So inc in the above example is equivalent to the java method: int inc (int a) { return a + 1 } A lambda function is an expression that can be used by itself without becoming the value of a variable (as with inc). For example, the following expression evaluates to 4: (\a :: Int -> a + 1) 3 Functions can also be defined in a multi-line form; for example, here is a definition of the factorial function fac (which would need to be inside a let): fac :: Int -> Int fac 0 = 1. fac n = n * fac (n - 1) In this form, the first line provides the name and function signature. The second and third lines define how the function works by pattern matching on the left of =. (Note that the third line is separated by "." at the end of the second line. This is something that is not in Haskell but is needed here as we are not using an end-of-line token.) The second line indicates that if fac has a parameter value of 0 then the result will be 1. The third line, only used if the pattern match on the second line fails, instantiates a new variable n with the value of fac's parameter. There are no constraints on the pattern matching, so the third line will always succeed (providing the second line has failed). With the new variable n, the expression on the right of = is evaluated. Note that the brackets are required otherwise n * (fac n) - 1 would be evaluated. All of these programs have just one expression at the top level. In fact, that's the definition of a program in HasLang: a single expression. Expression forms are interchangeable as long as they have the correct type. E.g., anywhere we can put a number, can also take a block or some other kind of expression that evaluates to a number. For example, here is an artificial program that uses lets nested inside an arithmetic operation. (let a :: Int = 3 in a + 1 ) * (let b :: Int = 10 in b - 1 ) This program will print 36 since it is multiplying 4 times 9. We've seen a few different forms of expression: numbers, addition expressions, multiplication expressions and function call expressions. There are also other arithmetic operations, Boolean values, Boolean literals, relational operators and conditional expressions. There are also lists and tuples like in Scala and the list cons operator : (whereas in Scala it is ::). The complete syntax of HasLang is given below. Finally, HasLang comments are as in Haskell: either beginning with two dashes and continuing to the end of the line, or surrounded by {- and -}. -- The answer to life the universe and everything 42 {- I'm also a comment -} Types in HasLang We will have three basic types: • Int - integers • Bool - Booleans true, false • () - this is the Unit type, meaning no type, e.g. for a function that doesn't return anything The composite types we will use: • function types of the form: type -> type • list types - written with square brackets, e.g. [Int] for a list of integers • tuple types - written with round brackets and commas, e.g. (Int,Bool) Patterns in HasLang As described in the fac example, pattern matching is done on the values of function parameters. The basic allowed patterns (for us) are: • a literal value - for us that is just integers and true, false; will match if the parameter value is the same as the literal value • an identifier - will always match, instantiating the variable • wildcard - will always match; written as an underscore (like in Scala) The composite patterns are recursively defined where pat is another pattern: • a list - written as: [pat, ... , pat] which matches the elements of a list value; can also have just [] • a tuple - written as: (pat, ... , pat) which matches the values of a tuple • a cons - written as: pat : pat which matches head and tail of a list value Here is another example of a function that calculates the length of a list of integers using list and cons patterns: length :: [Int] -> Int length [] = 0. length h:t = 1 + length t length is a function that takes a list of integers ([Int]) as its input and outputs an integer (-> Int). If length's argument is the empty list ([]) then the result is 0; otherwise decompose a non-empty list into is head and tail (h:t where : means cons) and then the result is one more than the length of the tail. The syntax of HasLang To guide your implementation, here is a context-free grammar for the HasLang language on which you can base your parser. First, the syntax of programs and expressions: program : exp. exp : exp exp | "let" definitions "in" exp | "if" "(" exp ")" "then" exp "else" exp | exp "==" exp | exp "<" exp | exp "+" exp | exp "-" exp | exp "*" exp | exp "/" exp | exp ":" exp | "false" | "true" | ident | integer | "(" exp ")" | "[" "]" | "[" exp ( "," exp )* "]" | "(" exp ( "," exp )+ ")" exp="" |="" exp="" "+"="" exp="" |="" exp="" "-"="" exp="" |="" exp="" "*"="" exp="" |="" exp="" "/"="" exp="" |="" exp="" ":"="" exp="" |="" "false"="" |="" "true"="" |="" ident="" |="" integer="" |="" "("="" exp="" ")"="" |="" "["="" "]"="" |="" "["="" exp="" (="" ","="" exp="" )*="" "]"="" |="" "("="" exp="" (="" ","="" exp="" )+="">