-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathAFN.info.htm
63 lines (55 loc) · 1.62 KB
/
AFN.info.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
<!DOCTYPE HTML>
<html>
<head>
<title>AFN</title>
<link rel="stylesheet" type="text/css" href="css/Thompson.css">
<style>
</style>
</head>
<body>
<a href="index.htm">Index</a> - <a href="xml/fr/doc/index.htm">Documentation</a>
<h1>AFN</h1>
<a name="toc1"></a>
<h2>Préambule</h2>
<p>
AFN = <a href="AF.info.htm">Automate Fini</a> Non déterministe<br>
( NFA = Non Finite Automaton )
</p>
<ul>
<li>peut avoir plusieurs transitions pour un état et un symbole.</li>
<li>peut avoir des transitions ε (transition sans lire de caractère).</li>
</ul>
<h2>Conversion des ER en AFN</h2>
<p>
Une analyse lexicale et syntaxique est réalisée sur l'<a href="src/regexp/syntax.htm" target="_INFO" title="expressions régulières">ER</a>,
puis depuis l'<a href="src/regexp/preview.htm" title="arbre syntaxique transformé">AST</a> obtenu,
on utilise l'algorithme de Thompson pour créer notre NFA :
</p>
<table cellspacing="20">
<tr>
<th>transition ε</th>
<th><div class="thompson epsilon" title=""></div></th>
</tr>
<tr>
<th>transition symbole</th>
<th><div class="thompson character" title=""></div></th>
</tr>
<tr>
<th>Alternative N<sub>1</sub>|N<sub>2</sub></th>
<th><div class="thompson alternation" title=""></div></th>
</tr>
<tr>
<th>Concatenation N<sub>1</sub>N<sub>2</sub></th>
<th><div class="thompson concatenation" title=""></div></th>
</tr>
<tr>
<th>Répétition N<sub>1</sub>*</th>
<th><div class="thompson kleeneClosure" title=""></div></th>
</tr>
<tr>
<th>Option N<sub>1</sub>?</th>
<th><div class="thompson optional" title=""></div></th>
</tr>
</table>
</body>
</html>