时间戳

首页 > 解决方案 > 将 dfa 转换为星号案例的规则

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

问题描述

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

Statements ::= (Statement ';')*

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

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

是 DFA的State0开始状态，代表无终端符号Statements，也是结束状态。从State0输入Statement和翻译到State1和输入';' 在State1，翻译为State0。此外，State0可以使用ε.

并按照龙书中的算法将上述dfa转换为常规语法后，我得到以下语法规则：

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

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

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

所以问题是是否有任何算法可以得到不包含新的非终端符号的上述结果Extend_NT？

或者这只是一个工程问题？

标签： regexparsinggrammardfaparser-generator

解决方案

我不确定我是否理解你的问题。

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

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

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

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

我不知道你是否称其为算法。我个人认为它是工程，但差异不是绝对的。

推荐阅读