Изначально, когда я решил написать компилятор за выходные, я решил, что нет смысла заморачиваться, и использовал сторонний лексический / синтаксический анализатор. Мой выбор пал на SLY, довольно известную библиотеку. И действительно, пара часов работы, и мой компилятор прекрасно строил синтаксические деревья из исходного кода на wend. Я пытался было заглянуть под капот, утонул в море технических терминов (LL(1), LR, LALR(1) и тому подобное), и решил, что парсинг своими руками - это не для меня, теория формальных языков меня слабо интересует. Однако же в итоге выяснилось, что базовый синтаксический анализатор - это не так сложно, и я закатал рукава. В основном меня на это мотивировало две вещи:

  • Отсутствие сторонних зависимостей - это здорово!

  • Неприятный синтаксис wend.

Причём второй пункт меня удручал больше всего. Я хотел язык с C-подобным синтаксисом, но так и не смог придумать под него грамматики, которую смог бы разобрать SLY. Вот иллюстрация:

Слева тот синтаксис, который я был вынужден использовать, справа тот, который я хотел. Насколько я понимаю, SLY использует алгоритм для разбора LALR(1) грамматик, а это означает, что парсер должен понимать, какую грамматическую конструкцию разбирает, подглядывая всего лишь на одну лексему вперёд. Это создаёт массу проблем. Представьте, что приходит поток лексем TYPE(int) ID(sqrt) ... - это объявление переменной или объявление функции? Чтобы решить, нам нужна минимум третья лексема. SLY на меня ругался, я раздражался и чесал затылок. Наверное, можно выкрутиться, но мне это было не очень интересно, и я плюнул.

И однажды наткнулся на описание синтаксического анализатора Уорли. И выяснилось, что это очень любопытная штука, крайне примитивная в реализации, если не гнаться за производительностью. А ещё парсер Уорли может разбирать любые контекстно-независимые грамматики, включая неоднозначные.

Ну что, поехали? При синтаксическом анализе нашей задачей является:

  1. распознать, является ли некая последовательность лексем синтаксически корректной, то есть, соответствующей грамматике нашего языка.

  2. при отсутствии синтаксических ошибок построить соответствующее абстрактное синтаксическое дерево.

На втором пункте мы остановимся попозже, для начала сконцентрируемся на первом.

Парсим 1+1 вручную

Пока что абстрагируемся от лексера, и просто вручную поработаем с потоками символов и грамматическими правилами. Допустим, что у нас есть всего два терминальных символа 1 и +. Рассмотрим для начала простейшую грамматику, например, такую:

Тут у меня два нетерминальных символа: s, начальный символ грамматики, и e, нетерминал, обозначающий арифметическое выражение. Эта грамматика может порождать последовательности символов вида 1, 1+1, 1+1+1 и т.д. Обратите внимание, что она неоднозначна: 1+1+1 можно распарсить как (1+1)+1, а можно как 1+(1+1). Обычно неодназначных грамматик пытаются избегать, но я специально выбрал этот пример, чтобы показать, что парсеру Уорли это не помеха.

А теперь представьте себе, что та последовательность, синтаксическую корректность которой нам нужно проверить, прибывает по почте, причём по одному символу в день. Это вполне реалистичная ситуация, когда лексер выдает не сразу массив лексем, а отправляет их по одной.

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

В нашем случае, пока ещё не прибыло ни одного письма, мы можем поставить в очередь задачу, позволяющую получить нетерминал s. Я запишу эту задачу как #0(s->.e, mon). За решёткой у меня стоит номер задачи, потом идёт обрабатываемое грамматическое правило с маркером, показывающим, какой символ правила мы будем сегодня обрабатывать. Ну и в конце идёт метка даты, показывающей, когда мы начали обрабатывать это правило.

При обработке каждой задачи у нас есть только три варианта:

  1. Ожидаемый символ - терминал.

  2. Ожидаемый символ - нетерминал

  3. Ожидаемого символа нет, маркер стоит в конце грамматического правила.

