3

问题

我正在尝试使用 Python Lex-Yacc (PLY) 实现容错解析器，但在输入字符串的末尾使用错误恢复规则时遇到问题。

如何从输入的意外结束中恢复？

例子

此示例语法生成形式为的字符串A END A END A END A END ...

Statement   : Expressions

Expressions : Expression Expressions
            | 

Expression  : A END

如果省略了 END 令牌，我想执行错误恢复，因此解析器会识别A A A END或识别刺痛。A A A

我的方法

我添加了一个错误恢复规则，它允许我接受像这样的输入A A A END

Expression : A END
           | A error

这使我可以接受以下输入： A A A END

但是，如果省略最后一个 END 标记 ( A A A)，我仍然会收到语法错误并且无法恢复。

示例层代码

from __future__ import print_function

# Tokens
tokens = ('A', 'END')

t_A   = r'A'
t_END = r'END'
t_ignore = " "

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

# Build the lexer
import ply.lex as lex
lex.lex()

# Rules
def p_statement_expr(p):
    '''statement : expressions'''
    print("parsed:", p[1])

def p_expressions(p):
    '''expressions : expression expressions'''
    p[0] = [p[1]] + p[2]

def p_expressions_empty(p):
    '''expressions : '''
    p[0] = list()

def p_expression_pharse(p):
    '''expression : A END
                  | A error'''
    p[0] = 'A'

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

import ply.yacc as yacc
yacc.yacc()

while 1:
    try:
        s = raw_input('query > ')   # use input() on Python 3
    except EOFError:
        break
    yacc.parse(s)
4

3 回答 3

4

