引言
PLY1 全称 Python Lex-Yacc 是纯 python 实现的 lex 和 yacc。lex 和 yacc 是 GNU Linux 上重要的工具，分别用于词法分析（基于正则表达式）和语法分析（基于上下文无关语言的语法推导）。这一工具链也是构成编译器前端的重要基础。PLY 争取最大限度的模拟了 lex 和 yacc 的命令格式甚至报错信息，阅读该源码可以更好的理解编译器前端相关的知识和细节，关于 PLY 的设计理念可以参考其作者的一个报告2。本文所讨论的源代码基于 ply 3.11，这篇内容只关注 lex 部分，也即 ply/lex.py。
Lex 使用的简单介绍
可能应用
lex 的基本功能就是基于预先指定好的正则表达式和 token 的联系，对文本流的所有字符打上标签，从而为下一步的语法分析奠定基础。这一对文本分类标签的功能用途广泛，并不局限于编译器的构造（毕竟大部分人不会有这种需求）。比如，对于 latex 文档去除所有注释这一任务，就可以通过 lex 打标签的功能优雅的完成。可能有人觉得这一问题，随便写两行就解决了，但实际情况非常复杂。比如说 \% 表示百分号转义而不是注释，但 \\% 表示换行加注释。又比如 comment 环境中的内容，加不加 % 都是注释等等。如果暴力用简单逻辑的脚本处理，不仅 corner case 很多，也很不优雅。而利用 ply 的基于状态和匹配打 token，这一任务并不困难。关于 latex 文档去注释这一功能，可以参考我的一个脚本，这也可以作为如何使用 ply 的一个基本教学的例子。
使用 API 简介
lex 模块详细的使用，可以参考其中文文档3。粗略来说，需要以 tuple 的形式给出 token 的定义 tokens=(FOO, BAR...)，之后对于每一种 token 的匹配，都以 t_token 形式的变量名给出字符串（正则表达式）或函数（docstring 为正则表达式字符串）的定义（只有一个变量，为对应的 token 对象）。之后引入 lexer = lex.lex() 词法分析器就自动完成了初始化，通过 lexer.input() 的方式输入待分析字符串，即可通过 lexer.token() 的形式获取字符串中的下一个 token 对象 （这一方法也有等价的 iterator 封装可用）。而每一个 token 对象里都包含了 value （默认为文本中的原值），type （对应的 token）等属性。以上就对应了 lex 使用的一个基本工作流。至于基于条件的扫描和额外状态维护实践中也经常用到，本文限于篇幅不再讨论。
代码原理和逻辑流的梳理
和原 Lex 的主要区别
PLY 的 lex 实现代码，利用了 python 自己的正则表达式处理模块 re，因此不需要手动实现一个正则表达式处理的模块，所以还是比较轻量级的。正则表达式处理的原理，如何将正则表达式转化为非确定有限自动机，再转化为确定有限自动机，并通过状态合并进行优化，最后用该自动机对输入字符串进行扫描，这些都是 re 模块内部的工作，我们不在这篇里探讨这些细节。但知道正则表达式匹配的这个大致框架，就可以看出为何频繁使用的正则表达式最好先 re.compile()，因为这相当于一次建好有限自动机模型，之后只需调用即可，比起每次直接匹配重新生成自动机模型要快很多。
另一方面，PLY 中的 lex 实现，输入是基于字符串，而非文本流，也就是一次性拿到了所有需要被分析的输入。这样也不需要去费心实现一些 lookahead 的功能，因为可以一次性的匹配到底，很容易选出最佳匹配。
实现的基本框架
lex 的代码由两个主要的 class 和一个主函数组成。Lexer 类就是具有 input 和 token 方法的，用来真正给文本打标签的类，整个代码的核心就是 Lexer.token() 方法。LexerReflect 类用来从定义文件获取所有的 token，state 和 rules，并确保它们正确相容有序，存放在适合的字典列表中。该 class 名字的来历在于获取 rules 主要依靠了 Python 的所谓反射机制。主要函数 lex() 的返回值是一个 Lexer 对象，这也是一些功能比较“单一”的 package 的典型设计模式。对外暴露一个函数并返回主要的工作类。lex() 函数中初始化了 Lexer 和 LexerReflect 类，并且把 LexerReflect 获取的词法分析器的定义数据都绑定到 Lexer 上，最后将准备好的 Lexer 类返回。
一个简化版的代码框架如下：
class LexToken:
# class for token
pass
class Lexer:
# main class for parser
def input(self, s):
self.lexdata = s
self.lexlen = len(s)
self.lexpos = 0
def token(self):
token = LexToken()
# main run-time parser
return token
def __iter__(self):
return self
def __next__(self):
# iterator interface
t = self.token()
if t is None:
raise StopIteration
return t
class LexerReflect:
# class to extract all rules and tokens from ldict
def __init__(self, ldict):
pass
def lex():
# main function: get definition of rules into ldict and return a well-ready Lexer
lexobj = Lexer()
# get all info into ldict
linfo = LexerReflect(ldict)
# bind all necessary attrs of linfo into lexobj
# create master regular expression and bind details into lexobj
return lexobj
逻辑流和实现细节
下面我们跟随代码执行的逻辑顺序，看一下实现的一些细节。
- 首先是在
lex()函数中从定义文件里提取按照 API 格式提前写好的 token 和 rule 定义（包括字符串定义和函数定义两种）的方法。我们看一下这一部分的代码梗概：
import sys
def get_caller_module_dict(levels):
f = sys._getframe(levels)
ldict = f.f_globals.copy()
if f.f_globals != f.f_locals:
ldict.update(f.f_locals)
return ldict
def lex(module=None):
if module:
_items = [(k,getattr(module,k)) for k in dir(module)]
ldict = dict(_items)
else:
ldict = get_caller_module_dict(2)
可以看到获取定义好的信息的方式有两种，一种是我们把这些信息写在了单独的文件内，比如 rules.py。那么我们调用 lex(module='rules.py')，指定对应的规则文件，我们将会通过 dir('rules.py') 的方式，拿到一个完整的 list，包含该文件的所有变量（string 的形式），这其中自然包含了 tokens 和一堆 t_token。同时我们利用 getattr 这一反射机制，通过字符串拿到了对应的真实的函数对象或字符串定义，从而形成了 rules 名称和真实对象组成的字典 ldict。更多的时候，我们希望直接在语法定义的同一文件下面，直接引入 lex() 使用，此时并未指定 module 用来获取运行文件本身的所有变量列表，dir 由于自引无法使用，我们采用了 sys._getframe() 的方式获取。这一方式设计需要 Python runtime 和 frame 的理解，在下一部分会详述。而数字 2 则是为了获取到存储有 rules 信息的 global frame，lex和 get_caller_module_dict 的两级压栈，使得向上两层恰好可以调用到定义 rules 信息的 frame。
- 不同 rules 对应正则表达式的排序处理。这一细节在
LexerReflect()类的get_rules()方法中。
class LexerReflect:
def get_rules(self):
# omitted part: get self.funcsym and self.strsym for rules in self.ldict
for f in self.funcsym.values():
f.sort(key=lambda x: x[1].__code__.co_firstlineno) # line no of the functions
for s in self.strsym.values():
s.sort(key=lambda x: len(x[1]), reverse=True)
def lex():
# only list the relevant part of the order
for fname, f in linfo.funcsym[state]:
regex_list.append('(?P<%s>%s)' % (fname, _get_regex(f)))
for name, r in linfo.strsym[state]:
regex_list.append('(?P<%s>%s)' % (name, r))
可以看到，所有正则表达式匹配规则的排序是先函数规则之后简单字符串定义的规则。对于函数规则，先后排序是按照定义的顺序，这体现在 __code__.co_firstlineno 代表了相应函数定义的行数。对于字符串规则，先后排序是按照从长到短，即优先匹配更长的正则表达式。
- 对于大量 rules 及其对应的正则表达式，PLY 选择将其合并编译成一个大的正则表达式，从而提升匹配效率。这一细节体现在以下函数中。
def _form_master_re(relist, reflags, ldict, toknames):
regex = '|'.join(relist)
# the form of elements in relist is : r'(?<t_state1_token2>blah.*)'
try:
lexre = re.compile(regex, reflags)
lexindexfunc = [None] * (max(lexre.groupindex.values()) + 1)
lexindexnames = lexindexfunc[:]
# eg. if we try to merge 3 reg expr, then we have lexindexfunc=[None,None,None]
# some manipulation on lexindexfunc and lexindexnames are omitted
return [(lexre, lexindexfunc)], [regex], [lexindexnames]
except Exception: # avoid too large reg exp for compiling by re module
m = int(len(relist)/2)
if m == 0:
m = 1
llist, lre, lnames = _form_master_re(relist[:m], reflags, ldict, toknames)
rlist, rre, rnames = _form_master_re(relist[m:], reflags, ldict, toknames)
return (llist+rlist), (lre+rre), (lnames+rnames)
以上函数会在 lex() 主函数中调用，返回的 master pattern 和其他信息都会绑定在 Lexer 对象上。由于 re 模块的限制，长度过长的正则表达式可能无法编译，因此该函数使用了 try...except... 的方式（但捕获全部 exception 不是一个好的实践），一旦无法把所有 rules 对应的正则表达式合并编译，就迭代二分，最后返回一个 list 的主正则表达式。注意到将不同正则合并是直接利用 | 算符，而 re 模块匹配时也是按照顺序从前至后依次尝试被 | 分割的不同部分。因此这种合并使得正则表达式的排序得到了保持。
- parser 的一些细节，这一部分集中在
Lexer.token()方法。
class Lexer:
def token(self):
# Make local copies of frequently referenced attributes
lexpos = self.lexpos
lexlen = self.lexlen
lexdata = self.lexdata
while lexpos < lexlen:
if lexdata[lexpos] in lexignore:
lexpos += 1
continue
for lexre, lexindexfunc in self.lexre:
m = lexre.match(lexdata, lexpos) # the main match between master reg and input
if not m:
continue
tok = LexToken
tok.value = m.group()
i = m.lastindex
func, tok.type = lexindexfunc[i]
if not func:
if tok.type: # string rule case
self.lexpos = m.end()
return tok
else: # ignore case
lexpos = m.end()
break # skip else part below
newtok = func(tok) # function rule case
if not newtok: # no return from the rule function
break # skip else part below
return newtok # return the tok
else: # else of for!
# omitted part: deal with literal case and error case, both return some token
raise LexError() # no match and hence an illegal character
if self.lexeoff: # deal with end case since lexpos=lexlen
## omitted: eof function and return token
return None # return None if lexpos>lexlen, this is the signal of stopiteration error of the iterator interface
从以上代码可以大致看出词法解析的大致顺序和逻辑。其解析顺序的推进是基于 self.lexpos 属性，初始 input() 时，Lexer 拿到输入字符串的总长度，token() 方法每次解析出一个新的 token，则相应的前移 lexpos 使得其始终保持在待解析区域的开始位置。这对应了 lexre.match() 的第二个参量，代表开始匹配时字符串的开始位置。其次就是该函数的 for-else 框架，这将在下一部分详细分析。值得一提的另一个细节，是在方法开始，重新将对象的属性赋值给 local 的变量。由于 Python 的动态语言特性，对于对象属性的访问需要依次确认若干个字典和方法，速度较慢，因此这里为了使 parser 性能提高，直接将反复使用的变量重新声明。
当然代码里还有大量处理优化模式，以及其对应的 lexer table 的 IO 操作，和基于条件的匹配的实现等内容。不过理解了代码的主框架，这些细节都是自然的延伸和更多的变量的跟踪罢了，没有什么额外的特别之处。
一些 python 语言相关的细节
ply.lex 一千行左右的代码里，利用了挺多 python 的特性，很多小点都值得仔细思考。像 iterator 的实现，isinstance() 判定和 dict.get() 来取值从而更好的容错，复制时注意 shallow copy 和 deep copy 这些比较常见的点，本文就不再赘述了。我们重点关注一些，该程序中利用的，平时不是很常用的语言特性和细节。
for-else 结构
除了 if-else，for-else 也是 Python 中的合法逻辑控制结构。以下代码说明了其用法：
for i in [1,2,3]:
if i>4:
break
else:
print('go to else')
# output: go to else
for i in [1,2,3]:
if i>2:
break
else:
print('go to else')
# no output
换句话说，这种结构的应用情景，是利用 for 循环寻找某个符合条件的元素。如果没找到这样的元素，（break 不被触发），则代码开始运行 else 代码段。关于这种语法的更多的讨论，参见4。事实上，这就是一个 else 关键字的复用，如果这一关键字被定义为 nobreak 可能意义更清晰些。
python 内置的 bitwise 算符及重载
除了算数算符和逻辑算符，python 也有一整套的 bitwise 的算符。只不过由于 python 这种语言的特性，和上层的东西打交道多一点，因此使用这些算符的情况较少一些。Python 中支持的 bitwise 算符如下表。其中 \(a=1 (0001),b=3(0011)\)。
| Operator | Description | Example | Function |
|---|---|---|---|
| & Binary AND | Operator copies a bit to the result if it exists in both operands | a & b ＝ 1 |
__and__() |
| | Binary OR | It copies a bit if it exists in either operand. | a|b ＝ 3 |
__or__() |
| ^ Binary XOR | It copies the bit if it is set in one operand but not both. | a^b = 2 |
__xor__() |
| ~ Binary Ones Complement | It is unary and has the effect of ‘flipping’ bits. | ~a = -2 |
__invert__() |
| « Binary Left Shift | The left operands value is moved left by the number of bits specified by the right operand. | b<<a = 6 |
__lshift__() |
| » Binary Right Shift | The left operands value is moved right by the number of bits specified by the right operand. | b>>a = 1 |
__rshift__() |
此外，这些算符除了作用在整数上以外，也有一些作用在其他数据类型上的内置重载（自定义类的重载很简单，重新定义对应的函数即可）。比如对于两个 set a|b 和 a.union(b) 作用相同。相应的 & 和 intersection， - 和difference, ^和 symmetric_difference 等价。当然其中减号是算数算符的重载。相应的集合 Venn 图，参考5。
re 模块 group 相关的细节
re 模块是 python 自带的强大的正则表达式处理模块。关于其基本使用可以参考这篇6。这里主要介绍其分组匹配的一些用法和 API。首先是正则表达式分组的写法，除了最基本的 () 形式，还可以给每组进行命名方便后续使用，语法是(?P<name>...)。match 对象和分组有关的 API 包括： lastindex 最后一个被捕获的分组在文本中的索引，lastgroup 最后一个被捕获分组的名字。groups() 各分组匹配到的内容的 tuple，groupdict 以分组别名为键以捕获内容为值的字典。以下是一个来自6的例子，不过代码是 python 2 风格的。
import re
m = re.match(r'(\w+) (\w+)(?P<sign>.*)', 'hello world!')
print "m.string:", m.string
print "m.re:", m.re
print "m.pos:", m.pos
print "m.endpos:", m.endpos
print "m.lastindex:", m.lastindex
print "m.lastgroup:", m.lastgroup
print "m.group(1,2):", m.group(1, 2)
print "m.groups():", m.groups()
print "m.groupdict():", m.groupdict()
print "m.start(2):", m.start(2)
print "m.end(2):", m.end(2)
print "m.span(2):", m.span(2)
print r"m.expand(r'\2 \1\3'):", m.expand(r'\2 \1\3')
### output ###
# m.string: hello world!
# m.re: <_sre.SRE_Pattern object at 0x016E1A38>
# m.pos: 0
# m.endpos: 12
# m.lastindex: 3
# m.lastgroup: sign
# m.group(1,2): ('hello', 'world')
# m.groups(): ('hello', 'world', '!')
# m.groupdict(): {'sign': '!'}
# m.start(2): 6
# m.end(2): 11
# m.span(2): (6, 11)
# m.expand(r'\2 \1\3'): world hello!
最后注意到 match 对象直接取匹配部分，除了使用.group(1) 之外，在 python 3.6 及更高的版本，也可以直接 matchobj[1] 来取匹配字符串。
re.compile().match() 和 re.match() 的 API 不同
虽然仍是 re 模块的问题，但由于这一条太容易出错，因此单列。一般人都会讲 pattern = re.compile('foo')，pattern.match() 和直接 re.match('foo',) 用法相同。但其实它们的 API 是不一样的。re.match(pattern, string, flags) 除了匹配的两个字符串之外，只有一个 flag 参数可选了，其代表了一些正则匹配细节的设定（比如大小写敏感之类）。但 re.compile 产生的 pattern 对象，对应的 pattern.match(string, pos, endpos)。此时 flag 的设定移到了 compile() 的参数中。而现在的 match 方法，可以指定待匹配字符串的起止 index，这在普通的 match 函数里无法做到，现在的匹配区间为 pos 到 endpos-1！因此两种 match 函数的 API 并不一致，千万要注意。而 pattern.search() 和 pattern.match() 的区别是，后者要求匹配从字符串指定的开始就匹配才算匹配，前者可在字符串任意位置匹配。注意到这里的 pos 参数和直接对输入字符串切片也不完全相同，因为 ^ 只匹配字符串的开始，如果指定 pos>0，则 ^ 不再匹配。因此 re 模块的准确使用，还是建议仔细阅读官方文档7。
python 的反射机制
所谓的反射机制，也没什么神秘的，说白了就是要实现这么个需求：我得到了某个函数或模块名的字符串，如何来调用对应的函数或模块？很明显直接 import 'string' 或是 'string'() 肯定是行不通。实现这一需求的方案即为反射机制。主要有两个部分，根据字符串导入模块：m = __import__('modulestrings')。根据字符串调用函数 f = getattr(module, 'funcstring', None)。
frame 对象和 __code__ 对象的应用
关于 frame 对象和 code 对象，要想详细了解其内涵和外延，需要对 python 究竟如何运行脚本有一个清晰的认识。这方面的内容可以参考我的笔记8和其中引用的课程。简单说 python 中的函数和类在运行之前先被编译为了 opcode，（之于虚拟机类似于指令集之于 CPU），而 __code__ 属性就给出了该对象，该对象包含了函数名称，参数名称，源代码行数，源代码所在文件名，变量数目，机器码本身等多种信息。在 lex 中，我们通过该对象来确定每个 rules 函数对应的原始行数，从而实现从前到后的排序。而在运行期，调用函数会形成新的 frame （类似压栈的概念），这就对应了运行时的 frame 对象，该对象包含了运行的函数，global 和 local 变量集等大量有用的属性。在 lex 中，我们主要通过该方案获取同一文件中定义的 rules。两个对象具体的属性，这里不再赘述，可以通过 dir() 命令来查看和测试。