Давайте придумаем по ходу пьесы, что делать в каждом из трёх случаев.

Понедельник, прибывает символ 1

Список задач на начало дня: #0(s->.e, mon)

  1. Берём пока что единственную задачу #0 распознать правило (s->.e, mon). В этой задаче обрабатываемый символ - это нетерминал e. Давайте попробуем предсказать, каким образом мы его можем получить. Смотрим в грамматику, и добавляем в список задач правила, позволяющие получить e: #1(e->.1, mon) и #2(e->.e + e, mon). Закрываем текущую задачу.

  2. Переходим к следующей задаче #1(e->.1, mon). В ней ожидаемый символ (тот, что стоит сразу за маркером) - это терминал, который совпадает с тем, что нам прислали по почте, ура! Следующий символ придёт только во вторник, поэтому ставим в список задач на вторник #3(e->1., пн), обратите внимание, что мы просто передвинули маркер.

  3. Берём задачу #2(e->.e + e, mon). В ней ожидаемый символ - это нетерминал e, но правила, позволяющие его получить, мы уже сегодня в таски закидывали. Посему задачу пропускаем, чтобы не попасть в бесконечный цикл. Задачи на день закончились, идём пить чай.

Список обработанных за день задач: #0(s->.e, mon), #1(e->.1, mon), #2(e->.e + e, mon).

Вторник, прибывает символ +

Список задач на начало дня: #3(e->1., mon)

  1. Берём пока что единственную задачу #3(e->1., mon), в ней маркер стоит в конце задачи, а это значит, что мы дошли до конца грамматического правила нетерминала e. Временная метка задачи - понедельник, поэтому пробегаем по списку задач понедельника, и ищем те задачи, в которых e идёт сразу за маркером, а это задачи #0(e->.e, mon) и #2(e->.e + e, mon). Добавляем в список задач на сегодня #4(s->e., mon) и #5(e->e.+e, mon). Закрываем #3.

  2. Переходим к #4(s->e., mon). В ней снова маркер стоит в конце задачи, а это значит, что мы дошли до конца грамматического правила нетерминала s. В понедельник у нас не было задач, где s был ожидаемым символом, закрываем #4.

  3. Берём #5(e->e.+e, mon). В ней ожидаемый символ - это терминал +, который совпадаем с тем символом, что нам прислали по почте, ура! Следующий символ придёт только среду, поэтому ставим в список задач на среду #6(e->e+.e., пн). Задачи на день закончились, идём пить чай.

Список обработанных за день задач: #3(e->1., mon), #4(e->e., mon), #5(e->e.+ e, mon).

Среда, прибывает символ 1

Список задач на начало дня: #6(e->e+.e, mon)

  1. Берём единственную задачу #6(e->e+.e, mon). Ожидаемый символ - нетерминал e, закидываем в список задач #7(e->.1, wed) и #8(e->.e + e, wed). Обратите внимание, что метка времени - среда, а не понедельник как раньше. Напоминаю, что эта метка не вообще время, когда мы начали работать, а время, когда мы начали обрабатывать конкретное грамматическое правило.

  2. Переходим к #7(e->.1, wed). Ожидаемый символ - терминал 1, который совпадает с тем, что прибыл по почте, ура! Закидываем в список задач на четверг #9(e->1., wed).

  3. Переходим к #8(e->.e + e, wed). Ожидаемый символ - нетерминал e, и соответствующие таски мы сегодня уже добавляли при обработке задачи #6. Посему #8 пропускаем, чтобы не попасть в бесконечный цикл. Задачи на день закончились, идём пить чай.

Список обработанных за день задач: #6(e->e +.e, mon), #7(e->.1, wed), #8(e->.e + e, wed).

Четверг, не прибывает ничего

Список задач на начало дня: #9(e->1., wed).

