将 dfa 转换为星号案例的规则

Question

这是一个简单但非常常见的 EBNF 格式语法规则案例，Statements 是一个 none 终端符号，Statement 是 none 终端符号：

Statements ::= (Statement ';')*

将此规则转化为NFA后，再进行NFA转化为DFA的子集构造，最终得到dfa：

State0 -> Statement -> State1 -> ';' ->State0
State0 -> ε -> State0

State0是DFA的起始状态，代表none终端符号Statements，也是结束状态。从 State0 输入 Statement 并翻译成 State1 并输入 ';'在 State1，翻译成 State0。此外，State0 可以通过 ε.

转换为自我

然后按照龙书上的算法将上面的dfa转为正规文法后，得到如下文法规则：

Statements -> ε
Statements -> Statement Extend_NT
Extend_NT  -> ';' Statements

它添加了新的none终结符号Extend_NT，但我想得到以下不包含扩展符号Extend_NT的常规语法：

Statements -> ε
Statements -> Statement ';' Statements

所以问题是有没有什么算法可以得到上面不包含新的none终结符号Extend_NT的结果？

还是只是工程问题？

Answer 1

我不太确定我理解你的问题。

如果您只有一个非终端的产生式，并且该产生式只有一个重复运算符，无论是在开头还是结尾，您都可以应用简单的脱糖：（这里 α 和β 是文法符号序列（但不是 EBNF 符号），α 可能为空。）

N ::= α (β)* ⇒  N → α | N β
N ::= (β)* α ⇒  N → α | β N

如果 α 为空，您可以使用以上任一方法。对于 LALR(1) 解析器生成器，左递归版本是通常的选择；如果您要构建 LL 解析器，您当然需要右递归版本。

如果右侧有多个 EBNF 运算符，那么您将需要额外的非终结符，每个 EBNF 重复运算符一个，但可能有一个除外。

我不知道你是否会称其为算法。我个人认为是工程，但是区别不是绝对的

Convert a dfa to rule for a asterisk case