Грамматика / собственный написанный парсер?

Question

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

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

Спасибо

Уильям ван Дорн

Answer 1

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

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

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

Answer 2

Стоит кодировать синтаксический анализатор вручную, если и только если вы очень заинтересованы в том, чтобы он был очень быстрым даже на машине с очень скромной скоростью. Например, в этой статье об истории Turbo Pascal до того, как он получил свое название, вы можете увидеть, как и почему прототип произвел впечатление на небольшую (тогда датскую) фирму "Borland", чтобы нанять автора прототипа ( Андерс Хейлсберг), полностью разработайте компилятор и запустите его в качестве основного продукта, и я цитирую ...:

без особых ожиданий я ударил ключ компиляции - И ТОГДА БЫЛ ПОЛНОСТЬЮ ПОЛ Моя тестовая программа, это заняло несколько минут, чтобы скомпилировать и связать используя Pascal MT + от Digital Research, был скомпилирован и запущен до того, как я мог моргнуть глаз! Это было здорово ВАУ момент!

Потрясающая скорость компиляции в Turbo Pascal - в первую очередь благодаря тщательно отрегулированному и тщательно настроенному анализатору рекурсивного спуска, написанному на ассемблере, - позволила ему использовать совершенно другую стратегию от большинства компиляторов: нет отдельного объекта, генерирующего проход компиляции файлы и библиотеки, а затем компоновщик, чтобы собрать их вместе, скорее, Turbo Pascal 1.0 был однопроходным компилятором, который непосредственно превращал исходный код в один исполняемый двоичный файл.

Я помню точно такой же удивительный опыт на крошечных персональных компьютерах той эпохи (когда Z80, 64K или RAM и две дискеты были lot ;-) - Turbo Pascal с его потрясающим parser, IDE и все остальное удобно помещаются в памяти вместе с существенной программой как в исходном, так и в скомпилированном виде - не нужны дискеты, что означает разницу во времени выполнения программы на много порядков.

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

Конечно, на сегодняшнем типичном ПК такая предельная скорость синтаксического анализа не понадобится большинству компиляторов. Возможные исключения включают компиляторы, которые должны беспрепятственно работать как часть «подобной интерпретатору» среды (по этой причине простые компиляторы для языков, таких как Perl и Python, обычно закодированы вручную, в значительной степени - это был выбор реализации, который сделал их жизнеспособными в 90-х, хотя сегодня неясно, что это все еще необходимо), или компиляторов, которые работают на очень ограниченных аппаратных ресурсах, таких как смартфоны или недорогие нетбуки.

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

Answer 3

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

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

И не думайте, что использование генераторов синтаксического анализатора как-то более профессионально или даже более просто.Бьярн Страуструп (Bjarne Stroustrup), когда писал первый компилятор C ++, намеревался использовать рекурсивный спуск, но об этом говорили некоторые увлеченные коллеги из Bell Labs, к большому огорчению.См. Раздел 3.3.2 «Проектирование и развитие C ++» для получения более подробной информации.