المعهد العالي للعلوم التطبيقية والتكنولوجيا
1
Computation Models, Formal Languages and Compilation
Semester Project
With Transformer, personalize your own “code”!
Normally, while trying to resolve problems using algorithms, you depict your algorithms in what is called Pseudo-Code.
Pseudo-Code allows you to write algorithms using simple vocabulary without necessarily being a professional in a well-known
programming language. It’s somehow an abstract programming language, that is understandable by many people (with
minimum IT background), before trying to transform it into a professional code written by a high-level programming
language.
The goal of this semester project is to let you design your own Pseudo-Code language, that better helps you writing your
algorithms, and then conceive and implement a Transformer that takes your Pseudo-Code as an input, and outputs an
equivalent code in the high-level programming language that you know the best, such as: C/C++, Java or Python.
Rules and Requirements
1. The Pseudo-Code language to be designed is called: PSXYZ, where X, Y, Z are the initial letters of the names of the 3
students forming the group (Nb. it will be PSXY for the groups of two students).
2. PSXYZ can use English vocabulary or French vocabulary for reserved words (see Annex I).
3. You decide what features your PSXYZ can have, but at least you must have the minimal requirements of Annex I. Any
additional feature will be rewarded.
2
4. The Transformer that you need to develop, which is effectively a specific compiler, must contain the following phases and
modules: Lexical Analysis – Syntax Analysis – Symbol Table Management – Error Management – Intermediate Code
Generation …
5. You must use the standard tools LEX, YACC (or their equivalent tools) for Lexical Analysis and Syntax Analysis respectively.
6. You choose an appropriate Intermediate Code, however you will generate the target language directly from it.
7. You decide what is the target high-level programming language, mainly C/C++, Java or Python.
8. The Transformer to be implemented will be called: TPSC,TPSJ or TPSP according to your choice in 8.
Timeline and deliverables
Date Task Deliverables
6/12/2021 Kick-off
13/12/2021 Forming the groups – Design of the PSXYZ language PSXYZ Grammar (vocabulary, syntax
constructions, semantic rules …)
22/12/2021 Lexical analysis using LEX Mini report describing your work for lexical
analysis + LEX listing + some tests …
2/1/2021 Syntax & Semantic analysis using YACC Mini report describing your work for syntax &
semantic analysis + YACC listing + some tests …
15/1/2021 Intermediate code – generation of code (of the target
high-level programming language)
Complete report – Complete project code –
Presentation – Demo …
3
Annex I
Minimal requirements and examples in both English-based PSXYZ and French-based PSXYZ (reserved words are in bold)
Features & Requirements English-based PSXYZ French-based PSXYZ
Declaration of variables proceeded by
a keyword. We’ll use only five basic
data types: Integer, Real,
Boolean, Char, String
var
a, b: integer
x, y: real
f: Boolean
c: char
s: string
var
a, b: entier
x, y: réel
f: booléen
c: char
s: chaine
Identifiers must start by a letter x, ab, y13, z_15, F x, ab, y13, z_15, F
Comments are between { and } { this is a comment } { c’est un commentaire }
Assignment x := y x := y
Arithmetic Operators *, +, -, /, div, mod *, +, -, /, div, mod
Boolean Operators =, <, <=, >, >=, <>, and, or, not =, <, <=, >, >=, <>, et, ou, non
Mathematical Functions abs, exp, log … abs, exp, log …
Beginning and ending of a group of
statements
begin
…
end
début
…
fin
Statements and expressions x < y { Boolean expression } X + y { expression } z := x + y { statement } f := true { statement } a et b { Boolean expression } x mod y { expression } z := x mod y { instruction } f := faux { instruction } Conditional Statements if Boolean expression then statements if Boolean expression then statements else statements si Boolean expression alors instructions si Boolean expression alors instructions sinon instructions Loop Statement while Boolean expression do statements tant que Boolean expression faire instructions Read and Write statements read (‘Enter the value of x =’, x) write (‘The value of x is’, x) lire (‘Entrer la valeur de x = ’, x) écrire (‘La value de x est ‘, x) Subprograms that accept parameters and return a value Function F (x, y): integer … return z Fonction F (a, b): booléen … retourner c Call of a function w := F(s, t) d := F(s, t)