Python Lex Yacc手册
Python Lex Yacc手册
如果你从事编译器或解析器的开发工作，你可能对lex和yacc不会陌生，PLY是David Beazley实现的基于Python的lex和yacc。作者最著名的成就可能是其撰写的Python Cookbook, 3rd Edition。我因为偶然的原因接触了PLY，觉得是个好东西，但是似乎国内没有相关的资料。于是萌生了翻译的想法，虽然内容不算多，但是由于能力有限，很多概念不了解，还专门补习了编译原理，这对我有很大帮助。为了完成翻译，经过初译，复审，排版等，花费我很多时间，最终还是坚持下来了，希望对需要的人有所帮助。另外，第一次大规模翻译英文，由于水平有限，如果错误或者不妥的地方还请指正，非常感谢。目录
1 前言和预备
2 介绍
3 PLY概要
4 Lex
4.1 Lex的例子
4.2 标记列表
4.3 标记的规则
4.4 标记的值
4.5 丢弃标记
4.6 行号和位置信息
4.7 忽略字符
4.8 字面字符
4.9 错误处理
4.10 构建和使用lexer
4.11 @TOKEN装饰器
4.12 优化模式
4.13 调试
4.14 其他方式定义词法规则
4.15 额外状态维护
4.16 Lexer克隆
4.17 Lexer的内部状态
4.18 基于条件的扫描和启动条件
4.19 其他问题
5 语法分析基础
6 Yacc
6.1 一个例子
6.2 将语法规则合并
6.3 字面字符
6.4 空产生式
6.5 改变起始符号
6.6 处理二义文法
6.7 parser.out调试文件
6.8 处理语法错误
6.8.1 根据error规则恢复和再同步
6.8.2 悲观恢复模式
6.8.3 从产生式中抛出错误
6.8.4 错误恢复总结
6.9 行号和位置的跟踪
6.10 构造抽象语法树
6.11 嵌入式动作
6.12 Yacc的其他
7 多个语法和词法分析器
8 使用Python的优化模式
9 高级调试
9.1 调试lex()和yacc()命令
9.2 运行时调试
10 如何继续
1 前言和预备
本文指导你使用PLY进行词法分析和语法解析的，鉴于解析本身是个复杂性的事情，在你使用PLY投入大规模的开发前，我强烈建议你完整地阅读或者浏览本文档。
PLY-3.0能同时兼容Python2和Python3。需要注意的是，对于Python3的支持是新加入的，还没有广泛的测试（尽管所有的例子和单元测试都能够在Pythone3下通过）。如果你使用的是Python2，应该使用Python2.4以上版本，虽然，PLY最低能够支持到Python2.2，不过一些可选的功能需要新版本模块的支持。
2 介绍
PLY是纯粹由Python实现的Lex和yacc（流行的编译器构建工具）。PLY的设计目标是尽可能的沿袭传统lex和yacc工具的工作方式，包括支持LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此，如果你曾经在其他编程语言下使用过yacc，你应该能够很容易的迁移到PLY上。
2001年，我在芝加哥大学教授“编译器简介”课程时开发了的早期的PLY。学生们使用Python和PLY构建了一个类似Pascal的语言的完整编译器，其中的语言特性包括：词法分析、语法分析、类型检查、类型推断、嵌套作用域，并针对SPARC处理器生成目标代码等。最终他们大约实现了30种不同的编译器！PLY在接口设计上影响使用的问题也被学生们所提出。从2001年以来，PLY继续从用户的反馈中不断改进。为了适应对未来的改进需求，PLY3.0在原来基础上进行了重大的重构。
由于PLY是作为教学工具来开发的，你会发现它对于标记和语法规则是相当严谨的，这一定程度上是为了帮助新手用户找出常见的编程错误。不过，高级用户也会发现这有助于处理真实编程语言的复杂语法。还需要注意的是，PLY没有提供太多花哨的东西（例如，自动构建抽象语法树和遍历树），我也不认为它是个分析框架。相反，你会发现它是一个用Python实现的，基本的，但能够完全胜任的lex/yacc。
本文的假设你多少熟悉分析理论、语法制导的翻译、基于其他编程语言使用过类似lex和yacc的编译器构建工具。如果你对这些东西不熟悉，你可能需要先去一些书籍中学习一些基础，比如：Aho, Sethi和Ullman的《Compilers: Principles, Techniques, and Tools》（《编译原理》），和O'Reilly'出版的John Levine的《lex and yacc》。事实上，《lex and yacc》和PLY使用的概念几乎相同。
3 PLY概要
PLY包含两个独立的模块：lex.py和yacc.py，都定义在ply包下。lex.py模块用来将输入字符通过一系列的正则表达式分解成标记序列，yacc.py通过一些上下文无关的文法来识别编程语言语法。yacc.py使用LR解析法，并使用LALR(1)算法（默认）或者SLR算法生成分析表。
这两个工具是为了一起工作的。lex.py通过向外部提供token()方法作为接口，方法每次会从输入中返回下一个有效的标记。yacc.py将会不断的调用这个方法来获取标记并匹配语法规则。yacc.py的的功能通常是生成抽象语法树(AST)，不过，这完全取决于用户，如果需要，yacc.py可以直接用来完成简单的翻译。
就像相应的unix工具，yacc.py提供了大多数你期望的特性，其中包括：丰富的错误检查、语法验证、支持空产生式、错误的标记、通过优先级规则解决二义性。事实上，传统yacc能够做到的PLY都应该支持。
yacc.py与Unix下的yacc的主要不同之处在于，yacc.py没有包含一个独立的代码生成器，而是在PLY中依赖反射来构建词法分析器和语法解析器。不像传统的lex/yacc工具需要一个独立的输入文件，并将之转化成一个源文件，Python程序必须是一个可直接可用的程序，这意味着不能有额外的源文件和特殊的创建步骤（像是那种执行yacc命令来生成Python代码）。又由于生成分析表开销较大，PLY会缓存生成的分析表，并将它们保存在独立的文件中，除非源文件有变化，会重新生成分析表，否则将从缓存中直接读取。
4 Lex
lex.py是用来将输入字符串标记化。例如，假设你正在设计一个编程语言，用户的输入字符串如下：
x = 3 + 42 * (s - t)
标记器将字符串分割成独立的标记：
'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'
标记通常用一组名字来命名和表示：
'ID','EQUALS','NUMBER','PLUS','NUMBER','TIMES','LPAREN','ID','MINUS','ID','RPAREN'
将标记名和标记值本身组合起来：
('ID','x'), ('EQUALS','='), ('NUMBER','3'),('PLUS','+'), ('NUMBER','42), ('TIMES','*'),('LPAREN','('), ('ID','s'),('MINUS','-'),('ID','t'), ('RPAREN',')
正则表达式是描述标记规则的典型方法，下一节展示如何用lex.py实现。
4.1 Lex的例子
下面的例子展示了如何使用lex.py对输入进行标记
# ------------------------------------------------------------
# calclex.py
#
# tokenizer for a simple expression evaluator for
# numbers and +,-,*,/
# ------------------------------------------------------------
import ply.lex as lex
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer
lexer = lex.lex()
为了使lexer工作，你需要给定一个输入，并传递给input()方法。然后，重复调用token()方法来获取标记序列，下面的代码展示了这种用法：
# Test it out
data = '''
3 + 4 * 10
+ -20 *2
'''
# Give the lexer some input
lexer.input(data)
# Tokenize
while True:
tok = lexer.token()
if not tok: break # No more input
print tok
程序执行，将给出如下输出：
$ python example.py
LexToken(NUMBER,3,2,1)
LexToken(PLUS,'+',2,3)
LexToken(NUMBER,4,2,5)
LexToken(TIMES,'*',2,7)
LexToken(NUMBER,10,2,10)
LexToken(PLUS,'+',3,14)
LexToken(MINUS,'-',3,16)
LexToken(NUMBER,20,3,18)
LexToken(TIMES,'*',3,20)
LexToken(NUMBER,2,3,21)
Lexers也同时支持迭代，你可以把上面的循环写成这样：
for tok in lexer:
print tok
由lexer.token()方法返回的标记是LexToken类型的实例，拥有tok.type,tok.value,tok.lineno和tok.lexpos属性，下面的代码展示了如何访问这些属性：
# Tokenize
while True:
tok = lexer.token()
if not tok: break # No more input
print tok.type, tok.value, tok.line, tok.lexpos
tok.type和tok.value属性表示标记本身的类型和值。tok.line和tok.lexpos属性包含了标记的位置信息，tok.lexpos表示标记相对于输入串起始位置的偏移。
4.2 标记列表
词法分析器必须提供一个标记的列表，这个列表将所有可能的标记告诉分析器，用来执行各种验证，同时也提供给yacc.py作为终结符。
在上面的例子中，是这样给定标记列表的：
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
4.3 标记的规则
每种标记用一个正则表达式规则来表示，每个规则需要以"t_"开头声明，表示该声明是对标记的规则定义。对于简单的标记，可以定义成这样（在Python中使用raw string能比较方便的书写正则表达式）：
t_PLUS = r'\+'
这里，紧跟在t_后面的单词，必须跟标记列表中的某个标记名称对应。如果需要执行动作的话，规则可以写成一个方法。例如，下面的规则匹配数字字串，并且将匹配的字符串转化成Python的整型：
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
如果使用方法的话，正则表达式写成方法的文档字符串。方法总是需要接受一个LexToken实例的参数，该实例有一个t.type的属性（字符串表示）来表示标记的类型名称，t.value是标记值（匹配的实际的字符串），t.lineno表示当前在源输入串中的作业行，t.lexpos表示标记相对于输入串起始位置的偏移。默认情况下，t.type是以t_开头的变量或方法的后面部分。方法可以在方法体里面修改这些属性。但是，如果这样做，应该返回结果token，否则，标记将被丢弃。
在lex内部，lex.py用re模块处理模式匹配，在构造最终的完整的正则式的时候，用户提供的规则按照下面的顺序加入：
所有由方法定义的标记规则，按照他们的出现顺序依次加入
由字符串变量定义的标记规则按照其正则式长度倒序后，依次加入（长的先入）
顺序的约定对于精确匹配是必要的。比如，如果你想区分‘=’和‘==’，你需要确保‘==’优先检查。如果用字符串来定义这样的表达式的话，通过将较长的正则式先加入，可以帮助解决这个问题。用方法定义标记，可以显示地控制哪个规则优先检查。
为了处理保留字，你应该写一个单一的规则来匹配这些标识，并在方法里面作特殊的查询：
reserved = {
'if' : 'IF',
'then' : 'THEN',
'else' : 'ELSE',
'while' : 'WHILE',
...
}
tokens = ['LPAREN','RPAREN',...,'ID'] + list(reserved.values())
def t_ID(t):
r'[a-zA-Z_][a-zA-Z_0-9]*'
t.type = reserved.get(t.value,'ID') # Check for reserved words
return t
这样做可以大大减少正则式的个数，并稍稍加快处理速度。注意：你应该避免为保留字编写单独的规则，例如，如果你像下面这样写：
t_FOR = r'for'
t_PRINT = r'print'
但是，这些规则照样也能够匹配以这些字符开头的单词，比如'forget'或者'printed'，这通常不是你想要的。
4.4 标记的值
标记被lex返回后，它们的值被保存在value属性中。正常情况下，value是匹配的实际文本。事实上，value可以被赋为任何Python支持的类型。例如，当扫描到标识符的时候，你可能不仅需要返回标识符的名字，还需要返回其在符号表中的位置，可以像下面这样写：
def t_ID(t):
...
# Look up symbol table information and return a tuple
t.value = (t.value, symbol_lookup(t.value))
...
return t
需要注意的是，不推荐用其他属性来保存值，因为yacc.py模块只会暴露出标记的value属性，访问其他属性会变得不自然。如果想保存多种属性，可以将元组、字典、或者对象实例赋给value。
4.5 丢弃标记
想丢弃像注释之类的标记，只要不返回value就行了，像这样：
def t_COMMENT(t):
r'\#.*'
pass
# No return value. Token discarded
为标记声明添加"ignore_"前缀同样可以达到目的：
t_ignore_COMMENT = r'\#.*'
如果有多种文本需要丢弃，建议使用方法来定义规则，因为方法能够提供更精确的匹配优先级控制（方法根据出现的顺序，而字符串的正则表达式依据正则表达式的长度）
4.6 行号和位置信息
默认情况下，lex.py对行号一无所知。因为lex.py根本不知道何为"行"的概念（换行符本身也作为文本的一部分）。不过，可以通过写一个特殊的规则来记录行号：
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
在这个规则中，当前lexer对象t.lexer的lineno属性被修改了，而且空行被简单的丢弃了，因为没有任何的返回。
lex.py也不自动做列跟踪。但是，位置信息被记录在了每个标记对象的lexpos属性中，这样，就有可能来计算列信息了。例如：每当遇到新行的时候就重置列值：
# Compute column.
# input is the input text string
# token is a token instance
def find_column(input,token):
last_cr = input.rfind('\n',0,token.lexpos)
if last_cr < 0:
last_cr = 0
column = (token.lexpos - last_cr) + 1
return column
通常，计算列的信息是为了指示上下文的错误位置，所以只在必要时有用。
4.7 忽略字符
t_ignore规则比较特殊，是lex.py所保留用来忽略字符的，通常用来跳过空白或者不需要的字符。虽然可以通过定义像t_newline()这样的规则来完成相同的事情，不过使用t_ignore能够提供较好的词法分析性能，因为相比普通的正则式，它被特殊化处理了。
4.8 字面字符
字面字符可以通过在词法模块中定义一个literals变量做到，例如：
literals = [ '+','-','*','/' ]
或者
literals = "+-*/"
字面字符是指单个字符，表示把字符本身作为标记，标记的type和value都是字符本身。不过，字面字符是在其他正则式之后被检查的，因此如果有规则是以这些字符开头的，那么这些规则的优先级较高。
4.9 错误处理
最后，在词法分析中遇到非法字符时，t_error()用来处理这类错误。这种情况下，t.value包含了余下还未被处理的输入字串，在之前的例子中，错误处理方法是这样的：
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
这个例子中，我们只是简单的输出不合法的字符，并且通过调用t.lexer.skip(1)跳过一个字符。
4.10 构建和使用lexer
函数lex.lex()使用Python的反射机制读取调用上下文中的正则表达式，来创建lexer。lexer一旦创建好，有两个方法可以用来控制lexer对象：
lexer.input(data) 重置lexer和输入字串
lexer.token() 返回下一个LexToken类型的标记实例，如果进行到输入字串的尾部时将返回None
推荐直接在lex()函数返回的lexer对象上调用上述接口，尽管也可以向下面这样用模块级别的lex.input()和lex.token()：
lex.lex()
lex.input(sometext)
while 1:
tok = lex.token()
if not tok: break
print tok
在这个例子中，lex.input()和lex.token()是模块级别的方法，在lex模块中，input()和token()方法绑定到最新创建的lexer对象的对应方法上。最好不要这样用，因为这种接口可能不知道在什么时候就失效（译者注：垃圾回收？）
4.11 @TOKEN装饰器
在一些应用中，你可能需要定义一系列辅助的记号来构建复杂的正则表达式，例如：
digit = r'([0-9])'
nondigit = r'([_A-Za-z])'
identifier = r'(' + nondigit + r'(' + digit + r'|' + nondigit + r')*)'
def t_ID(t):
# want docstring to be identifier above. ?????
...
在这个例子中，我们希望ID的规则引用上面的已有的变量。然而，使用文档字符串无法做到，为了解决这个问题，你可以使用@TOKEN装饰器：
from ply.lex import TOKEN
@TOKEN(identifier)
def t_ID(t):
...
装饰器可以将identifier关联到t_ID()的文档字符串上以使lex.py正常工作，一种等价的做法是直接给文档字符串赋值：
def t_ID(t):
...
t_ID.__doc__ = identifier
注意：@TOKEN装饰器需要Python-2.4以上的版本。如果你在意老版本Python的兼容性问题，使用上面的等价办法。
4.12 优化模式
为了提高性能，你可能希望使用Python的优化模式（比如，使用-o选项执行Python）。然而，这样的话，Python会忽略文档字串，这是lex.py的特殊问题，可以通过在创建lexer的时候使用optimize选项：
lexer = lex.lex(optimize=1)
接着，用Python常规的模式运行，这样，lex.py会在当前目录下创建一个lextab.py文件，这个文件会包含所有的正则表达式规则和词法分析阶段的分析表。然后，lextab.py可以被导入用来构建lexer。这种方法大大改善了词法分析程序的启动时间，而且可以在Python的优化模式下工作。
想要更改生成的文件名，使用如下参数：
lexer = lex.lex(optimize=1,lextab="footab")
在优化模式下执行，需要注意的是lex会被禁用大多数的错误检查。因此，建议只在确保万事俱备准备发布最终代码时使用。
4.13 调试
如果想要调试，可以使lex()运行在调试模式：
lexer = lex.lex(debug=1)
这将打出一些调试信息，包括添加的规则、最终的正则表达式和词法分析过程中得到的标记。
除此之外，lex.py有一个简单的主函数，不但支持对命令行参数输入的字串进行扫描，还支持命令行参数指定的文件名：
if __name__ == '__main__':
lex.runmain()
想要了解高级调试的详情，请移步至最后的高级调试部分。
4.14 其他方式定义词法规则
上面的例子，词法分析器都是在单个的Python模块中指定的。如果你想将标记的规则放到不同的模块，使用module关键字参数。例如，你可能有一个专有的模块，包含了标记的规则：
# module: tokrules.py
# This module just contains the lexing rules
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
现在，如果你想要从不同的模块中构建分析器，应该这样（在交互模式下）：
>>> import tokrules
>>> lexer = lex.lex(module=tokrules)
>>> lexer.input("3 + 4")
>>> lexer.token()
LexToken(NUMBER,3,1,1,0)
>>> lexer.token()
LexToken(PLUS,'+',1,2)
>>> lexer.token()
LexToken(NUMBER,4,1,4)
>>> lexer.token()
None
module选项也可以指定类型的实例，例如：
import ply.lex as lex
class MyLexer:
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
# Note addition of self parameter since we're in a class
def t_NUMBER(self,t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(self,t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(self,t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer
def build(self,**kwargs):
self.lexer = lex.lex(module=self, **kwargs)
# Test it output
def test(self,data):
self.lexer.input(data)
while True:
tok = lexer.token()
if not tok: break
print tok
# Build the lexer and try it out
m = MyLexer()
m.build() # Build the lexer
m.test("3 + 4") # Test it
当从类中定义lexer，你需要创建类的实例，而不是类本身。这是因为，lexer的方法只有被绑定（bound-methods）对象后才能使PLY正常工作。
当给lex()方法使用module选项时，PLY使用dir()方法，从对象中获取符号信息，因为不能直接访问对象的__dict__属性。（译者注：可能是因为兼容性原因，__dict__这个方法可能不存在）
最后，如果你希望保持较好的封装性，但不希望什么东西都写在类里面，lexers可以在闭包中定义，例如：
import ply.lex as lex
# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)
def MyLexer():
# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'
# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
t.value = int(t.value)
return t
# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)
# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'
# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)
# Build the lexer from my environment and return it
return lex.lex()
4.15 额外状态维护
在你的词法分析器中，你可能想要维护一些状态。这可能包括模式设置，符号表和其他细节。例如，假设你想要跟踪NUMBER标记的出现个数。
一种方法是维护一个全局变量：
num_count = 0
def t_NUMBER(t):
r'\d+'
global num_count
num_count += 1
t.value = int(t.value)
return t
如果你不喜欢全局变量，另一个记录信息的地方是lexer对象内部。可以通过当前标记的lexer属性访问：
def t_NUMBER(t):
r'\d+'
t.lexer.num_count += 1 # Note use of lexer attribute
t.value = int(t.value)
return t
lexer = lex.lex()
lexer.num_count = 0 # Set the initial count
上面这样做的优点是当同时存在多个lexer实例的情况下，简单易行。不过这看上去似乎是严重违反了面向对象的封装原则。lexer的内部属性（除了lineno）都是以lex开头命名的（lexdata、lexpos）。因此，只要不以lex开头来命名属性就很安全的。
如果你不喜欢给lexer对象赋值，你可以自定义你的lexer类型，就像前面看到的那样：
class MyLexer:
...
def t_NUMBER(self,t):
r'\d+'
self.num_count += 1
t.value = int(t.value)
return t
def build(self, **kwargs):
self.lexer = lex.lex(object=self,**kwargs)
def __init__(self):
self.num_count = 0
如果你的应用会创建很多lexer的实例，并且需要维护很多状态，上面的类可能是最容易管理的。
状态也可以用闭包来管理，比如，在Python3中：
def MyLexer():
num_count = 0
...
def t_NUMBER(t):
r'\d+'
nonlocal num_count
num_count += 1
t.value = int(t.value)
return t
...
评论关闭