Почта говорит, что больше писем не будет.

  1. Берём единственную задачу #9(e->1., wed). В ней символов не ожидается, поскольку маркер стоит в самом конце грамматического правила нетерминала e. Пробегаем по списку задач среды, и ищем те задачи, в которых ожидаемым символом является e, это были таски #6(e->e +.e, mon) и #8(e->.e + e, wed). Добавляем в список задач #10(e->e+e., mon) и #11(e->e.+e, wed), закрываем #9.

  2. Берём #10(e->e+e., mon), это опять оконченное грамматическое правило нетерминала e. Пробегаем по таскам понедельника, ищем задачи, где ожидался e. Это #0(s->.e, mon) и #2(e->.e + e, mon). Ставми в очередь #12(s->e., mon) и #13(e->e. + e, mon), закрываем #10.

  3. Берём #11(e->e.+e, wed). В неё ожидаемый символ - это терминал +, а почта нам сказала, что новых символов не будет. Закрываем #11.

  4. Берём #12(s->e., mon), оконченное грамматическое правило для s. В понедельник не было не одной задачи, где бы ожидался s, закрываем #12.

  5. Берём последнюю задачу #13(e->e. + e, mon), в ней опять ожидается терминал, которых больше не будет. закрываем #13.

Список обработанных за день задач: #9(e->1., wed), #10(e->e + e., mon), #11(e->e.+ e, wed), #12(s->e., mon), #13(e->e.+ e, mon).

Пятница, не прибывает ничего

Список задач на начало дня: сегодня ж пятница, какие ещё задачи?!

Убеждаемся, что в списке обработанных за четверг задач у нас есть оконченное правило, соответствующее начальному нетерминалу s, обработка которого началась в понедельник. Такое есть, это #12(s->e., mon). Рапортуем об удаче, идём пить пиво.

Давайте я нарисую график задач:

В нём стрелочками указано, из какой задачи какая получилась. Розовые пунктирные стрелки - это задачи, которые мы не добавили, чтобы избежать бесконечных циклов.

Как я уже говорил, при обработке каждой задачи у нас есть только три варианта:

  1. Ожидаемый символ - терминал. Проверяем ожидаемый символ с тем, что пришёл, если совпадают, добавляем на завтра новую задачу, рисуем зелёную стрелочку.

  2. Ожидаемый символ - нетерминал. Пытаемся предсказать, как этот нетерминал может получиться. Добавляем столько же задач, сколько есть соответствующих грамматических правил, рисуем чёрные стрелочки.

  3. Ожидаемого символа нет, маркер стоит в конце грамматического правила. То есть, мы закончили обработку этого правила, и входная последовательность символов соответствует какому-то нетерминалу. Проверяем историю задач, и открываем новые таски для тех задач, где наш нетерминал был ожидаемым символом. Рисуем голубые стрелочки, они всегда приходят парами: сплошная идёт из текущей обрабатываемой задачи, а пунктирная показывает, в каком правиле мы передвинули маркер.

Обратите внимание, что во всей вышеописанной процедуре сами стрелочки мы нигде не хранили, обходились только списком задач на день без связей между ними. Даже номер задачи мне нигде не нужен, мне хватает только индекса грамматического правила, индекса маркера и временно́й метки.

Формализуем подход и пишем код

Синтаксический анализатор Уорли обрабатывает по одному входному символу за раз. Для каждой входной позиции он строит набор пар . Каждая пара имеет вид . Первая часть элемента - это грамматическое правило . Правило имеет маркер (точку), расположенный в правой части. Эта точка показывает, какая часть этого производящего правила была уже обработана. Вторая часть пары это индекс , количество лексем, прочитанных до начала разбора нетерминала . В коде пару можно представить как класс Task, хранящий три целочисленных индекса.

