Должен ли я использовать генератор синтаксического анализатора или я должен свернуть свой собственный код лексера и анализатора?

Какие конкретные преимущества и недостатки каждого способа работы над грамматикой языка программирования?

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

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

Вариант 1: генераторы парсера, или «вам нужно разобрать какой-то язык, и вы просто хотите, чтобы он работал, черт возьми»

Скажем, вас попросили создать парсер для какого-то древнего формата данных СЕЙЧАС. Или вам нужен ваш парсер, чтобы быть быстрым. Или вам нужен ваш парсер, чтобы его было легко обслуживать.

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

Преимущества очевидны:

• (Обычно) довольно легко написать спецификацию, в частности, если формат ввода не слишком странный (вариант 2 был бы лучше, если он есть).
• В итоге получается очень легко поддерживаемая часть работы, которую легко понять: определение грамматики обычно выглядит намного более естественным, чем код.
• Парсеры, генерируемые хорошими генераторами парсеров, обычно намного быстрее, чем рукописный код. Рукописный код может быть быстрее, но только если вы знаете свои вещи - вот почему наиболее широко используемые компиляторы используют рукописный синтаксический анализатор с рекурсивным спуском.

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

Вариант 2: парсеры, написанные от руки, или «вы хотите создать свой собственный парсер и заботиться о том, чтобы быть удобным для пользователя»

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

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

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

С точки зрения образования, написание собственного парсера научит вас больше, чем использованию генератора. В конце концов, вы должны писать все более и более сложный код, плюс вы должны точно понимать, как вы разбираете язык. С другой стороны, если вы хотите научиться создавать свой собственный язык (то есть получить опыт работы с языковым дизайном), предпочтительным является вариант 1 или 3: если вы разрабатываете язык, он, вероятно, сильно изменится, и варианты 1 и 3 облегчают вам процесс.

Вариант 3: написанные от руки генераторы синтаксического анализатора, или «вы пытаетесь многому научиться из этого проекта, и вы не против получить изящный кусок кода, который вы можете многократно использовать повторно»

Это путь, по которому я сейчас иду: вы пишете свой собственный генератор парсеров. Хотя это весьма нетривиально, это, вероятно, научит вас больше всего.

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

Генератор лексера

