在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。
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'\)'
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+'
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 += unt("\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 = ken()
if not token:
break
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 = ken()
if not token:
break
print token
if __name__=='__main__':
startlex()
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会取出一个逻辑相等的记号,而不是两个等号。
函数 ken() 用来返回从输入流中取得的下一个记号对象。
上面的代码执行结果如下:
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 )
| 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):
while语句怎么用在python中 'expression : expression MINUS term'
p[0] = p[1] - p[3]
def p_expression_term(p):
'expression : term'
p[0] = p[1]
# 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):
while语句怎么用在python中 '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")
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
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'''
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'
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 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)
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@huawei
Email:leiyuhou@huawei
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论