Tôi tác giả của Debuggex, có yêu cầu rất giống như của bạn: tối ưu hóa cho số lượng thông tin mà có thể được hiển thị.
Dưới đây là đoạn mã được sửa đổi nhiều (cho readablity) từ trình phân tích cú pháp mà Debuggex sử dụng. Nó không hoạt động như, nhưng có nghĩa là để chứng minh việc tổ chức mã. Hầu hết xử lý lỗi đã bị xóa. Vì vậy, có nhiều phần logic đơn giản nhưng tiết.
Lưu ý rằng recursive descent được sử dụng. Đây là những gì bạn đã làm trong trình phân tích cú pháp của mình, ngoại trừ bạn được làm phẳng thành một hàm duy nhất. Tôi đã sử dụng khoảng ngữ pháp này cho tôi:
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)? '}'
Bạn sẽ nhận thấy rất nhiều mã của tôi chỉ xử lý các đặc điểm của javascript của regex. Bạn có thể tìm thêm thông tin về họ tại this reference. Đối với PHP, this có tất cả thông tin bạn cần. Tôi nghĩ rằng bạn đang rất tốt trên con đường của bạn với phân tích cú pháp của bạn; tất cả những gì còn lại là thực hiện phần còn lại của các toán tử và nhận được các trường hợp bên phải.
:) Thưởng thức:
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(); };
Bạn đã thử sử dụng regex chưa? Ồ không, bạn đã có hàng tá vấn đề: O –
@Ivo: Trên thực tế, triển khai đầu tiên của tôi dựa trên regex, nhưng nó trở nên phức tạp đến mức tôi chuyển sang vòng lặp dựa trên ký tự đơn giản. –
Bạn thực sự muốn triển khai một cái gì đó như thế này http://xenon.stanford.edu/~xusch/regexp/analyzer.html chính xác? –