logo标签列表

用运算符优先解析器解析正则表达式？

regexparsing
3
能否让给我点踩的人告诉我一下，在他眼中我做错了什么？ - von spotz
1
这是一个范畴错误。你不能用正则表达式来解析；你只能识别一个字符串是否匹配。Thompson的构造将正则表达式转换为NFA；模拟NFA的执行将让你决定一个字符串是否属于由正则表达式定义的语言。而“解析”是根据某个具体的语法，通常是上下文无关文法，将句子分成部分。正则表达式在那个意义上不是一种语法。（顺便说一句，这不是我的踩票。） - rici
1
不，这不是范畴错误。我非常清楚使用作为工具表示正则语言的正则表达式（“解析 with”）实现为NFA/子集构造DFA和从给定正则表达式构造 NFA/DFA 的正则表达式引擎之间的区别，然后轮流接受输入作为该语言的成员-或者不接受。我真的开始厌烦别有用心的误解和一直听到“RTFM”这个“RTFM”那个。从太胆小而无法识别的人那里毫无理由地被投票降低。 - von spotz
也许我的问题很愚蠢，我不知道。如果你说“von Spotz，你的问题很愚蠢”，那么我会接受这个评价。我只是看不出汤普森算法中除了如何将（union | expression）表示为NFA的规则之外还有什么。它怎么可能成为一个预测分析算法呢？它怎么能从一个开括号中知道只有Kleene星表达式才能跟随呢？我所知道的是，要想到达闭合括号并查看其后面的定量修饰符需要大量的前瞻。（而且甚至不清楚这些括号是否真的匹配）如果能给我解释一下就太感激了。 - von spotz
1
简单来说，主持人询问的是将[0-9]+转换为((([(0)-(9))]))+的过程，而不是是否可以使用正则表达式进行解析。 - martian17
2个回答
3
我认为正则表达式没有运算符优先级语法，如果是这样的话，你就不能使用运算符优先级解析器。
这是一个正则表达式的语法，我从Perl风格的语法中简化了它：
<RE>    ::=     <union> | <simple-RE>
<union>     ::= <RE> "|" <simple-RE>
<simple-RE>     ::=     <concatenation> | <basic-RE>
<concatenation>     ::= <simple-RE> <basic-RE>
<basic-RE>  ::= <star> | <plus> | <elementary-RE>
<star>  ::= <elementary-RE> "*"
<plus>  ::= <elementary-RE> "+"
<elementary-RE>     ::= <group> | <any> | <char>
<group>     ::=     "(" <RE> ")"
<any>   ::=     "."
<char>  ::=     any non metacharacter | "\" metacharacter

请注意，<concatenation> 右侧有两个相邻的非终结符，这意味着这不是一个运算符优先级语法。
我认为解析正则表达式的首选方法可能是 递归下降解析器。
1
非常感谢Martin Broadhurst！那么维基百科示例使用的是什么算法呢？https://en.wikipedia.org/wiki/Thompson's_construction#Application_of_the_algorithm - von spotz
你无法从示例中得知使用了哪种解析算法，因为它展示了使用的组成部分，但没有指示它们是如何派生出来的。 - user325117
非常感谢您。答案真的非常感谢。 - von spotz
0

正则表达式确实可以使用运算符优先级解析器进行解析。提供的C语言代码基本上采用了普拉特（操作符优先级）解析器方法。该程序打印出一系列状态转换表示的NFA（非确定有限自动机）。输入是带有通常的*？（）+。[] 运算符的正则表达式。普拉特解析器函数parse()首先为正则表达式创建一个表达式树。它将两个连续的字符（或括号分组）视为它们之间存在一个不可见的二元串联运算符。在此之后，函数print_nfa()从右向左遍历表达式树，并即时打印NFA状态转换。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_PREC 10
#define MAX_CHAR 255 // code for chars from 0 to incl. MAX_CHAR

enum Type { CHAR = MAX_CHAR+1, CONCAT, ANY, SET };

typedef unsigned short IType;

struct Node {
    IType type, ch, state;
    struct Node *left, *right;
    char charset[1];
};

static char *regex;
static IType state;
static struct Node *parse(int prec, struct Node *left);

static int next_token(void) { return *regex ? *regex++ : 0; }

struct Node *allocnode(IType type, IType ch, int extra)
{
    struct Node *node = calloc(1, sizeof(struct Node) + extra);
    node->type  = type;
    node->ch    = ch;
    node->state = state++;
    return node;
}

