Apr 15

基于0型文法的二进制加法器

Mathematics 1 Comments

最近学习编译原理，正在学习文法，书上提到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写的一个简单实现该转换的程序：