动手写语法分析器

前言

本来这篇文章打算考试完之后写的，但是我懒了一下，就等到了答辩结束。

这次我用的Python写的，主要是以前只是用过Python，但是没有它做过项目，这次就用Python来试一下。感觉用Python开发还是蛮舒服的，短小精悍的代码，还有跨平台。

任务要求

Create a phaser analysis program, which uses LL(1) method, Operator precedence analyzing or LR(1) method.
The inputs of the program are a text document including a set of productions of the 2º grammar (context free grammar) and the token table generated by Task 1. The out of the program is YES or NO. i.e., the source code string accords with this 2º grammar or the source code string doesn’t accord with this 2º grammar.

要求是用LL(1)或者LR(1)方法，这次读入的是2型文法（词法分析器是3型文法），也就是上下文无关文法。
源代码符合输入的文法，就输出YES，否则就输出NO，并给出错误的位置。

任务分析

在语法分析中，主要完成以下几个操作：

• First函数：用来求解FIRST集
• Closure函数：用来求解某个项目的闭包
• Go函数：将LR(1)的小圆点向后移动一位
• GetItemSet函数：用来根据一个项目集和一个符号(终结符或非终结符)生成另一个项目集
• MakeTable函数：用来生成ACTION表和GOTO表

其实这几个函数，在课本中都有叙述，你只需要将课本上用文字描述的语言转换成C++、Java或Python就可以了。下面就一个一个的看看这些函数怎么转换。

First函数

LR(1)使用FIRST集作为向前搜索符号集，取代了SLR(1)中的FOLLOW集。
First集的求解方法是在LL(1)中讲到的。
$$FIRST(\alpha)=\lbrace\alpha|\alpha\buildrel*\over\Rightarrow\alpha\beta,\alpha\in V_T,\alpha,\beta\in V^*\rbrace$$
其实简单来说，$FIRST(\alpha)$就是求的$\alpha$可以推导出的句子的第一个终结符，当$\alpha\buildrel*\over\Rightarrow\epsilon$，则规定$\epsilon\in FIRST(\alpha)$。
因此，当$\alpha\buildrel*\over\Rightarrow\epsilon$时，$FIRST(\alpha\beta)=FIRST(\beta)$
因此，FIRST函数相当于一个DFS，但是注意要标记走过的路径，否则可能无限递归到爆栈。

# items是一个list，例如：['E','+', 'T']
# visit是一个空set，用来标记走过的路径
def first(self, items, visit):
	# 求First集
	res = []
	if items[0] in visit:		# item为空
		return (res, False)
	empty = True				# empty标记子节点是否为空
	for item in items:
		if empty == False:
			return (res, False)
		if item not in self.vn:		# 当前字符为终结符时，结束搜索
			res.append(item)
			return (res, False)
		empty = False
		for der in self.grammar[item]:	# 访问子节点
			if len(der) == 0:		# 判空
				empty = True
				continue
			visit.add(item)			# 标记访问
			(ans, flag) = self.first(der, visit)	# 访问子节点
			res += ans
			temp = set(res)
			res = list(temp)
			visit.remove(item)
			if flag == True:
				empty = True
	return (res, empty)	# 返回first集，并返回是否为空

Closure函数

闭包定义：

1. 假定$I$是一个项目集，$I$的任何项目都属于$Closure(I)$
2. 若有项目$A\Rightarrow\alpha∙B\beta, \alpha$，属于$Closure(I)$，$B\Rightarrow\gamma$是文法中的产生式，$\beta\in V^*$，$b\in FIRST(\beta\alpha)$，则$B\Rightarrow∙\gamma, b$
   在这里，我的Closure函数并没有计算一个项目集的闭包，而是计算的单个项目的闭包，对于整个项目集的操作，我放到了GetItemSet这个函数中

# derivation表示一个项目 {'data':('E', 'E', '+', 'T',), 'pointPosition':1, 'flag':firstSet}
# visit为一个空set，用来标记是否已经加入闭包
def closer(self, derivation, visit):
	# 获得从一个项目获得一串新的项目
	res = []
	# 空项目集  已经加入项目集    不需要求闭包
	if len(derivation) == 0 or \
		len(derivation['data']) == 0 or \
		hash(derivation['data']) in visit :
		return res
		id = self.getItemHash(derivation)		# 将自己加入闭包中
	if id not in visit:
		visit.add(id)
		res.append(derivation)
			
	if len(derivation['data']) <= derivation['pointPosition']: 
		return res  # 小圆点在最后的 返回自身
	
	if derivation['data'][derivation['pointPosition']] in self.vn:
		for item in self.grammar[derivation['data'][derivation['pointPosition']]]:
			newItem = [derivation['data'][derivation['pointPosition']]] + list(item)
			firstSet = []
			for flag in derivation['flag']:		# 对每一个向前搜索符组成的子句进行first集求解
				firstSet += self.first(tuple(list(derivation['data'][derivation['pointPosition'] + 1:]) + [flag]), set())[0]
			firstSet = set(firstSet)
			firstSet = list(firstSet)
			item = {
				'data':tuple(newItem),
				'pointPosition':1,
				'flag':firstSet
			}
			id = self.getItemHash(item)
			newRes = []
			if id not in visit:		# 判断是否已经加入了闭包中
				visit.add(id)
				res.append(item)
				newRes = self.closer(item, visit)
			res += newRes
	return res

GO函数

