0

我正在尝试制作一个上下文无关的语法来表示简单的正则表达式。我想要的符号是[0-9][az][AZ]，运算符是“|”、“()”和“.” 对于连接，对于序列，我现在只想要“*”，稍后我将添加“+”，“？”等。我在 javacc 中尝试了这个语法：

void RE(): {}
{
    FINAL(0) ( "." FINAL(0) | "|" FINAL(0))*
}

void FINAL(int sign): { Token t; }
{
    t = <SYMBOL> {
        if ( sign == 1 )
            jjtThis.val = t.image + "*";
        else
            jjtThis.val = t.image;
    }
    | FINAL(1) "*"
    | "(" RE() ")"
}

问题是在 FINAL 函数| FINAL(1) "*"中给我一个错误的行Left recursion detected: "FINAL... --> FINAL...。将“*”放在 FINAL(1) 的左侧可以解决问题，但这不是我想要的..

我已经尝试从维基百科阅读文章以删除左递归，但我真的不知道该怎么做，有人可以帮忙吗？：秒

4

1 回答 1

1

以下处理左递归

RE --> FACTOR ("." FINAL | "|" FINAL)*
FINAL --> PRIMARY ( "*" )*
PRIMARY --> <SYMBOL> | "(" RE ")"

但是，这不会给 . 优先于 | . 为此，您可以执行以下操作

RE --> TERM ("|" TERM)*
TERM --> FINAL ("." FINAL)*
FINAL --> PRIMARY ( "*" )*
PRIMARY --> <SYMBOL> | "(" RE ")"

一般规则是

A --> A b | c | d | ...

可以转化为

A --> B b*
B --> c | d | ...

其中 B 是一个新的非终结符。

于 2013-05-17T01:29:44.873 回答