Сначала я создал свой собственный генератор лексеров. Я обычно проектирую программное обеспечение, начиная с того, как будет использоваться код, поэтому я подумал о том, как я хотел иметь возможность использовать свой код, и написал этот фрагмент кода (он находится на C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

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

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

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

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

Генератор парсера

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

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

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

Вот как может выглядеть фрагмент кода с использованием моего генератора синтаксического анализатора:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Обратите внимание, что IntWrapper - это просто Int32, за исключением того, что C # требует, чтобы он был классом, поэтому мне пришлось ввести класс-обертку)

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

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

Я бы также посоветовал вам попробовать прочитать http://compilers.iecc.com/crenshaw/, поскольку он очень практично относится к тому, как это сделать.

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

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

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

Бьярн Страуструп рассказывает о том, как он использовал YACC для первой реализации C ++ (см . Дизайн и развитие C ++ ). В этом первом случае он хотел бы, чтобы он написал свой собственный парсер рекурсивного спуска!

Вариант 3: Ни один (Бросьте свой собственный генератор парсера)

Просто потому, что есть причина не использовать ANTLR , бизонов , Coco / R , Grammatica , JavaCC , Lemon , Parboiled , SableCC , Quex и т. Д. - это не означает, что вы должны немедленно бросить свой собственный анализатор + лексер.

Определите, почему все эти инструменты недостаточно хороши - почему они не позволяют вам достичь вашей цели?

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

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

В первые годы был большой интерес к генераторам синтаксических анализаторов, мотивированным сложным (некоторые сказали бы, «замученным») синтаксисом языка. JOVIAL был особенно плохим примером: требовалось два символа, в то время как все остальное требовало не более одного символа. Это сделало создание синтаксического анализатора для компилятора JOVIAL более сложным, чем ожидалось (так как Отдел General Dynamics / Fort Worth научился трудному пути, когда они закупали компиляторы JOVIAL для программы F-16).

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

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

Однажды я написал парсер для коммерческого применения и использовал yacc . Был конкурирующий прототип, где разработчик написал все это вручную на C ++, и он работал примерно в пять раз медленнее.

Что касается лексера для этого парсера, я написал его полностью от руки. Это заняло - извините, это было почти 10 лет назад, поэтому я точно не помню - около 1000 строк в Си .

Причиной, по которой я написал лексер вручную, была грамматика ввода синтаксического анализатора. Это было требование, которому должна соответствовать моя реализация синтаксического анализатора, а не то, что я разработал. (Конечно, я разработал бы его по-другому. И лучше!) Грамматика сильно зависела от контекста, и в некоторых местах даже лексизм зависел от семантики. Например, точка с запятой может быть частью токена в одном месте, но разделителем в другом месте - на основе семантической интерпретации некоторого элемента, который был проанализирован ранее. Итак, я «похоронил» такие семантические зависимости в написанном от руки лексере, и это оставило меня с довольно простым BNF, который легко реализовать в yacc.

ДОБАВЛЕНО в ответ на Macneil : yacc предоставляет очень мощную абстракцию, которая позволяет программисту думать с точки зрения терминалов, нетерминалов, производств и тому подобного. Кроме того, при реализации yylex()функции это помогло мне сосредоточиться на возврате текущего токена и не беспокоиться о том, что было до или после него. Программист C ++ работал на уровне символов, не пользуясь такой абстракцией, и в итоге создал более сложный и менее эффективный алгоритм. Мы пришли к выводу, что более медленная скорость не имеет ничего общего с самим C ++ или любыми библиотеками. Мы измерили чистую скорость анализа файлов, загруженных в память; если бы у нас была проблема с буферизацией файла, yacc не был бы нашим лучшим инструментом для ее решения.

ТАКЖЕ ХОЧУ ДОБАВИТЬ : это не рецепт написания парсеров в целом, а лишь пример того, как это работает в одной конкретной ситуации.

Это полностью зависит от того, что вам нужно разобрать. Можете ли вы катить свой собственный быстрее, чем вы можете достичь кривой обучения лексера? Является ли материал для анализа достаточно статичным, чтобы вы не пожалели о решении позже? Считаете ли вы существующие реализации слишком сложными? Если это так, получайте удовольствие, катаясь самостоятельно, но только если вы не уклоняетесь от обучения.

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

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

Это зависит от вашей цели.

Вы пытаетесь узнать, как работают парсеры / компиляторы? Тогда напишите свой с нуля. Это единственный способ научиться ценить все то, что они делают. Я писал один за последние пару месяцев, и это был интересный и ценный опыт, особенно моменты «ах, вот почему язык Х делает это ...».

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

Вам нужно что-то, что вы захотите расширить в течение следующих 10, 20, может быть, даже 30 лет? Напишите свое и не торопитесь. Это того стоит.

Рассматривали ли вы подход Мартина Фаулерса к языку ? Цитата из статьи

Наиболее очевидным изменением, которое языковое рабочее место вносит в уравнение, является простота создания внешних DSL. Вам больше не нужно писать парсер. Вы должны определить абстрактный синтаксис - но на самом деле это довольно простой шаг моделирования данных. Кроме того, ваш DSL получает мощную IDE - хотя вам нужно потратить некоторое время на определение этого редактора. Генератор - это все еще то, что вы должны сделать, и я чувствую, что это не намного проще, чем когда-либо. Но тогда создание генератора для хорошего и простого DSL является одной из самых простых частей упражнения.

Читая это, я бы сказал, что дни написания вашего собственного парсера прошли, и лучше использовать одну из доступных библиотек. Как только вы освоите библиотеку, все знания DSL, которые вы создадите в будущем, получат пользу от этих знаний. Кроме того, другие не должны изучать ваш подход к анализу.

Изменить, чтобы покрыть комментарий (и пересмотренный вопрос)

Преимущества катания самостоятельно

1. Вы будете владеть синтаксическим анализатором и получите весь этот прекрасный опыт размышления над сложной серией проблем
2. Вы можете придумать что-то особенное, о чем никто не думал (вряд ли, но вы кажетесь умным парнем)
3. Это будет занимать вас интересной проблемой

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

Преимущества использования чужой библиотеки

1. Вы избежите повторного изобретения колеса (распространенная проблема в программировании, с которой вы согласитесь)
2. Вы можете сосредоточиться на конечном результате (новый язык) и не слишком беспокоиться о том, как он анализируется и т. Д.
3. Вы увидите свой язык в действии намного быстрее (но ваша награда будет меньше, потому что это был не весь вы)

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

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

Большим преимуществом написания своих собственных является то, что вы будете знать, как писать свои собственные. Большим преимуществом использования такого инструмента, как yacc, является то, что вы будете знать, как его использовать. Я фанат Treetop для первоначального изучения.

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

В моих синтаксических анализаторах я использовал регулярные выражения (я имею в виду, стиль Perl) для токенизации и использовал некоторые вспомогательные функции для повышения читабельности кода. Однако, анализатор сгенерированный код может быть быстрее, делая таблицы состояний и долго switch- caseс, что может увеличить размер исходного кода , если вы .gitignoreих.

Вот два примера моих пользовательских написанных парсеров:

https://github.com/SHiNKiROU/DesignScript - диалект BASIC, потому что мне было лень писать вглядные выражения в нотации массива, я жертвовал качеством сообщений об ошибках https://github.com/SHiNKiROU/ExprParser - Калькулятор формул. Обратите внимание на странные приемы метапрограммирования

«Должен ли я использовать это проверенное и испытанное« колесо »или заново его изобрести?»