MOSIG M1 - PLSCD - Practical Work
The purpose of this work is to implement an interpreter for the While language (the one you studied in the 1st part of the PLSCD course).
- the behaviour of the interpreter is defined by the operational semantics of the language
(you should choose static links for the procedures and a dynamic links for the variables)
- its purpose it to compute and print the value of the memory and environments at each execution step of the program
- it can be implemented by a traversal of the program Abstract Syntax Tree (see below)
Your are free to choose the programming language you prefer to implement this interpreter. Some resources are provided in this
page if you want to implement it in C, but Note that using a functionnal programming
language (such Objective Caml, for instance,
see the user manual ...) might be much easier.
Some practical constraints:
- you should work as teams of two people
- you should send the result of your work by e-mail to Laurent Mounier
before November the 15th,
in a file archive containing:
- the source files
- a very short "user manual" of your interpreter (a few lines): how to execute it, what are
the current limits ...
- some examples of while programs
you tried (with the execution results)
Some resources provided
(if you want to implement your interpreter in C)
- source code of a parser
- main.c: main program, lauch the parser on
the specified input file
- tree.c: routines used to build and print
the AST
- type.h: global type and constant
definitions
- while.l: source of the lexical analyser,
in flex input format
- while.y: source of the syntactic
analyser, in yacc input format
- Makefile: to build the parser
- examples of syntacticaly correct while programs
- ex1.w: a very simple example
- ex2.w: an example with (almost) all available constructs
- ex3.w: an example to illustrate the semantics of static links
The whole directory isd also available as a tarball WhileParser.tgz.
How to use
the resources provided in this directory
- how to build the parser: make
- how to use the parser:
./while
ex1.w parse the file ex1.w and
pretty-print its AST.
or
./while
parse the
input stream read on stdin (terminated by ^D), and pretty-print its AST.
The
while language
Concrete
grammar
(terminal symbols are written in bold,
an identifier is a sequence of
letters or digits begining with a letter, an integer is a sequence of digits).
Note that this concrete syntax slightly differs from the one used during trhe course.
program ::= bloc
bloc ::= declare
declaration_list begin
instruction_list end
declaration_list ::= declaration | declaration_list ; declaration
declaration ::= var identifier | proc identifier ()
is bloc
instruction_list ::= instruction | instruction_list ; instruction
instruction ::= identifier := e | while b do instruction od| if
b then instruction else instruction | call identifier ()
e ::= e + t | t
t ::= t * f | f
f::= ( e )| identifier
| integer
b ::= b /\ bb | bb
bb ::= e < e | e = e | ^ bb | (b)
Abstract Syntax Tree (AST)
The structure of the AST can be deduced from the print_tree() function of file
tree.c
We assume that input programs are well-typed (no verification
performed by the parser)