Le décodage Kaldi/FST pour la reconnaissance de l'écriture Wassim Swaileh
Tutoriel pour la pris en main de Kaldi / FST pour la reconnaissance de l'écriture
Finite state transducers, decoding graph with kaldi, decoding approaches of kaldi
Tout le monde connait les annotations dans Java notamment par le biais de la JSR 330. Par contre connaissez-vous les décorateurs Python ? Je vous propose un petit parallèle des deux approches qui sont diamétralement opposées et qui pourtant peuvent contribuer aux mêmes types de problématiques.
This document discusses the operating system architecture and system calls of the Tock operating system. It describes the key components of Tock including processes, system calls like command, subscribe, yield, and allow, and the driver API. Processes in Tock are isolated and protected with memory protection units. System calls allow processes to interact with drivers to perform actions or register callbacks. Drivers implement the SyscallDriver trait to handle system calls.
This document discusses Android services and AIDL (Android Interface Definition Language). It describes services as Android components that run in the background for ongoing tasks and processes with lower priority. Services have lifecycle methods like onCreate(), onStart(), and onDestroy(). Services can implement AIDL to allow activities to remotely call methods on the service. AIDL defines the interface for remote communication between components using a Java-like language and limited data types. The example shows a service that returns prime numbers every second and how to connect to it using AIDL.
This document discusses threads in Android. It defines threads as splits in a process that allow for multiple processing ways through separate functions. There are two types of threads: user threads and kernel threads. User threads are fast-switching but can block the whole process if one thread blocks, while kernel threads only block individual threads and allow for OS semaphores. Java implements threads through either extending the Thread class and overriding the run() method, or implementing the Runnable interface and providing a run() method. The difference between Runnable and Thread is that Runnable is an interface that allows objects to extend other classes, while Thread is a class that objects must extend.
This document discusses lists, adapters, and recycling in Android. It covers the model-view-controller pattern and how ListActivity works. ArrayAdapter and custom adapters extend BaseAdapter to display data from a model in a list. Adapters reuse list elements to optimize performance through recycling and tagging views. Lists can contain simple or complex elements defined in XML.
This document provides an overview of building Android user interface (UI) applications. It discusses Android concepts like tasks, activities, intents, manifest files, resources, and widgets. Activities are organized into tasks that display a stack. Developers construct GUIs with XML layout files and add interactivity with intents. The manifest declares app components and permissions. Resources like strings, images and layouts are stored in XML files and accessed programmatically. Toasts display short notifications. Key topics include tasks, activities, containers, menus, resources, and widgets.
Android is a software stack that includes an operating system, middleware, and key applications. It uses a modified version of the Linux kernel and other open source software. The Android runtime, known as Dalvik and later ART, allows apps to be run in a virtual machine using the Java programming language. Android apps are composed of components like activities, services, content providers and broadcast receivers that can interact and run either in the foreground or background. The Android SDK provides libraries for building apps that have access to the device's capabilities like sensors, internet connectivity and more.
This document provides an overview of the hardware components and software platforms used in mobile devices. It discusses the main processors used (ARM, RISC), memory types (RAM, SSD), display technologies (touchscreens, resolutions), connectivity radios (WiFi, Bluetooth), operating systems (Android, iOS, Windows), and programming languages (Java, Swift, C++). It also covers other components like sensors, storage, and development boards for prototyping mobile applications.
This document provides information about a new mobile device applications course, including rules, an outline of topics, required knowledge, expectations, and a golden ticket opportunity. The key points are:
- Students must start their video cameras for the entire course and actively participate by asking questions. Exams will be 70% written and 30% labs and homework, with a minimum of 5 labs required to enter the exam.
- The course will cover Android and iOS devices, applications, services, and internet technologies. Topics include languages like Java, Kotlin, C++, and TypeScript.
- Students should spend about 8 hours per week on the course, including 2 hours of classes and 1 hour of labs, with
La Révolution Bénédictine Casadéenne du Livradois-Forez: De Charlemagne à Fra...Editions La Dondaine
An elderly vacationing researcher, a researcher still in marching order, and an industrialist whose company is a world leader in the field of braiding and cables, are here – finally – beginning to examine the roots of Livradois-Forez. Where did the braiding industry and its very special and specific technique come from? Where did the cultivation of Indian hemp come from, which would provide cable and canvas, two essential elements when Colbert decided to build the Royal Navy of Louis XIV, the Sun King, in Saint Nazaire? The third essential element was wood, and it would be the Casadean pine.
Concerning the development of Livradois-Forez, very little is known at the time of the Gauls, and even the Gallo-Romans, it was totally ignored under the Merovingians, and would only begin after the reforms of Charlemagne (King and Emperor 768-814), and above all the religious reform which compulsorily released 52 Sundays, then 3 weeks of festivities for the Nativity, the Passion, and the Assumption, plus some local religious festivals, in all 80 days of non-working time for everyone. This reform would find its crowning moment with the Gregorian Reform of Gregory VII (Pope 1073-1095) who, against the Germanic Emperors, would impose the supreme authority of the church, the Papacy, Rome.
All these are only the foundations of the development which will be led by the engineers of the Middle Ages, the Benedictines, who Christianized Europe from England and Ireland, then agriculturalized Europe from local resources. With the final abolition of slavery, and the unification of land ownership (Lords, Church-Abbeys, and a few autonomous allod-holders), a true agricultural green revolution can come, with the invention of the horse's collar which can henceforth plow, the horse of course, and the recovery of water mills, invented but never used by the Romans, to replace human working time devoted to Christian ritual practices, and to intensify production. In this context in 1043, Robert de Turlande founded the Abbey of La Chaise-Dieu and the tight network of priories and affiliated parishes. But the question remains of who introduced Indian hemp cultivation and braiding to this region, the very keys to many centuries of development that led to Omerin's cables of the extreme.
This is the beginning of our research, from Charlemagne to Francis I, covering eight centuries. Perhaps one day we will ask the question of the occupation of this region by the Neanderthals and the “Cromagnons,” before the Glaciation and the Gauls, at the time of the woolly rhinoceroses of Gannat and the Rhinopolis center. But how far behind, archaeology still is in Puy de Dôme!
2. Bibliographie pour aujourd'hui
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey
D. Ullman, Compilers: Principles, Techniques,
and Tools (2nd Edition)
– Chapitre 4
• 4.5
• 4.6
• 4.7.4
7. Arbre de dérivation / syntactique
E E + E
E E * E
E n
n : [0-9]+
Lexer
2 * 3 + 4 * 5
n * n + n * n
2 3 4 5
parser
n n n n
2 3 4 5
* *
+
n n n n
2 3 4 5
E * E E * E
E + E
E
• jetons (tokens)
• Valeurs
• Grammaire
• Arbre de dérivation
• Arbre syntactique
8. Types d’analyse syntactique
Descendent (top-down)
Avec backtracking
Prédictive
Descendent récursive, LL avec un tableau
Ascendant (bottom-up)
Avec backtracking
Shift-reduce
LR(0),SLR,LALR, LR canonique
9. Parser LL, LR
Nous devrions éviter backtracking
Une grammaire qui permet le parser déterministe
LL(k) lit left-to-right, dérivation left
LR(k) lit left-to-right, dérivation right
K – lookahead (combien de tokens sont lus)
LL(k) < LR(k)
L'algorithme est indépendant du langage, la
grammaire dépend du langage
10. Parser ascendant
Un analyseur vers le haut, ou shift-reduce commence à
« feuille » et construit vers le haut de l'arbre de dérivation
Étapes de réduction suivent une dérivation droite dans
l'ordre inverse
S aABe
A Abc | b
B d
GRAMMAIRE:
Nous analysons la chaîne d'entrée abbcde.
(Aho,Sethi,Ullman, pp. 195)
11. Exemple de parser ascendant
a dbb cInput:
Parser ascendant
e Output:$
Production
S aABe
A Abc
A b
B d
(Aho,Sethi,Ullman, pp. 195)
S aABe
12. Exemple de parser ascendant
a dbb c
Parser ascendant
e
A
b
$
S aABe
A Abc
A b
B d
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
13. Exemple de parser ascendant
a dbA c
Parser ascendant
e
A
b
$
S aABe
A Abc
A b
B d
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
14. Nous ne pouvons pas réduire, le parser s'arrêterait.
Exemple de parser ascendant
a dbA c
Parser ascendant
e
A
b
$
S aABe
A Abc
A b
B d
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
15. Exemple de parser ascendant
a dbA c
Parser ascendant
e
A
b
$
S aABe
A Abc
A b
B d
c
A
b
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
16. Exemple de parser ascendant
a dA
Parser ascendant
e
A c
A
b
$
S aABe
A Abc
A b
B d
b
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
17. Exemple de parser ascendant
a dA
Parser ascendant
e
A c
A
b
$
S aABe
A Abc
A b
B d
b
B
d
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
18. Exemple de parser ascendant
a BA
Parser ascendant
e
A c
A
b
$
S aABe
A Abc
A b
B d
b
B
d
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
19. Exemple de parser ascendant
a BA
Parser ascendant
e
A c
A
b
$
S aABe
A Abc
A b
B d
b
B
d
a
S
e
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
20. Exemple de parser ascendant
S
Parser ascendant A c
A
b
$
S aABe
A Abc
A b
B d
b
B
d
a
S
e
Parser LR parce que l'entrée este lu « De gauche à droite »,
et construit « dérivation plus à droite » dans l'ordre inverse.
(Aho,Sethi,Ullman, pp. 195)
Input: Output:
Production
21. Exemple de parser ascendant
• Analyse les productions pour le match
avec le texte d'entrée
• Backtracking
• Inefficace
• Pouvons-nous faire mieux?
22. Exemple de parser LR
Input
P
I
L
e
Algorithme de
parser LR
action goto
Output
(Aho,Sethi,Ullman, pp. 217)
23. Exemple de parser LR
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
GRAMMAIRE:
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
Il peut être parser avec les tableaux
‘action’ et ‘goto’
(Aho,Sethi,Ullman, pp. 219)
24. Exemple de parser LR
id idid+ Input: $
Pile: E0
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
Program de
parser LR
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
GRAMMAIRE:
Output:
(Aho,Sethi,Ullman, pp. 220)
25. id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
E5
id
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
26. 0
id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
27. E3
F
0
id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
28. 0
id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
29. id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
E2
T
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
30. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E7
2
T
0 T
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
31. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
E5
id
7
2
T
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
F
id
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
32. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
E7
2
T
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
F
id
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
33. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
E10
F
7
2
T
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
34. 0
id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
35. id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
2
T
0 T
T F
F
id
id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
E
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
36. 0
id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
37. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
1
E
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
38. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E6
+
1
E
0
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
39. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E5
id
6
+
1
E
0
F
id
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
40. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
T
T F
F
id
id
E6
+
1
E
0
F
id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5 (Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
41. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E3
F
6
+
1
E
0
F
id
T
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
42. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
T
T F
F
id
id
E6
+
1
E
0
F
id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5 (Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
43. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E9
T
6
+
1
E
0
F
id
T
E
+
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
44. id idid + $
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
0
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E
F
id
T
E
+
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
45. id idid + $
(1) E E + T
(2) E’ T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
T
T F
F
id
id
E1
E
0 F
id
T
E
+
(Aho,Sethi,Ullman, pp. 220)
Exemple de parser LR
Input:
Pile:
Program de
parser LR
GRAMMAIRE:
Output:
46. Construction de tableaux de parser
• Tous les analyseurs utilisent le même algorithme
• La différence est dans l'action et goto
• Simple LR (SLR) se poursuit moins la grammaire, mais il est le plus
facile à mettre en œuvre
• Canonique LR allez sur la plupart de grammaire, mais il est plus
difficile à mettre en œuvre.
• LR Lookahead (LALR) va sur la plupart des constructions syntaxiques
utilisées dans les langages de programmation, mais produire des
tableaux beaucoup plus petites que Canonique LR.
47. Shift-Reduce
Actions:
Une séquence de shift et reduce
Pile
Règles et jetons
Etat
Etat suivante
Pile et input
48. Actions Shift-Reduce
Shift: push lookahead
Reduce: pop , push X
pile input action
( 1+2+(3+4))+5 shift 1
(1 +2+(3+4))+5
pile input action
(S+E +(3+4))+5 reduce S S+ E
(S +(3+4))+5
49. Analyse Shift-Reduce
derivation pile input action
(1+2+(3+4))+5 (1+2+(3+4))+5 shift
(1+2+(3+4))+5 ( 1+2+(3+4))+5 shift
(1+2+(3+4))+5 (1 +2+(3+4))+5 reduce Enum
(E+2+(3+4))+5 (E +2+(3+4))+5 reduce SE
(S+2+(3+4))+5 (S +2+(3+4))+5 shift
(S+2+(3+4))+5 (S+ 2+(3+4))+5 shift
(S+2+(3+4))+5 (S+2 +(3+4))+5 reduce Enum
(S+E+(3+4))+5 (S+E +(3+4))+5 reduce SS+E
(S+(3+4))+5 (S +(3+4))+5 shift
(S+(3+4))+5 (S+ (3+4))+5 shift
(S+(3+4))+5 (S+( 3+4))+5 shift
(S+(3+4))+5 (S+(3 +4))+5 reduce E num
...
S S + E | E
E num | (S)
50. Sélection de l'action
Comment sélectionnons-nous l'action?
shift ou reduce?
Quelle règle s'appliquons-nous?
Éviter le blocage
La pile peut être réduite de plusieurs façons
51. Sélection de l'action
Starea curenta:
Pile
Symbole look-ahead b
existe la production X , et la pile est de forme =
Le parser devrait:
Shift b sur la pile, b ?
Reduce avec la production X , si la pile est = , et
transformer la pile en X ?
Décision fondée su b et le préfix
est différent pour différentes productions, parce que le
côté droit de productions (les ) peuvent avoir des
longueurs différentes
52. Algorithme de parser LR
action gotoState
id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
GRAMMAIRE:
(1) E E + T
(2) E T
(3) T T F
(4) T F
(5) F ( E )
(6) F id
53. Tableau de parser LR
Algorithme: état curent S si token C au input
Si Action[S,C] = s(S’) shift et aller sur S’:
push(C), push(S’)
Si Action[S,C] = X reduce:
pop(2*||), S’= top(), push(X), push(Goto[S’,X])
Action et
etat prochaine
Etat prochaine
Jeton (Token) Regle
Etat
Tableau ‘action’ Tableau‘Goto’
55. Exemple de etat LR(0)
Un element LR(0) est une production avec un “.”
dans la partie droite
Les éléments avant “.” sont sur la pile
Les elements apres “.” nous dire ce que nous
pouvions lire suivante
E num .
E ( . S)
etat
element
56. Grammaire LR(0)
Grammaire de liste
S (L) | id
L S | L,S
Exemple:
(a,b,c)
((a,b), (c,d), (e,f))
(a, (b,c,d), ((f,g)))
S
( L )
L , S
L , S
( L )S
a L , S
S
b
c
d
Arbre de derivation pour
(a, (b,c), d)
57. Etat de start et Closure
Etat de start
Production S’ S
Etat start: Closure (S’ . S )
Closure pour l’ensable des éléments LR(0):
Closure (S) = S
Pour toutes les éléments en S:
X . Y
Toutes les éléments LR(0) de forme Y . , pour
toutes les production Y de la grammaire
58. Exemple
S (L) | id
L S | L,S
Elément LR(0) “start”
S’ . S
Closure
S’ . S
S . (L)
S . id
59. Goto
Transitions entre les états (ensembles des éléments
LR(0) )
S’ . S
S . (L)
S . id
Goto(I, ‘(‘) Closure ( { S ( . L) } )
60. Questions
I = { [E’ . E]}, Closure (I) = ??
I = { [E’ E . ], [E E . + T] }, Goto(I,+) = ??
E’ E
E E + T | T
T T * F | F
F (E) | id
61. Goto: tokens
S’ . S
S . (L)
S . id
S ( . L)
L . S
L . L, S
S . (L)
S . id
S id .
id
(
id (
Grammaire
S (L) | id
L S | L,S
62. Goto: règles
S’ . S
S . (L)
S . id
S ( . L)
L . S
L . L, S
S . (L)
S . id
S id .
id
(
id (
Grammaire
S (L) | id
L S | L,S
S (L . )
L L . , S
L S .
L
S
63. Reduce
S’ . S
S . (L)
S . id
S ( . L)
L . S
L . L, S
S . (L)
S . id
S id .
id
(
id (
Grammaire
S (L) | id
L S | L,S
S (L . )L
L L . , S
L S .
L
S
Etats de reduce
(le point e a la fin!)
64. Automate LR
S’ . S
S . (L)
S . id
S ( . L)
L . S
L . L, S
S . (L)
S . id
S id .id
(
id
(
S (L . )
L L . , S
L S .
S
L L , . S
S . (L)
S . id
L L,S .
S (L) .
S’ S .
Etat finale / accepte
1 2 8 9
6
5
3
74
S
,
)
S
$
id
L
Grammaire
S (L) | id
L S | L,S
(
66. Tableau de parser LR(0)
Etats = états de Automate LR
S S’ avec jeton C:
Action[S,C] += Shift(S’)
S S’ avec la règle N:
Goto[S,N] += S’
Si S est état de réduction X .:
Action[S,*] += Reduce(X )
68. Limites LR(0)
Une action pou
L L , S .
L L , S .
S S . , L
L S , L .
L S .
OK shift/reduce reduce/reduce
69. num + $ E S
1 s4 g2 g6
2 SE s3/SE SE
Exemple de shift/reduce
S’ . S
S .E + S
S . E
E .num
E num .
S E . +S
S E .
E
num
+
S E + S .
accept
S
S E + . S
S . E + S
S . E
E . num
S’ S .
1 2
5
3
7
4
S Grammaire
S E + S | E
E num
$
E
num
Shift ou
reduce
etat 2?
70. Parser SLR
SLR =“Simple LR”= extension simple LR(0)
Pour X , le prochain jeton C
reduce seulement si C est de FOLLOW(X)
Résoudre partial les shift/reduce
Identique avec LR(0) sauf ‘reduction’
Réduction X seulement les symboles de FOLLOW(X)
num + $ E S
1 s4 g2 g6
2 s3 SE
Exemple: FOLLOW(S) = {$}
71. Exemple de parser SLR
num + $ E S
1 s4 g2 g6
2 s3 SE
3 s4 g2 g5
4 Enum Enum
5 SE+S
6 s7
7 accept
Grammaire
S E + S | E
E num
72. Automate SLR
S’ . S
S .E + S
S . E
E .num
E num .
“+” “$” : reduce
S E . +S
S E .
“$” : reduce
E
num
+
S E + S .
“$” : reduce
accept
S
S E + . S
S . E + S
S . E
E . num
S’ S .
1 2
5
3
7
4 S Grammaire
S E + S | E
E num
$
E
num
num + $ E S
1 s4 g2 g6
2 s3 SE
73. LALR(1)
SLR: Decizia de reduce pentru “X->” se face doar daca urmatorul
simbol e in FOLLOW(X)
LALR(1): Fiecare productie are un set de simboli care ii pot urma.
“X-> , S” se reduce doar daca urmatorul simbol e in S.
Seturile se pot calcula prin aplicarea recursiva a regulilor:
S’ .S, {$}
B α.Aβ
c in FIRST(β)
A .Xδ , {c}
B α.Aβ , {c}
c FOLLOW(β)
β * ε
A .Xδ , {c}
X α.Xβ , c
X αX.β , c
S’ .S , {$}
S .L=R
S .R
L .*R
L .ident
R .L
S’ .S , {$}
S .L=R
S .R
L .*R , {=}
L .ident , {=}
R .L
S’ .S , {$}
S .L=R , {$}
S .R , {$}
L .*R , {= $}
L .ident , {=
$}
R .L , {$}
L .ident, {= $}
L ident. , {= $}
74. DFA pentru LALR
•
S L = R
S R
L *R
L ident
R L
S’ .S {$}
S .L=R {$}
S .R {$}
L .*R {= $}
L .ident {= $}
R .L {$}
S’ S. {$}
“$” : accept
S L.=R {$}
R L. {$}
“$” : reduce
S R. {$}
“$” : reduce
L *.R {=$}
L .*R {=$}
L .ident {=$}
R .L {=$}
L ident. {$ =}
“$” “=“ : reduce
S L=.R {$}
L .*R {$}
L .ident {$}
R .L {$}
L *R. {$ =}
“$” “=“ : reduce
R L. {=$}
“$” “=“ : reduce
S L=R. {$}
“$” : reduce
S
L
L
L
R
R
R
*
*
ident
ident
*
ident
=