在Python中使用Ply进行词法语法分析.doc

在Python中使用Ply进行词法语法分析
关键词：Python Lex Yacc Ply 词法分析 语法分析。
摘 要：本文描述了如何在Pyhont中使用Ply进行词法分析和语法分析。
缩略语清单：

1 PLY简介
PLY是Python Lex-Yacc的缩写。是用来在Python语言中中进行Lex、Yacc词法分析和语法分析的工具，它本身也完全采用Python写成。在功能上与流行的Flex和Bison相比存在一些欠缺，但是其非常的简单易用。下面我们就简单的介绍PLY的背景安装和使用。
Python具有良好的可扩展性，我们如果要使用Python语言来进行相关的词法语法分析，可以使用Flex以及Bison工具、以及C语言创建Python模块，然后在Python中使用。这种做法能够极大的发挥Flex以及Bison的强大功能，而且运行效率勿庸置疑。但是不够简单直观。PLY的出现，使得我们可以直接在Python语言中进行词法语法分析，并且非常方便。
首先得安装Python解释器，我这里安装的是ActivePython 2.3.2。然后到下面的网站下载PLY的安装程序，当前版本是1.5。
http://systems.cs.uchicago.edu/ply/
下载之后解压缩，然后运行里面的setup.py，如下：
python setup.py install
那么PLY就安装到你的Python安装目录下，我们可以开始使用PLY了。

2 词法分析
PLY进行词法分析的原理和Flex相似，但是在实现上有很大的不同。下面用一个计算表达式的例子来说明。下面的代码分析数学表达式，里面可以有圆括号，＋－×/和＝等赋值运算，整数，变量名等。
import lex
tokens = (
'NAME','NUMBER',
'PLUS','MINUS','TIMES','DIVIDE','EQUALS',
'LPAREN','RPAREN',
)

#Tokens的正则表达式定义
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_EQUALS = r'='
t_LPAREN = r'\('
t_RPAREN = r'\)'
t_NAME = r'[a-zA-Z_][a-zA-Z0-9_]*'

def t_NUMBER(t):
r'\d+'
try:
t.value = int(t.value)
except ValueError:
print "Integer value too large", t.value
t.value = 0
return t

t_ignore = " \t"

def t_newline(t):
r'\n+'
t.lineno += t.value.count("\n")

def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.skip(1)

# Build the lexer
lex.lex()

def startlex():
s = "100*(3+5/2)"
while True:
token = lex.token()
if not token:
break
print token

if __name__=='__main__':
startlex()

PLY利用了Python的自省机制（introspection）。上面的代码中首先定义了tuple类型变量tokens，其元素是各个记号的名字。然后下面就是各个记号的正则表达式规则定义，有两种方式来定义。一是通过t_tokenname的形式来定义字符串，另一种就是t_tokenname的形式来定义函数。一般情况下，如果记号不作为语法分析的输入（比如注释），或者要求对记号属性做一些变化，那么就采用函数的形式来定义正则表达式；其他情况下采用字符串来定义。采用函数定义的时候，函数的documeng string，就是记号的正则表达式，比如上面例子中的t_NUMBER。
函数具有固定的形式：
def t_TOKENNAME( t )
如果该记号不作为语法分析的输入，那么就不要返回任何值（例如t_newline）。否则，必须返回t（例如t_NUMBER）。其中t是一个LexToken类型的对象。
和Flex类似，PLY也对记号进行排序，按照优先级对字符串进行解析。以函数形式定义的记号，先定义的具有更高的优先级；以字符串形式定义的记号，正则表达式更长的，具有更高的优先级。例如，等号“＝”和逻辑相等“＝＝”。后者的优先级就比较高，当输入流中出现两个连续的等号的时候，PLY会取出一个逻辑相等的记号，而不是两个等号。
函数 lex.token() 用来返回从输入流中取得的下一个记号对象。
上面的代码执行结果如下：
LexToken(NUMBER,100,1)
LexToken(TIMES,'*',1)
LexToken(LPAREN,'(',1)
LexToken(NUMBER,3,1)
LexToken(PLUS,'+',1)
LexToken(NUMBER,5,1)
LexToken(DIVIDE,'/',1)
LexToken(NUMBER,2,1)
LexToken(RPAREN,')',1)
PLY中的Lex部分全部采用Python写成，并且在运行之前需要进行一定的初始化工作，所以效率上肯定比不上Flex和C语言。在200MHz主频的计算机上，一个包含32000个记号的4700行C语言代码，PLY解析完成需要20秒的时间。当然最新版本的Python解释器和更强劲的CPU，会使得效率大大提升。

