SLY python не может анализировать простые токены

Я работаю над созданием простого интерпретируемого языка программирования с использованием SLY для создания AST, который я буду интерпретировать без использования SLY.

В настоящее время я смог сгенерировать все свои токены и передать их парсеру, но он не может распознать ни одно правило, только пустые.

Лексер:

from .sly.lex import Lexer

class ALexer(Lexer):
    tokens = { ID, NUMBER, STRING, BOOL, PLUS, TIMES, MINUS, DIVIDE, ASSIGN, LPAREN, RPAREN, COMMA, NL }
    ignore = ' \t'

# Tokens
@_(r'\d+[[.]?\d*[f]?]?')
def NUMBER(self, t):
    endswithF = t.value.endswith('f')
    isfloat = endswithF or t.value.find('.') != -1
    t.value = float(t.value[:-1] if endswithF else t.value) if isfloat else int(t.value)   # Convert to a numeric value
    return t

ID = r'[a-zA-Z_][a-zA-Z0-9_]*'
ID['true'] = BOOL
ID['false'] = BOOL

@_(r'".*"')
def STRING(self, t):
    t.value = t.value[1:-1]
    return t

# Special symbols
PLUS = r'\+'
MINUS = r'-'
TIMES = r'\*'
DIVIDE = r'/'
ASSIGN = r'='
LPAREN = r'\('
RPAREN = r'\)'
COMMA = r','

@_(r'true', r'false')
def BOOL(self, t):
    t.value = t.value == 'true'
    return t

@_(r'\n')
def NL(self, t):
    self.lineno += 1

def error(self, t):
    print("Illegal character '%s'" % t.value[0])
    self.index += 1

Полезные классы:

from enum import Enum

class SupportedOp(str, Enum):
    CONSTANT = "CONSTANT",
    VARIABLE = "VARIABLE",
    ARGS_LIST = "ARGS_LIST",
    FUNC_CALL = "FUNC_CALL",
    STATEMENT = "STATEMENT",
    STATEMENT_LIST = "STATEMENT_LIST",
    PROGRAM = "PROGRAM",
    SUM = '+',
    SUB = '-',
    DIV = '/',
    MUL = '*',
    ASSIGNMENT = '='

class ParsedOp(dict):
    def __init__(self, op: SupportedOp, *values):
        dict.__init__(self, op=op, values=values)

Парсер:

class AParser(Parser):
debugfile = 'parser.out'
tokens = ALexer.tokens

precedence = (
      #('nonassoc', LESSTHAN, GREATERTHAN),  # Nonassociative operators
      ('left', PLUS, MINUS),
      ('left', TIMES, DIVIDE)
      #('right', UMINUS),            # Unary minus operator
 )

@_('statement_list')
def program(self, p):
    print('program', p[0])
    return ParsedOp(SupportedOp.PROGRAM, p[0])

@_('statement BACK_IN_LINES statement_list')
def statement_list(self, p):
    print('statement_list', p[0], p[1], p[2])
    lst: list = p[1].values[0]
    lst.append(p[0])
    return ParsedOp(SupportedOp.STATEMENT_LIST, lst)

@_('statement')
def statement_list(self, p):
    print('statement_list', p[0])
    return ParsedOp(SupportedOp.STATEMENT_LIST, [p[0]])

@_('empty')
def statement_list(self, p):
    print('empty statement_list')
    return ParsedOp(SupportedOp.STATEMENT_LIST, [])

@_('NL BACK_IN_LINES', 'NL')
def BACK_IN_LINES(self, p):
    print('BACK_IN_LINES', p[0])
    #unused
    return 'NL'

@_('assignment', 'expr')
def statement(self, p):
    print('statement', p[0])
    return ParsedOp(SupportedOp.STATEMENT, p[0])

@_('ID ASSIGN expr')
def assignment(self, p):
    print('assignment', p[0], p[1], p[2])
    return ParsedOp(SupportedOp.ASSIGNMENT, p[0], p[2])

