Python Lex-Yacc (PLY) Исправление ошибок в конце ввода

Question

проблема

Я пытаюсь реализовать устойчивый к ошибкам синтаксический анализатор с помощью 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), Я все еще получаю синтаксическую ошибку и не могу восстановить.

---

Пример кода PLY

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)

Answer 1

Я добавляю его в качестве нового ответа (и знаю, что для награды слишком поздно:-(), потому что это совсем другой подход. Если мы использовали flexбыло бы намного проще, так как он имеет понятие <<EOF>> токен, который соответствует только в конце файла. Подумав об этом, я понял, что очень просто добавить эту функциональность в PLY без каких-либо изменений в исходном модуле, используя прокси вокруг лексера. А Python позволяет легко внедрять прокси благодаря __getattr__ особый метод.

Я просто добавляю

• новый токен EOF это будет отправлено в конце файла
• прокси во всем token метод лексера, который по окончанию файла возвращает специальный EOF токен на первом проходе, а затем нормальный None
• конец жетона statement правило

И все же поменять правило 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)

Сюда:

• оригинальная грамматика не изменилась
• метод исправления ошибок остается тупо простым и не зависит от оставшейся грамматики
• это может быть легко расширено на сложные парсеры

Answer 2

Поскольку вы хотите принять все элементы, вы можете явно объявить правило для A не сопровождается END и использовать тот факт, что yacc и PLY дружественно справляются с неоднозначными правилами.

Вы можете просто иметь нормальное правило:

Expression : A END

и ниже правила с более низким приоритетом (как это происходит позже), который выдаст предупреждение

Expression : A

Таким образом, все A будут приняты, не будет никакой синтаксической ошибки, и предупреждение будет выдано для любого A, за которым не следует END, включая одно в конце потока. Чтобы легче было найти нарушителя, я добавил в предупреждение положение символа в потоке.

Редактировать:

Сценарий изменен, чтобы правильно обрабатывать другие синтаксические ошибки (такие как 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']

(все токены, кроме последнего)

Благодаря настоящему гибкому решению для бизонов можно было бы использовать специальные <<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:

Я признаю, что упустил момент восстановления после последней ошибки токена. Это потому, что во всех синтаксических анализаторах, которые я видел в реальных случаях использования, исправление ошибок состояло в отклонении части, которая была синтаксически неправильной (и, следовательно, не используемой напрямую), и повторной синхронизации синтаксического анализатора в следующей правильной группе токена. Во всем, что я видел, если можно использовать частичное предложение, оно должно обрабатываться не механизмом исправления ошибок, а правилом грамматики, в котором легко описать соответствующее действие.

Если вы просто хотите сохранить ошибочный ввод для последующей обработки, я думаю, что это не является проблемой действия в зависимости от синтаксиса, и я просто хотел бы отметить позицию ошибочного токена или, самое большее, отметить позицию последнего правильно проанализированного токена (конец полного элемента), начало токена восстановления первой ошибки и говорят, что то, что находится между, неверно.

Но это будет сильно отличаться от того, что здесь просят...

Answer 3

Это работает для всех примеров, которые я мог себе представить

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)