Haslang代写 | Lexical Analyser, Parser And Tree Builder For Haslang

本次cs代写是为一个Haslang开发Lexical Analyser, Parser 和 Tree Builder的assignment


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

a :: Int = 5;

b :: Int = a + 1

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:

x   :: Int        = 100;

inc :: Int -> Int = \a :: Int -> a + 1

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.

a :: Int = 3

b :: Int = 10

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