blob: 7e94d9c6265947a33c229e19f7faea5f22573fca (
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
|
/*
* RegexParser
* Parsing a regular expression using recursive descent method.
* parse() returns a NFA (constructed following Thompson's algrotihm).
*/
function RegexParser() {};
// Accessor functions
RegexParser.prototype.getRegex = function() { return this.regex; };
RegexParser.prototype.getErrorMessage = function() { return this.errorMessage; };
RegexParser.prototype.getErrorPosition = function() { return this.errorPosition; };
// Next symbol in regex.
RegexParser.prototype.lookahead = function() {
if (this.str.length > 0) {
return this.str.substring(0, 1);
};
return '';
};
// Removing the firstmost symbol of regex.
RegexParser.prototype.consume = function(symbol) {
this.str = this.str.substring(1);
};
// Check if symbol matches expected symbol.
RegexParser.prototype.trymatch = function(symbol) {
if (this.str.substring(0, symbol.length) == symbol) {
this.consume(symbol);
return true;
};
return false;
};
// See above.
RegexParser.prototype.match = function(symbol) {
if (!this.trymatch(symbol)) {
throw("RegexParser.match(): Expected symbol '"+symbol+"'.");
};
};
// Checks if a symbol is in set of symbols.
RegexParser.prototype.isIn = function(symbol, set) {
if (symbol.length > 0) {
return set.indexOf(symbol) >= 0;
};
return false;
};
// See above. Set = alphabet.
RegexParser.prototype.isLetter = function(symbol) {
return this.isIn(symbol, ALPHABET);
};
// Is symbol a literal?
RegexParser.prototype.literal = function() {
var symbol = this.lookahead();
if(this.isLetter(symbol)) {
this.consume(symbol);
return new Nfa(symbol);
};
throw("RegexParser.literal(): Expected a letter or '"+EMPTYSYMBOL+"'.");
};
// Atomar expression.
RegexParser.prototype.atom = function() {
if(this.trymatch('(')) {
var nfa = this.expr();
this.match(')');
return nfa;
};
return this.literal();
};
// Factor.
RegexParser.prototype.factor = function() {
return this.star(this.atom());
};
// Kleene Star.
RegexParser.prototype.star = function(nfa) {
if (this.trymatch('*')) {
return this.star(nfa.kleene());
};
return nfa;
};
// Term.
RegexParser.prototype.term = function() {
var nfa = this.factor();
var symbol = this.lookahead();
if (this.isLetter(symbol) || (symbol == '(')) {
return nfa.concat(this.term());
};
return nfa;
};
// Expression.
RegexParser.prototype.expr = function() {
var nfa = this.term();
if (this.trymatch('|')) {
return nfa.union(this.expr());
};
return nfa;
};
// Parse function.
var nfa;
RegexParser.prototype.parse = function(regex) {
this.str = regex;
this.errorMessage = 'Ok'
this.errorPosition = -1;
var nfa;
try {
nfa = this.expr();
if(this.str.length > 0) {
throw('RegexParser.parse(): Supernumerous symbols.');
};
} catch(e) {
this.errorMessage = e;
this.errorPosition = regex.length - this.str.length;
nfa = null;
};
return nfa;
};
|
