Compilation
Source code written Errors
in a language X Compiler
or
A compiled program ready for
execution
In detail…..
Source Code
ExampleIn the C language we have:
Lexical analysis Lexical errors
main() {
int x, y;
Tokens if x==2) y=1;
Syntaxic Analysis Syntaxic error x = 3,14;
Table of }
Syntax tree
symboles
• The program is lexically correct.
Semantic Analysis Semantic errors
• The program has a syntax error in
Generation/optimizati errors the if statement — the opening
of code parenthesis is missing.
compiled program
• The program has a semantic error :
x = 3,14
Regular expressions
Regular expressions are a formal concept used for writing automata.
In a regular expression, all characters are meaningful, including spaces.
The following characters (in the table) are reserved: they must be preceded
by \ or enclosed in quotation marks " " if you want to use their literal value
Regular expression
chararcter significations exemples
+ Repeat 1 ou more times x+ x...x
* Répéter 0 ou more times t* none or t...t
? 0 or 1 times a? none or a
| or ab|bc ab or bc
() factorisation (a|b)c ac or bc
" Litteral value of a sequence "+?"+ +?...+?
of characters
\ Litteral value of the \+++…+
preceeding even between " "
"\"+ error!!.
. Any character except line .|\n any character
break (\n).
[...] Define a set of characters [aeiou] a or e or i or o or u.
- used in [] to define an [0-9] 0,1,2,3,4,5,6,7,8,9
interval
^ used in [] to define the [^0-9] any character except numeric ones
complement of ensemble
[...] = character set, not a regular expression, which means:
*(0|1)++ → one of the characters (, ), 0, 1, |, +, not a sequence of 0s or 1s.
However, the characters ^, \, and - remain special characters.
[^\++ → any character except +.
Regular expression
{} Bounded repetition r{1,5} r or rr or rrr or rrrr or rrrrr
r{2,} rr or rrr or ….
r{3} rrr …….
^ Used outside [ ], it indicates the ^r → matches r only if r is at the
beginning-of-line condition. beginning-of-line
$ End-of-line condition. r$ → matches r only if r is at the end of
the line.
Regular expressions
Exercice :
Give a regular expression that defines the following entities:
1. A sequence of alphanumeric characters starting with an alphabetic character:
2- Signed numeric constants (with + or -):
3- Any character (including the end of line \n):
4- Any character except spaces, tabs, and line breaks:
Regular expressions
Exercice :
Give a regular expression that defines the following entities:
1. A sequence of alphanumeric characters starting with an alphabetic character:
[a-zA-Z]([a-zA-Z]|[0-9])*
2- Signed numeric constants (with + or -):
[+-]([1-9][0-9]*|0)
3- Any character (including the end of line \n):
.|\n
4- Any character except spaces, tabs, and line breaks:
[^ \n\t]
Lexical analysis
The lexical analyzer is the first stage of a compiler. Its main tasks are:
Reading the input characters and producing as output a sequence of lexical entities (tokens)
that will be processed by the syntax analyzer.
Eliminating unnecessary characters such as comments, tabs, line breaks, etc.
Managing line numbers in the source program in order to associate each subsequent error
with the line in which it occurs.
Exemple :
Source code before compilation:
If (x==2) y=z ; /* affectation*/
After lexical analysis:
Mc_If ( Idf Egal Const ) Idf Aff Idf pvg
Lexical analysis
The lexical analyzer is based on the following simple
algorithm:
Read (InputString);
Switch (InputString)
Case (RegExp1): encode("Entity1");
Case (RegExp2): encode("Entity2");
…
Case (RegExpN): encode("EntityN");
Default: write("Lexical error");
The implementation of such an algorithm would require writing hundreds or even
thousands of lines of code. Fortunately, software tools such as F(lex) exist to make this
task easier.
Flex
Flex is a translator that converts our lexical analyzer, written in a simple language
(Flex), into the C programming language.
programme.l [Link].c
Lexical analyser flex Lexical analyser in C
written in flex language
%{
C language definitions
%}
Regular expression definitions
%%
RegularExpression { C Action }
%%
Redefinitions of predefined functions
The format of a Flex file consists of three sections separated by %% .
Flex
A lexical analyzer for a language of the instruction : x=5;
Exemple :
%{
int nb_ligne=0;
%}
lettre [a-zA-Z]
chiffre [0-9]
IDF {lettre}({lettre}|{chiffre})*
cst {chiffre}+
%%
{IDF} return idf;
{cst} return cst;
= return aff;
; return pvg;
[ \t]
\n {nb_ligne++; }
. printf("erreur lexicale à la ligne %d \n",nb_ligne) ;