blob: c7efde664f28d66de37f0533b6a859734161f160 (
plain)
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
|
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Language" content="en_EN" />
<meta name="author" content="Patrick Simianer" />
<title>Visualizing Regular Expressions | regexvis</title>
<link rel="stylesheet" type="text/css" href="stylesheets/styles.css" />
<!-- http://raphaeljs.com -->
<script type="text/javascript" src="javascripts/lib/raphael.js"></script>
<!-- http://jquery.com -->
<script type="text/javascript" src="javascripts/lib/jquery.js"></script>
<!-- http://jqueryui.com -->
<script type="text/javascript" src="javascripts/lib/jquery-ui.js"></script>
<!-- http://bassistance.de/jquery-plugins/jquery-plugin-tooltip/ -->
<script type="text/javascript" src="javascripts/lib/jquery.bgiframe.js"></script>
<script type="text/javascript" src="javascripts/lib/jquery.dimensions.js"></script>
<script type="text/javascript" src="javascripts/lib/jquery.tooltip.js"></script>
<link rel="stylesheet" type="text/css" href="stylesheets/jquery.tooltip.css" />
<script type="text/javascript" src="javascripts/globals.js"></script>
<script type="text/javascript" src="javascripts/NfaState.js"></script>
<script type="text/javascript" src="javascripts/Nfa.js"></script>
<script type="text/javascript" src="javascripts/RegexParser.js"></script>
<script type="text/javascript" src="javascripts/Stack.js"></script>
<script type="text/javascript" src="javascripts/NfaSimulator.js"></script>
<script type="text/javascript" src="javascripts/Nfa2Dfa.js"></script>
<script type="text/javascript" src="javascripts/graph.js"></script>
<script type="text/javascript" src="javascripts/ui.js"></script>
</head>
<body>
<div id="wrapper">
<!-- meta -->
<div id="top">
<a id="reloadButton" class="message gray grayc" href='#'>Reload</a>
<a id="descButton" class="message gray grayc" href="#">Description</a>
<span id="desc">This is little application to visualize <a href="http://en.wikipedia.org/wiki/Regular_expression">regular expressions</a>
using a <a href="http://en.wikipedia.org/wiki/Finite_state_automata">deterministic finite state automaton</a>.
It was developed for a seminar by Karin Haenelt --
"<a href="http://kontext.fraunhofer.de/haenelt/kurs/FSA/index.html">Endliche Automaten für die Sprachverarbeitung</a>"
in summer term 2010. It is written in pure JavaScript (plus some SVG and underlying HTML) using the
<a href="http://raphaeljs.com/">Raphaël</a> and <a href="http://jquery.com/">jQuery</a> libraries. The corresponding
presentation can be downloaded <a href="">here</a> (in German).<br />
The project includes a parser for basic regular expressions, a simulator for testing if a given word is included in the
language defined by the regular expression and additional a relatively fancy simulator for checking includance graphically step
by step. These parts are based on several standard algorithms which can be found in the following literature:
<ul>
<li><strong>Recursive descent parser, Thompson's algorithm:</strong>
<em>Algorithmen in Java</em> (Hans Werner Lang);
<em>Regular expression search algorithm</em> (K. Thompson);
<em>Compilers. Principles, Techniques & Tools.</em> (Aho et al)</li>
<li><strong>Epsilon closure:</strong> <em>The treatment of epsilon moves in subset construction.</em> (Gertjan van Noord)</li>
</ul>
The user interface should be self explanatory and fail safe but you can obtain help for each step by hovering over The
corresponding <span style="font-family:Courier">?</span> symbol. If there's a problem just click <em>Reload</em>.
<p class="small"><strong>Browser compatibility:</strong>
<ul>
<li><em>Firefox</em> (3-31): full functionality</li>
<li><em>Opera</em> (10): full functionality</li>
<li><em>WebKit (Safari/Chrome)</em>: backspace in graphical simulation does not work</li>
<li><em>Internet Explorer:</em> unknown, probably none</li>
</ul>
</p>
<p class="small r">To hide this text click <em>Description</em> again.</p>
</span>
</div>
<!-- /meta -->
<!-- form -->
<table>
<tr>
<td><div class="message gray grayc">-1</div></td>
<td style="width:200px" class="r grayc"><strong>Alphabet:</strong></td>
<td style="width:500px">
<strong class="grayc"><div id="alphabet"></div></strong>
</td>
<td>
<div title="Alphabet: - The alphabet that is usable in the regular expression. The symbol
<span style='font-family:Courier'>%</span> and all special characters
(see help for <em>Regular Expression</em>) are forbidden and will be removed, any whitespace will be omitted.
Input will be treated case sensitive. Double click to change the usable symbols (click outside the
input box to save)." id="helpAlphabet" class="message green greenc help">?</div>
</td>
</tr>
<tr>
<td><div class="message gray grayc"> 0</div></td>
<td class="r grayc"><strong>Draw Graph:</strong></td>
<td>
<input id="graphit" type="checkbox" name="graphit" value="" autocomplete="off" checked="checked" />
</td>
<td>
<div title="Draw Graph: - Tick if you want a graphical simulation (default), untick for simple checking."
id="helpGraph" class="message green greenc help">?</div>
</td>
</tr>
<tr>
<td><div class="message gray grayc"> 1</div></td>
<td class="r"><strong>Regular Expression:</strong></td>
<td>
<input id="regex" type="text" name="regex" value="" autocomplete="off" />
<input type="button" name="parseButton" id="parseButton" value="Parse" disabled='disabled' autocomplete="off" />
</td>
<td>
<div title="Regular Expression: - Enter a regular expression here, the special symbols
<span style='font-family:Courier'>*</span>, <span style='font-family:Courier'>|</span> and
<span style='font-family:Courier'>()</span> are currently supported. Click on <em>Parse</em> to parse
the string. If <em>Draw Graph</em> is ticked the corresponding graph will be drawn below."
id="helpRe" class="message green greenc help">?</div>
</td>
</tr>
<tr>
<td><div class="message gray grayc"> 2</div></td>
<td class="r"><strong>Word:</strong></td>
<td>
<input id="word" type="text" name="word" value="" disabled="disabled" autocomplete="off" />
<input id="checkButton" type="button" name="checkButton" value="Check" disabled='disabled' autocomplete="off" />
</td>
<td>
<div title="Word: - Enter the word to be simulated here. The simulation process will be shown step by step
if <em>Draw Graph</em> was ticked before parsing, otherwise click on <em>Check</em> to simulate the word.
Backspace works as expected. <span class='small'>Do not type too fast during graphical simulation,
because synchronization is not perfect, you can press backspace several times in case of problems.</span>"
id="helpWord" class="message green greenc help">?</div>
</td>
</tr>
</table>
<!-- /form -->
<!-- messages -->
<p>
<span id="parseMessage" class="message" style="display:none"></span>
<span id="checkMessage" class="message" style="display:none"></span>
</p>
<!-- /messages -->
<!-- svg drawing area -->
<div id="holder"></div>
<!-- /svg drawing area -->
</div>
</body>
</html>
|
