Подходящее применение для yacc / byacc / bison и lex / flex

StackOverflow https://stackoverflow.com/questions/2414303

  •  19-09-2019
  •  | 
  •  

Вопрос

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

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

Предполагая , что разработчик ...

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

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

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

Решение

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

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

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

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

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

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

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

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

Другие советы

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

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

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

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

Поэтому я разработал небольшой DSL для задания запросов (например[FirstName]='Joe' И [LastName]='Bloggs' выбрали бы всех с именем "Джо Блоггс").У него было несколько более сложных опций, например, был синтаксис "отказаться (medium)", который выбирал всех людей, которые отказались от получения сообщений на определенном носителе (электронная почта, sms и т.д.).Существовала "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 для этого, но я использовал генератор синтаксического анализа (название которого на данный момент ускользнуло от меня ...)

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top