Компиляция. 5: нисходящий разбор

До сих пор занимались восходящим синтаксическим разбором. Какие ещё есть варианты?
Отложим бизона в сторону, и вернёмся к теории.

Далее в посте:

1. Идея
2. Воплощение
3. Холивар
4. Бэктрекинг

Идея

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

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

OP: '{' OPS '}' // блок
    | EXPR ';'  // выражение
    | 'if' '(' EXPR ')' OP
    | 'if' '(' EXPR ')' OP 'else' OP
    | 'while' '(' EXPR ')' OP
    | 'exit' ';' ;

и мы видим, что дальше в тексте идёт while, тогда разворачивать будем по правилу OP: 'while' '(' EXPR ')' OP ;

Для магазинного автомата такой парсинг можно реализовать следующим образом:

• Во время развёртки, записываем в стек правую часть правила: продолжение текста будем разбирать в соответствии с ней.
• Если наверху стека терминал, и во входном тексте такой же терминал, значит, текст соответствует ожидаемому. Удаляем верхний терминал из стека, читаем следующий символ текста.
• Если наверху стека нетерминал, значит его надо развернуть. Правило для развёртки выбираем на основании входного символа.

Сразу же обратим внимание, что действие при развёртке выполнять бессмысленно: правая часть развёрнутого правила ещё не прочитана, и неизвестно, будет ли прочитана вообще. Можно было бы при развёртке класть в стек под символы правой части пустышку-сигнал «правило успешно прочитано, можно выполнять действие»; но к этому моменту вся правая часть уже стёрта из стека! С чем же действие будет работать?

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

WORD: S1 'a' 'i' 'l' | S2 'a' 'l' 'e' ;
S1: 's' ;
S2: 's' ;

Как нам разворачивать WORD, когда следующий символ 's'?
Непонятно, как выбирать: оба правила для WORD начинаются именно на 's'.

Воплощение

Можно разрешить автомату заглядывать вперёд дальше, чем на один символ: этот подход, судя по отзывам, применили в ANTLR, популярном генераторе LL-парсеров.
Техническая сложность в том, что каждый новый символ, от которого зависит выполнение развёртки, увеличивает размерность таблиц перехода; так что несжатые таблицы для автомата из N состояний, читающего 3 символа из текста (плюс к символу из стека), содержали бы N·256⁴ элементов, а это десятки гигабайт.
Поэтому применимость LL-парсинга с далёким заглядыванием вперёд определяется именно способностью генератора парсеров эффективно сжимать таблицы (вспомним, как бизон сжал нам таблицу 258х14 в семь коротких одномерных массивов).

LR-парсеры с далёким заглядыванием вперёд, насколько я понимаю, не делают — потому, что и так всех всё устраивает: конфликты, вызванные недостаточно далёким заглядыванием, в LR-парсерах редки. Чтобы нашу грамматику мог разпознавать бизон, достаточно не просить его выбрать между двумя одинаковыми свёртками:

WORD: 's' 'a' 'i' 'l' | 's' 'a' 'l' 'e' ;

С другой стороны, для LL-парсера ничего не изменилось: по-прежнему оба правила соответствуют символу 's'. Поэтому, чтобы «адаптировать» грамматику для LL-разбора, общее начало разных правил для одного и того же нетерминала выносят во «вспомогательный нетерминал»:

WORD1: 's' 'a' WORD ;
WORD: 'i' 'l' | 'l' 'e' ;

Этот трюк называется «левая факторизация»: из одинаково начинающихся правил как будто бы выносится «общий множитель».
Теперь развёртка WORD1 однозначная, а две возможные развёртки для WORD начинаются на разные буквы.

Зачем заморачиваться с факторизацией и плодить в грамматике бессмысленные нетерминалы, если чудо-сжиматель ANTLR способен заглядывать сколько захочет вперёд?
Вернёмся к грамматике

OP: '{' OPS '}' // блок
    | EXPR ';'  // выражение
    | 'if' '(' EXPR ')' OP
    | 'if' '(' EXPR ')' OP 'else' OP
    | 'while' '(' EXPR ')' OP
    | 'exit' ';' ;

Как разворачивать OP, когда следующий символ if? Есть два правила, которые могут так начинаться; и их общая часть — 'if' '(' EXPR ')' OP — может быть произвольной длины, так что как далеко бы парсер ни заглядывал вперёд, это его не спасёт.

Другая проблема, с которой LL не может справиться, — левая рекурсия. Помним грамматику калькулятора торговок с рынка:

EXPR: NUM | EXPR OP NUM ;

Оба правила для EXPR начинаются на NUM: первое явно, второе неявно; при этом нет общего «фактора», который можно было бы вынести из правил наружу. Если предположим ещё, что длина NUM не ограничена, — понятно, что никакое заглядывание вперёд проблему не решит.

Чтобы починить грамматику, отталкиваемся от её смысла: первый NUM в строке — готовое выражение, а все остальные выражения содержат по два операнда.

