Компиляция. 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·2564 элементов, а это десятки гигабайт.
    Поэтому применимость 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, в которых локализация ошибки реализована именно так.

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

    Комментарии 26

      0
      Многие писали ЛР на эту тему в своих ВУЗах. Я на этом собачатинки тоже отведал. Когда-то дела «рекурсивный спуск» на С++, ох как же это давно было…
        0
        >По поводу удобства: в основном, каждый хвалит тот инструмент, к которому привык, и питает неприязнь к непривычному.
        >Например, процитирую один «лучший ответ» со 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.

        Вот не разделяю вашей иронии тут. Вменяемые сообщения об ошибках — это действительно очень важное качество результирующего продукта. И LR()/LALR тут реально проигрывает.
          0
          Лолвут?
          These are errors that Bison catches when generating the parser, so it doesn't effect the end-user experience

          Вменяемые сообщения об ошибках разбора у бизона есть: habrahabr.ru/blogs/programming/99397/#comment_3073829
            0
            Это вы про «Один раз делаю дифф, и накладываю его на сгенерированный парсер сразу после генерации, той же строчкой в мейкфайле.»? :-)

            по поводу error-verbose — это фича исключительно бизона. Скажем byacc не имеет ее. И кстати, насколько я помню — этот error-verbose в старых бизонах тоже отсутствует. ДЛя линукса это не очень важно, а на юниксах можно любую версию yacc встретить

              0
              Я не понимаю вашей логики. LR реально проигрывает потому, что когда-то в бизоне не было этой фичи?

              Встретить antlr на юниксах, мне кажется, сложнее, чем современого бизона. (Или какую замену вы предлагаете?)
                0
                логика в том, что: допиливать сообщения об ошибках приходится в любом случае. В случае с LR грамматиками гемороя больше. Эмпирически так сказать установленный факт.

                что касается antlr — он может жить везде где живет ява, это же просто jar. но я кстати им не ползуюсь практически.

                По поводу замены — В большинстве случаев я использую LL(сколько получится), рисую синтаксические диаграммы вирта, и по ним уже пишу парсер. «Функция на правило», пишется быстро, с такой скоростью, с какой вообще можно писать. И естественно с любой обработкой ошибок там замечательно.

                Есть пара мелких старых проектов где использовал продукционные правила флойда для парсера.

                Это я к тому что выбор далеко не ограничивается bison, i.e. LALR() против antlr ie LL()

                  0
                  Что касается бизона — он может жить везде, где есть компилятор Си, это же просто программа на Си :)

                  Не пытаюсь свести выбор к «bison vs. antlr»: просто именно таков был спор на stackoverflow, из которого вы неожиданно заключили об отсутствии в бизоне вменяемых сообщений об ошибках.
                    +1
                    Вы невнимательно читали — не только в бизоне. В LR/LALR распознавалках.

                    Из за их природы. Потому что они принимают решение по _правому_ символу в нетерминале. А человеку надо в сообщение левый символ, с которым проблема.

                    >Что касается бизона — он может жить везде, где есть компилятор Си, это же просто программа на Си :)

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

          Основным критерием является производительность труда программиста. «Качество собственно парсинга», если имеется ввиду производительность, при этом должно быть на приемлемом уровне, не более того.

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

          В ANTLR есть возможность изменять глубину заглядывания вперед локально. То есть, для «почти» LL(1) грамматики можно построить парсер, который будет вести себя как LL(1), а в особо сложном месте заглянет вперед на нужное количество лексем (возможно, бесконечное). Это называется guessing mode: парсеру говорят, если вход от текущего места разберется как вот эта конструкция, то выбирай эту альтернативу, иначе — другую.
          И нет там никаких глобальных таблиц перехода.

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

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


            0
            И нет там никаких глобальных таблиц перехода.

            Ниже в тексте объясняю, что он рекурсивный.

            Но всегда правильнее преобразовать грамматику

            Не вижу преобразования?
              0
              Рука опять дернулась, переписанная грамматика в следующем комментарии, с ()?

              От левой рекурсии в большинстве случаев довольно легко избавиться.
              0
              «Качество собственно парсинга», если имеется ввиду производительность

              Речь шла о качествах, а не об абстрактном всеобъемлющем качестве.
              Наверное, лучше было написать «характеристики собственно парсинга».

              Имеел в виду: набор поддерживаемых грамматик (леворекурсивные не годятся), возможность изменять действия при разборе (например, структуру генерируемого дерева), и т.п.

              В конечном счёте, эти характеристики влияют именно на объём труда для программиста.

              -

              Повторюсь: каждый программист эффективнее работает с тем, с чем привык. Для одних это бизон, для других antlr, и в этом нет ничего удивительного.
                0
                >«Качество собственно парсинга», если имеется ввиду производительность, при этом должно быть на приемлемом уровне, не более того.

                it depends. Например для sql выражений скорость разбора — очень важна.
                  +1
                  Значит, приемлемый уровень в данном случае высок. Но с какого-то момента скорость разбора перестанет играть существенную роль, узкие места будут в другом. Из технологий, которые обеспечат такую скорость разбора, надо выбирать такую, которая минимизирует затраты на разработку (надо рассматривать весь жизненный цикл).
                    0
                    да, согласен, кроме того, скорость нисходящих парсеров совсем не маленькая.
                  0
                  Я бы просто написал так:

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


                  но можно и так:

                  OP: '{' OPS '}' // блок
                      | EXPR ';'  // выражение
                        // вроде, можно не дублировать, но не помню синтаксис
                      | ( 'if' '(' EXPR ')' OP 'else' OP )=> 'if' '(' EXPR ')' OP 'else' OP
                      | 'if' '(' EXPR ')' OP
                      | 'while' '(' EXPR ')' OP
                      | 'exit' ';' ;
                  


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

                  Зачем нам куча дополнительных нетерминалов, когда есть extended bnf?
                  EXPR: NUM ( OP NUM )*;

                  невозможность написания «заплаток» на сгенерированный код, потому что он меняется при изменении грамматики, да ещё и размножается по десяткам функций.

                  Это одно из самых страшных зол, которые только бывают. Сгенерированный код не должен залатываться! Вместо этого DSL должен допускать вставку кода, которая попадет в нужное место сгенерированного кода.
                    0
                    Это одно из самых страшных зол, которые только бывают. Сгенерированный код не должен залатываться!

                    Имхо, зависит от назначения и от времени жизни кода.

                    -

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

                      Свой первый транслятор я писал, чтобы уйти от регулярного исправления сгенерированного кода в больших объемах :)
                        0
                        Совершенно не гур и не гурий имел в виду: например, для экспериментального прототипа твикабельность ценнее удобства сопровождения, разве нет?
                          0
                          Для экспериментального проекта важнее всего низкие трудозатраты на эксперимент. Эксперимент — это результат любым способом, в том числе и правкой сгенерированного кода. А удобство сопровождения — это, в числе прочего, низкие трудозатраты на внесение изменений правильным способом, который не ломает технологию и не снижает качество кода. Так что да, твикабельность ценее. Но эксперименты реализуются не правкой сгенерированного кода, а правкой исходного.
                      0
                            // вроде, можно не дублировать, но не помню синтаксис
                          | ( 'if' '(' EXPR ')' OP 'else' OP )=> 'if' '(' EXPR ')' OP 'else' OP
                          | 'if' '(' EXPR ')' OP
                      


                      не.

                      Вот так:

                      'if' '(' expr ')' op ( ('else') => 'else' op)?


                      то есть когда распознали then оператор, глянули на один символ вперед. Если он 'else', то продолжаем разбор. Никакое дублирование тут не нужно.
                    +1
                    Получил по почте комментарий от незарегистрированного на Хабре читателя:
                    Логично в качестве позиции ошибки показывать самую правую, до которой сумела добраться хотя бы одна развёртка, — т.е. последнюю позицию, до которой у парсера ещё были надежды, что текст распарсится удачно.
                    Предполагаю, что есть реализации packrat, в которых локализация ошибки реализована именно так.
                    Вообще-то да, есть. Например вот тут: www.meta-alternative.net/mbase.html

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

                    Так же, преимущество packrat перед автоматным LL — возможноть реализации левой рекурии в лоб.

                    Ну и важнейшее свойство packrat — он lexerless во первых, и расширяемый во вторых. Можно наследовать свойства грамматик, можно расширять грамматики динамически.

                    Всё это многократно перевешивает мизерные и неинтересные пролемы с большим линейным коэффициентом (есть куча оптимизаций, сокращающих его до минимума) и расходом памяти — на самом деле не так уж и много ее надо — для языков вроде C++ надо помнить не больше чем один top level declaration, а они обычно коротенькие.

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

                    Так что не надо так людей packrat-ом запугивать. У packrat и GLR большое будущее, а автоматам пришел заслуженный конец.

                    Вам я написал, потому как когда-то у меня была точно такая же позиция (в MBase это легко прослеживается по предыдущей версии автоматного LL-генератора), и у меня был весьма прочищающий мозги разговор с автором языка Kathadin. Мне тогда это пошло на пользу. Возможно, и вам пригодится знание о том, на что способен packrat.

                    P.S.:
                    Тем более, что одно из самых естественных применений для новых компиляторов — поддержка всяких компактных платформ, где сэкономленная память имеет значение.
                    Делаем сейчас компактный драйвер для встраиваемых устройств, на основе Clang + LLVM. Там, соответственно, банальный hard-coded recursive descent parser. Clang, как известно, рвет по скорости парсинга всех прочих в хвост и в гриву (хоть он и «ленивый слон»). Так вот, я жалею, что это не Packrat. Для такого типа грамматики мемоизацию можно или отключить или ограничить, а преимуществ было бы немало.
                      +1
                      одно из самых естественных применений для новых компиляторов — поддержка всяких компактных платформ, где сэкономленная память имеет значение

                      Не могу согласиться. Обычно используется кросс-компиляция.

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

                      На первый взгляд да, на практике бывают ситуации, когда ошибочный текст действительно оказывается [почти] правильной, но совсем не той конструкцией.
                      Я бы несколько вариантов ошибки попробовал показать. Типа, если вы хотели написать объявление функции, то вот тут ошибка, а если объявление массива — то тут.

                      Иногда делают так: собирают информацию о типичных ошибках. Расширяют язык так, чтобы типично ошибочные конструкции вошли в язык. Сообщение об ошибке становится действием, которое долно выполняться при распознавании этих конструкций. Эвристика, но качество может приподнять.

                      Рассказывали байку, кажется про DECовский С++ компилятор, который умел компенсировать пропущенные (или лишние?) разделители. Первое сообщение — тут у вас точки с запятой не хватает, не волнуйтесь, я ее сама вставлю. Второе — а чего это у вас тут точка с запятой лишняя? Позиция та же. :)

                      Кстати, вот что я всё хочу добавить, но забываю. Классические компиляторы уже не обеспечивают достаточное количество возможностей. При проектировании «инструмента обработки формального текста» надо учитывать потребности IDE. Иначе придется отдельно реализовывать автопродолжение, outline и прочие стандартные средства. А для IDE надо уметь частично разбирать некорректные программы, извлекая из них максимум возможной информации. К примеру, компилятор, закончив синтаксический разбор, уже не имеет права останавливаться, если были ошибки — всё равно надо пытаться выделить декларации верхнего уровня и т.п.
                      0
                      Отличные материалы! Спасибо.

                      Мне кажется, что в этой заметке уместно было упомянуть S-грамматику. Это LL без альтернатив: первый токен в правой части правил всегда терминальный и однозначно идентифицирует правило.
                        0
                        А они встречаются в жизни? :)
                          0
                          Всё в наших руках :-) Я их иногда использую. Бывает удобно для конфигов.

                          Кроме того, я, навскидку, не вижу, в каком месте языки типа LISP, Tcl, и многих диалектов ассемблера выпадают из S-парадигмы.

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

                      Самое читаемое