Python: проблемы с YACC - PullRequest
Новая
       20

Python: проблемы с YACC

3 голосов
/ 29 мая 2010

Я использую PLY для разбора предложений вроде:

«CS 2310 или эквивалентный опыт»

Желаемый вывод: 

[[("CS", 2310)], ["equivalent experience"]]

Символы токена YACC: 

tokens = [
    'DEPT_CODE',
    'COURSE_NUMBER',
    'OR_CONJ',
    'MISC_TEXT',
]

t_DEPT_CODE = r'[A-Z]{2,}'
t_COURSE_NUMBER  = r'[0-9]{4}'

t_OR_CONJ = r'or'

t_ignore = ' \t'

terms = {'DEPT_CODE': t_DEPT_CODE,
         'COURSE_NUMBER': t_COURSE_NUMBER,
         'OR_CONJ': t_OR_CONJ}

for name, regex in terms.items():
    terms[name] = "^%s$" % regex

def t_MISC_TEXT(t):
    r'\S+'
    for name, regex in terms.items():
        # print "trying to match %s with regex %s" % (t.value, regex)
        if re.match(regex, t.value):
            t.type = name
            return t

    return t

(MISC_TEXT должен соответствовать чему-либо, что не учитывается другими терминами.)

Некоторые соответствующие правила парсера: 

precedence = (
    ('left', 'MISC_TEXT'),
)


def p_statement_course_data(p):
    'statement : course_data'
    p[0] = p[1]

def p_course_data(p):
    'course_data : course'
    p[0] = p[1]


def p_course(p):
    'course : DEPT_CODE COURSE_NUMBER'
    p[0] = make_course(p[1], int(p[2]))


def p_or_phrase(p):
    'or_phrase : statement OR_CONJ statement'
    p[0] = [[p[1]], [p[3]]] 


def p_misc_text(p):
    '''text_aggregate : MISC_TEXT MISC_TEXT
                      | MISC_TEXT text_aggregate
                      | text_aggregate MISC_TEXT '''
    p[0] = "%s %s" % (p[0], [1])

def p_text_aggregate_statement(p):
    'statement : text_aggregate'
    p[0] = p[1]

К сожалению, это не удается: 

# works as it should
>>> token_list("CS 2110 or equivalent experience")
[LexToken(DEPT_CODE,'CS',1,0), LexToken(COURSE_NUMBER,'2110',1,3), LexToken(OR_CONJ,'or',1,8), LexToken(MISC_TEXT,'equivalent',1,11), LexToken(MISC_TEXT,'experience',1,22)]

# fails. bummer.
>>> parser.parse("CS 2110 or equivalent experience")
Syntax error in input: LexToken(MISC_TEXT,'equivalent',1,11)

Что я делаю не так? Я не совсем понимаю, как установить правила приоритета.

Кроме того, это моя функция ошибки: 

def p_error(p):
    print "Syntax error in input: %s" % p

Есть ли способ узнать, какое правило пробовал синтаксический анализатор при сбое? Или каким-то другим способом заставить парсер печатать, который управляет его попыткой?

ОБНОВЛЕНИЕ token_list() - это просто вспомогательная функция: 

def token_list(string):
    lexer.input(string)
    result = []
    for tok in lexer:
        result.append(tok)
    return result

ОБНОВЛЕНИЕ 2: Вот анализ, который я хочу выполнить: 

Symbol Stack                                Input Tokens                                                Action
                                            DEPT_CODE COURSE_NUMBER OR_CONJ MISC_TEXT MISC_TEXT
DEPT_CODE                                   COURSE_NUMBER OR_CONJ MISC_TEXT MISC_TEXT                   Shift DEPT_CODE
DEPT_CODE COURSE_NUMBER                     OR_CONJ MISC_TEXT MISC_TEXT                                 Shift COURSE_NUMBER
course                                      OR_CONJ MISC_TEXT MISC_TEXT                                 Reduce course : DEPT_CODE COURSE_NUMBER
course_data                                 OR_CONJ MISC_TEXT MISC_TEXT                                 Reduce course_data : course
statement                                   OR_CONJ MISC_TEXT MISC_TEXT                                 Reduce statement : course_data
statement OR_CONJ                           MISC_TEXT MISC_TEXT                                         Shift OR_CONJ

statement OR_CONJ MISC_TEXT                 MISC_TEXT                                                   Shift MISC_TEXT
statement OR_CONJ text_aggregate            MISC_TEXT                                                   Reduce text_aggregate : MISC_TEXT
statement OR_CONJ text_aggregate MISC_TEXT                                                              Shift MISC_TEXT
statement OR_CONJ text_aggergate                                                                        Reduce text_aggregate : text_aggregate MISC_TEXT

statement OR_CONJ statement                                                                             Reduce statement : TEXT_AGGREGATE
or_phrase                                                                                               Reduce or_phrase : statement OR_CONJ statement
statement                                                                                               Reduce statement : or_phrase

Я добавил это действие для разбора: 

def p_misc_text_singleton(p):
    'text_aggregate : MISC_TEXT'
    p[0] = p[1]

Когда я пытаюсь собрать парсер, я получаю такой вывод: 

Generating LALR tables
WARNING: 2 shift/reduce conflicts
WARNING: 3 reduce/reduce conflicts
WARNING: reduce/reduce conflict in state 8 resolved using rule (text_aggregate -> MISC_TEXT MISC_TEXT)
WARNING: rejected rule (text_aggregate -> MISC_TEXT) in state 8

Синтаксический анализ все равно не выполняется из-за синтаксической ошибки, как указано выше.

1 Ответ

1 голос
/ 17 ноября 2014

Я не могу воспроизвести вашу ошибку, вместо этого я получаю синтаксическую ошибку "или". Вы не включили правило, которое использует or_phrase. Когда я включаю один, я не получаю ошибок.

Я не думаю, что это проблема приоритета. Было бы полезно, если бы вам пришлось настроить ведение журнала, чтобы вы могли видеть шаги, предпринимаемые PLY, и сравнивать их с тем, что вы хотите, чтобы произошло. Для этого передайте debug=1 в функцию анализа (вам также может потребоваться передать это yacc). Посмотрите на PLY yacc.py, если вы не можете запустить отладку.

Конфликт уменьшения / уменьшения возникает из-за неоднозначности того, следует ли уменьшить MISC_TEXT MISC_TEXT до text_aggregate MISC_TEXT или уменьшить MISC_TEXT MISC_TEXT до text_aggregate.

Не имея возможности воспроизвести проблему, я думаю, что бы исправить вашу ошибку - изменить правило p_misc_text на:

'''text_aggregate : MISC_TEXT | text_aggregate MISC_TEXT'''

Я думаю, вы также можете удалить кортеж precedence.

...