-
Notifications
You must be signed in to change notification settings - Fork 0
/
Lexers.htm
188 lines (178 loc) · 6.21 KB
/
Lexers.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
<html>
<head>
<title>Mes Lexers</title>
<style>
SECTION { margin-left: 1em; }
UL {
list-style-position: inside;
padding: 0 1em;
margin: 1em 0;
}
LI {
padding: 0 1em;
}
H2, H3 {
clear: left;
}
TD, TH {
border: 1px solid #999;
border-width: 0 1px 1px 0;
box-shadow: .25em .25em .25em #ccc;
padding: .5em;
}
TD UL {
margin: 0 0 1em;
padding: 0;
}
.lexer {
background: #eee;
}
</style>
</head>
<body>
<a href="index.htm">Index</a>
<h1>Mes Lexers</h1>
<p>J'ai créé trois différents lexers depuis une <a href="xml/fr/doc/LexerClass.xml" title="LexerClass">même base</a>, ils utilisent soit :</p>
<ul>
<li>des automates finis déterministes.</li>
<li>une expression régulière par token.</li>
<li>une expression régulière pour tous les tokens d'une règle.</li>
</ul>
<h2>Performance</h2><section>
<p>Elle est mesurée et comparée sur deux méthodes :</p>
<ul>
<li><b>readToken</b>: <a href="Lexers.performance.readToken.htm">vitesse de lecture des tokens</a> pour un lexer.</li>
<li><b>scan</b>: comparaison de la <a href="Lexers.performance.scan.htm">vitesse de lecture totale</a> des lexers.</li>
</ul>
<p>
L'<a href="Lexers.result.comparaison.htm">équivalence des résultats</a> des analyses lexicales est comparée
afin d'assurer des mesures dans des conditions identiques.
</p>
<p>La performance est dépendante de l'objet retourné par la fonction <a href="Lexeme.htm">Lexeme</a>.</p>
</section>
<h2>Caractéristiques</h2><section>
<ul>
<li>Parcours du texte une et une seule fois.</li>
<li>Détection du début d'un token parent avec imbrication de token enfant.</li>
<li>Détection de fin d'un token parent et finalisation du parent.</li>
<li>Réalisation d'un double scannage d'un token, à éviter si possible.</li>
<li>Calcul des numéros de ligne des tokens (début et fin).</li>
<li>Utilisation d'une liste d'<i>objets</i> pour reconnaître les tokens.</li>
<li>Utilisation d'une liste de <i>règles</i> pour reconnaître les syntaxes.
<blockquote>
<small><b>ATTENTION</b></small>: Premier objet arrivé, premier objet trouvé.
<ol>
<li>Un ordre est requis (mots clés avant identifiant, ...)</li>
<li>Les objets trouvés le plus souvant doivent être classés en tête :
<i>amélioration des performances</i>.</li>
</ol>
</blockquote>
</li>
<li>Contrôle optionnel du token précédant.</li>
<li>Omission de certains tokens du résultat.</li>
<li>Affectation de classes css au tokens.</li>
<li>Renommage possible des noms de token.</li>
<li><a href="Lexers.performance.scan.incremental.htm">Analyse partielle</a> pour les éditeurs de texte.</li>
</ul>
<p>
Ils réalisent une analyse à <a href="Lexers.result.comparaison.htm">plusieurs niveaux</a>:
un <i>arbre lexical</i> est créé et non pas une liste.<br>
L'avantage de cette approche est la simplification des grammaires de l'analyse syntaxique.
</p>
<p>Si vous recherchez un lexer retournant une liste de tokens, consultez le site d'Eli Bendersky, il pourra vous être utile :</p>
<ul>
<li><a target="_blank" href="http://eli.thegreenplace.net/2013/06/25/regex-based-lexical-analysis-in-python-and-javascript">Regex-based lexical analysis in Python and Javascript</a></li>
<li><a target="_blank" href="http://eli.thegreenplace.net/2013/07/16/hand-written-lexer-in-javascript-compared-to-the-regex-based-ones">Hand-written lexer in Javascript compared to the regex-based ones </a></li>
</ul>
</section>
<h2>Observations</h2><section>
<table border="1">
<tr>
<th>Lexer</th>
<th title="Objet utilisé pour reconnaître les tokens">Tokens</th>
<th title="Nombre de tokens pouvant être reconnu par un objet">Portée</th>
<th>Vitesse</th>
<th>Taille modules</th>
<th>Observations</th>
</tr>
<tr class="lexer"><th>AutomatonLexer</th>
<th>AFD</th>
<th>1..n</th>
<th style="color:orange;">moyenne</th>
<th style="color:red;">énormes</th>
<td style="color:green;">
Plus long token retourné.
</td>
</tr>
<tr>
<td colspan="6">
<ul>
<li>Les AFD doivent-être précalculés :
<ol>
<li>Chaque <a href="AFD.generator.htm">ER transformé en AFD</a></li>
<li>Les <a href="AFD.aggregator.htm">AFD sont ensuite aggrégés entre eux</a> afin d'en obtenir plus qu'un!</li>
</ol>
</li>
<li>Le défaut: il est parfois préférable d'utiliser plusieurs AFD au lieu d'un.
<ol>
<li>La taille de l'automate résultat peut être énorme !</li>
<li>La <a href="Lexers.modules.generator.htm">création de l'AFD</a> prend beaucoup de temps.</li>
</ol>
</li>
</ul>
</td>
</tr>
<tr class="lexer"><th>MultiRegExpLexer</th>
<th>ER</th>
<th>1..1</th>
<th style="color:red;">lente</th>
<th style="color:green;">normal</th>
<td style="color:red;">
Premier token arrivé, premier servi.
</td>
</tr>
<tr>
<td colspan="6">
<ul>
<li>L'ordre des ER est important.
<ol>
<li>Première arrivée, première trouvée !</li>
<li>Les ER les plus souvant rencontrés doivent être montée dans les premières position pour une performance optimisée.</li>
</ol>
</li>
</ul>
</td>
</tr>
<tr class="lexer"><th>OneRegExpLexer</th>
<th>ER</th>
<th>1..n</th>
<th style="color:green;">rapide</th>
<th style="color:green;">normal</th>
<td style="color:green;">
Plus long token retourné, par défaut.<br>
Puis premier token arrivé, premier servi.
</td>
</tr>
<tr>
<td colspan="6">
<ul>
<li>Une seule grande ER est créée pour reconnaître tous les tokens.</li>
<li>Les défauts:
<ol>
<li>Quand un mot est trouvé il faut déterminé son type. Pour cela il faut réaliser une boucle!</li>
<li>Quand le token trouvé est incompatible avec le token précédant, il faut réaliser une boucle avec les definitions de chaque token pour trouver un autre résultat.</li>
</ol>
</li>
<li>L'ordre des ER est important.
<ol>
<li>Première arrivée, première trouvée !</li>
<li>Les ER les plus souvant rencontrés doivent être montée dans les premières position pour une performance optimisée.</li>
</ol>
</li>
</ul>
</td>
</tr>
</table>
</section>
</body>
</html>