Парсер для регулярных выражений в PHP?

Я создатель Debuggex , чьи требования очень похожи на ваши: оптимизируйте объем информации, которая может быть показана.

Ниже представлен сильно измененный (для удобочитаемости) фрагмент из анализатора, который использует Debuggex. Он не работает как есть, а предназначен для демонстрации организации кода. Большая часть обработки ошибок была удалена. Так было много логики, которые были простыми, но многословными.

Обратите внимание, что используется рекурсивный спуск . Это то, что вы сделали в своем синтаксическом анализаторе, за исключением того, что вы сглажены в одну функцию. Я использовал примерно эту грамматику для моего:

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)? '}' 

Вы заметите, что мой код просто касается особенностей javascript-аромата регулярных выражений. Вы можете найти дополнительную информацию о них по этой ссылке . Для PHP это имеет всю необходимую информацию. Я думаю, что вы очень хорошо на своем пути с вашим парсером; все, что остается, – это реализация остальных операторов и правильное использование краевых дел.

🙂 Наслаждаться:

 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(); }; 

Модуль perl модуля YAPE :: Regex :: Explain можно, по-видимому, легко переносить на PHP. Вот пример его вывода

 C:\>perl -e "use YAPE::Regex::Explain;print YAPE::Regex::Explain->new(qr/['-])->explain;" The regular expression: (?-imsx:['-]) matches as follows: NODE EXPLANATION ---------------------------------------------------------------------- (?-imsx: group, but do not capture (case-sensitive) (with ^ and $ matching normally) (with . not matching \n) (matching whitespace and # normally): ---------------------------------------------------------------------- ['-] any character of: ''', '-' ---------------------------------------------------------------------- ) end of grouping ---------------------------------------------------------------------- C:\>perl -e "use YAPE::Regex::Explain; print YAPE::Regex::Explain->new(qr/(\w+), ?(.)/)->explain;" The regular expression: (?-imsx:(\w+), ?(.)) matches as follows: NODE EXPLANATION ---------------------------------------------------------------------- (?-imsx: group, but do not capture (case-sensitive) (with ^ and $ matching normally) (with . not matching \n) (matching whitespace and # normally): ---------------------------------------------------------------------- ( group and capture to \1: ---------------------------------------------------------------------- \w+ word characters (az, AZ, 0-9, _) (1 or more times (matching the most amount possible)) ---------------------------------------------------------------------- ) end of \1 ---------------------------------------------------------------------- , ',' ---------------------------------------------------------------------- ? ' ' (optional (matching the most amount possible)) ---------------------------------------------------------------------- ( group and capture to \2: ---------------------------------------------------------------------- . any character except \n ---------------------------------------------------------------------- ) end of \2 ---------------------------------------------------------------------- ) end of grouping ---------------------------------------------------------------------- C:\> 

Вы можете посмотреть исходный код и быстро увидеть реализацию.

Вам нужна грамматика и способ генерации парсера для нее. Самый простой способ создания парсера состоит в том, чтобы закодировать рекурсивный спуск непосредственно на вашем целевом языке (например, на PHP), в котором вы создаете чистый парсер, который сформирован точно так же, как и ваша грамматика (что также позволяет поддерживать парсер).

Много подробностей о том, как сделать это, когда у вас есть грамматика, приведены в моем описании SO, как построить рекурсивные партизаны спуска и дополнительные детали теории здесь

Что касается грамматик регулярных выражений, простая грамматика (возможно, не та, о которой вы имели в виду):

 REGEX = ALTERNATIVES ; ALTERNATIVES = TERM ( '|' TERM )* ; TERM = '(' ALTERNATIVES ')' | CHARACTER | SET | TERM ( '*' | '+' | '?' ) ; SET = '~' ? '[' ( CHARACTER | CHARACTER '-' CHARACTER )* ']' ; CHARACTER = 'A' | 'B' | ... | '0' ... '9' | ... ; 

Рекурсивный анализатор спуска, написанный на PHP для обработки этой грамматики, должен быть порядка нескольких сотен строк, макс.

Учитывая это как исходное место, вы должны иметь возможность добавлять к нему функции PHP Regexes.

Счастливый разбор!

Вас может заинтересовать проект, который я сделал прошлым летом. Это Javascript-программа, которая обеспечивает динамическое синтаксическое выделение регулярных выражений, совместимых с PCRE:

См .: Динамическое (?: Выделение регулярных выражений) ++ с помощью Javascript!
и связанную страницу тестера
и страница проекта GitHub

В коде используется (Javascript) регулярное выражение, чтобы разделить регулярное выражение (PCRE) на различные его части и применять разметку, чтобы пользователь мог наводить курсор мыши на различные компоненты и видеть соответствующие скобки и номера групп захвата.

(Я написал его с помощью регулярного выражения, потому что я не знал ничего лучшего! 8 ^)

Итак, вы можете взглянуть на реализацию регулярных выражений в php. Поскольку php является проектом с открытым исходным кодом, все источники и документация доступны для общественности.

Я бы попытался перевести библиотеку регулярных выражений ActionScript 1/2 в PHP. Более ранние версии Flash не поддерживали поддержку регулярных выражений, поэтому в AS существует несколько библиотек, написанных в AS. Перевод с одного динамического языка на другой должен быть намного проще, чем пытаться расшифровать C.

Вот одна ссылка, на которую стоит обратить внимание: http://www.jurjans.lv/flash/RegExp.html