class Task:
    def __init__(self, rule, dot, start):
        self.rule  = rule  # index of the parse rule in the grammar
        self.dot   = dot   # index of next symbol in the rule (dot position)
        self.start = start # we saw this many tokens when we started the rule

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

    worklists = [ [ Task(0,0,0) ] ]

Тут список worklists будет содержать все наборы . Алгоритм успешно разбирает последовательность из входных лексем , если пара находится в множестве , иначе же рапортует об ошибке.

Сам алгоритм выглядит следующим образом: поочерёдно, для каждого индекса, мы применяем следующие три правила, изменяющие множество , до тех пор, пока ни одно из правил не будет иметь эффекта:

  • СРАВНЕНИЕ. Если множество содержит пару , где совпадает с текущим входным символом , то пара добавляется в . Обратите внимание, что это правило не изменяет сам набор , и это единственное правило, изменяющее .

  • ПРЕДСКАЗАНИЕ. Если множество содержит пару , где - это нетерминальный символ, то для всех правил грамматики вида в добавляется пара . Обратите внимание на смену временно́й метки. Заодно заметим, что шаги предсказания могут вызывать другие шаги предсказания, если начинается с нетерминала.

  • ЗАВЕРШЕНИЕ. Если множество содержит пару с завершенным правилом , то для каждой пары вида в множестве , в добавляется пара .

Сила парсера Уорли заключается в том, что он параллельно обрабатывает несколько предсказаний и даже завершений. Предсказания, которые не оправдались, фактически отмирают, потому что в какой-то момент они приводят к элементам, несовместимым со встреченными входными лексемами.

terminals = ['+', '1']
grammar = [['s', ['e']          ],
           ['e', ['1']          ],
           ['e', ['e', '+', 'e']]]

class Task:
    def __init__(self, rule, dot, start):
        self.rule  = rule  # index of the parse rule in the grammar
        self.dot   = dot   # index of next symbol in the rule (dot position)
        self.start = start # we saw this many tokens when we started the rule

    def next_symbol(self):
        prod = grammar[self.rule][1]
        return prod[self.dot] if self.dot<len(prod) else None

    def __eq__(self, other):
        return self.rule == other.rule and self.dot == other.dot and self.start == other.start

    def __repr__(self):
        prod = grammar[self.rule][1]
        a = ' '.join(prod[:self.dot])
        b = ' '.join(prod[self.dot:])
        week = ['mon', 'tue', 'wed', 'thu', 'fri', 'sat', 'sun']
        return f'({grammar[self.rule][0]}->{a}.{b}, {week[self.start]})'

def recognize(tokens):
    worklists = [ [ Task(0,0,0) ] ]

    def add_task(i, task):
        if len(worklists)==i:
            worklists.append([])
        if task not in worklists[i]:                    # avoid infinite loops, do not add the same task twice
            worklists[i].append(task)

    token_counter = 0
    while True:                                         # fetch tokens one by one until end of file
        token = next(tokens, None)
        if token_counter == len(worklists):             # the worklist is empty => not good
            return False
        i = 0                                           # task id
        while i < len(worklists[token_counter]):        # iterate through all tasks in current worklist
            task  = worklists[token_counter][i]
            next_symbol = task.next_symbol()            # next symbol in the production rule
            if next_symbol is None:                     # if no symbol: completed task
                for prev in worklists[task.start]:
                    if prev.next_symbol() == grammar[task.rule][0]:
                        add_task(token_counter, Task(prev.rule, prev.dot+1, prev.start))
            elif next_symbol in terminals:              # if next symbol is a terminal,
                if token and next_symbol == token:      # scan a token
                    add_task(token_counter+1, Task(task.rule, task.dot+1, task.start))
            else:                                       # if next symbol is nonterminal, emit a prediction task
                for idx, (lhs, rhs) in enumerate(grammar):
                    if lhs == next_symbol:
                        add_task(token_counter, Task(idx, 0, token_counter))
            i += 1
        token_counter += 1
        if not token: break                             # end of file
    cur = [ task for task in worklists[-1] if task == Task(0, len(grammar[0][1]), 0) ] # all completed tasks at the end of the parse
    print(worklists)
    return bool(cur)

