简单正则表达式的语法树生成应该使用什么算法？

future0906

最近在学编译原理，想自己写一个简单的正则表达式引擎。

包含的运算符号有+、*、|、(、)、

其语义与普通正则表达式相同。

我现在卡在第一步，就是语法树的生成。

请问，应该如何生成一个表达式？

prc

用状态机，regex --> NFA --> DFA
编译原理的书上应该有算法

future0906

原帖由 prc 于 2008-6-19 18:13 发表
用状态机，regex --> NFA --> DFA
编译原理的书上应该有算法

嗯,应该是这样.

也可以这样regex--> 语法树 --> (NFA) -->DFA
NFA完全可以跳过.

但问题是,我不知道该如何生成语法树.

或者说,不知道如何从regex-->NFA.书上介绍的Tomposon算法,我完全理解.但具体如何做呢?

prc

都理解算法了，那就设计一下存储结构，把伪代码变成c代码就可以了吧

heixia108

可以看一下lex,我也想做一个

future0906

可能是我没讲清楚....

我理解了Tompson算法,但龙书上讲述的Tompson算法只是说如何从语法分析树中得到NFA,却没有说明如何构造该分析树.

所以我的问题就是如何从正则表达式转换到分析树.

我尝试过使用自顶向下的超前预则法进行语法树的生成.

但由于正则表达式的文法具有左递归.而改写文法,使其不再具有左递归的时候,却无法生成语法树.

不知道有什么解决的方法呢?

tyz

可不可以先消除左递归，再使用自顶向下的超前预则法进行语法树的生成

future0906

原帖由 tyz 于 2008-6-20 13:53 发表
可不可以先消除左递归，再使用自顶向下的超前预则法进行语法树的生成

左递归应该可以消除，但文法改写后，语法树的生成比较困难。

prc

好像NFA不能做语法分析吧，DFA可以
NFA可以转化成等价的DFA呀

emacsnw

转成NFA一般认为是比较简单的步骤，直接翻译你要的语法就行。比如假设字符集只有一个字符 a ，简单NFA就是（e是正则表达式，E是非空正则表达式，epsilon是空串）：
e -- epsilon
e -- E
E -- ae
e -- (E)
e -- E+
e -- E*
e -- E|E
把这个NFA转成DFA以后直接coding就行了。