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

#!/usr/bin/python
# a binary adder based on grammar..
# this has nothing to do with compute,
# actually,it's just string operations.
# version: 0.0.1
# usage:
# if you "111+11+1",<7+3+1>in decimal.
# output will be "1011",<11>in decimal.

s=str(raw_input("input a binary expression string:"))

# recursively calculate the binary expression..
def adder(s):
	r=""
	if '+' not in s:	# it's the result format already..
		return s
	else:
		s1=s[:s.index('+')]			# split the expression to two parts.
		s2=adder(s[s.index('+')+1:])# and process the second first..
		s=core(s1,s2)				# calculate the normal format:Ax+By..
		r=adder(s[:-1])+s[-1]+r	# append the last char to the result...
		return r

# core(),define the core principles.
# return the result of Ax+By,where x,y belong to {0,1}
# P: A->A0|A1|e
# e+A->A
# A+e->A
# A0+A0->A+A0
# A0+A1->A+A1
# A1+A0->A+A1
# A1+A1->A+A+10
def core(s1,s2):
	# correspond to: e+A->A && A+e->A
	if len(s1)==0 or len(s2)==0:
		return s1+s2
	else:
		p1=s1[:-1]
		p2=s2[:-1]
		# correspond to: A0+A0->A+A0
		if s1[-1]+s2[-1]=='00':
			if len(p1)==0 or len(p2)==0:
				return p1+p2+'0'
			else:
				return p1+'+'+p2+'0'
		# correspond to: A0+A1->A+A1 && A1+A0->A+A1
		elif s1[-1]+s2[-1]=='01' or s1[-1]+s2[-1]=='10':
			if len(p1)==0 or len(p2)==0:
				return p1+p2+'1'
			else:
				return p1+'+'+p2+'1'
		# correspond to: A1+A1->A+A+10
		else:
			if len(p1)==0 and len(p2)==0:
				return '10'
			elif len(p1)==0 or len(p2)==0:
				return p1+p2+'+'+'10'
			else:
				return p1+'+'+p2+'+'+'10'

print adder(s)

• 相关文章
• 全局相关文章