static int getprec(int op) // get the precedence level of op (highest precedence is 0)
{
    switch (op) {
        case '[': case '(': return 0;           // brackets and parenthesis are like literals: highest precedence
        case '*': case '+': case '?': return 1; // postfix operators
        case CONCAT: default: return 2;         // concat
        case '|': return 3;                     // alternate operator is lowest precedence
        case ')': return 4;                     // closing parenthesis is even lower
    }
}

static struct Node *charset(void)
{
    struct Node *node;
    int         i;

    node = allocnode(SET, 0, 1024);

    // scan until end of set
    for (i=0; regex[0] != ']' && regex[0] != '\0'; ++regex, ++i)
        node->charset[i] = regex[0];
    node->charset[i] = '\0';

    if (regex[0] == ']') // eat terminating ]
        ++regex;

    return node;
}

static struct Node *paren(struct Node *left)
{
    struct Node *node = parse(getprec(')'), left);
    if (regex[0] == ')')
        ++regex;

    return node;
}

static struct Node *single(void)
{
    if (regex[-1] == '.')
        return allocnode(ANY, 0, 0);
    else
        return allocnode(CHAR, regex[-1], 0);
}

static struct Node *postfix(int tok, struct Node *left)
{
    struct Node *node = allocnode((IType) tok, 0, 0);
    node->left = left;
    return node;
}

static struct Node *binary(int tok, struct Node *left)
{
    struct Node *node = allocnode((IType) tok, 0, 0);
    node->left = left;
    node->right = parse(getprec(tok) + 1, NULL);
    return node;
}

static struct Node *parse(int prec, struct Node *left)
{
    int tok = next_token();

    // handle prefix
    switch (tok) {
        case '[': left = charset(); break;
        case '(': left = paren(NULL); break;
        case '*': case '+': case '?': break;
        case '|': break;
        case '\0': return left;
        default: left = single(); break;
    }

    // handle infix and postfix operators
    while (*regex && getprec(regex[0]) < prec) {
        tok = next_token();
        switch (tok) {
            case '*': case '+': case '?': left = postfix(tok, left); break;
            case '|': left = binary('|', left); break;

            // concat is like an invisible infix operator (that's why we -- here)
            default: --regex; left = binary(CONCAT, left); break;
        }
    }

    return left;
}

static IType print_nfa(struct Node *root, IType final)
{
    IType temp;

    if (root == NULL)
        return 0;

    switch (root->type) {
        case CONCAT: // build two nfa's that link left-->right
            return print_nfa(root->left, print_nfa(root->right, final));

        case '|':
            // build two nfa's that both link to final: left-->final and right-->final
            // create two epsilon transitions to the two nfa's
            printf("(%d, ε, %d)\n", root->state, print_nfa(root->left, final));
            printf("(%d, ε, %d)\n", root->state, print_nfa(root->right, final));
            return root->state;

            case '*':
            case '+':
            case '?':
                // build an nfa that links to a new state (root): left-->root (or final in case of ?)
                temp = print_nfa(root->left, (IType) (root->type=='?'?final:root->state));
                // create two epsilon transitions one to the nfa above and one to final
                printf("(%d, ε, %d)\n", root->state, temp);
                printf("(%d, ε, %d)\n", root->state, final);
                if (root->type == '+')
                    return temp; // return the start state of the nfa as the start state into this
                else
                    return root->state; // return root as the start state into this

            case CHAR: // create a transition from this state (root) to final
                printf("(%d, %d, %d)\n", root->state, root->ch, final);
                return root->state;

            case ANY:
                printf("(%d, ANY, %d)\n", root->state, final);
                return root->state;

            case SET:
                printf("(%d, [%s], %d)\n", root->state, root->charset, final);
                return root->state;

            default:   break;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    struct Node *root;
    IType       final, start;

    if (argc < 2) {
        printf("usage: %s regex\n", argv[0]);
        return 0;
    }

    regex = argv[1];

    root = parse(MAX_PREC, NULL);
    start = print_nfa(root, final = state++);
    printf("start = %d, final = %d\n", start, final);
    return 0;
}

这种方法结合了两种算法：Vaughan Pratt的自顶向下运算符优先级解析方案，如Nystrom的书《Crafting Interpreters》第17章所述，以及Thompson NFA算法，如启发性文章“Regular Expression Matching Can Be Simple And Fast”（https://swtch.com/~rsc/regexp/regexp1.html）中所介绍的。由于我没有在一个程序中找到这两种方法的组合，所以我决定分享我想出来的东西，即使原始问题已经有5年了。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接