Go操作就是将一个项目集的所有小圆点向后移动一位(如果小圆点不在最后面的话)。
具体定义如下：
$GO(I, X)=CLOSURE(J)$
其中，$I$是LR(1)中的项目集，$X$是文法符号(终结符和非终结符)。
$J=\{任何形如[A\Rightarrow\alpha X∙\beta, \alpha]的项目|[A\Rightarrow\alpha∙X\beta, \alpha\in I\}$
文法的初始项目集为$[S’\Rightarrow∙S, \#]$，然后由初始项目集通过闭包函数和转移函数，生成所有的项目集。

def go(self, item, v):
	# 圆点后移一位
	item = copy.copy(item)		# 由于Python的原因，list和dic作为参数，都是传递的引用，因此要在这里进行copy
	res = []
	if item['pointPosition'] < len(item['data']):		# 小圆点不再最后
		if item['data'][item['pointPosition']] != v:	
			return res									# 不符合转移条件
		item['pointPosition'] += 1
		newItems = self.closer(item, set())
		res += newItems
	return res

GetItemSet函数

GetItemSet就是对一个项目集的所有项目，做一个转移和闭包操作(闭包操作在GO函数中)。

def getItemSet(self, items, v):
	newItems = []
	for item in items:
		newItems += self.go(item, v)
	return newItems

MakeTable函数

通过这个函数来生成Action表和Goto表，程序很长，但是并不复杂

def makeTable(self):
	# 生成项目集 ACTION表 GOTO表
	self.grammar.setdefault('begin-1', [(self.begin,)])
	
	# 给推导式编号
	for vn, exp in self.grammar.items():
		for item in exp :
			temp = [vn]
			temp += list(item)
			self.hashSet.setdefault(hash(tuple(temp)), tuple(temp))		# 通过其哈希值，直接作为其编号
	
	# 构造初始项目集
	initItem = {
		'data':('begin-1', self.begin),
		'pointPosition':1,
		'flag':['$end']
	}	
	initItemSet = {
		'id':self.getItemSetHash(self.closer(initItem, set())),
		'data':self.closer(initItem, set())
	}

	# 获取ACC标志
	self.accflag = hash(initItem['data'])
	
	# 获取语法分析的初始状态
	self.parserBegin = initItemSet['id']
	
	self.c = []		# c用来存放所有的项目集
	self.c.append(initItemSet)
	
	visit = set() 	# 判断项目集是否重复
	visit.add(initItemSet['id'])
	for items in self.c:
		for v in self.v:
			res = self.getItemSet(items['data'], v)
			if len(res) == 0:		# 生成了空项目集
				continue
				
			newItemSet = {
				'id':self.getItemSetHash(res),
				'data':res
			}
			
			# 构造GOTO表
			if v in self.vn:
				self.goto.setdefault(items['id'], {})
				self.goto[items['id']].setdefault(v, newItemSet['id'])
				
			# 构造部分ACTION表  状态转移，用flag=s区分
			if v not in self.vn:
				self.action.setdefault(items['id'], {})
				self.action[items['id']].setdefault(v, {})
				self.action[items['id']][v] = {
					'flag':'s',	
					'data':newItemSet['id']
				}
				
				
			if  newItemSet['id'] not in visit:
				visit.add(newItemSet['id'])
				self.c.append(newItemSet)
	
	# 构造ACTION表  归约，用flag=r区分
	for itemSet in self.c:
		for item in itemSet['data']:
			if item['pointPosition'] >= len(item['data']):
				id = hash(item['data'])
				self.action.setdefault(itemSet['id'], {})
				for v in item['flag']:
					self.action[itemSet['id']].setdefault(v, {})
					self.action[itemSet['id']][v] = {
						'flag':'r',
						'data':id
					}

语法分析过程

分析过程跟课本上说的一样，构造状态栈、符号栈，通过Action表和GOTO表进行状态转移和归约。

def parser(self):
	# 进行语法分析
	self.makeTable()
	# 初始化
	signal = []		# 符号栈
	stateStack = []	# 状态栈
	stateStack.append(self.parserBegin)
	
	self.tokens.append([0, 0, '$end', 'EOF'])
	
	while True:
		token = self.tokens[0][2]
		if token == '$end' and signal[-1] == self.begin:	# 结束标志
			break
		if token in self.action[stateStack[-1]].keys():
			thisAction = self.action[stateStack[-1]][token]
			
			# 对可归约状态进行归约
			if thisAction['flag'] == 'r' and thisAction['data'] != self.accflag:
				length = len(self.hashSet[thisAction['data']]) - 1 		# 获取回退步数
				if length != 0:
					stateStack = stateStack[0:-length]
				token = self.hashSet[thisAction['data']][0]
				if token in self.goto[stateStack[-1]].keys():
					thisGoto = self.goto[stateStack[-1]][token]
				stateStack.append(thisGoto)
				if length != 0:
					signal = signal[0:-length]
				signal.append(token)
			else:
				signal.append(token)
				self.tokens.pop(0)
				stateStack.append(thisAction['data'])
			
		else:		# 没有可转移的状态，不符合语法规范
			print "Error:%s:%s %s" %(self.tokens[0][0], self.tokens[0][1], self.tokens[0][3])
			break
	if signal[-1] == self.begin:
		return True
	else:
		return False

后记

整个语法分析最复杂的，感觉是闭包函数和First函数，需要递归操作，经常无限递归，然后程序就死了。其次就是第一次写完程序运行时，发现程序的运行速度太慢了！通过做性能分析，发现是copy.deepcopy函数的原因，果断放弃，换了copy.copy。
还有就是，深入了解了一下Python的参数传递的方式。

整个项目的源码在这里：点击查看

这个项目里不仅仅有语法分析程序，还有词法分析程序，主要是因为要统一语言，所以我把上次的词法分析器又重写了一边。。。