我将其添加为新答案（并且知道赏金为时已晚 :-( ），因为这是一种非常不同的方法。如果我们使用flex，它会容易得多，因为它具有<<EOF>>匹配的令牌的概念仅在文件末尾。考虑到这一点后，我意识到通过在词法分析器周围使用代理，在不更改原始模块的情况下将该功能添加到 PLY 非常简单 。并且 Python 允许轻松实现代理，这要感谢特殊的方法。__getattr__

我只是添加

  • EOF将在文件末尾发送的新令牌
  • token一个围绕词法分析器方法的代理，它在文件末尾返回EOF第一次传递的特殊标记，然后返回正常None
  • 结束statement规则的 eof 令牌

并且仍然反转规则expressions : expressions expression而不是expressions : expression expressions允许立即减少

代码变为：

from __future__ import print_function

# Tokens
tokens = ('A', 'END', 'EOF')

t_A   = r'A'
t_END = r'END'
t_ignore = " "

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

# Build the lexer
import ply.lex as lex

orig_lexer = lex.lex()

class ProxyLexer(object):
    def __init__(self, lexer, eoftoken):
        self.end = False
        self.lexer = lexer
        self.eof = eoftoken
    def token(self):
        tok = self.lexer.token()
        if tok is None:
            if self.end :
                self.end = False
            else:
                self.end = True
                tok = lex.LexToken()
                tok.type = self.eof
                tok.value = None
                tok.lexpos = self.lexer.lexpos
                tok.lineno = self.lexer.lineno
        # print ('custom', tok)
        return tok
    def __getattr__(self, name):
        return getattr(self.lexer, name)

lexer = ProxyLexer(orig_lexer, 'EOF')

# Rules
def p_statement_expr(p):
    '''statement : expressions EOF'''
    print("parsed:", p[1])

def p_expressions(p):
    '''expressions : expressions expression'''
    p[0] = p[1] + [p[2]]

def p_expressions_empty(p):
    '''expressions : '''
    p[0] = list()

def p_expression_pharse(p):
    '''expression : A END
                  | A error'''
    p[0] = 'A'

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

import ply.yacc as yacc
parser = yacc.yacc()

while 1:
    try:
        s = raw_input('query > ')   # use input() on Python 3
    except EOFError:
        break
    parser.parse(s, lexer = lexer)

那样 ：

  • 原来的语法没有改变
  • 错误恢复方法仍然非常简单，并且不依赖于其余的语法
  • 它可以很容易地扩展到复杂的解析器
于 2014-10-24T09:29:49.520 回答
2

由于您想接受所有元素，您可以明确声明 aA不跟随a 的规则，END并使用 yacc 和 PLY 友好处理模棱两可的规则这一事实。

你可以简单地有一个正常的规则：

Expression : A END

并低于将发出警告的较低优先级规则（稍后会出现）

Expression : A

这样，所有的 A 都将被接受，不会有任何语法错误，并且对于任何没有后跟 END 的 A 都会发出警告，包括流程末尾的一个。为了更容易找到违规的 A，我在警告中添加了符号在流程中的位置。

编辑：

修改脚本以正确处理其他语法错误（例如AENDENDAEND），并expressions通过替换expressions : expression expressions为立即减少expressions : expressions expression

这是修改后的脚本（在 python 3.4 中测试，只需替换raw_input为input）：

from __future__ import print_function

# Tokens
tokens = ('A', 'END')

t_A   = r'A'
t_END = r'END'
t_ignore = " "

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

# Build the lexer
import ply.lex as lex
lex.lex()

# Rules
def p_statement_expr(p):
    '''statement : expressions'''
    print("parsed:", p[1])

def p_expressions(p):
    '''expressions : expressions expression'''
    p[0] = p[1] + [p[2]]

def p_expressions_err(p):
    '''expressions : expressions error'''
    p[0] = p[1]

def p_expressions_empty(p):
    '''expressions : '''
    p[0] = list()

def p_expression_pharse(p):
    '''expression : A END'''
    p[0] = 'A'

# add a separate rule BELOW previous one to display a warning
def p_expression_pharse_warn(p):
    '''expression : A'''
    print("Warning at absolute position %d (line %d)" % (p.lexpos(1), p.lineno(1)))
    p[0] = 'A'

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


import ply.yacc as yacc
yacc.yacc()

while 1:
    try:
        s = raw_input('query > ')   # use input() on Python 3
    except EOFError:
        break
    yacc.parse(s)

编辑：以下是避免附加规则的错误尝试：它比上述版本更复杂且效率更低。请看下面我的结论

根据评论编辑：

我理解你的观点，你不想增加语法规则。除了最后一个令牌外，它可以是容错的。如果您的最后一个令牌有误，它将不会被任何东西跟随，也永远不会被规则捕获expression : A error。

但是这里有一个容错解析器，如果出现错误，它会保留除最后一个标记之外的所有内容：

from __future__ import print_function

# Tokens
tokens = ('A', 'END')

t_A   = r'A'
t_END = r'END'
t_ignore = " "

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

# Build the lexer
import ply.lex as lex
lex.lex()

# Rules
def p_statement_expr(p):
    '''statement : expressions'''
    # print("parsed:", p[1])

def p_expressions(p):
    '''expressions : expressions expression'''
    p[0] = p[1] + [p[2]]
    result.append(p[2])

def p_expressions_empty(p):
    '''expressions : '''
    p[0] = list()

def p_expression_pharse(p):
    '''expression : A END
                  | A error'''
    p[0] = 'A'

def p_error(p):
    if p:
        global lasterr
        print("Syntax error at '%s' (%d)" % (p.value, p.lexpos))
    else:
        print("Syntax error at EOI")

import ply.yacc as yacc
yacc.yacc()

while 1:
    try:
        s = input('query > ')   # use input() on Python 3
    except EOFError:
        break
    result = []
    yacc.parse(s)
    print('Result', result)

expressions : expressions expression原则是通过而不是进行整理expressions : expression expressions，并将所有内容保存在全局变量中。

输入 A END A A END A A A END它给出

Result ['A', 'A', 'A', 'A', 'A', 'A']

并与 : A END A A END A A A END，它给出

Result ['A', 'A', 'A', 'A', 'A']

（除最后一个之外的所有标记）

使用真正的 flex - bison 解决方案，可以利用<<EOF>>在输入末尾匹配的特殊标记，在最后一个标记之后总是有另一个标记。不幸的是，它没有在 PLY 中实现，唯一真正的解决方案是引入一个单独接受A令牌的规则。对于真正的解析器，它还保证您实际上正在处理正确的令牌：我使用

def p_expression_pharse(p):
    '''expression : A END'''
    p[0] = 1 + p.lexpos(1)

# add a separate rule BELOW previous one to display a warning
def p_expression_pharse_warn(p):
    '''expression : A'''
    print("Warning at absolute position %d (line %d)" % (p.lexpos(1), p.lineno(1)))
    p[0] = -1 - p.lexpos(1)

唯一标识结果字符串中的标记，我得到正确的位置。

而且...错误处理很简单...

讨论 TL/DR：

我承认我错过了最后一个令牌错误恢复的要点。这是因为在我在实际用例中看到的所有解析器中，错误恢复包括拒绝语法上不正确的部分（因此不能直接使用）并在下一个正确的 token 组上重新同步解析器。在我所看到的一切中，如果可以使用部分句子，它一定不是由错误恢复机制处理，而是由语法规则处理，其中很容易描述适当的动作。

如果您只想保留违规输入以供以后处理，我认为这不是取决于语法的操作问题，我会简单地记录违规标记的位置，或者最多记下最后正确分析的标记的位置（一个完整元素的结尾），第一个错误恢复令牌的开始，并说中间的内容不正确。

但这与这里要求的有很大不同......

于 2014-10-16T09:03:04.067 回答
1

这适用于我能想象的所有例子 

from __future__ import print_function

# Tokens
tokens = ('A', 'END')

t_A   = r'A'
t_END = r'END'
t_ignore = " "

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

# Build the lexer
import ply.lex as lex
lex.lex()

# Rules
def p_statement_expr(p):
    '''statement : expressions'''
    #
    print("parsed:", p[1])

def p_expressions(p):
    '''expressions : expression expressions'''
    p[0] = p[1] + p[2]

def p_expressions_empty(p):
    '''expressions : '''
    p[0] = list()

def p_expression_pharse(p):
    '''expression : A END'''
    p[0] = ['A']

def p_expression_error(p):
    '''expression : A error'''
    p[0] = ['A']
    if p[2] is not None:
        p[0] += p[2]

def p_error(p):
    if p is None:
        print("Syntax error at EOI")
        e = yacc.YaccSymbol()
        e.type = 'error'
        e.value = None
        yacc.errok()
        return e
    elif p.type == 'error':
        yacc.errok()
        return
    elif hasattr(p, 'value'):
        print("Syntax error at '%s'" % p.value)
        e = yacc.YaccSymbol()
        e.type = 'error'
        e.value = p.value
        yacc.errok()
        return e




import ply.yacc as yacc
yacc.yacc()

while 1:
    try:
        s = raw_input('query > ')   # use input() on Python 3
    except EOFError:
        break
    yacc.parse(s)
于 2014-10-15T20:53:34.250 回答