Reference no: EM132982937

Assignment Instructions

Syntax Analysis

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

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 -}

You have to write and test a Scala syntax analyser including tree builder for HasLang.

You are strongly advised not to try to solve the whole assignment in one go. It is best to write code to handle the parsing and tree construction for some simple constructs first and then build up to the full language.

Your code must use the Scala parsing library as discussed in lectures and practicals. You should use the expression language syntax analyser and tree builder from the weekly classes as a guide for your implementation.

The supplied code bundle has modules that are very similar to those used in the practical exercises for weeks 5, 6. The skeleton contains the modules you will need. Some of the parsing and tree construction is given to you as an illustration; you must provide the rest (look for FIXME in the code).

As well as lexing and parsing the input, your program should construct a suitable source program tree to represent the parsed result. See HasLangTree.scala in the skeleton for the full definition and description of the tree structures that you must use. You do not need to modify the tree classes, just create instances in your parser code.

The program contains a single let expression with two definitions: one for "x" and one for "inc". The function definition contains two children: one for the name, and one for the function itself. The lambda expression contains two children: the argument name and type, and one for the body expression. Finally, the let has the function call as its value expression.

Running the syntax analyser and testing it

The skeleton for this assignment is designed to be run from within sbt. For example, to compile your project and run it on the file test/simple.hal you use the command

run test/simple.hal

Assuming your code compiles and runs, the run will print the tree that has been constructed (for correct input), or will print a syntax error message (for incorrect input).

The project is also set up to do automatic testing. See the
file SyntaxAnalysisTests.scala which provides the necessary definitions to test the syntax analyser on some sample inputs. Note that the tests we provide
are not sufficient to test all of your code. You must augment them with other tests which you will put at the BOTTOM of the tests file.

You can run the tests using the test command in sbt. This command will build the project and then run each test in turn, comparing the output produced by your program with the expected output. Any deviations will be reported as test failures.

Attachment:- Syntax Analysis.rar