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

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

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

75 голосов | спросил Maniero 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 09:48:06 +0300 2010, 09:48:06

12 ответов


71

Существует три варианта: все три из них предпочтительнее в разных ситуациях.

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

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

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

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

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

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

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

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

В этих случаях использование рукописного рекурсивного спуска парсера, вероятно, является лучшим. Хотя правильное решение может быть сложным, у вас есть полный контроль над вашим парсером, чтобы вы могли делать всевозможные приятные вещи, которые вы не можете сделать с генераторами парсеров, такими как сообщения об ошибках и даже восстановление ошибок (попробуйте удалить все точки с запятой из файла 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 # требует, чтобы он был классом, поэтому мне пришлось ввести класс-оболочку)

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

ответил Alex ten Brink 13 62010vEurope/Moscow11bEurope/MoscowSat, 13 Nov 2010 23:09:59 +0300 2010, 23:09:59
21

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

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

ответил 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 20:33:45 +0300 2010, 20:33:45
13

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

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

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

Bjarne Stroustrup рассказывает о том, как он использовал YACC для первой реализации C ++ (см. The Design and Evolution of C ++ ). В этом первом случае он пожелал, чтобы он написал собственный рекурсивный парсер спуска.

ответил Macneil 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 18:20:26 +0300 2010, 18:20:26
10

Вариант 3: Ни (сверните свой собственный генератор синтаксического анализатора)

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

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

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

ответил Peter Boughton 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 14:44:47 +0300 2010, 14:44:47
7

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

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

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

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

ответил John R. Strohm 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 16:28:14 +0300 2010, 16:28:14
6

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

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

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

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

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

ответил azheglov 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 17:53:22 +0300 2010, 17:53:22
3

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

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

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

ответил Tim Post 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 09:58:58 +0300 2010, 09:58:58
3

Вы считали Мартин Фаулерс подход к работе на рабочем месте ? Цитата из статьи

  

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

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

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

Преимущества использования собственных

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

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

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

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

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

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

ответил Gary Rowe 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 12:54:07 +0300 2010, 12:54:07
2

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

ответил philosodad 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 20:07:16 +0300 2010, 20:07:16
2

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

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

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

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

ответил GrandmasterB 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 22:34:12 +0300 2010, 22:34:12
1

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

ответил JBRWilkinson 9 22010vEurope/Moscow11bEurope/MoscowTue, 09 Nov 2010 13:29:44 +0300 2010, 13:29:44
1

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

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

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

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

ответил Ming-Tang 13 62010vEurope/Moscow11bEurope/MoscowSat, 13 Nov 2010 04:09:38 +0300 2010, 04:09:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132