@_('expr COMMA expr_list')
def expr_list(self, p):
    print('expr_list', p[0], p[1], p[2])
    lst: list = p[1].values[0]
    lst.append(p[0])
    return ParsedOp(SupportedOp.ARGS_LIST, lst)

@_('expr')
def expr_list(self, p):
    print('expr_list', p[0])
    return ParsedOp(SupportedOp.ARGS_LIST, [p[0]])

@_('empty')
def expr_list(self, p):
    print('empty expr_list')
    return ParsedOp(SupportedOp.ARGS_LIST, [])

@_('constant')
def expr(self, p):
    print('expr', p[0])
    return p[0]

@_('ID')
def expr(self, p):
    print('expr', p[0])
    return ParsedOp(SupportedOp.VARIABLE, p[0])

@_('LPAREN expr RPAREN')
def expr(self, p):
    print('expr', p[0], p[1], p[2])
    return p[1]

@_('ID LPAREN expr_list RPAREN')
def expr(self, p):
    print('expr', p[0], p[1], p[2], p[3])
    #if exists p.ID in functions
    return ParsedOp(SupportedOp.FUNC_CALL, p.ID, p.expr_list)

@_( 'expr PLUS expr',
    'expr MINUS expr',
    'expr TIMES expr',
    'expr DIVIDE expr')
def expr(self, p):
    print('expr', p[0], p[1], p[2])
    return ParsedOp(SupportedOp(p[1]), p[0], p[2])

@_('NUMBER', 'STRING', 'BOOL')
def constant(self, p):
    print('constant', p[0])
    return ParsedOp(SupportedOp.CONSTANT, p[0])

@_('')
def empty(self, p):
    print('empty')
    pass

def error(self, p):
    if p:
        print("Syntax error at token", p.type)
        # Just discard the token and tell the parser it's okay.
        self.errok()
    else:
        print("Syntax error at EOF")

Я не знаю, все ли мои правила в порядке, но я прокомментировал каждое правило, оставив без комментариев только «постоянное» правило, которое является простым, но все еще не может его распознать.

Главный:

tokens_out = lexer.ALexer().tokenize(event.get("code"))
tree = AParser().parse(tokens_out)

Все мои токены хорошо распознаются, так что с лексером все в порядке. Парсер не может распознать ни одно правило. Есть идеи?

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

rici 20.11.2022 19:26

В любом случае, отключение правил не позволит анализатору распознавать больше. Это может только заставить его распознавать меньше. Если Sly сообщает о конфликтах синтаксического анализатора, вы должны решить их, прежде чем пытаться что-либо еще. И вы обязательно должны упомянуть их в своем вопросе.

rici 20.11.2022 19:32

@rici Я добавил лексер в свой пост, проблема в том, что он не распознает никаких правил, кроме пустого, если я удалю пустой, я получаю ошибку EOF в моем парсере. Я также пытался оставить только постоянное правило и быть началом парсера, но все равно получаю EOF

Ivan Lo Greco 20.11.2022 23:38

20 Продолжение вопросов: что именно возвращает event.get("code")?

rici 20.11.2022 23:48

@rici event.get("code") - это строка кода, который я должен разобрать, я передаю его лексеру, чтобы получить от него токены, все в порядке в качестве ввода, например "x = 2" или любой оператор описан внутри метода парсера. Проблема в том, что я написал в своих предыдущих сообщениях, у меня нет конфликтов, он просто не распознает мои токены.

Ivan Lo Greco 20.11.2022 23:51

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

rici 21.11.2022 02:56

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

rici 21.11.2022 02:59
Мутабельность и переработка объектов в Python
Мутабельность и переработка объектов в Python
Объекты являются основной конструкцией любого языка ООП, и каждый язык определяет свой собственный синтаксис для их создания, обновления и...
Другой маршрут в Flask Python
Другой маршрут в Flask Python
Flask - это фреймворк, который поддерживает веб-приложения. В этой статье я покажу, как мы можем использовать @app .route в flask, чтобы иметь другую...
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
Проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
Python PyPDF2 - запись метаданных PDF
Python PyPDF2 - запись метаданных PDF
Python скрипт, который будет записывать метаданные в PDF файл, для этого мы будем использовать PDF ридер из библиотеки PyPDF2 . PyPDF2 - это...
Переменные, типы данных и операторы в Python
Переменные, типы данных и операторы в Python
В Python переменные используются как место для хранения значений. Пример переменной формы:
Почему Python - идеальный выбор для проекта AI и ML
Почему Python - идеальный выбор для проекта AI и ML
Блог, которым поделился Harikrishna Kundariya в нашем сообществе Developer Nation Community.
1
7
117
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Насколько я вижу, ваш код работает нормально до момента, когда вы пытаетесь разобрать второй оператор. Я попробовал это с вводом x=2, как было предложено в вашем комментарии, и это дало следующий результат (красиво напечатанный с модулем pprint):

{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
  'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
                'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'x',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 2,)})},)}],)},)}

Но как только вы попытаетесь разобрать два утверждения — скажем, x=2 и y=2 в разных строках — все начнет разваливаться.

Есть несколько вопросов, которые я постараюсь решить по одному.

Первая проблема заключается в том, что ваше правило лексера NL ничего не возвращает, а это значит, что токен не генерируется. Это означает, что правило BACK_IN_LINES не может совпадать, потому что оно ожидает увидеть один или несколько токенов NL. Это генерирует каскад ошибок синтаксического анализатора, которые вы должны были видеть на своей консоли.

Легко запутаться в прогрессе парсера. Поскольку синтаксический анализатор не видит токен NL, он видит x = 2 y .... В тот момент, когда он видит y, он еще не уменьшил expr; в конце концов, следующим токеном мог быть + или другой оператор. Но ID не является одним из возможных токенов, которые могут следовать за 2, поэтому немедленно выдается синтаксическая ошибка, в результате чего expr, statement и statement_list не уменьшаются, и поэтому их действия сокращения никогда не выполняются, и, таким образом, вы никогда не видите никаких выходных данных отладки, которые вы поместили в действия сокращения. На самом деле это не означает, что правило не было признано; точнее было бы сказать, что правило было признано, но все еще возможно более длительное совпадение.

Если вы исправите лексер, добавив return t в конце правила NL, то вы столкнетесь со второй проблемой, которая заключается в действии сокращения для statement_list: statement BACK_IN_LINES statement_list. Эта ошибка приводит к сбою синтаксического анализа даже для ввода, состоящего только из x=2, если этот ввод завершается символом новой строки. Действие запускается, потому что BACK_IN_LINES теперь распознано, поэтому грамматика требует, чтобы statement_list has two subcomponents, a statement (x=2) and a statement_listconsisting of the rest of the input. The rest of the input is empty, which is OK because you allow astatement_list` соответствовал пустому вводу. Но, как я уже сказал, это приводит к выполнению действия сокращения, и это действие сокращения включает в себя:

lst: list = p[1].values[0]

Эта линия имеет несколько проблем. Во-первых, p[1] — это грамматический символ BACK_IN_LINES; вы, очевидно, намеревались использовать p[2], который является statement_list. Итак, p[1] — это строка NL, не имеющая атрибута values. (Это должно быть очевидно из трассировки Python, если предположить, что вы можете видеть трассировку исключений. Если вы не видите, вам следует серьезно подумать об отладке в консоли Python, а не в том, что вы используете.)

Но когда мы исправим это, чтобы вместо этого использовать p[2], мы все равно получим исключение Python TypeError. Вместо того, чтобы жаловаться на то, что у str нет атрибута values, теперь он жалуется, что builtin_function_or_method не может быть подписан. builtin_function_or_method — это values метод объекта dict, потому что p[2] — это SupportedOp, который является подклассом dict. Если бы вы намеревались использовать метод values, вам пришлось бы его вызвать, но я не думаю, что это то, что вы намеревались (поэтому ключ values, возможно, плохо назван). На самом деле вы имели в виду значение, связанное с ключом values, что означает, что строка должна выглядеть так:

lst: list = p[2]["values"][0]

Но это все еще немного проблематично. Давайте посмотрим на проанализированный результат ввода, состоящий из трех строк:

first = 1
second = 2
third = 3

Это производит (опять же, красиво напечатано с pprint):

{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
  'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
                'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'third',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 3,)})},)},
                              { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'second',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 2,)})},)},
                              { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'first',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 1,)})},)}],)},)}

Если вы внимательно посмотрите на этот вывод, то увидите, что три утверждения действительно есть, но в неправильном порядке.

Это результат вашего решения использовать праворекурсивное правило для statement_list:

statement_list: statement BACK_IN_LINES statement_list

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

statement_list: statement_list BACK_IN_LINES statement

Это имеет два преимущества. Во-первых, не требуется использование стека синтаксического анализатора для хранения всех промежуточных и неполных подпарсеров statement_list до тех пор, пока не будет достигнут конец списка. Что еще более важно, он выполняет действия сокращения для рекурсивного нетерминала в том порядке, в котором вы, вероятно, ожидаете их выполнения, то есть слева направо.

Праворекурсивное правило выполняет действия приведения справа налево, потому что первое рекурсивное приведение является последним вложенным statement_list. И в результате получается то, что мы уже видели: statement присоединяются к statement_list в обратном порядке, начиная с последнего.

Правило легко переписать как леворекурсивное. Но если мы сделаем наивное изменение, мы получим другую проблему. (Возможно) желательно, чтобы ввод был разрешен, но не обязательно заканчивался новой строкой. Это работало с праворекурсивным производством, потому что statement_list было разрешено быть пустым. Но это не поможет с правилом левой рекурсии; леворекурсивное правило с опцией empty помещает опцию empty в начало списка (именно потому, что оно создает список слева направо). С леворекурсивным правилом удобнее оставить statement пустым. Но вместо того, чтобы добавлять «пустой оператор», который будет загромождать AST, мы можем просто добавить правило к statement_list, которое принимает пустую последовательность вместо оператора. Как только мы это сделаем, мы избавимся от необходимости в BACK_IN_LINES, потому что грамматическая логика сохраняется в statement_list.

Таким образом, мы можем удалить BACK_IN_LINES и заменить правила для statement_list следующим:

    @_('statement')
    def statement_list(self, p):
        print('statement_list', p[0])
        return ParsedOp(SupportedOp.STATEMENT_LIST, [p[0]])
    
    @_('empty')
    def statement_list(self, p):
        print('empty statement_list')
        return ParsedOp(SupportedOp.STATEMENT_LIST, [])
    
    @_('statement_list NL')
    def statement_list(self, p):
        print('statement_list', p[0])
        return p[0]
    
    @_('statement_list NL statement')
    def statement_list(self, p):
        print('statement_list', p[0], p[1], p[2])
        lst: list = p[0]["values"][0]
        lst.append(p[2])
        return ParsedOp(SupportedOp.STATEMENT_LIST, lst)

Теперь, наконец, мы получаем ожидаемый разбор:

{ 'op': <SupportedOp.PROGRAM: 'PROGRAM'>,
  'values': ( { 'op': <SupportedOp.STATEMENT_LIST: 'STATEMENT_LIST'>,
                'values': ( [ { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'first',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 1,)})},)},
                              { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'second',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 2,)})},)},
                              { 'op': <SupportedOp.STATEMENT: 'STATEMENT'>,
                                'values': ( { 'op': <SupportedOp.ASSIGNMENT: '='>,
                                              'values': ( 'third',
                                                          { 'op': <SupportedOp.CONSTANT: 'CONSTANT'>,
                                                            'values': ( 3,)})},)}],)},)}

Другие вопросы по теме