Lab 1 - Tiger Language
Setup
Before starting this lab, please create a new directory lab1/
in your git repository.
Execute the following commands at the top of your repository:
$ mkdir lab1
$ cd lab1
$ wget -qO- www.sifflez.org/lectures/compil/lab1/dragon-tiger.tar.gz | tar zxv
$ git add dragon-tiger
$ git commit -m "Import dragon-tiger for lab1" dragon-tiger
$ cd dragon-tiger
To compile tiger language you need,
- a Tiger compiler called
dtiger
(insidesrc/driver/
) - a runtime library
libruntime.a
(insidesrc/runtime/posix
) that implements all the Tiger primitives such asprint
orprint_int
.
You can use dtiger
to compile a Tiger program test.tig
as follows,
$ echo 'print("Hello World!\n")' > test.tig
$ src/driver/dtiger -o test.o test.tig
$ clang++-9 test.o src/runtime/posix/libruntime.a -o test
$ ./test
Hello World!
The second command transforms the Tiger source into an object file which contains the generated assembly code.
The third command links the object file with the runtime library which contains the implementation of Tiger primitives.
Each time you answer a question marked with [file.ext
] you will create a new file
lab1/dragon-tiger/file.ext
and write the answer inside (a tiger program or a regular expression).
You will then add this new file to the git, commit your changes with a meaningful message and push your changes.
Ensure that you commit everything and follow precisely the instructions. This lab is graded and machine corrected !
Tiger Language
We will familiarize ourselves with the Tiger language by writing a few programs. If in doubt check the specifications of the Tiger language but remember that in these lectures we will not use and implement array and record types.
▶ [hello.tig
] Write a Tiger program, hello.tig
, that prints the string “Hello World!” followed by a new line character to the standard output.
▶ [fibonacci.tig
] Complete the following program and save it in a fibonacci.tig
file. The function fibonacci
should return the \(n^{th}\) term of the Fibonacci sequence which is defined recursively as follows,
let
function fibonacci(n : int) : int =
/* ... complete here ... */
in
for i := 1 to 8 do
(print_int(fibonacci(i)); print("\n"))
end
▶ [read_unsigned.tig
] Complete the following program and save it in read_unsigned.tig
file. The function read_unsigned
reads a line from the standard input (stdin
). If the line contains only numerical characters it returns the number as a positive base-ten integer. Otherwise, it returns \(-1\). You should correctly handle the line termination character \n
.
The following primitives will be useful:
function getchar() : string
, reads a single character fromstdin
and returns it as string of size one. If EOF is reached, the empty string is returned.function ord(s : string) : int
, returns the ASCII code of the first character of the input string.
let
/* Read a positive integer from the standard input.
Returns -1 on error */
function read_unsigned() : int =
/* ... complete here ... */
var a : int := read_unsigned()
in
print_int(a*2);
print("\n")
end
Regular Expressions and Finite Automata
▶ Give a regular expression and an automata for each of the following languages in \(\Sigma = \{a, b\}\):
-
[
regexp1.txt
] words in \(\Sigma^{*}\) for which the firsta
(if it exist) precedes the firstb
(if it exists). -
[
regexp2.txt
] words in \(\Sigma^{*}\) for which the number of a is even (0 is considered even).
You will write regular expressions in the format accepted by grep -E
.
The two committed files will contain nothing but the regular expression.
You can test what a regular expression matches like this:
echo "aaaaab" | grep -E -x --color "$(cat regexp2.txt)"
The parts of the input that match will be colored.
Automata Determinisation
▶ What is the language accepted by the automaton in the figure below?
▶ Show that it is not deterministic.
▶ Determinise it.