EXPR: NUM EXPR1 ;
EXPR1: | OP NUM EXPR1 ;

Левой факторизацией и устранением левой рекурсии можно любую однозначную грамматику приспособить для LL-парсинга, ценой добавления уймы вспомогательных нетерминалов, совершенно бессмысленных.
Например, в свёртке правила EXPR: EXPR OP NUM ; мы запросто строили узел синтаксического дерева: левый аргумент — вот он, в $1; правый аргумент — вот он, в $3. А что можно сделать при развёртке EXPR1: OP NUM EXPR1 ;? Левый аргумент уже развёрнут и стёрт из стека; зато у нас в руках есть EXPR1 — под-выражение после правого аргумента. Будто бы в нём какой-то прок!

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

С одной стороны, приведение грамматики к LL-виду совершенно формально, и его можно поручить бездушной железяке. С другой стороны, как отлаживать автомат, который работает не по заданной грамматике, а по какой-то своей?
В частности, нам не дадут писать действия для развёрток, потому что развёртываться всё равно будут не те правила, которые задали мы, — а какие-то другие, которые железяка задала себе сама. Хорошо ещё, если такой парсер сумеет сгенерировать заданное дерево разбора; для этого ему придётся соотносить правила заданной грамматики с теми правилами, по которым фактически работает автомат, и перестраивать дерево, «возвращая на место» узлы, переехавшие из одного правила в другое.

Холивар

Спор о преимуществах LL vs. LR так же стар, как автоматический синтаксический разбор вообще; у обоих подходов свои сторонники. Например, глубоко уважаемый лично мной Никлаус Вирт был активным апологетом LL-разбора, и одним из design goals при разработке Паскаля была возможность LL(1)-разбора — т.е. автоматом, который видит только один следующий символ текста. Большинство «живых языков» в LL не укладываются: например, в Си на int может начинаться объявление либо переменной, либо функции, и мы не может отличить одно от другого, пока не дочитаем строку до конца.

По поводу удобства: в основном, каждый хвалит тот инструмент, к которому привык, и питает неприязнь к непривычному.
Например, процитирую один «лучший ответ» со stackoverflow, касательно спора «ANTLR vs. bison»:

In terms of personal taste, I think that LALR grammars are a lot easier to construct and debug. The downside is you have to deal with somewhat cryptic errors like shift-reduce and (the dreaded) reduce-reduce. These are errors that Bison catches when generating the parser, so it doesn't effect the end-user experience, but it can make the development process a bit more interesting.

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

Удобочитабельный генерируемый код — это самое сильное отличие ANTLR от табличных парсеров. Фактически, вместо специализированного стека разбора используется стек вызовов, и распознавание каждого правила грамматики реализуется как вызов функции (для рекурсивного правила — рекурсивная функция). Поэтому при отладке из стека вызовов непосредственно видно, как парсер попал в текущее состояние; тогда как с бизоном, как мы помним, приходится включать отладочную печать переходов между состояниями, и сверяться с распечаткой автомата, чтобы понять причину переходов.
Недостатки рекурсивной реализации перед табличной также ясны: куда больший объём кода, а значит потребление памяти; невозможность написания «заплаток» на сгенерированный код, потому что он меняется при изменении грамматики, да ещё и размножается по десяткам функций.

Бэктрекинг

LL-парсеры, предопределённым образом выбирающие правило для каждой развёртки, — не единственный вариант нисходящего синтаксического разбора. Альтернативная идея: когда есть несколько подходящих правил, попробуем все, какое-нибудь да подойдёт. Например, можно сделать нечто навроде fork(): создать клоны парсера в текущем состоянии, и каждый клон пусть пробует по одному из вариантов развёртки. Если клон натыкается на ошибку синтаксиса, он умирает. Если все клоны умерли, значит ни один вариант развёртки не подходит: во входном тексте синтаксическая ошибка.

Для правильных текстов этот подход более-менее приемлим; но с обнаружением ошибок возникают проблемы. Во-первых, которую из обнаруженных ошибок печатать? Большинство их — результат неверно выбранной развёртки, а не ошибки в тексте программы; но с точки зрения парсера, все совершенно равноправны.

Во-вторых, разбор может никогда не закончиться: каждый раз, когда делаем развёртку по леворекурсивному правилу, один из клонов будет точно в том же состоянии, как до развёртки; так что на каждом шаге будет получаться ещё один точно такой же клон, и так до бесконечности. Если один из клонов доберётся-таки до конца разбора, тогда всех остальных можно будет убить; а если, наоборот, все остальные клоны напорются на ошибки синтаксиса и умрут, и продолжать жить будет только бесполезно плодящийся клон?

Наконец, что делать с неоднозначными грамматиками? И LL-, и LR-парсеры обнаружат конфликты во время компиляции; здесь же компиляции, как таковой, нет: парсер руководствуется грамматикой практически в сыром виде, т.е. интерпретирует её на ходу.
Значит, может получиться, что для одного и того же текста будем получать то один разбор, то другой: смотря который клон раньше успеет закончить разбор.

