sto il creatore di Debuggex, i cui requisiti sono molto simile al tuo: ottimizzare per la quantità di informazioni che possono essere visualizzati.
Di seguito è riportato uno snippet pesantemente modificato (per la leggibilità) dal parser utilizzato da Debuggex. Non funziona così com'è, ma ha lo scopo di dimostrare l'organizzazione del codice. La maggior parte della gestione degli errori è stata rimossa. Quindi c'erano molti pezzi di logica che erano semplici ma prolissi.
Si noti che viene utilizzato recursive descent. Questo è ciò che hai fatto nel tuo parser, tranne che il tuo è appiattito in una singola funzione. Ho usato circa questa grammatica per la mia:
Regex -> Alt
Alt -> Cat ('|' Cat)*
Cat -> Empty | (Repeat)+
Repeat -> Base (('*' | '+' | '?' | CustomRepeatAmount) '?'?)
Base -> '(' Alt ')' | Charset | Literal
Charset -> '[' (Char | Range | EscapeSeq)* ']'
Literal -> Char | EscapeSeq
CustomRepeatAmount -> '{' Number (',' Number)? '}'
Si noterà un sacco del mio codice è solo a che fare con le peculiarità del sapore javascript di espressioni regolari. È possibile trovare ulteriori informazioni su di loro a this reference. Per PHP, this ha tutte le informazioni che ti servono. Penso che tu stia molto bene con il parser; tutto ciò che rimane è implementare il resto degli operatori e ottenere i casi limite giusto.
:) Enjoy:
var Parser = function(s) {
this.s = s; // This is the regex string.
this.k = 0; // This is the index of the character being parsed.
this.group = 1; // This is a counter for assigning to capturing groups.
};
// These are convenience methods to make reading and maintaining the code
// easier.
// Returns true if there is more string left, false otherwise.
Parser.prototype.more = function() {
return this.k < this.s.length;
};
// Returns the char at the current index.
Parser.prototype.peek = function() { // exercise
};
// Returns the char at the current index, then advances the index.
Parser.prototype.next = function() { // exercise
};
// Ensures c is the char at the current index, then advances the index.
Parser.prototype.eat = function(c) { // exercise
};
// We use a recursive descent parser.
// This returns the root node of our tree.
Parser.prototype.parseRe = function() {
// It has exactly one child.
return new ReTree(this.parseAlt());
// We expect that to be at the end of the string when we finish parsing.
// If not, something went wrong.
if (this.more()) {
throw new Error();
}
};
// This parses several subexpressions divided by |s, and returns a tree
// with the corresponding trees as children.
Parser.prototype.parseAlt = function() {
var alts = [this.parseCat()];
// Keep parsing as long as a we have more pipes.
while (this.more() && this.peek() === '|') {
this.next();
// Recursive descent happens here.
alts.push(this.parseCat());
}
// Here, we allow an AltTree with single children.
// Alternatively, we can return the child if there is only one.
return new AltTree(alts);
};
// This parses several concatenated repeat-subexpressions, and returns
// a tree with the corresponding trees as children.
Parser.prototype.parseCat = function() {
var cats = [];
// If we reach a pipe or close paren, we stop. This is because that
// means we are in a subexpression, and the subexpression is over.
while (this.more() && ')|'.indexOf(this.peek()) === -1) {
// Recursive descent happens here.
cats.push(this.parseRepeat());
}
// This is where we choose to handle the empty string case.
// It's easiest to handle it here because of the implicit concatenation
// operator in our grammar.
return (cats.length >= 1) ? new CatTree(cats) : new EmptyTree();
};
// This parses a single repeat-subexpression, and returns a tree
// with the child that is being repeated.
Parser.prototype.parseRepeat = function() {
// Recursive descent happens here.
var repeat = this.parseBase();
// If we reached the end after parsing the base expression, we just return
// it. Likewise if we don't have a repeat operator that follows.
if (!this.more() || '*?+{'.indexOf(this.peek()) === -1) {
return repeat;
}
// These are properties that vary with the different repeat operators.
// They aren't necessary for parsing, but are used to give meaning to
// what was parsed.
var min = 0; var max = Infinity; var greedy = true;
if (this.peek() === '*') { // exercise
} else if (this.peek() === '?') { // exercise
} else if (this.peek() === '+') {
// For +, we advance the index, and set the minimum to 1, because
// a + means we repeat the previous subexpression between 1 and infinity
// times.
this.next(); min = 1;
} else if (this.peek() === '{') { /* challenging exercise */ }
if (this.more() && this.peek() === '?') {
// By default (in Javascript at least), repetition is greedy. Appending
// a ? to a repeat operator makes it reluctant.
this.next(); greedy = false;
}
return new RepeatTree(repeat, {min:min, max:max, greedy:greedy});
};
// This parses a "base" subexpression. We defined this as being a
// literal, a character set, or a parnthesized subexpression.
Parser.prototype.parseBase = function() {
var c = this.peek();
// If any of these characters are spotted, something went wrong.
// The) should have been eaten by a previous call to parseBase().
// The *, ?, or + should have been eaten by a previous call to parseRepeat().
if (c === ')' || '*?+'.indexOf(c) !== -1) {
throw new Error();
}
if (c === '(') {
// Parse a parenthesized subexpression. This is either a lookahead,
// a capturing group, or a non-capturing group.
this.next(); // Eat the (.
var ret = null;
if (this.peek() === '?') { // excercise
// Parse lookaheads and non-capturing groups.
} else {
// This is why the group counter exists. We use it to enumerate the
// group appropriately.
var group = this.group++;
// Recursive descent happens here. Note that this calls parseAlt(),
// which is what was initially called by parseRe(), creating
// a mutual recursion. This is where the name recursive descent
// comes from.
ret = new MatchTree(this.parseAlt(), group);
}
// This MUST be a) or something went wrong.
this.eat(')');
return ret;
} else if (c === '[') {
this.next(); // Eat the [.
// Parse a charset. A CharsetTree has no children, but it does contain
// (pseudo)chars and ranges, and possibly a negation flag. These are
// collectively returned by parseCharset().
// This piece can be structured differently depending on your
// implementation of parseCharset()
var opts = this.parseCharset();
// This MUST be a ] or something went wrong.
this.eat(']');
return new CharsetTree(opts);
} else {
// Parse a literal. Like a CharsetTree, a LiteralTree doesn't have
// children. Instead, it contains a single (pseudo)char.
var literal = this.parseLiteral();
return new LiteralTree(literal);
}
};
// This parses the inside of a charset and returns all the information
// necessary to describe that charset. This includes the literals and
// ranges that are accepted, as well as whether the charset is negated.
Parser.prototype.parseCharset = function() {
// challenging exercise
};
// This parses a single (pseudo)char and returns it for use in a LiteralTree.
Parser.prototype.parseLiteral = function() {
var c = this.next();
if (c === '.' || c === '^' || c === '$') {
// These are special chars. Their meaning is different than their
// literal symbol, so we set the 'special' flag.
return new CharInfo(c, true);
} else if (c === '\\') {
// If we come across a \, we need to parse the escaped character.
// Since parsing escaped characters is similar between literals and
// charsets, we extracted it to a separate function. The reason we
// pass a flag is because \b has different meanings inside charsets
// vs outside them.
return this.parseEscaped({inCharset: false});
}
// If neither case above was hit, we just return the exact char.
return new CharInfo(c);
};
// This parses a single escaped (pseudo)char and returns it for use in
// either a LiteralTree or a CharsetTree.
Parser.prototype.parseEscaped = function(opts) {
// Here we instantiate some default options
opts = opts || {};
inCharset = opts.inCharset || false;
var c = peek();
// Here are a bunch of escape sequences that require reading further
// into the string. They are all fairly similar.
if (c === 'c') { // exercises
} else if (c === '0') {
} else if (isDigit(c)) {
} else if (c === 'x') {
} else if (c === 'u') {
// Use this as an example for implementing the ones above.
// A regex may be used for this portion, but I think this is clearer.
// We make sure that there are exactly four hexadecimal digits after
// the u. Modify this for the escape sequences that your regex flavor
// uses.
var r = '';
this.next();
for (var i = 0; i < 4; ++i) {
c = peek();
if (!isHexa(c)) {
throw new Error();
}
r += c;
this.next();
}
// Return a single CharInfo desite having read multiple characters.
// This is why I used "pseudo" previously.
return new CharInfo(String.fromCharCode(parseInt(r, 16)));
} else { // No special parsing required after the first escaped char.
this.next();
if (inCharset && c === 'b') {
// Within a charset, \b means backspace
return new CharInfo('\b');
} else if (!inCharset && (c === 'b' || c === 'B')) {
// Outside a charset, \b is a word boundary (and \B is the complement
// of that). We mark it one as special since the character is not
// to be taken literally.
return new CharInfo('\\' + c, true);
} else if (c === 'f') { // these are left as exercises
} else if (c === 'n') {
} else if (c === 'r') {
} else if (c === 't') {
} else if (c === 'v') {
} else if ('dDsSwW'.indexOf(c) !== -1) {
} else {
// If we got to here, the character after \ should be taken literally,
// so we don't mark it as special.
return new CharInfo(c);
}
}
};
// This represents the smallest meaningful character unit, or pseudochar.
// For example, an escaped sequence with multiple physical characters is
// exactly one character when used in CharInfo.
var CharInfo = function(c, special) {
this.c = c;
this.special = special || false;
};
// Calling this will return the parse tree for the regex string s.
var parse = function(s) { return (new Parser(s)).parseRe(); };
Hai provato a utilizzare regex? Oh no, hai già una dozzina di problemi: O –
@Ivo: In effetti, la mia prima implementazione era basata sulle regex, ma è diventato così complicato che sono passato a un semplice loop basato sui caratteri. –
Vuoi davvero implementare qualcosa di simile a http://xenon.stanford.edu/~xusch/regexp/analyzer.html corretto? –