Upload
others
View
5
Download
0
Embed Size (px)
Citation preview
Polycopié d'InformatiqueFondamentale IMA4-SC
� Version 2013 �
Polytech'Lille, Villeneuve d'Ascq
Laure Gonnord
A�n d'améliorer ce poly n'hésitez pas à me
soumettre toute critique, suggestion, remarque
ou correction, dans mon casier ou, électroni-
quement, à l'adresse
A man provided with paper, pencil, and rubber,
and subject to strict discipline, is in e�ect a
universal machine.
Alan Turing, �Intelligent Machinery : A Report
by A. M. Turing� (Summer 1948)
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Table des matières
1 Introduction, automates �nis et langages réguliers 4
2 Automates à pile et grammaires hors contexte 15
3 Automates à compteurs et machines de turing 22
4 Graphes, notions de NP-complétude 31
5 Construction d'un compilateur en Java 48
3/58
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Chapitre 1
Introduction, automates �nis et langages
réguliers
Dans ce cours nous abordons le modèle de calcul le plus simple, les automates �nis, ainsi
que la notion de langage régulier.
4/58
Informatique Fondamentale IMA S8Cours 1 - Intro + schedule + finite state machines
Laure Gonnordhttp://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
2013
Course introduction and schedule
Until now
During S5,S6,S7, IMA students have learnt :(programming stuff) C programing and compiling,(conception stuff) algorithm design and encoding,(microelec) circuits and embedded systems hardware,(auto) design flows of industrial processes
I Solved (computation) problems by ad-hoc solutions.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 2 / 38 �Course introduction and schedule
Until now 2/2
But :No general scheme to design algorithms.(manual) evaluation of the cost of our programs.worse no assurance of correctness.even worse it there always a solution ?
I All these problems will be addressed in this course
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 3 / 38 �
Course introduction and schedule
Schedule
Finite state machines (regular automata), regularlanguages. Notion of non determinism. Link with circuits.I/O automata, stack automata and grammars. Link to“simple” languages.Counter automata, Turing machines and undecidableproblems. Link to “classical” programs.Graphs and classical problems/algorithms on graphs.Compiler Construction. (+ lab)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 4 / 38 �
Course introduction and schedule
I - Regular languages and automata
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 5 / 38 �
Finite state machines
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 6 / 38 �Finite state machines
What for ?
We want to model :the behaviour of systems with behavioural modes.the behaviour of (Boolean) circuits.sets of words.
I A finite representation.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 7 / 38 �
Finite state machines
ExampleOpening/Closing door - Source Wikipedia.
1
Opened
E: open door
2
Closed
E: close door
state
transition
transition condition
close_door open_door
entry action
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 8 / 38 �
Finite state machines
General definition
Finite state machine (FSM) or regular automataStates are labeled, and there are finitely many (s ∈ Q)Initial state(s) (i ∈ I) and accepting (terminating/finishing)states (t ∈ F )Transitions are finitely many.Transitions are labeled with letters (a ∈ A).
I The transition function is δ : Q×A→ Q.
s0 s1 s2a
b
a
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 9 / 38 �
Finite state machines
Accepted language 1/2
Accepted wordA word w on the alphabet A is accepted by the automaton iffthere exists a finite path from an initial state to an acceptingstate which is labeled by w.
s0 s1 s2a
b
a
I w = aa is accepted/recognised.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 10 / 38 �Finite state machines
Accepted language 2/2
Accepted languageThe accepted language of a given automaton A is the set ofall accepted words and is denoted by L(A).
I Remark : it can be infinite.
s0 s1 s2a
b
a
I L(A) = {abka, k ∈ N}.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 11 / 38 �
Finite state machines
Data Structure for implementation
Problem : how to encode an automata ?
s0 s1 s2a
b
a
The transition function can be (for instance) encoded as atransition table :
s0 s1 s2s0 −− a −−s1 −− b a
s2 −− −− −−
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 12 / 38 �
Regular Languages
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 13 / 38 �
Regular Languages
Goal
Problem : how to describe languages easily in a textual “linear”way ?I use regular expressions.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 14 / 38 �Regular Languages
Regular expressions
Regular expression (recursive def)A regular expression e on the alphabet A is defined byinduction. It can be of any of the following kinds :
the empty word εa letter a ∈ Aa choice between an expression e1 and another expressione2 : e1 + e2
two successive expressions : e1 · e20,1 or more successive occurrences of e1 : e∗1.
Example with A = {a, b, c, d} : e = a · (b+ c · d)∗
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 15 / 38 �
Regular Languages
Regular expression vs word
A regular expression “encodes” the form of a word. Forinstance :
i ·m · a · (3 + 4 + 5)
(on the alphabet {i,m, a, 3, 4, 5}) describes all words beginningby the prefix “ima” and finishing by one of the numbers 3, 4 or 5.
I A regular expression describes a language
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 16 / 38 �
Regular Languages
Regular language
Regular languageGiven a regular expression e, L(e) denotes the set of words(the language) that are described by the regular expression e.
Example with A = {0, . . . , 9} :e = (1 + 2 + . . .+ 9) · (0 + 1 + 2 + . . .+ 9)∗. What is L(e)?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 17 / 38 �
Regular Languages
Linux world
Some commands use (extended) regular expressions(regexp) :
ls *.pdf lists all pdfs of the current directorygrep ta*.* *.c find all lines in .c files that contains wordsthat begin with t + some a’s.sed ''s ta*.*/toto/g'' file replace all occurrences...
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 18 / 38 �Regular Languages
Relationship between automata and languages - 1/3
First, some experiments.
Given the following automata A, are you able to give a regularexpression e such that L(e) = L(A)?
s0 s1 s2a
b
a
I e =?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 19 / 38 �
Regular Languages
Relationship between automata and languages - 2/3
And the converse :
Given the following regular expression e = b∗ · (c+ a)∗, are youable to give an automaton A such that L(A) = L(e)?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 20 / 38 �
Regular Languages
Relationship between automata and languages - 3/3
General result - Kleene TheoremThe regular languages are exactly the languages that aredescribed by finite automata.
I What we’ve done before is always possible.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 21 / 38 �
The notion of non determinism
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 22 / 38 �The notion of non determinism
Goal
Sometimes some info lacks to make a choice between twotransitions :
q0 q1 q2a
c
c
I From state q1, there is a non deterministic choice whilereading c : either go to state q2 or stay in q1.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 23 / 38 �
The notion of non determinism
Definition
Non deterministic FSMA deterministic automaton is A =< A,Q, I, F, δ > with
δ : A×Q→ Q
A non deterministic automata is the same with :
δ : A×Q→ P (Q)
A non deterministic automata with ε-transitions is thesame with
δ : (A ∪ {ε})×Q→ P (Q)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 24 / 38 �
The notion of non determinism
Example
A non deterministic automata with ε-transitions :
p q ra
c
d
ε
I Then L(A) = a · (c∗ · d)∗.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 25 / 38 �
Classical Algorithms
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 26 / 38 �Classical Algorithms
Find the associated language
Goal : Given A an automaton, find the associated language.
I Exercises !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 27 / 38 �
Classical Algorithms
Construction of automaton from a regular expression
Goal : Given a regular expression, construct a regularautomaton that “recognises” it.
I Exercises !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 28 / 38 �
Classical Algorithms
Determinisation
Goal : transform a non deterministic automaton into adeterministic one.
I Exercises !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 29 / 38 �
Classical Algorithms
Other Algorithms
In the literature you will easily find :algorithms to eliminate ε transitions without determinising(ε closure) ;algorithms to minimise automata (the number of states) ;algorithms to use automata to find words in a text ;algorithms to test language inclusion (if they are regular). . .
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 30 / 38 �Expressivity of regular languages
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 31 / 38 �
Expressivity of regular languages
Non regular languages
Important resultThere exists some non-regular languages.
Examples of non-regular languages :{anbn, n ∈ N}.palindromes on a non-singleton alphabet.{ap, p prime}
I There exists a quite systematic way to prove that a givenlanguage is not regular (Pumping Lemma).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 32 / 38 �
Link to other models
1 Finite state machines
2 Regular Languages
3 The notion of non determinism
4 Classical Algorithms
5 Expressivity of regular languages
6 Link to other models
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 33 / 38 �
Link to other models
Moore and Mealy Machines - 1Moore : I/O machine whose output values are determinedsolely by the current state :
source Wikipedia
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 34 / 38 �Link to other models
Moore and Mealy Machines - 2Mealy : output values are determined both by the current stateand the value of the input.
source Wikipedia
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 35 / 38 �
Link to other models
UML Implementation of FSMs
UML variants of FSMs are hierarchical, react to messages andcall functions.
source Wikipedia
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 36 / 38 �
Link to other models
Hardware Implementation of FSMs
It requires :a register to store state variablesa block of combinational logic for the state transition(optional) a block of combinatorial logic for the output
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 37 / 38 �
Conclusion
Summary
Regular Automata or Finite State Machines are :Acceptors for regular languages. But some languages arenot regular.Algorithmically efficient.Useful to describe (simple) behaviours of systems.Closely linked to circuits.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 38 / 38 �
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Chapitre 2
Automates à pile et grammaires hors
contexte
Les automates à pile sont un modèle de calcul un peu plus puissant que les automates �nis.
Nous caractériserons leur pouvoir d'expressivité en terme de grammaire.
15/58
Informatique Fondamentale IMA S8Cours 2 - Stack automata + Grammars
Laure Gonnordhttp://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
2013
II - Stack automata and Grammars
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 2 / 22 �Stack automata
1 Stack automata
2 Grammars
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 3 / 22 �
Stack automata
What for ?
Express more than regular languages !
I Give a way for automata to “count”, to “have a memory”.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 4 / 22 �
Stack automata
Example
(source : Wikipedia)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 5 / 22 �
Stack automata
General definition
Stack/P automataStates (Q), initial state (q0), finite states (F).Two alphabets (one for read : Σ one for stack : Γ)γ0 ∈ Γ the end of stack character.Transitions are finitely many.A stack to write into.Transitions use the stack.
I The transition function is :
Q× (Σ ∪ ε)× Γ→ P(Q× Γ∗)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 6 / 22 �Stack automata
How it works ? 1/3
ConfigurationA configuration is a triple (q, w, α) where :
q is the current statew ∈ Σ∗ the part of the input tape which is not yet readα ∈ Γ∗ the current stack word
Two different conditions for accepting words :“accepting state” : the read word leads to a configurationof the form (q, ε, α) where q ∈ F (with any α)“empty stack” : ... (q, ε, γ0) (with any q, but γ0 is the “emptystack” character.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 7 / 22 �
Stack automata
How it works ? 2/3
Given a configuration (q, w, α), the next one is computed by thehelp of the transition function Q× (Σ ∪ ε)× Γ→ P(Q× Σ∗) :
enabled transitions : those of the form (q, a, A)→ (q′, A′)where a is the next letter to read on the input tape (or ε),and A the letter on top of the stack : w = aw′ and α = Aα′.Pick one enabled transition, and compute the nextconfiguration (q′, w′, A′α′).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 8 / 22 �
Stack automata
How it works ? 3/3
(source : wikipedia)
I Try to derive 0011 and 00111 !I The PDA recognises {0n1n|n ∈ N} by accepting state.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 9 / 22 �
Stack automata
Important theoretical results on PDA
Important Stack automata are non deterministic !The two acceptance criteria define the same class oflanguages
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 10 / 22 �Grammars
1 Stack automata
2 Grammars
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 11 / 22 �
Grammars
Goal
Problem : Express languages with the same expressivity asstack automata.I use grammars
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 12 / 22 �
Grammars
General grammars
Grammar ruleA grammar rule (production rule) is of the form
w −→ w′
where w and w′ are words.
A grammar is a set of rules.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 13 / 22 �
Grammars
Grammars
GrammarA grammar is composed of :
A finite set N of non terminal symbolsA finite set Σ of terminal symbols (disjoint from N )A finite set of production rules, each rule of the formw → w′ where w is a word on Σ ∪N with at least one letterof N . w′ is a word on Σ ∪N .A start symbol S ∈ N .
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 14 / 22 �Grammars
Grammars
Example :S → aSb
S → ε
is a grammar with N = .... and ....
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 15 / 22 �
Grammars
Associated Language
DerivationG a grammar defines the relation :
x⇒G y iff ∃u, v, p, qx = upv and y = uqv and (p→ q) ∈ P
I A grammar describes a language (the set of words on Σ thatcan be derived from the start symbol).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 16 / 22 �
Grammars
Examples
S → aSb
S → ε
The grammar defines the language {anbn, n ∈ N}
S → aBSc
S → abc
Ba→ aB
Bb→ bb
The grammar defines the language {anbncn, n ∈ N}I Exercises
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 17 / 22 �
Grammars
Context-free grammars
Context-free grammarA CF-grammar is a grammar where all production rules are ofthe form N → (Σ ∪N)∗.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 18 / 22 �Grammars
Example of CF-grammar
S → S + S|S ∗ S|aThe grammar defines a language of arithmetical expressions.
I Notion of derivation tree.Draw a derivation tree of a*a+a, of S+S !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 19 / 22 �
Grammars
Relationship between stack automata and grammars
General resultThe context-free/algebraic languages are exactly the languagesthat are described by stack automata.
I The proof is not difficult.
I Exercises
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 20 / 22 �
Grammars
Some other results/definitions
Regular languages are algebraic languages, but not theconverse.There exists normal forms for algebraic grammarsA grammar can be ambiguous.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 21 / 22 �
Conclusion
Summary
Stack Automata or PushDown Automata are :Acceptors for context-free languages. But some languagesare not context free.Non deterministic.
I http://en.wikipedia.org/wiki/Pushdown_automaton foruseful pointers
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 - S8SC � 22 / 22 �
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Chapitre 3
Automates à compteurs et machines de
turing
Dans ce chapitre nous étudions des modèles plus proches de nos programmes habituels, les
automates à compteurs, et introduisons le modèle couramment utilisé pour formaliser la notion
de calcul, les machines de Turing.
22/58
Informatique Fondamentale IMA S8Cours 3: Counter automata, Turing Machines and decidable
problems
Laure Gonnordhttp://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
2013
III - Counter automata, Turing Machines and decidable problems
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 2 / 30 �Counter automata
1 Counter automata
2 Programs
3 Turing Machines
4 Decidability - Complexity
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 3 / 30 �
Counter automata
What for ?
Express more than context-free languages !
I Give a way for automata to “count more” : include variables.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 4 / 30 �
Counter automata
Example
kinit k1
cos(y) ≤ x → x := x+ 1
x 6= y → y := yx
true → y := y + 2
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 5 / 30 �
Counter automata
General definition
Counter AutomataA finite number of counters (variables)A finite number of control pointsTransitions between them that operate on counters.
I The transition function is of the form g → a (g is the guard, ais the action)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 6 / 30 �Counter automata
How it works ? 1/3
StateA state is (q, σ)
q is the current control pointσ : V ar → V al is a function that assigns a value (a realone or ⊥) to all counters.
I Non deterministic/No notion of acceptance/Notion ofreachability.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 7 / 30 �
Counter automata
How it works ? 2/3
Given a state (q, σ), the next one is computed by the help of thetransition function :
enabled transitions are transition of the current controlpoints where the current valuations of variables satisfy theguard.Pick one enabled transition, and compute the next state :(q′, σ′). The new values for the variables are computedw.r.t. the action.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 8 / 30 �
Counter automata
How it works ? 3/3
Example of an affine automata :
kinit k1 k2true → x := 0; y := 0 x ≤ 1 → x := x+ 1; y := 2y − 4
y + 2x ≤ 2 → x := 2x+ 5
I Compute successive states.
I Exercises.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 9 / 30 �
Counter automata
What kind of systems ?
These automata are used to encode, for example :Simple systems (coffee machine, ...) specificationsEnergy consumption of sensors :
Sleep Idle
Transmit
Receive
35.1 mW
145.8 mW
140.4 mW
140.4 mW
140.4 mW
145.8 mW
140.4 mW
140.4 mW
140.4 mW
140.4 mW
400 µs
332 µs
144 µs
144 µs
100 µs 100 µs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 10 / 30 �Counter automata
What for ?
Some classical problems :
Automatically finding invariantsReachability analysisFormula proving.(deterministic) Code generation.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 11 / 30 �
Programs
1 Counter automata
2 Programs
3 Turing Machines
4 Decidability - Complexity
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 12 / 30 �
Programs
Expressing programs as counter automata
An example :x:=0;y:=0
while (x<=100) do
read(b);
if b then
x:=x+2
else begin
x:=x+1;
y:=y+1;
end;
endif
endwhile
p
pin
x ≤ 100 →
x := x+ 1y := y + 1
x ≤ 100 →
x := x+ 2
(x, y) := (0, 0)
pout
x ≥ 100
I Some approximations are made (arrays, Boolean, . . . )
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 13 / 30 �
Programs
Expressing properties of programsSome (safety) properties of programs can be expressed insidethe counter automaton :
p
pin
x ≤ 100 →
x := x+ 1y := y + 1
x ≤ 100 →
x := x+ 2
(x, y) := (0, 0)
pout
x ≥ 100
I Encode the fact that state = pout ∧ y > 100 is “bad”I Some modifications of the automaton can be automaticallydone.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 14 / 30 �Programs
Expressing properties of programs - 2Automatically deriving bad states :
int j;
char user[USERSZ];
for(j = 0; line[j] != EOS; ++j)
if (!strchr("-", line[j]))
break;
if(j == J && line[j] == ' ') { /* long list */
/* BUG! No bounds check. */
assert(USERSZ>=N-j,"badstate");
r_strcpy (user, line + j);
}
I “badstate” is reachable.Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 15 / 30 �
Programs
Expressing programs as counter automata
Pros : finding and proving program propertiesCons : how do we define the operations ? the fact thatintegers are encoded on bits ?
I There is a need for a more accurate (not specialised) model !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 16 / 30 �
Turing Machines
1 Counter automata
2 Programs
3 Turing Machines
4 Decidability - Complexity
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 17 / 30 �
Turing Machines
Turing Machine, def - 1
Turing Machine, Turing, 1935A tape (infinite in both sides) : the memory. (it has aworking alphabet which contains a blank symbol).A head : read/write symbols on the tape.A finite transition table (or function)
I A PushDown automaton which is more flexible.
image credits : Wikipedia.org
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 18 / 30 �Turing Machines
Turing Machine, def - 2
Turing Machine elementsStates (Q), initial state (q0), final (accepting) states (F).One alphabet Γ for the tape.b ∈ Γ the blank letter.Transitions are finitely many : read the letter under thehead, and then :
Erase a symbol or write one under the headMove the head (read, write, or stays)The “state” can be modified.
I The transition function is :
Q× Γ× → Q× Γ× {L,R, S}
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 19 / 30 �
Turing Machines
An Example
TM that decides if x is odd : (final State : q4)State/char 0 1 B
q1 (q1,0,R) (q1,1,R) (q2,B,L)q2 (q3,0,L) (q4,1,L) —
Play on BBBBBBB11BBBBB and BBBBBBB10BBBBB
I A configuration is a tuple (word on the tape, position of thehead, state).Adapted from : http://www.madchat.fr/coding/algo/algo_epfl.pdf slide 4
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 20 / 30 �
Turing Machines
Another Example
Demo of a TM recognising a language : anbncn
Program found here :http://www.cs.columbia.edu/~zeph/software/BJDweck/
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 21 / 30 �
Turing Machines
General results 1/2
There exists Turing machines for the following languages :palindromesanbncn (non algebraic language)ai with i prime (non algebraic)an
2, with n > 0
I Turing machines are more powerful than all other models (wehave seen yet)
Decidable LanguagesA language that is recognised by a Turing Machine is said to bedecidable.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 22 / 30 �Turing Machines
Accepting or computing
A TM can also compute functions
TM that writes 1 if x is odd, 0 else (q6 is final state) :State/char 0 1 B
q1 (q1,0,R) (q1,1,R) (q2,B,L)q2 (q3,B,L) (q4,B,L) —q3 (q3,B,L) (q3,B,L) (q5,1,R)q4 (q4,B,L) (q4,B,L) (q5,0,R)q5 — — (q6,B,R)
Play on BBBBBBB11BBBBB and BBBBBBB10BBBBB
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 23 / 30 �
Turing Machines
Another Example
Demo of a TM computing the subtraction.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 24 / 30 �
Turing Machines
General results 2/2
There exists Turing machines for the computation of :x 7→ x+ 1
(x, y) 7→ x+ y
x 7→ x2
all the functions you are able to write on computers
Computable functionsA function (defined for all its input) that is computable by aTuring Machine is said to be TM computable
I A Model of what can be computed with machines. (ChurchThesis)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 25 / 30 �
Decidability - Complexity
1 Counter automata
2 Programs
3 Turing Machines
4 Decidability - Complexity
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 26 / 30 �Decidability - Complexity
Decidable - Semi-decidable languages
If L is a language, L is decidable if there exists a TuringMachine (or an algorithm) that outputs for all w :
1 if w ∈ Lelse 0.
Semi-decidable :1 if w ∈ Lelse does not terminate
I equivalent definition for problems.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 27 / 30 �
Decidability - Complexity
Complexity
Link with computational complexity :The number of steps in the execution of a TM gives thecomplexity in time,The number of seen squares in the execution of a TMgives the complexity in space.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 28 / 30 �
Decidability - Complexity
Examples of undecidable problems
The halting problem for TM or counter automata (for morethat 2 counters)Given a program, does it loops ?Is a given algebraic expression (with log, *, exp, sin, abs)equal to 0 ? (Richardson, 1968)The 10th Hilbert Problem (Diophantine equations)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 29 / 30 �
Conclusion
SummaryTuring Machines :
A model closed to programming languages.Non deterministic.Acceptors for decidable languages. But some languagesare not decidable !(equivalently) Computes solutions to problems. But ...
Important factSome common problems are undecidable !
Counter automata :are a more simpler modelhave the same power of expression as Turing Machines.Reachability is undecidable too. But we can doapproximations.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8SC � 30 / 30 �
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Chapitre 4
Graphes, notions de NP-complétude
Les graphes o�rent une modélisation intéressante de beaucoup de problèmes d'informatique.
Nous abordons leur représentation machine et présentons rapidement les algorithmes classiques.
Nous pro�tons du modèle pour parler de complexité théorique, de problèmes �di�ciles�, et de
NP-complétude
Figure 4.1 � Pillow talk, http://xkcd.com/69/, sous License Creative Commons
Figure 4.2 � Travelling salesman Problem, http://xkcd.com/399/, sous License CreativeCommons
31/58
Informatique Fondamentale IMA S8Cours 4 : graphs, problems and algorithms on graphs,
(notions of) NP completeness
Laure Gonnordhttp://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
2013
IV - Graphs, problems and algorithms on graphs, NP-completeness
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 2 / 64 �Some generalities on graphs
1 Some generalities on graphsGeneralities and first definitionsInternal representation
2 Paths finding - search, and applications
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 3 / 64 �
Some generalities on graphs Generalities and first definitions
Goal
Model :relationships between objects (“I know him”, “Thisregister is in conflict with with one”, “there is a roadbetween these two towns”)classical problems of paths (“Do I have a friend that knowsa friend ..... who knows the Dalai-Lama ?”, “It is possible togo from this town to this another in less than 600 km ?”,“how to get out of the labyrinth ?”)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 4 / 64 �
Some generalities on graphs Generalities and first definitions
Who ?
Euler (1740) formalised the theory and the Konisberg problem :
I IProblem : compute an eulerian path.Source (fr) : http://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 5 / 64 �
Some generalities on graphs Generalities and first definitions
Other classical problems
The travelling salesman problem : TSPTask scheduling (on parallel machines or not !), the PERTmethod.Coloring mapsCovering (telecom) treesMinimal paths ...
I Graphs are everywhere.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 6 / 64 �Some generalities on graphs Generalities and first definitions
General definition
GraphA finite set of vertices (a vertex) : VA finite set of edges. E ⊆ V × V
v1
v2
v3
e1 e3
I A simplier model than the previous ones !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 7 / 64 �
Some generalities on graphs Generalities and first definitions
Other definitions
Non Oriented Graph iff∀(v1, v2), (v1, v2) ∈ E ⇒ (v2, v1) ∈ E.Tree (non oriented acyclic connex) - Forest .Directed Acyclic Graph : DAG . Oriented Graph with nocycle.
I trees are dags !
v1
v2
v3
v4
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 8 / 64 �
Some generalities on graphs Internal representation
Sources
Picture and Java codes fromhttp://pauillac.inria.fr/~levy/courses/X/IF/a1/a1.html
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 9 / 64 �
Some generalities on graphs Internal representation
Adjacency matrix
0
1
2
3 4
0 1 0 0 01 0 1 0 00 1 0 0 00 0 0 0 10 0 0 1 0
I If the graph is oriented, then the matrix is NOT symmetricI Memory complexity : O(V 2)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 10 / 64 �Some generalities on graphs Internal representation
Adjacency matrix - Java
boolean [ ] [ ] m;
Graph ( i n t n ) {m = new boolean [ n ] [ n ] ;for ( i n t i = 0 ; i < n ; ++ i )
for ( i n t j = 0 ; j < n ; ++ j )m[ x ] [ y ] = f a l s e ;
}
s t a t i c void addEdge ( Graph g , i n t x , i n t y ){ g .m[ x ] [ y ] = t rue ;
g .m[ y ] [ x ] = t rue / / on ly i f non o r ien ted }
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 11 / 64 �
Some generalities on graphs Internal representation
Array of lists
0
1
2
3 4
I Memory complexity : O(V + E)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 12 / 64 �
Some generalities on graphs Internal representation
Array of lists - Java
L i s t e [ ] succ ;
Graph ( i n t n ) { succ = new L i s t e [ n ] ; }
s t a t i c void addEdge ( Graph g , i n t x , i n t y ) {g . succ [ x ] = new L i s t e ( y , g . succ [ x ] ) ;/ / i f non o r ien ted also modify g . succ [ y ] !
}}
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 13 / 64 �
Paths finding - search, and applications
1 Some generalities on graphs
2 Paths finding - search, and applicationsLooking for all nodesConnexityTopological Sort
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 14 / 64 �Paths finding - search, and applications Looking for all nodes
Search Algorithms
! Translation problem ! (en) Search Algorithms - (fr) Parcours deGraphesReminder : search/do algorithm on a binary tree :
1 If the tree is not empty, do f(root).2 recursively apply the function on the left sub-tree3 recursively apply the function on the right sub-tree
I Deep-First Search
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 15 / 64 �
Paths finding - search, and applications Looking for all nodes
Deep First Search on Graphs
On graphs, there can be cycles !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 16 / 64 �
Paths finding - search, and applications Looking for all nodes
Deep First Search on Graphs - Javas t a t i c i n t [ ] num; / / numbering the edges according to the v i s i t i n g order
s t a t i c void v i s i t e r ( Graphe g ) {i n t n = g . succ . leng th ;num = new i n t [ n ] ; numOrdre = −1;for ( i n t x = 0; x < n ; ++x ) num[ x ] = −1; / / −1 = ‘ ‘ not seen ’ ’for ( i n t x = 0; x < n ; ++x )
i f (num[ x ] == −1)dfs ( g , x ) ;
}
s t a t i c void dfs ( Graphe g , i n t x ) {num[ x ] = ++numOrdre ;for ( L i s t e l s = g . succ [ x ] ; l s != n u l l ; l s = l s . su i van t ) {
i n t y = l s . va l ;i f (num[ y ] == −1)
dfs ( g , y ) ;}
}
I Complexity = O(V + E). Tarjan [1972]
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 17 / 64 �
Paths finding - search, and applications Looking for all nodes
Breadth First Search on Graphs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 18 / 64 �Paths finding - search, and applications Looking for all nodes
Conventions
BLANC = not (yet) processed NOIR = has been processedGRIS = being processed
f i n a l s t a t i c i n t BLANC = 0 , GRIS = 1 , NOIR = 2;s t a t i c i n t [ ] cou leur ;
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 19 / 64 �
Paths finding - search, and applications Looking for all nodes
Breadth First Search on Graphs - Javai n t n = g . succ . leng th ; cou leur = new i n t [ n ] ;FIFO f = new FIFO ( n ) ;for ( i n t x = 0; x < n ; ++x ) cou leur [ x ] = BLANC;for ( i n t x = 0; x < n ; ++x )
i f ( cou leur [ x ] == BLANC) {FIFO . a j o u t e r ( f , x ) ; cou leur [ x ] = GRIS ;b fs ( g , f ) ;
}
s t a t i c void bfs ( Graphe g , FIFO f ) {while ( ! f . v ide ( ) ) {
i n t x = FIFO . supprimer ( f ) ;for ( L i s t e l s = g . succ [ x ] ; l s != n u l l ; l s = l s . su i van t ) {
i n t y = l s . va l ;i f ( cou leur [ y ] == BLANC) {
FIFO . a j o u t e r ( f , y ) ; cou leur [ y ] = GRIS ;}cou leur [ x ] = NOIR ;
} } }
I Complexity ?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 20 / 64 �
Paths finding - search, and applications Looking for all nodes
Application : Labyrinth
Finds exit , ie a path from d to s ?cou leur [ d ] = GRIS ;i f ( d == s )
return new L i s t e ( d , n u l l ) ;for ( L i s t e l s = g . succ [ d ] ;
l s != n u l l ; l s = l s . su i van t ) {i n t x = l s . va l ;i f (num[ x ] == BLANC) {
L i s t e r = chemin ( g , x , s ) ;i f ( r != n u l l )
return new L i s t e ( d , r ) ;}
}return n u l l ;
}
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 21 / 64 �
Paths finding - search, and applications Connexity
Definition - Connex Component
Connex componentA connex component is a maximal set of connected vertices.
I Exercise : Algorithm for computing CCs.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 22 / 64 �Paths finding - search, and applications Connexity
Definition - Connex Graph
Connex graphA graph is connex if it has only one connex component.
I Exercise : Algorithm that tests the connexity of a graph.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 23 / 64 �
Paths finding - search, and applications Topological Sort
Other AlgorithmsThere exists variants of DFS algo to :
Compute Cover Forets (in bold in the picture) :
Detect Cycles.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 24 / 64 �
Algorithms specific to oriented graphs
1 Some generalities on graphs
2 Paths finding - search, and applications
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 25 / 64 �
Algorithms specific to oriented graphs
Topological sorting of a DAG
I Give a list of vertices in an order compatible with the DAGorder : vi < vj ⇒ vj → vi (total order from a partial header).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 26 / 64 �Algorithms specific to oriented graphs
Topological sorting of a DAG - Example
1
2
3
4
5
6
7
I If we know an entrant node, a dfs gives the result.Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 27 / 64 �
Algorithms specific to oriented graphs
Topological sorting of a DAG - implementation
f i n a l s t a t i c i n t BLANC = 0 , GRIS = 1 , NOIR = 2;
s t a t i c L i s t e aFai re ( Graphe g , i n t x ) {i n t n = g . succ . leng th ;i n t [ ] cou leur = new i n t [ n ] ;for ( i n t x = 0; x < n ; ++x ) cou leur [ x ] = BLANC;return dfs ( g , x , n u l l , cou leur ) ;
}
s t a t i c L i s t e dfs ( Graphe g , i n t x , L i s t e r , i n t [ ] cou leur ) {cou leur [ x ] = GRIS ;for ( L i s t e l s = g . succ [ x ] ; l s != n u l l ; l s = l s . su i van t ) {
i n t y = l s . va l ;i f ( cou leur [ y ] == BLANC)
r = dfs ( g , y , r , cou leur ) ;}return new L i s t e ( x , r ) ;
}
I dfs here returns a list.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 28 / 64 �
Algorithms specific to oriented graphs
Topological sorting of a DAG - Applications
instruction schedulingcell evaluation in spreadsheetsorder of compilation tasks (Makefiles)symbol dependencies in linkerssheduling in project managements (PERT, 1960)
http://en.wikipedia.org/wiki/Topological_sorting
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 29 / 64 �
Algorithms specific to oriented graphs
Transitive closure
The graph G+ = (V,E+) of the transitive closure of G = (V,E)is such that E+ is the smallest set verifying :
E ⊆ E+
(x, y) ∈ E+ and (y, z) ∈ E+ ⇔ (x, z) ∈ E+
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 30 / 64 �Algorithms specific to oriented graphs
Algorithm for Transitive closure
If E is the adjacency matrix : E+ = E + E2 + . . . En−1.I An algorithm in O(n4).
I Is it possible to have a better complexity ? Yes (Warshall, inO(n3), see later).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 31 / 64 �
Algorithms specific to oriented graphs
Definition of oriented valuated graph
Valuated graphIt’s a graph with a function d : V × V → N called distance.
I G is represented by an adjacency matrix with integer values,or +∞ if there is no edge.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 32 / 64 �
Algorithms specific to oriented graphs
The shortest path problem
Given G, find a path whose sum of distances is minimal !
more variants on http://en.wikipedia.org/wiki/Shortest_path_problem
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 33 / 64 �
Algorithms specific to oriented graphs
Multiple Source Shortest Path with dynamicprogramming -1
Between all the vertices ! Floyd-Warshall algorithmPrinciple : Let dkx,y be the minimal distance between x and ypassing through vertices whose number is < k. Then
d0x,y = dx,y and dkx,y = min{dk−1x,y , dk−1
x,k + dk−1k,y }
I Store all these temporary distances.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 34 / 64 �Algorithms specific to oriented graphs
Multiple Source Shortest Path with dynamicprogramming -2
s t a t i c Graphe plusCourtsChemins ( Graphe g ) {i n t n = g . d . leng th ;Graphe gplus = copieGraphe ( g ) ;for ( i n t k = 0; k < n ; ++k )
for ( i n t x = 0; x < n ; ++x )for ( i n t y = 0; y < n ; ++y )
gplus . d [ x ] [ y ] = Math . min ( gplus . d [ x ] [ y ] ,gplus . d [ x ] [ k ] + gplus . d [ k ] [ y ] ) ;
return gplus ; }
I Complexity O(n3), space O(n2).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 35 / 64 �
Algorithms specific to oriented graphs
Simple Source Shortest Path
All d are > 0 : Dijkstra, 1959Negative distances : Bellman Ford ' 1960
I Routing algorithms (Bellman uses only local information).
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 36 / 64 �
More difficult problems on graphs
1 Some generalities on graphs
2 Paths finding - search, and applications
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 37 / 64 �
More difficult problems on graphs
Eulerian and Hamiltonian paths
Eulerian/Hamiltonian PathAn Eulerian path : each edge is seen only once.An Hamiltonien path : each node ...
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 38 / 64 �More difficult problems on graphs
Hamiltonian Tour, one solution
Extend a path until not possibleBacktrack one time, and try with another neighbourAnd so on.
I Worst case complexity time : exponential in n
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 39 / 64 �
More difficult problems on graphs
Application 1 : Knight’s Tour
Is it possible to make a Knight’s tour ? « The knight is placed onthe empty board and, moving according to the rules of chess,must visit each square exactly once.»I A variant of the Hamiltonian tour that can be solved inpolynomial time.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 40 / 64 �
More difficult problems on graphs
The Travelling Salesman Problem
with valuated (non oriented) graph.I Find an hamiltonian cycle of minimum weight
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 41 / 64 �
More difficult problems on graphs
Travelling Salesman Problem - 2
A (non-polynomial) algorithm for this problem :Transform into a linear programming problem with integersSolve it with the simplex !
I This algorithm is exponential in the size of the graph
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 42 / 64 �More difficult problems on graphs
Graph Coloring Problem
I Application to the register allocation in compilers.I The sudoku problem (9-coloring of a 81-vertices graph)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 43 / 64 �
More difficult problems on graphs
Graph Coloring Problem - 2
Are you able to design a polynomial algorithm ?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 44 / 64 �
More difficult problems on graphs
Graph Coloring Problem - 3
We do not know any polynomial algorithm for this problem.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 45 / 64 �
NP - completeness
1 Some generalities on graphs
2 Paths finding - search, and applications
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 46 / 64 �NP - completeness
Complexity
The complexity of an implementation / an algorithm is linked toTuring machines :
The number of steps in the execution of a TM gives thecomplexity in time,The number of seen squares in the execution of a TMgives the complexity in space.
We can replace the TM by “a C implementation”.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 47 / 64 �
NP - completeness
P Problems
PA problem (or a language) belongs to P if there exists adeterministic Turing Machine that gives the result inpolynomial time.
I there is a polynom p such that for all entry x, the Turingmachine stops (with the good result) in less than p(|x|) steps.
Example : L = anbncn, the TM of the previous course checksany aibici in O(n) steps
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 48 / 64 �
NP - completeness
P Problems
Integer multiplicationEulerian tour (each edge once)Linear programming (recall that polynomial diophantineequations are undecidible.)Primality test
http://www.cs.uu.nl/groups/AD/compl-diaz.pdf
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 49 / 64 �
NP - completeness
NP Problems
NPA problem (or a language) belongs to NP if there exists adeterministic Turing Machine that checks the result inpolynomial time.
Example : there exists a TM that is able to check if a given pathis an hamiltonien tour, in polynomial time.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 50 / 64 �NP - completeness
NP Problems - Examples
Factoring3-SAT (formulae in CNF with 3 litterals on each term)Hamiltonian tour3-colorability
http://www.cs.uu.nl/groups/AD/compl-diaz.pdf
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 51 / 64 �
NP - completeness
NP vs P - some facts
If a problem belongs to NP , then there exists anexponential brute-force deterministic algorithm to solve it(easy to prove)P ⊆ NP (trivial)
I P = NP ? P 6= NP ? Open question ! Problem of the millenium !Is finding more difficult that verifying ?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 52 / 64 �
NP - completeness
NP-complete problems - 1
Given a problem :if we find a polynomial algorithm I Pif we find a polynomial time checking algorithm I NP, butwe want to know more :
“it it really hard to solve it ?”“is it worth looking for a better algorithm ?”
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 53 / 64 �
NP - completeness
NP-complete problems - 2
The key notion is the notion of polynomial reduction
Polynomial reduction of problemsGiven two problems P1 and P2, P1 reduces polynomially to P2 ifthere exists an f such that :
f is polynomialx1 solution of P1 iff f(x1) solution of P2.
Example : Hamiltonian circuit is polynomially reductible to TSP.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 54 / 64 �NP - completeness
NP-complete problems - 3
The most difficult problems in NP. All problems in NPC arecomputationally equivalent in the sense that, if one problemis easy, all the problems in the class are easy. Therefore, if oneproblem in NPC turns out to be in P, then
P=NP
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 55 / 64 �
NP - completeness
NP-complete problems - 4
Reminder : we want to characterise the most difficult problemsin NP.
NP-completeA problem is said to be NP-complete if :
It belongs to NPAll other problems in NP reduce polynomially to it.
In other words, if we solve any NP-complete in polynomial time,we have proved P = NP (and we become rich)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 56 / 64 �
NP - completeness
NP-complete problems - 4
Problem : how to prove that a problem is NP-complete ?The very first one is hard to proveThen, we use the following result :
If two problems / languages L1 and L2 belong to NP and L1 isNP-complete, and L1 reduces polynomially to L2, then L2 is
NP-complete.
I Pick one NP complete problem and try to reduce it to yourproblem.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 57 / 64 �
NP - completeness
NP-complete problems - The historical example
SATISFIABILITY is NP-complete (Cook, 1971)SAT reduces polynomially to 3SAT3SAT reduces polynomially to Vertex CoverVertex Cover reduces polynomially to Hamiltonian circuit
I “So”Hamiltonian circuit, then TSP are also NP-completeproblems
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 58 / 64 �NP - completeness
Some NP-complete (common) problems
Some classical examples :Hamiltonian cycle and TSPGraph Coloring ProblemVertex coverKnapsack (integer)Flow shop problemSudoku
The book : Computers and Intractability : A Guide to the Theoryof NP-Completeness. A short list on the french webpage :http://fr.wikipedia.org/wiki/Liste_de_probl%C3%A8mes_
NP-complets
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 59 / 64 �
NP - completeness
Conclusion - 1
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 60 / 64 �
NP - completeness
Conclusion - 2
Knowing that a given problem is NP complete is just thebeginning :
handle less general classes of inputscompute less precise solutions
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 61 / 64 �
Docs
1 Some generalities on graphs
2 Paths finding - search, and applications
3 Algorithms specific to oriented graphs
4 More difficult problems on graphs
5 NP - completeness
6 Docs
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 62 / 64 �Docs
More docs on graphs
In french : http://laure.gonnord.org/site-ens/mim/graphes/cours/cours_graphes.pdf or type “cours deThéorie des graphes” in GoogleIn english : an interactive tutorial here : http://primes.utm.edu/cgi-bin/caldwell/tutor/graph/intro.(en) The theorical book “Graph Theory”, R. Diestel(electronic version :http://diestel-graph-theory.com/basic.html)(en) e-book for algorithms : http://code.google.com/p/graph-theory-algorithms-book/
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 63 / 64 �
Docs
More docs on complexity
The Book : computers and intractability, a guide to the theoryof NP completeness, by Garey/Johnson
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 64 / 64 �
Laure Gonnord Polycopié d'Informatique Fondamentale IMA4SC � S8 � 2013
Chapitre 5
Construction d'un compilateur en Java
Ce chapitre plus pratique utilise les bases fondamentales des chapitres précédents pour construire
le �front-end� d'un compilateur en Java.
48/58
Informatique Fondamentale IMA S8Cours 5 : Lexical and Syntactic Analysis and Compiler
front-end construction
Laure Gonnordhttp://laure.gonnord.org/pro/teaching/
Université Lille 1 - Polytech Lille
2013
V - Lexical and syntactic analysis : the compiler front-end in practise
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 2 / 38 �
Refreshing memories
Compiler Front-End I Abstract Syntax Tree (AST)
int y = 12 + 4*x ;
=⇒ [TKINT, TKVAR("y"), TKEQ, TKINT(12), TKPLUS,TKINT(4), TKFOIS, TKVAR("x"), TKPVIRG]=⇒
=
yint +
12
4 x
*
int
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 3 / 38 �
Lexical Analysis aka Lexing
1 Lexical Analysis aka LexingIntro
2 Syntactic Analysis aka Parsing
3 Syntactic Analysis and rules
4 Towards a methodology for designing front-ends and simpleevaluators in Java
5 Other technologies for the front-end
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 4 / 38 �
Lexical Analysis aka Lexing Intro
What for ?
int y = 12 + 4*x ;
=⇒ [TKINT, TKVAR("y"), TKEQ, TKINT(12), TKPLUS,TKINT(4), TKFOIS, TKVAR("x"), TKPVIRG]
I The Lexing produces from a flow of characters a list oftokens.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 5 / 38 �
Lexical Analysis aka Lexing Intro
Algorithm
What’s behind ?
From a Regular language, produce an automaton (see course1)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 6 / 38 �Lexical Analysis aka Lexing Intro
Tools : lexical analysers constructors
Lex(C) JFlex(Java), OCamllex, ... are tools that produces anautomaton that recognises a given language and producestokens :(here we focus on JFlex)
input : a set of regular expressions with actions(toto.jflex).output : a .java that contains the associated automaton.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 7 / 38 �
Lexical Analysis aka Lexing Intro
Lexing tool for java : JFLEX
The official webpage : jflex.de (GPL)
A first example : numbers.flex.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 8 / 38 �
Lexical Analysis aka Lexing Intro
.lex format and compilation.flex construction
%%%p u b l i c <<<−−− generates a p u b l i c c lass%class xx <<<−−− which name i s xx . java%standalone <<<−−− standalone use ( no cup )%unicode <<<−−− encoding
%{<<<−− d e c l a r a t i o n o f l o c a l vars
%}%%
<<<−− f l e x ru l es
Compilation with :
jflex toto.flex // produces xx.java
javac xx.java // compiles into xx.class
java xx filetotest // tests if file2text is recognized
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 9 / 38 �
Lexical Analysis aka Lexing Intro
Lexing in java - ex2
An example from the flex distribution (standalone.flex)
%%
%p u b l i c <<<−−− generates a p u b l i c c lass%class Subst <<<−−− which name i s Subst . java%standalone <<<−−− standalone use ( no cup )
%unicode <<<−−− encoding
%{S t r i n g name ; <<<−− d e c l a r a t i o n o f l o c a l var
%}
%%
"name " [ a−zA−Z]+ { name = y y t e x t ( ) . subs t r i ng ( 5 ) ; }[Hh ] " e l l o " { System . out . p r i n t ( y y t e x t ( )+ " "+name+" ! " ) ; }
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 10 / 38 �Lexical Analysis aka Lexing Intro
.flex variables and functions
Access to lexing info :yytext() : last recognized stringyylength() : yytext’s length
(and other, see flex documentation on/usr/share/doc/jflex/)
Functions :yylex() lexing standard function (standalone)lexing function with cup : next_token()
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 11 / 38 �
Lexical Analysis aka Lexing Intro
Lexing in java - ex 3 - more than regular languagesCounting in JFLEX - counts.flex
[ . . ]%{ /∗ v a r i a b l e d e c l a r a t i o n ∗ /
i n t num_lines ;%}
%i n i t { /∗ code to be embedded i n the c lass cons t ruc to r ∗ /num_lines =0;
%i n i t }
%eof { /∗When EOF occurs , t h i s code i s executed ∗ /System . out . p r i n t l n ( num_lines+" l i g n e s " ) ;
%eof }
NEWLINE=\ r | \ n | \ r \ nSPACE=\ | \ t%%{NEWLINE} { num_lines ++; }{SPACE} { }
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 12 / 38 �
Syntactic Analysis aka Parsing
1 Lexical Analysis aka Lexing
2 Syntactic Analysis aka ParsingParsing ?JFlex : producing tokensJCup : construct acceptors
3 Syntactic Analysis and rules
4 Towards a methodology for designing front-ends and simpleevaluators in Java
5 Other technologies for the front-end
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 13 / 38 �
Syntactic Analysis aka Parsing Parsing ?
What’s Parsing ?
[TKINT, TKVAR("y"), TKEQ, TKINT(12), TKPLUS, TKINT(4),TKFOIS, TKVAR("x"), TKPVIRG]=⇒
=
yint +
12
4 x
*
int
or “yes, it belongs to the grammar !”
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 14 / 38 �Syntactic Analysis aka Parsing Parsing ?
From the grammar to the parser
The grammar must be a context-free grammar
S-> aSb
S-> eps
In this grammar :S is the start symbola and b are terminal tokens (produced by the lexingphase)
I This grammar recognizes anbn.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 15 / 38 �
Syntactic Analysis aka Parsing Parsing ?
So Far ...
JFlex has been used to produce acceptors for (' regular)languages.We want more (general) grammars acceptors !I From a context-free grammar, construct an automaton (seecourse 2).
Thus we need a way :to declare terminal symbols (tokens)to produce them from the input file. (JFlex)to write grammars.
I In .flex and .cup files.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 16 / 38 �
Syntactic Analysis aka Parsing JFlex : producing tokens
Terminal symbols/tokens
For instance :numbersidentifiersoperationskeywordsbraces, brackets
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 17 / 38 �
Syntactic Analysis aka Parsing JFlex : producing tokens
Returning tokens With Java/JFLex
Tokens as symbol instances
"+ " { return symbol (sym .PLUS ) ; }
(using Symbol from java_cup.runtime.Symbol)
The token may have values :an integer value for numbersa string value for identifiants
Tokens with values
[0−9]+ { return symbol (sym . TKINT , new In tege r ( y y t e x t ( ) ) ) ; }
Tokens must be declared (in cup file), see later.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 18 / 38 �Syntactic Analysis aka Parsing JCup : construct acceptors
.cup format and compilation
.cup construction
impor t java_cup . runt ime . ∗ ; <<<−−− impor ts
i n i t w i th { : . . . : } ; <<<−−− o p t i o n a l user codet h i s one to be execut ing before pars ing
te rm ina l . . . . : <<<−−− token d e c l a r a t i o nnon te rm ina l . . . ;
precedence . . . ; <<<−−− precedence and a s s o c i a t i v i t y ( opt )
S : : = . . . ; <<<−− grammar ru l es and ( opt ) ac t i ons
The compilation of the cup file produces parser.java andsym.java
java -jar java-cup-11a.jar toto.cup
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 19 / 38 �
Syntactic Analysis aka Parsing JCup : construct acceptors
Recognising anbn - with Flex and Cup -1anbn.flex
impor t java_cup . runt ime . ∗ ; / / impor t Symbol c lass etc%%%class Anbn%unicode%l i n e%column%cup%{/∗ create tokens along wi th l i n e , co l . numbers ∗ /p r i v a t e Symbol symbol ( i n t type ) {
return new Symbol ( type , yy l i ne , yycolumn ) ;}
%}%%
/∗ r u l es ∗ /’ ’ a ’ ’ { return symbol (sym .TKA) ; }’ ’ b ’ ’ { return symbol (sym .TKB) ; }
I flex generates Anbn.javaLaure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 20 / 38 �
Syntactic Analysis aka Parsing JCup : construct acceptors
Recognising anbn - with Flex and Cup -2
anbn.cup
impor t java_cup . runt ime . ∗ ;
parser code { : /∗ to handle syntax e r r o r s ∗ /p u b l i c void r e p o r t _ f a t a l _ e r r o r ( S t r i n g message , Object i n f o )
throws Except ion {r e p o r t _ e r r o r ( message , i n f o ) ;throw new Except ion ( " Syntax Er ro r " ) ;}
: } ;
t e rm ina l TKA,TKB;non te rm ina l S ;
S : : = TKA S TKB | ;
I cup generates two classes : parser.java and sym.java
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 21 / 38 �
Syntactic Analysis aka Parsing JCup : construct acceptors
Recognising anbn - with Flex and Cup -3The main class :
Analyseur.java
impor t java . i o . ∗ ;
p u b l i c c lass Analyseur {s t a t i c p u b l i c void main ( S t r i n g argv [ ] ) {
t r y {parser p = new parser (new Anbn (new Fi leReader ( argv [ 0 ] ) ) ) ;Object r e s u l t = p . parse ( ) ;System . out . p r i n t l n ( " \ n f i l e OK" ) ;
} catch ( Except ion e ) {System . out . p r i n t l n ( " \ n f i l e not found ? " ) ;
}}
}
I Compiled with all .java. I warning, to run, java-cup-11a.jarmust be in the classpath (or used with the -cp option)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 22 / 38 �Syntactic Analysis aka Parsing JCup : construct acceptors
A Makefile for flex/cupJFLEX=/home/laure/analyseurs/jflex-1.4.3/bin/jflex
CUPJAR=/home/laure/analyseurs/jflex-1.4.3/java-cup-11a.jar
# directory/package containing your sources
CUPFILE=anbn.cup # the cup file containing your grammar
LEXFILE=anbn.flex # the flex file containing your lexical analyzer
CPATH=.:$(CUPJAR)
SOURCES=*.java
all: cup flex
javac -cp $(CPATH) $(SOURCES)
cup: $(CUPFILE)
java -jar $(CUPJAR) $(CUPFILE)
flex: $(LEXFILE)
$(JFLEX) $(LEXFILE)
clean:
rm *.class parser.java sym.java *~ Anbn.java
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 23 / 38 �
Syntactic Analysis and rules
1 Lexical Analysis aka Lexing
2 Syntactic Analysis aka Parsing
3 Syntactic Analysis and rules
4 Towards a methodology for designing front-ends and simpleevaluators in Java
5 Other technologies for the front-end
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 24 / 38 �
Syntactic Analysis and rules
So Far ...
JFLex/Cup have been used to produce acceptors forcontext-free languages
=⇒ the abstract syntax tree remains to be constructed (thenused !)
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 25 / 38 �
Syntactic Analysis and rules
Semantic actions
Semantic actions : code that are performed each time agrammar rule is matched.
Printing as a semantic action in JavaCup
S: : = TKA S TKB { : System . out . p r i n t l n ( " ru le1 " ) ; : }
I We can do more than pretty print !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 26 / 38 �Syntactic Analysis and rules
Semantic actions for expressions
a part of expr.flex
{ i n t e g e r } { return symbol (sym . TKINT , new In tege r ( y y t e x t ( ) ) ) ; }"+ " { return symbol (sym .TKPLUS) ; }
a part of expr.cup
non te rm ina l I n tege r E ;
S : : = E : e TKSEMICOL { : System . out . p r i n t l n ( e . i n tVa lue ( ) ) ; : };
E : : = TKINT : n{ : RESULT = new In tege r ( n . i n tVa lue ( ) ) ; : }
| E : e1 TKPLUS E: e2{ : RESULT = new In tege r ( e1 . i n tVa lue ( ) + e2 . i n tVa lue ( ) ) ; : }
I we can attach attributes to (non) terminals.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 27 / 38 �
Syntactic Analysis and rules
Semantic actions : priorities
We can tell JavaCup how to solve conflicts while parsing :precedences to solve 3 + 4 * 5
associativity to solve the pb of 3 + 4 + 5
nonassoc : 2==0 but not 3==6==10
a part of expr.cup
precedence l e f t TKPLUS;precedence l e f t TKTIMES ; / / ∗ has more precedence than +[ . . . ]
S : : = . . .
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 28 / 38 �
Syntactic Analysis and rules
Explicit AST, why ?
Why not program our compilers entirely using semanticactions ?
Because manipulating a tree is easier.Because the semantics actions are not really easy to readBecause of the separation of concernshttp:
//en.wikipedia.org/wiki/Separation_of_concerns
I Parse, then evaluate/print/construct another internalrepresentation, . . .
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 29 / 38 �
Syntactic Analysis and rules
Semantic actions and explicit AST in Java - 1The class ASTExpr.java : The Tree !
p u b l i c c lass ASTExpr {f i n a l s t a t i c i n t INT=0 , ADD=1 , MUL=2 ;i n t tag ;i n t as In t ; / / value used i f tag = INTASTExpr e1 , e2 ; / / used i f ADD or MUL/ / Const ruc torsASTExpr ( i n t i ) { tag = INT ; as In t = i ; }ASTExpr ( ASTExpr e1 , i n t op , ASTExpr e2 ) {
tag = op ; t h i s . e1 = e1 ; t h i s . e2 = e2 ; }/ / eva lua t i on o f an expressioni n t eval ( ) {
switch ( t h i s . tag ) {case ASTExpr . INT : return t h i s . as I n t ;case ASTExpr .ADD: return t h i s . e1 . eva l ( )+ t h i s . e2 . eva l ( ) ;case ASTExpr .MUL: return t h i s . e1 . eva l ( )∗ t h i s . e2 . eva l ( ) ;}
throw new Er ro r ( " i n c o r r e c t tag " ) ;}
}
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 30 / 38 �Syntactic Analysis and rules
Semantic actions and explicit AST in Java - 2
a part of expr.cup
non te rm ina l ASTExpr E ;
S : : = E : e TKSEMICOL { : System . out . p r i n t l n ( e . eva l ( ) ) ; : };
E : : = TKINT : n{ : RESULT = new ASTExpr ( n . i n tVa lue ( ) ) ; : }
| E : e1 TKPLUS E: e2{ : RESULT = new ASTExpr ( e1 , ASTExpr .ADD, e2 ) ; : }
;
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 31 / 38 �
Towards a methodology for designing front-ends and simpleevaluators in Java
1 Lexical Analysis aka Lexing
2 Syntactic Analysis aka Parsing
3 Syntactic Analysis and rules
4 Towards a methodology for designing front-ends and simpleevaluators in Java
5 Other technologies for the front-end
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 32 / 38 �
Towards a methodology for designing front-ends and simpleevaluators in Java
The running example
vars x,y,z;
y:=13;
z:=80;
x:=y+z;
z:=x*12;
print(x);
I Parse and evaluate expressions in Java !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 33 / 38 �
Towards a methodology for designing front-ends and simpleevaluators in Java
Questions
What is the grammar ? (and keywords, and end symbols ...)Write the lex and cup files.Construct the intermediate representation in Java ButHow ?
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 34 / 38 �Towards a methodology for designing front-ends and simple
evaluators in Java
A class hierarchy as intermediate representation
A quick look at the grammar :
program ::= instruction_l
instruction_l ::= instruction instruction_l
instruction ::= declaration | assignment | print
ThenEach non-terminal is a class.Instruction will be an abstract classclass Declaration extends Instruction
the class Program will have an interpret() function.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 35 / 38 �
Towards a methodology for designing front-ends and simpleevaluators in Java
Last ( ?) problem
We have to store the variables and their (current) values, thecontextI Use a hashmap !
HashMap<String,Integer> currentContext
I Evaluating an expression requires this context !
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 36 / 38 �
Other technologies for the front-end
1 Lexical Analysis aka Lexing
2 Syntactic Analysis aka Parsing
3 Syntactic Analysis and rules
4 Towards a methodology for designing front-ends and simpleevaluators in Java
5 Other technologies for the front-end
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 37 / 38 �
Other technologies for the front-end
Front-end more recent technologies
XML parsers (java, . . . ) : more for data languagesANTLR (multi languages)ROSE (C/C++ frontend) : source to source translator,provides high level functions in C++LLVM, (C/C++) more for code optimisation, still in researchdomain.
Laure Gonnord (Lille1/Polytech) Informatique Fondamentale IMA S8 2013 S8-SC � 38 / 38 