Написание компилятора LALR(1)-парсеров. Базовая теория

    Введение, или зачем нужны синтаксические анализаторы


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

    Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

    Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

    Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.


    Два вида парсеров


    Ок, после осознания важности данной технологии, необходимо поднять вопрос о стандартах написания данного класса программ.

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

    Первый подход означает разделение анализатора на две части — описание формата/схемы входной информации и логики, которая оперирует уже не чистым потоком данных, а структурированным в соответствии со схемой. Пример:
    scheme:
        DIGIT = '0'..'9'
        ADD = DIGIT '+' DIGIT
        SIGN = ('+' | '-') DIGIT
        EXPR = ADD | SIGN
    
    code:
        long result = 0;
    
        ParseNode & expr = Parse(input);
        ParseNode & oper = expr.child()
        switch (oper.type)
        {
        // 0: DIGIT, 1: '+', 2: DIGIT
        case ADD:
            result = oper.child(0) + oper.child(2);
            break;
        // 0: '+' or '-', 1: DIGIT
        case SIGN:
            result = oper.child(0) == '-' ? - oper.child(1) : oper.child(1);
            break;
        }
    


    Второй подход проще показать, чем объяснить:
        char c = '';
        long result = 0;
    
        input >> c;
        // we have three variants of first symbol
        switch (c)
        {
        case '+':
            // next symbol is digit
            input >> c;
            if (c < '0' || c > '9')
                return SyntaxError;
            result = c - '0';
            break;
        case '-':
            // next symbol is digit
            input >> c;
            if (c < '0' || c > '9')
                return SyntaxError;
            result = c - '0';
            break;
        default:
            if (c < '0' || c > '9')
                return SyntaxError;
            result = c - '0';
            input >> c;
            if (c != '+')
                return SyntaxError;
            input >> c;
            if (c < '0' || c > '9')
                return SyntaxError;
            result += (c - '0');
            break;
        }
    


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

    Преимущества описания грамматики:
    1. Прежде всего, это легкая поддержка языка. То есть модификации, даже самые кардинальные, накладываются очень просто.
    2. Так как синтаксические конструкции собраны в одном месте и компактно, то очень просто обозреть структуру языка в целом. В альтернативе можно просто-напросто погрязнуть среди тысяч и десятков тысяч строк вперемешку с логикой. Кроме того обеспечивается прозрачность языка, очевидно прослеживается эволюция конструкций. То есть в нашем примере видно как DIGIT превращается в ADD, а затем в EXPR, собственно позволяя наметить точки для внедрения семантической логики.
    3. Легкое отслеживание ошибок. Причём сразу двух категорий — синтаксических ошибок входных данных и ошибок составления самого кода. При ручном написании, код может содержать противоречивости, мертвые участки, и прочие логические радости и при этом компилироваться. С заданной схемой такое невозможно. Противоречия выявляются сразу на этапе генерации.
    4. Введение дополнительной абстракции упрощает исходный код и позволяет отлаживать и тестировать более высокоуровневые сущности, которые по определению являются менее многочисленными и более конкретными чем простой поток символов.


    Несмотря на всё это, и у программирования «наживую» есть ряд своих плюсов:
    1. Порог входа значительно ниже. То есть практически любому программисту можно сказать — «сиди пиши код», и парсер будет запрограммирован в предложенном стиле. Для составления формальной грамматики нужно обладать пусть и небольшим, но всё же важным, объёмом теории — азы математической логики, разбираться в построении грамматики, владеть инструментом генерации кода.
    2. Несмотря на то, что грамматикой можно описать практически всё, есть и исключения. Кроме того к ним добавляется ограниченность инструментария. Прямое написания кода обладает наивысшей гибкостью.
    3. Есть еще совсем крохотный плюс — всё в одном месте. То есть при нормальной организации программы, можно выделять ключевые фрагменты логики и сразу понимать их суть. В первом варианте у нас фактически два нужных экрана — экран схемы + экран кода. Иногда нужно переключаться между ними для уточнения нюансов. Это не совсем удобно. Но повторюсь, это крайне небольшое преимущество, особенно если учесть второй плюс раздельного кодирования.


    Структура парсера


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



    Это весьма условная схема, анализатор может состоять из всех трех частей, или иметь объединение первых или последних двух, и даже быть цельным куском без разделения на компоненты. Здесь уже почти нет best practises в организации. Но лично я предпочитаю отделять мух от котлет. Не буду разводить холивар, а просто опишу возможные варианты.

    Прежде всего стоит разобраться, что же это за составляющие. Лексический анализатор получает на вход поток символов заданного алфавита (буквы, цифры, используемые символы, etc). Дальше он разбивает этот поток на более комплексные примитивы (такой вот оксюморон, да), так называемые токены или терминалы. К примеру вместо последовательности цифр какой-то длины синтаксический анализатор получает «Число» с атрибутом равным значению этого числа. Зачем он нужен объясню ниже. Дальше синтаксический анализатор на основе токенов и правил составления символов второго иерархического порядка (первый — токены), так называемых нетерминалов, собирает дерево вывода. Данная АТД однозначно представляет структуру распознанных данных. И наконец, последний этап — это семантический анализ полученного дерева и выполнение бизнес-логики. Как раз этот этап представлен на первом листинге.

    Зачем же нужен лексический анализатор, если он фактически может быть интегрирован в синтаксическую часть? Ведь какая разница какой алфавит получать — исходный или новый синтетический. Ответ достаточно очевиден — во-первых, это как правило сужение алфавита, то есть упрощение семантики; во-вторых, мы убираем один или даже несколько нижних уровней дерева при полном сохранении его свойств. Понятное дело что лексический анализатор не должен брать на себя роль синтаксического, а тем более семантического, поэтому на «1+2» он не должен возвращать 3, но простейшие действия, такие как формирование чисел вполне подходит. Немного усложним пример, и посмотрим на дерево вывода в двух случаях. Заодно и покажу что это за дерево такое тем, кто не совсем понял краткого объяснения.
        DIGIT = '0'..'9'
        NUMBER = NUMBER? DIGIT
        ADD = NUMBER '+' NUMBER
        SIGN = ('+' | '-') NUMBER
        EXPR = ADD | SIGN
    


    Разбор идёт выражения 12+34


    Даже на таком простом примере видно что удобнее разделять анализ как минимум на 2 этапа. Кроме того специализация лексического анализатора позволяет использовать более эффективные, отличные от разбора грамматик, алгоритмы. Основное различие, кроме вышепредставленного эмпирического, лексера от синтаксического анализатора — это отсутствие правил вывода, точнее их неявно можно представить, но справа будут стоять только знаки алфавита, и в правилах никогда нет связи с остальными нетерминалами лексера. То есть они самодостаточны и описывают только ожидаемый поток символов.

    Теперь рассмотрим второй потенциальный сплав. Это интеграция семантической логики напрямую в синтаксический анализатор, минуя стадию построения дерева. Здесь тактика проста — намечаем точки, которые имеют семантическое значение и пишем код. Пример:
        DIGIT = '0'..'9' {value = child[0] - '0'}
        ADD = DIGIT '+' DIGIT {value = child[0].value + child[1].value}
        SIGN = ('+' | '-') DIGIT {value = child[0].value == '-' ? - child[1].value : child[1].value}
        EXPR = ADD | SIGN {result = child[0].value}
    


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

    LL против LR, или слон против кита

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

    Выделяют две группы анализаторов — восходящие (LR) и нисходящие (LL).

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

    LR-парсер условно имеет стек, в котором хранит последние поступившие символы (и терминалы, и нетерминалы), на каждом шаге, считывая очередной токен, парсер пытается подобрать правило, которое может применить к набору символов с вершины стека, если находит, то он сворачивает последовательность символов в один нетерминал. То есть если стек выглядит как {DIGIT, +, DIGIT}, то анализатор свернет это в {ADD}, а затем в {EXPR}. Псевдокод такого парсера будет примерно таким:

    input >> term;
    while (term != EOF)
    {
        stack.push(term);
        do 
        {
            reduced = false;
            for (Rule rule : rules)
                if (rule.Reduce(stack))
                {
                    stack.pop(rule.right.length);
                    stack.push(rule.symbol);
                    reduced = true;
                    break;
                }
        } while (reduced);
        input >> term;
    }
    


    LL-парсер пытается сделать наоборот — для каждого входящего символа угадать к какому правилу он относится. Самый примитив это выбор из альтернатив (например, EXPR может развернуться в ADD или в SIGN, то есть 2 альтернативы) по первому символу, и рекурсивный спуск с новым набором правил, которые продуцируют нетерминалы из выбранного пути. И так до тех пор пока не правила не разложатся до терминалов. Описание довольно сложное, в коде понять это будет куда проще:
    function ExpandRule(symbol, term)
    {
        for (Rule rule : rules)
        {
            if (rule.sybmol == symbol && firstTerminal(rule) == term)
                break;
        }
        for (s : rule)
        {
            if (s.type == NonTerminal)
                term = ExpandRule(s, term);
            else
            {  
                if (term != s)
                    throw SyntaxError;
                input >> term;
            }
        }
        return term;
    }
    input >> term;
    ExpandRule(EXPR, term);
    


    Какой синтаксический анализатор использовать — дело вкуса. Практически по всем характеристикам они одинаковы. Гуляет байка о том, что в Советах использовали LL(x), а на Западе — LR(x), но не знаю насколько это правдиво. Лично мне идеологически приглянулся LR, более подробно о нём расскажу в следующей части.

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

    Части статьи


    1. Часть 1. Базовая теория
    2. Часть 2. Описание LR-генераторов
    3. Часть 3. Особенности написания и возможные фичи LR-генераторов
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 26

      +2
      Занятно, но что-то толкове откоментировать получится лишь после второй части, когда можно будет сравнить.
        +6
        Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров.

        А какие генераторы вы рассматривали, и чем именно, если не секрет, они вам не подошли? Ничего не имею против самой статьи, просто интересна мотивация писать парсер с нуля.
          +1
          Расскажу в следующей части :)
          В общем-то рассматривал я все популярные — ANTLR, bison, Coco/R, Lemon, boost::spirit, GOLD, sablecc + еще парочка, которые не остались в моей памяти.
            0
            Спасибо, значит, буду ждать следующую часть. )
          +1
          Зачем же нужен лексический анализатор, если он фактически может быть интегрирован в синтаксическую часть?

          Можно добавить, что без отдельного лексического анализатора, грамматика будет явно содержать whitespace между токенами, что очень неудобно. Lexer же удаляет пробелы и комментарии.
            0
            Это решаемо, но опять же плодится огромное число лишних листьев.
            Так что полностью согласен.
              0
              Я бы еще написал про возможность преобразования деревьев в LR. Скажем в ANTLR мне очень понравились правила преобразования «на лету», когда из второго вашего дерева в примере можно сразу получить ADD(12, 34). Работать с таким деревом гораздо приятнее (ничего лишнего).
                +1
                Это не преобразование дерева вывода (prase tree), а построение новой сущности AST, abstract syntax tree. Это более высокоуровневая конструкция, которая слабо зависит от грамматики, если prase tree полностью опирается на грамматику, и имеет четкие правила построения (узел — нетерминал левой части, дочерние элементы — символы правой части). Тогда как в AST мы сами задаём формат, который может вообще не опираться ни на какие символы и правила.
                Да, я не забыл про это, но я боялся написать слишком много — мало кто захочет читать такую простыню, пусть и немного разбавленную кодом и картинками :)
                Вообще изначально планировал уместить всё в одну статью, но вовремя заметил то что объем увеличивается очень быстро. Что удивило меня весьма, ибо вроде воду не лью и стараюсь излагать лаконично.
            0
            > интеграция семантической логики напрямую в синтаксический анализатор, минуя стадию построения дерева
            > Заметно то, что сложную грамматику так не описать

            Достаточно спорное утверждение. Простыню кода можно спрятать в вызов функции.
              0
              Я опираюсь на свой опыт.
              В частности мне нужно было встретив в дерево продукцию X,, у которой терминал a принимал определенное значение, пробежаться по дереву вверх до одной из родительских продукций.
              Если честно, то как это сделать без дерева, я не представляю.
              И таких ситуаций было больше одной, и даже больше десятка.
                0
                Разработчик может самостоятельно поддерживать дерево. Понятно, что если генератор парсера это делает за разработчика, то это круто. Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?
                  0
                  > Но возникает вопрос: а если разработчику нужно чуть другая структура данных, а текущая структура наглухо прописана в годе генератора?

                  Я думаю, начав статью («Написание компилятора LALR(1)-парсеров»), ответил на этот вопрос? :)
                  Это была одна из причин разработки велосипеда.
              0
              Спасибо. Но я видел довольно много постов про основы. А вот практическое построение синтаксического дерева разбора и последующий проход и компиляция — это было бы очень интересно почитать.
                0
                Интересно будет почитать продолжение. Я сейчас активно мучаю ANTLR в дипломном проекте, переехал на него после связки bison+flex. Очень волнует вопрос: а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.
                  +2
                  Подозреваю, что в вакансиях вы такого почти наверняка и не найдете. Хотя знания эти очень полезны и могут сослужить добрую службу в самых неожиданных местах. Равно как и знание основ вычмата и прочих смежных к программированию дисциплин.

                  У меня кстати тоже курсовые работы были посвящены ANTLR и формальным языкам. Интересное было время. Сейчас им занимаюсь уже в качестве хобби.
                    +1
                    Расскажите, что такого у вас в дипломном проекте, для чего не хватило bison+flex? Я теряюсь в догадках.

                    а есть ли спрос на знания в области обработки языков? Я периодически просматриваю вакансии и ещё ничего даже близко похожего не нашёл.
                    Спрос есть, а вот насколько он велик — вопрос открытый. Большинство вакансий на рынке — унылый ынтырпрайз и никакой обработки языков, увы.
                    Поищите вакансии на сайтах компаний-разработчиков различных IDE, там без этого никуда.
                      0
                      С точки зрения самого разбора ничего такого что мешало бы использовать bison+flex нет. ANTLR выбрал за родную поддержку Python, да и большую роль сыграл фактор «почему бы и нет» :)
                  • UFO just landed and posted this here
                      +4
                      у меня задача синтаксического анализа одной грамматики. Существующие решения мне увы не подходили, поэтому встала проблема написания собственного генератора парсеров.


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

                      При всем уважении, у Вас узкий кругозор. Надо было начинать с написания своей операционной системы.
                        +1
                        > и Вы начали с написания своего генератора парсеров?
                        Не, я начал с того что примерно неделю пытался допиливать существующие решения.
                        А написание своего у меня заняло 3 дня.
                        Выгода во времени вроде очевидна?
                          +1
                          Довольно спорное рассуждение. Берем Bison/Flex либо ANTLR и имеем профит.
                            +1
                            Надеюсь, вы расскажете, что и как вам нужно парсить — всем, кто разбирается в теме, интересно, почему вам не хватает существующих решений.
                              0
                              Конечно, вполне возможно меня будут тыкать в более правильные варианты разработки без своего парсера :)
                          +3
                          Для интересующихся темой, возможно, будут интересны следующие статьи:
                          habrahabr.ru/blogs/programming/99162/
                          habrahabr.ru/blogs/programming/99298/
                          habrahabr.ru/blogs/programming/99366/
                          habrahabr.ru/blogs/programming/99397/
                          и прочие из серии. На данный момент насчитывается 10 частей.
                            0
                            Тёмыч отличные статьи написал по синтаксическому анализу и компиляторам.
                            +1
                            мне бы в этой статье было бы интереснее узнать почему существующие решения не подходили, я думаю если на то действительно существовали причины, то они могли бы вызвать живой интерес, ну если конечно эти причины вызваны не убеждениями или нежеланием, а конкретными предметными вещами.

                            Only users with full accounts can post comments. Log in, please.