Соответствующее использование для yacc / byacc / bison и lex / flex

Question

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

• Используйте библиотеку буста (вставьте соответствующую библиотеку буста здесь)
• Не создавать DSL-использование (введите любимый язык сценариев здесь)
• Antlr лучше

---

При условии, что разработчик ...

• ... комфортно с языком C
• ... знает хотя бы один сценарий язык (например, Python, Perl и т. д.)
• ... должен написать некоторый код синтаксического анализа почти каждый проект работал на

---

Итак, мои вопросы:

• Каковы подходящие ситуации, которые хорошо подходят для этих утилит?
• Существуют ли (разумные) ситуации где не лучше альтернатива проблеме, чем YACC и лекс (или производные)?
• Как часто в реальных проблемах разбора Можно ли ожидать столкновения с любым коротким приходит в YACC и Lex, которые лучше адресовано более свежим решения?
• Для разработчика, которого еще нет знакомы с этими инструментами стоит это для них, чтобы инвестировать время в изучать их синтаксис / идиомы? Как это по сравнению с другими решениями?

Answer 1

Причины, по которым lex / yacc и производные выглядят настолько повсеместно в наши дни, заключаются в том, что они существуют гораздо дольше, чем другие инструменты, что они имеют гораздо больший охват в литературе и что они традиционно поставляются с операционными системами Unix. Это очень мало связано с тем, как они сравниваются с другими инструментами генерации лексеров и парсеров.

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

Кроме того, в конце 1960-х и начале 1970-х годов, когда были созданы lex / yacc, аппаратные ограничения представляли серьезную проблему для синтаксического анализа. Метод анализа LR на основе таблиц, используемый Yacc, был наиболее подходящим в то время, потому что его можно было реализовать с небольшим объемом памяти, используя относительно небольшую общую программную логику и сохраняя состояние в файлах на ленте или диске. Методы синтаксического анализа, основанные на коде, такие как LL, занимали больший минимальный объем памяти, потому что сам код программы синтаксического анализа представляет грамматику, и поэтому для его выполнения необходимо полностью помещаться в ОЗУ и сохранять состояние стека в ОЗУ.

Когда памяти стало больше, было проведено гораздо больше исследований, посвященных различным методам синтаксического анализа, таким как LL и PEG, и методам создания инструментов с использованием этих методов. Это означает, что многие из альтернативных инструментов, которые были созданы после семейства lex / yacc, используют разные типы грамматик. Однако переключение типов грамматики также влечет за собой значительную кривую обучения. Если вы знакомы с одним типом грамматики, например, грамматикой LR или LALR, вы с меньшей вероятностью захотите переключиться на инструмент, использующий грамматику другого типа, например грамматики LL.

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

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

Вот несколько причин, по которым я мог бы использовать lex / yacc или flex / bison:

• разработчик уже знаком с lex / yacc или flex / bison
• разработчик наиболее знаком и удобен с грамматиками LR / LALR
• у разработчика есть много книг на lex / yacc, но нет книг на других
• у разработчика есть предполагаемое предложение о работе, и ему сказали, что навыки lex / yacc повысят его шансы получить работу
• разработчик не может получить бай-ин от участников проекта / заинтересованных сторон за использование других инструментов
• в среде установлен lex / yacc, и по какой-то причине невозможно установить другие инструменты

Answer 2

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

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

Конечно, lex и yacc производят (и требуют, чтобы вы писали свои действия в) C (или C ++). Если вам неудобно с ними, инструмент, который использует и производит предпочитаемый вами язык (например, Python или Java), несомненно, будет гораздо лучшим выбором. Я, например, не советовал бы пытаться использовать такой инструмент с языком, с которым вы незнакомы или неудобны. В частности, если вы пишете код в действии, которое приводит к ошибке компилятора, вы, вероятно, получите значительно меньшую помощь от компилятора, чем обычно, в отслеживании проблемы, поэтому вам действительно нужно быть достаточно знакомым с языком, чтобы распознать проблему только с минимальной подсказкой о том, где компилятор заметил, что что-то не так.

Answer 3

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

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

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

Answer 4

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

Answer 5

В предыдущем проекте мне нужен был способ, чтобы генерировать запросы на произвольные данные таким образом, чтобы его мог легко использовать относительно не технический специалист. Данные были типа CRM (например, Имя, Фамилия, Адрес электронной почты и т. Д.), Но они предназначались для работы с несколькими различными базами данных, все с различными схемами.

Поэтому я разработал небольшой DSL для определения запросов (например, [FirstName] = 'Joe' AND [LastName] = 'Bloggs' выберет всех, кого зовут "Joe Bloggs"). У него были некоторые более сложные опции, например, был синтаксис «optedout (medium)», который выбирал всех людей, которые отказались от получения сообщений на определенном носителе (электронная почта, смс и т. Д.). Был «ingroup (xyz)», который выбирал всех в определенной группе и т. Д.

По сути, это позволило нам указать запросы, такие как «ingroup ('GroupA') и не ingroup ('GroupB')", которые будут преобразованы в SQL-запрос, подобный этому:

SELECT
    *
FROM
    Users
WHERE
    Users.UserID IN (SELECT UserID FROM GroupMemberships WHERE GroupID=2) AND
    Users.UserID NOT IN (SELECT UserID GroupMemberships WHERE GroupID=3)

(Как видите, запросы не настолько эффективны, насколько это возможно, но я думаю, это то, что вы получаете при генерации машин).

Я не использовал для этого flex / bison, но я использовал генератор синтаксических анализаторов (имя которого сейчас ускользнуло от меня ...)