print(recognize(iter(['1',
                      '+',
                      '1'
                     ])))

При запуске этого кода мы увидим рапорт об успешном распознавании последовательности 1+1, а заодно вот такой список обработанных за неделю задач.
Сравните его с нарисованным выше графиком, они должны совпадать.

[[(s->.e, mon), (e->.1, mon), (e->.e + e, mon)],
 [(e->1., mon), (s->e., mon), (e->e.+ e, mon)],
 [(e->e +.e, mon), (e->.1, wed), (e->.e + e, wed)],
 [(e->1., wed), (e->e + e., mon), (e->e.+ e, wed), (s->e., mon), (e->e.+ e, mon)]]

Вышеприведённый код даёт лишь бинарный ответ, соответствует ли входная последовательность лексем заданной грамматике. Как же построить синтаксическое дерево? У нас при разборе получился граф (на моём рисунке он соответствует стрелкам, нарисованным сплошными линиями). Достаточно лишь проследить путь от начального узла до конечного, причём нас интересуют только сплошные голубые стрелки. В данном примере их три, поэтому синтаксическое дерево будет состоять из трёх узлов, корня + и двух ветвей 1 и 1.

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

Код можно посмотреть в репозитории.

Послесловие

При тщательной реализации синтаксический анализатор Уорли работают за наихудшее время , для однозначных грамматик он может работать за . На LL и LR-грамматиках парсер Уорли вовсе может работать за линейное время. Джон Айкок и Найджел Хорспул в своей статье [Practical Earley Parsing] пишут, что умудрились добиться от техник Уорли производительноси всего на 50% худшей, нежели у LALR парсера Bison, что крайне впечатляет, учитывая, как расширяются возможности. В моём компиляторе я заметил ухудшение производительности при уходе со SLY на мой собственный парсер, но время компиляции всё равно остаётся приемлемым.

Последнее, что стоит упомянуть при смене парсера, так это приоритет операций. Когда я использовал SLY, то в грамматике в одну кучу закинул всю арифметику, и просто сказал библиотеке самой разобраться с приоритетом:

precedence = ( # arithmetic operators take precedence over logical operators
     ('left', PLUS, MINUS),
     ('left', TIMES, DIVIDE, MOD),
     ('right', UMINUS), # unary operators
     ('right', UPLUS)
)

[...]

@_('expr PLUS expr',
   'expr MINUS expr',
   'expr TIMES expr',
   'expr DIVIDE expr',
   'expr MOD expr')
def expr(self, p):
    return ArithOp(p[1], p.expr0, p.expr1, {'lineno':p.lineno})

Тут такой фокус не пройдёт, но это совершенно не страшно. Весь приоритет операций можно запихнуть на уровень самой грамматики. Вот пример однозначной грамматики, корректно реализующей приоритет арифметических операций:

terminals = ['MINUS', 'PLUS', 'TIMES', 'DIVIDE', 'INTEGER', 'LPAREN', 'RPAREN']
grammar = [['expression',   ['addend']                         ],
           ['addend',       ['term']                           ],
           ['addend',       ['addend', 'MINUS', 'term']        ],
           ['addend',       ['addend', 'PLUS', 'term']         ],
           ['term',         ['factor']                         ],
           ['term',         ['term', 'TIMES', 'factor']        ],
           ['term',         ['term', 'DIVIDE', 'factor']       ],
           ['factor',       ['atom']                           ],
           ['factor',       ['PLUS', 'atom']                   ],
           ['factor',       ['MINUS', 'atom']                  ],
           ['atom',         ['INTEGER']                        ],
           ['atom',         ['LPAREN', 'expression', 'RPAREN'] ]]