我正在尝试弄清楚如何根据给定的正则表达式构造 CFG(上下文无关语法)。 例如，a(ab)*(a|b) 我认为有一个算法可以通过，但它确实令人困惑。 这是我到目前为止得到的:
S->aAB;
A->aAb|empty;
B->a|b;
这看起来对吗？ 任何帮助将不胜感激。
最佳答案
分三部分构建 CFG，分别针对 a、(ab)* 和 (a|b)。
对于 (a|b)，您有 B -> a | b 对。
(ab)* 表示 ab、abab、ababab 等字符串。所以 A -> abA | empty 是正确的产生式。
因此，完整的语法变成:
S -> aAB
A -> abA | empty
B -> a | b
注意:A -> aAb | empty 将派生字符串，如 ab、aabb、aaabbb 等，这不是 regular language , 并且不可能代表 regular expression .
关于regex - 如何根据给定的正则表达式构造一个CFG，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23448734/