3 语法分析
PLY的语法分析使用起来非常简单，完全体现了语法制导翻译（syntax directed translation）的思想。这里语法指的是上下文无关文法（context free grammar）。PLY采用的是至底向上的分析方法，默认是SLR，我们也可以通过参数指定为 LALR(1)。还是以分析数学表达式为例，为了避免冲突，数学表达式的产生式如下：
expression : expression + term
| expression - term
| term

term : term * factor
| term / factor
| factor

factor : NUMBER
| ( expression )
针对该产生式，我们采用PLY写出如下语法制导翻译的Python代码：
import yacc

# Get the token map from the lexer. This is required.from calclex import tokens

def p_expression_plus(p):
'expression : expression PLUS term'
p[0] = p[1] + p[3]

def p_expression_minus(p):
'expression : expression MINUS term'
p[0] = p[1] - p[3]

def p_expression_term(p):
'expression : term'
p[0] = p[1]

def p_term_times(p):
'term : term TIMES factor'
p[0] = p[1] * p[3]

def p_term_div(p):
'term : term DIVIDE factor'
p[0] = p[1] / p[3]

def p_term_factor(p):
'term : factor'
p[0] = p[1]

def p_factor_num(p):
'factor : NUMBER'
p[0] = p[1]

def p_factor_expr(p):
'factor : LPAREN expression RPAREN'
p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
print "Syntax error in input!"

# Build the parser
yacc.yacc()

# Use this if you want to build the parser using LALR(1) instead of SLR
# yacc.yacc(method="LALR")

while 1:
try:
s = raw_input('calc > ')
except EOFError:
break
if not s: continue
result = yacc.parse(s)
print result

可以看到，上面代码中定义了不少p_开始的函数，它们只有一个参数p，这是一个函数对应语法规则中包含的语法符号的序列。函数的document string就是函数所对应的语法规则，而函数本身则是对应的翻译执行时所要执行的动作。定义完所有的产生式之后，调用yacc.yacc来初始化内部数据结构，然后调用yacc.parse来解析字符串，解析结果就是最终的运行结果。
Yacc.yacc的参数method可以为‘SLR’或者‘LALR’，分别表示不同的语法分析方式。PLY中的yacc必须要求有Lex的支持，必须定义了相关的token。
每一个产生式函数的参数 p，是一个YaccProduction类型的实例。我们可以使用p[i]的方式来取得产生式的元素。具体请参考上面的代码。
PLY还能够处理产生式中的冲突，能够为某些记号定义优先级。并且还有较强的容错处理机制。比如上面的产生式太复杂，那么可以使用PLY的优先级机制，简化如下：
Import yacc
precedence = (
('left','PLUS','MINUS'),
('left','TIMES','DIVIDE'),
('right','UMINUS'),
)

# dictionary of names
names = { }

def p_statement_assign(p):
'statement : NAME EQUALS expression'
names[p[1]] = p[3]

def p_statement_expr(p):
'statement : expression'
print p[1]

def p_expression_binop(p):
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
if p[2] == '+' : p[0] = p[1] + p[3]
elif p[2] == '-': p[0] = p[1] - p[3]
elif p[2] == '*': p[0] = p[1] * p[3]
elif p[2] == '/': p[0] = p[1] / p[3]

def p_expression_uminus(p):
'expression : MINUS expression %prec UMINUS'
p[0] = -p[2]

def p_expression_group(p):
'expression : LPAREN expression RPAREN'
p[0] = p[2]

def p_expression_number(p):
'expression : NUMBER'
p[0] = p[1]

def p_expression_name(p):
'expression : NAME'
try:
p[0] = names[p[1]]
except LookupError:
print "Undefined name '%s'" % p[1]
p[0] = 0

def p_error(p):
print "Syntax error at '%s'" % p.value

yacc.yacc()

def startcalc():
s = "100+200*2"
yacc.parse(s)

可以看到首先定义了变量precedence，其中指定了相关终结符的优先级以及结合方向（left，right）。按照出现的顺序，优先级递增。然后我们可以看到，产生式简单的变成了：
'''expression : expression PLUS expression
| expression MINUS expression
| expression TIMES expression
| expression DIVIDE expression'''
这样的产生式本来是会产生冲突的，但是因为优先级的定义和存在，结果PLY就能够正确的解决冲突。

4 总结
上面简单的介绍了PLY的大概使用方法，具体的方法请参考PLY的随机文档。总的来说，PLY的功能比不上Flex和Bison强大，效率也没有它们高。但是非常的简单灵活。而且和Python脚本本身结合的相当巧妙。应付一般的词法分析和分析目的绰绰有余。如果追求更加强大的功能，那么请使用FlexBisonModules，或者最原始的Flex、Bison来编写Python扩展模块。

关于作者：本文作者雷雨后，是华为技术有限公司的软件测试专家。他目前从事软件测试自动化和软件测试技术方面的研究。
Email：leiyuhou@