Apr 15

最近学习编译原理,正在学习文法,书上提到0型方法的描述能力相当于图灵机,
于是想验证一下,既然是相当于图灵机,那么应该可以仅通过方法规则来进行运算。。
我就来定义了一个二进制加法器:
P:
A->A0 | A1 | e
A+e->A
e+A->A
A0+A0->A+A0
A0+A1->A+A1
A1+A0->A+A1
A1+A1->A+A+10

如果我们要从111+11+1推导出1011
可以像这样: 111+11+1=>111+1+e+10
                                    =>111+1+10
                                    =>111+e+e+100
                                    =>111+e+100
                                    =>111+100
                                    =>11+101
                                    =>1+111
                                    =>e+e+1011
                                    =>e+1011
                                    =>1011
下面是我用python写的一个简单实现该转换的程序: