Как создать алгоритм синтаксического анализа списка токенов?

Question

[Иван Четчасов]

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

Каждый токен - список: ['type', 'value']

Пример желаемой работы:

tns = [['lpar', '('], ['int', '5'], ['plus', '+'], ['int', '5'], ['star', '*'], ['int', '5'], ['rpar', ')'], ['slash', '/'], ['int', '10']]
print(Parser.parse(tns))
# >>> [[['plus', '+'], ['int', '5']], [['star', '*'], ['int', '5']],\
#     [['plus', '+'], ['int', '5']], [['slash', '/'], ['int', '10']]]

или

tns = [['lpar', '('], ['int', '5'], ['plus', '+'], ['int', '5'], ['star', '*'], ['int', '5'], ['rpar', ')'], ['slash', '/'], ['int', '10']]
print(Parser.parse(tns))
# >>> [[[['int', '5'], ['plus', '+'], ['int', '5']], ['star', '*'],
#     ['int', '5']], ['slash', '/'], ['int', '10']],
#     ['div', 'mul', 'add']

Результативный код, естественно не рабочий, выглядит как-то так:

Спойлер

import re
import sys
import os
from typing import Any


class ExceptionTeplate(Exception):
    def __call__(self, *args):
        return self.__class__(*(self.args + args))
    pass

class Parser:
    class Error(ExceptionTeplate):pass
    class Stack:
        top, lst, size = 0, [], 1024
        def push(var: Any):
            if Parser.Stack.top >= Parser.Stack.size:
                raise OverflowError("Stack data overflow")
            Parser.Stack.lst.append(var)
            Parser.Stack.top += 1
            pass
        def pop() -> Any:
            if Parser.Stack.top <= 0:
                raise StopIteration("Stack is null")
            Parser.Stack.top -= 1
            ret = Parser.Stack.lst[-1]
            Parser.Stack.lst = Parser.Stack.lst[:-1]
            return ret
        def last() -> Any:
            return Parser.Stack.lst[Parser.Stack.top]
        pass
    #
    def parse(formula_string):
        number = ''
        for formula_string in formula_string:
            for s in formula_string: # т.к. принимает список строк,
                if s[0] in ['int']:        # их нужно парсить по отдельности
                    number += s[1]
                elif number:
                    yield float(number) if not number.startswith('0x') else int(number, 16)
                    number = ''
                if s[1] in '+-*/|%^&*=' or s[1] in "()":
                    yield s[1]
            if number:
                yield float(number) if not number.startswith('0x') else int(number, 16)
        pass
    pass
#

Но Parser.parse(code_line) возвращает какой-то набор несвязанных чисел и скобок.

Был бы очень благодарен за ответ!

Comments

[Vindicar]

Тебе что парсить-то нужно? Только математические выражения?
Потому что в этом случае есть алгоритм Дейкстры (railroad algorythm). Переводишь своё выражение в постфиксную нотацию, а уж расчёт на её базе элементарно реализуется с помощью стека.

[Иван Четчасов]

Vindicar, нет, не только математические выражения, но и строки кода, где могут появляться переменные и функции.

Answer 1

[Vindicar]

Ну для начала, ты неправильно ставишь цель. После синтаксического разбора у тебя будет не список, а древовидная структура данных, а итоговый код будет результатом обхода этой структуры в глубину.
Так что читай про восходящий алгоритм. Идея у него простая. У тебя должен быть набор правил твоей грамматики, например:
ЦИКЛ_WHILE = 'while' '(' ВЫРАЖЕНИЕ ')' ОПЕРАТОР
Заглавными я записал нетерминальные символы - что-то, что раскрывается далее в последовательность токенов.
Остальное - терминальные символы, т.е. токены.
Итак, у тебя есть цепочка символов - терминальных или нетерминальных. Нетерминальные хранят в себе кусочек дерева программы, терминальные хранят в себе один токен.
1. Перебираешь правила, ищешь правило, соответствующее текущей позиции в цепочке. Для начала цепочки это будет правило "программа в целом".
2. Строишь узел дерева, соответствующий найденному правилу.
3. Помещаешь в этот узел терминальные символы, входящие в правило. В примере выше это будут 'while' и '('. Сдвигаешь позицию в цепочке.
4. Если в правиле дальше идёт нетерминальный символ, рекурсивно обрабатываешь цепочку по правилу для этого символа, начиная с текущей позиции. Когда обработка закончится, у тебя позиция в цепочке сместится на конец последовательности символов для этого нетерминала, и можно будет продолжить для следующего символа в правиле.
5. Когда правило закончилось - возвращаешь полученное мини-дерево, чтобы вышележащий код его встроил в свой узел дерева.
6. Если есть альтернативы, сохраняешь текущую позицию в цепочке и пробуешь альтернативы по очереди. Если альтернатива не сработала (правило тут не подходит), то возвращаешься к сохранённой позиции и пробуешь уже с другой альтернативой.
7. Если в какой-то момент ни одно правило не подошло, или если мы получили неожиданный терминал, есть синтаксическая ошибка в коде.

Это сравнительно легко реализуется через косвенную рекурсию. Т.е. у тебя в парсере будет много методов nfrjuj вида (псевдокод!):

def parse_while_node(tokens: List[Token], pos: int) -> TreeNode, int:
    """Принимает список токенов и позицию в нём, возвращает мини-дерево и новую позицию в списке."""
    node = WhileNode() # узел дерева разбора, соответствующий циклу while
    assert tokens[pos].type == 'while'  # проверяем фиксированный токен, выкидываешь исключение если это не он
    pos += 1
    assert tokens[pos].type == '('
    pos += 1
    # обращаемся к другому правилу для разбора нетерминального символа ВЫРАЖЕНИЕ
    # сохраняем мини-дерево для выражения условия и обновляем позицию
    node.condition, pos = parse_expression_node(tokens, pos)
    assert tokens[pos].type == ')'
    pos += 1
    # аналогично парсим нетерминал ОПЕРАТОР
    node.body, pos = parse_operator_node(tokens, pos)
    # возвращаем вызвавшему нас коду наше минидерево с узлом while на вершине,
    # а также позицию где мы остановились
    return node, pos

А для реализации правила вида
ОПЕРАТОР = ПРИСВАИВАНИЕ | ВЕТВЛЕНИЕ | ЦИКЛ_WHILE
можно будет сделать так:

def parse_operator_node(tokens: List[Token], pos: int) -> TreeNode, int:
    variants = [parse_assignment_node, parse_if_node, parse_while_node]
    for variant in variants:
        try: # пробуем вариант из ветвления
            node, pos = variant(tokens, pos)
        except:
            pass # вариант не подошёл - пробуем другой
        else: # вариант подошёл
            return node, pos
    else: # ни один вариант не подошёл
        raise Exception()

Comments

[Иван Четчасов]

Спасибо, вы мне помогли понять суть. Думаю, теперь я смогу это реализовать.