Последнюю проблему решили наиболее оригинально: объявили, что возможность неоднозначного разбора — фундаментальная проблема грамматик, и вместо них нужно использовать парсящие выражения, которые отличаются по сути лишь тем, что между правилами развёртки задан строгий приоритет. Например, если грамматики
OP: EXPR ';' | 'if' '(' EXPR ')' OP | 'if' '(' EXPR ')' OP 'else' OP ;
и
OP: EXPR ';' | 'if' '(' EXPR ')' OP 'else' OP | 'if' '(' EXPR ')' OP ;
— это одна и та же самая неоднозначная грамматика, то парсящее выражение
OP: EXPR ';' / 'if' '(' EXPR ')' OP 'else' OP / 'if' '(' EXPR ')' OP
однозначно указывает парсеру «сначала попробуй распознать if..else, и только если не удастся, распознавай if-без-else». А выражение
OP: EXPR ';' / 'if' '(' EXPR ')' OP / 'if' '(' EXPR ')' OP 'else' OP
означает «сначала распознавай if-без-else», и поэтому else им вообще никогда не будет распознан.

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

Вы когда-нибудь ездили на ленивом слоне? Он идет медленно и сильно раскачивается. И не идет по дороге, а блуждает во всех направлениях, которые сочтет интересными, но если они не совпадают с нужным, то погонщик слону говорит «не, нам не сюда». Так, перепробовав все варианты, слон оказывается в той точке, про которую не сказали «не сюда». Вот и парсер-комбинаторы так же, перепробуют все комбинации вариантов, пока какой-нибудь один из них не сработает. И после каждого отката начинают заново делать одну и ту же работу. <...> Программа в пару строчек разбиралась быстро. В три строчки уже несколько секунд. Пять строчек я не дождался. Запомните, дети, такие парсер-комбинаторы годятся только для очень простых грамматик.

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

С зацикливанием проще: если мы дважды оказались в одном состоянии, не продвинувшись по входному тексту, — значит, окажемся в нём и в третий раз, и сколько угодно. Выходит, нужно для каждой позиции во входном тексте хранить список всех состояний, в которых в этой позиции уже побывали: если второй раз приходим в то же состояние, говорим, «не, хватит, больше туда не пойду».

В качестве бесплатного бонуса получаем «линейное» время работы, если запоминать будем не просто галочку «ага, тут были», а ещё и результат прошлого разбора (развёртка подошла / не подошла); тогда самый худший вариант по времени работы — если в каждой позиции текста побываем во всех возможных состояниях. Если текст длиной N символов, и в грамматике парсящем выражении M правил (включая альтернативные варианты развёртки каждого нетерминала) — то получаем время работы O(M*N). Если хитро прищуриться и сделать вид, что M константа — ага, время линейное. Для сравнения, у традиционных LL- и LR-парсеров с предопределённым действием в каждом состоянии точно так же в худшем случае O(M*N):

S: | T1 S ;
T1: T2 ;
T2: T3 ;
...
TM: 't' ;

Здесь LR будет после каждого сдвига 't' выполнять M свёрток 't' -> TM -> ... -> T3 -> T2 -> T1; а LL, перед «съедением» каждого 't', делает M развёрток T1 -> T2 -> T3 -> ... -> TM -> 't'.
Весь вопрос в том, насколько отличается средний случай от худшего: как минимум, «линейный слон» при любом разборе выполняет больше развёрток, чем LL на такой же грамматике.

Другой подвох в расходе памяти. Нам потребуется хранить M*N результатов прошлых развёрток — и это впридачу к тому, что входной текст придётся хранить в памяти весь целиком, потому что слону нужно без конца бегать по нему взад и вперёд. Это при том, что магазинно-автоматные парсеры к уже прочитанному тексту никогда не возвращаются, и поэтому их требования к памяти зависят только от грамматики, но не от текста.
«Историю одного байта» читали все? Тем более, что одно из самых естественных применений для новых компиляторов — поддержка всяких компактных платформ, где сэкономленная память имеет значение.

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

DECL: DECLVAR / DECLFN ;
DECLVAR: TYPE ID ';' ;
DECLFN: TYPE ID '(' ARGS ')' ;

— отдалённо напоминающее синтаксис объявлений в Си.
Если во входном тексте встретили последовательность, которую можно разобрать как TYPE ID '!', то в какой позиции ошибка синтаксиса? Packrat проверит первую развёртку, она не подойдёт, парсер откатывается к началу TYPE и пробует вторую развёртку; она тоже не подходит. Получается, ошибка будет обнаружена перед TYPE; а что, если TYPE — хардкорное выражение на полстроки?
Логично в качестве позиции ошибки показывать самую правую, до которой сумела добраться хотя бы одна развёртка, — т.е. последнюю позицию, до которой у парсера ещё были надежды, что текст распарсится удачно.
Предполагаю, что есть реализации packrat, в которых локализация ошибки реализована именно так.

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