About
RSS

Bit Focus


PLY 构造词法分析工具

Posted at 2013-08-03 11:18:01 | Updated at 2018-10-17 02:09:31

    PLY 需要安装一份. 可以直接通过 pip 安装

# pip install ply

    这东西并非一个扩展的正则表达式工具, 而是一个完备的编译器构造工具, 不过这篇文章只打算讨论其词法分析器构造部分.

基本例子

    PLY 很魔法的一点是它使用到了模块内部反射. 也就是说在产生一个词法分析器时, 并不是把词法规则传递给 PLY 的接口, 而是依次将一些指定名字的变量或函数定义在 py 文件中.
    下面给出第一个例子, 从文本中抓出十进制数值.
import ply.lex

tokens = (
    'NUMBER',
)

t_NUMBER = r'\d*[.]?\d+'

def t_error(t):
    t.lexer.skip(1)

ply.lex.lex()
ply.lex.input('''
    The Chinese mathematician Zu Chongzhi, around 480 AD, calculated that
        pi ~= 355/113
    (a fraction that goes by the name Milv in Chinese), using Liu Hui's
    algorithm applied to a 12288-sided polygon. With a correct value for its
    seven first decimal digits, this value of 3.141592920... remained the most
    accurate approximation of pi available for the next 800 years.

    <From Wikipedia:Pi>
''')

for token in iter(ply.lex.token, None):
    print token.type, token.value
    输出

NUMBER 480
NUMBER 355
NUMBER 113
NUMBER 12288
NUMBER 3.141592920
NUMBER 800

    上面的代码有这么一些要点

利用分词输出

    从这个基本例子迈向一个用于简单表达式计算的词法分析器并不困难. 如果按照之前一篇文章里所演示的那个功能 (请将该文章中最后一段代码保存在 expr_eval.py 中以供这次使用), 需要至少以下这些词元类型
    以及, 尽量地, 应该忽略空格换行等字符. 这个在 PLY 中可以通过定义 t_ignore 来实现.
    并且, 这次不是将结果打印出来完事, 而是要构造一个能用的词元序列. 因此需要一个将 PLY 词元转换为在 expr_eval.py 中定义的 Token 类实例的函数. Token 对象构造时, 除了词元字符串值参数外, 还需要两个值表示是否为数值以及是否可能是前置一元运算符, 这两个参数都可以根据词元类型获取.
    下面是对应的代码
import ply.lex
import expr_eval

tokens = (
    'BINARY_OP', 'UNARY_OR_BINARY_OP', 'OPEN_PAREN', 'CLOSE_PAREN', 'INTEGER',
)

t_BINARY_OP = r'[*/^]'
t_UNARY_OR_BINARY_OP = r'-|\+'
t_INTEGER = r'\d+'
t_OPEN_PAREN = r'('
t_CLOSE_PAREN = r')'
t_ignore = ' '

def t_error(t):
    raise ValueError('invalid character: ' + t.value[0])

def create_token(token):
    if token.type in ['OPEN_PAREN', 'CLOSE_PAREN', 'BINARY_OP']:
        return expr_eval.Token(token.value, False, False)
    if token.type in ['UNARY_OR_BINARY_OP']:
        return expr_eval.Token(token.value, False, True)
    return expr_eval.Token(token.value, True, False)

ply.lex.lex()
if __name__ == '__main__':
    ply.lex.input('''-(6 * 5) + (4 ^ 3) ^ 2 - 1''')
    expr = expr_eval.buildExpression([
        create_token(token) for token in iter(ply.lex.token, None)
    ])
    print expr.evaluate()
    print -(6 * 5) + (4 ** 3) ** 2 - 1
需要注意的是, t_ignore 取值并不是一个正则表达式 (并非 r'[ ]+'); 这是个坑, 如果不慎写成了这种形式, 输入字符串中所有的加号也会被忽略

在获取词元时转换

    create_token 的实现显得非常直截了当, 但并不很优雅. 而实际上 PLY 提供其它的机制令开发者绕开这种笨拙的映射, 这一机制的实现是将词元规则定义为函数而不是一个字符串. 比如
def t_UNARY_OR_BINARY_OP(token):
    r'-|\+'
    token.value = expr_eval.Token(token.value, False, True)
    return token
    匹配词元的正则表达式成为了这个函数的文档字符串; 而在这个函数中, 传入参数的 tokenvalue 属性被修改为了期望的词元对象, 因此, 在 create_token 中, 对应类型的词元不需再次转换了
def create_token(token):
    if token.type in ['OPEN_PAREN', 'CLOSE_PAREN', 'BINARY_OP']:
        return expr_eval.Token(token.value, False, False)
    if token.type in ['UNARY_OR_BINARY_OP']:
        return token.value
    return expr_eval.Token(token.value, True, False)
    当然, 如果所有的词元类型都这么处理了, create_token 这个赘余就不再需要了, 也就是说代码被修改成这样
import ply.lex
import expr_eval

tokens = (
    'BINARY_OP', 'UNARY_OR_BINARY_OP', 'OPEN_PAREN', 'CLOSE_PAREN', 'INTEGER',
)

def t_BINARY_OP(token):
    r'[*/^]'
    token.value = expr_eval.Token(token.value, False, False)
    return token

def t_UNARY_OR_BINARY_OP(token):
    r'-|\+'
    token.value = expr_eval.Token(token.value, False, True)
    return token

def t_INTEGER(token):
    r'\d+'
    token.value = expr_eval.Token(token.value, True, False)
    return token

def t_OPEN_PAREN(token):
    r'('
    token.value = expr_eval.Token(token.value, False, False)
    return token

def t_CLOSE_PAREN(token):
    r')'
    token.value = expr_eval.Token(token.value, False, False)
    return token

t_ignore = ' '

def t_error(t):
    raise ValueError('invalid character: ' + t.value[0])

ply.lex.lex()
if __name__ == '__main__':
    ply.lex.input('''-(6 * 5) + (4 ^ 3) ^ 2 - 1''')
    expr = expr_eval.buildExpression([
        token.value for token in iter(ply.lex.token, None)
    ])
    print expr.evaluate()
    print -(6 * 5) + (4 ** 3) ** 2 - 1
    冗余代码仍旧很多, 有兴趣可以考虑试试装饰器.

Post tags:   Compiler Construction  Python  Tutorial  PLY

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site