regex – 如何基于给定的正则表达式构造CFG

发布时间：2020-12-14 05:58:37 所属栏目：百科来源：网络整理

导读：我试图弄清楚如何基于给定的正则表达式构造CFG(无上下文语法). 例如,a(ab)*(a | b) 我认为有一个算法可以通过,但它确实令人困惑. 这是我到目前为止所得到的： S-aAB; A-aAb|empty; B-a|b; 这看起来不错吗？任何帮助,将不胜感激. 解决方法将CFG分为三个部分

我试图弄清楚如何基于给定的正则表达式构造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 |空的将是正确的生产.

因此,完整的语法变为：

S -> aAB
A -> abA | empty
B -> a | b

注意：A – > aAb | empty会导出像ab,aabb,aaabbb等字符串,这不是regular language,也不可能代表regular expression.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!