Узнать больше О синтаксическом анализе
https://stackoverflow.com/questions/1053549
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я программирую с 1999 года для работы и развлечения.Я хочу учиться новому, и в последнее время я сосредоточился на синтаксическом анализе, поскольку большая часть моей работы - это чтение, интеграция и анализ данных.У меня также есть большое количество повторяющихся задач, которые, я думаю, я мог бы выразить на очень простых предметно-ориентированных языках, если бы накладные расходы были достаточно низкими.У меня есть несколько вопросов по этому поводу.
- Большая часть моего текущего кода синтаксического анализа не определяет формальную грамматику.Обычно я собираю что-то вместе на выбранном мной языке, потому что это легко, я знаю, как это сделать, и я могу написать этот код очень быстро.Это также легко поддерживать другим людям, с которыми я работаю.Каковы преимущества и недостатки определения грамматики и генерации реального синтаксического анализатора (как можно было бы сделать с ANTLR ( АНТЛР ) или YACC ( ЯКЦ )) чтобы проанализировать вещи по сравнению с взломами, которые большинство программистов использовали для написания синтаксических анализаторов?
- Каковы наилучшие инструменты генерации синтаксических анализаторов для написания синтаксических анализаторов на основе грамматики на C ++, Perl и Ruby?Я просмотрел на ANTLR ( АНТЛР ) и не нашел много информации об использовании ANTLRv3 с целью C ++, но в остальном это выглядит интересно.Каковы другие инструменты, похожие на ANTLR, о которых мне следует прочитать?
- Каковы канонические книги и статьи, в которых кому-то интересно узнать больше о синтаксическом анализе?Курс по компиляторам, к сожалению, не был частью моего образования, поэтому базовый материал очень приветствуется.Я слышал замечательные вещи о Книга Дракона, но что еще там есть?
Решение
На 1., я бы сказал, что главным преимуществом является ремонтопригодность -- внесение небольшого изменения в язык просто означает внесение соответственно небольшого изменения в грамматику, а не тщательное изучение различных мест в коде, которые могут иметь какое-то отношение к тому, что вы хотите изменить...на порядки выше производительность и меньше риск ошибок.
Вкл. 2.и 3., Я не могу предложить многого сверх того, что вы уже нашли (я в основном использую Python и pyparsing, и мог бы прокомментировать опыт работы со многими фреймворками синтаксического анализа, ориентированными на Python, но для C ++ я в основном использую старый добрый yacc или bison в любом случае, и мой старый корявый экземпляр "Книги дракона" - на самом деле не последнее издание - это все, что я держу при себе для этой цели ...).
Другие советы
Вот мой взгляд на ваши (очень хорошие) вопросы:
- Я думаю, что синтаксический анализатор больше всего выигрывает в нетривиальных ситуациях, когда грамматика действительно существует.Вы должны знать о том, как работают синтаксические анализаторы и грамматики, чтобы придумать этот метод, а это делает не каждый разработчик.
- lex / yacc - это более старые инструменты Unix, которые могут быть полезны вам как разработчику C ++.Может быть, и Бизон тоже.
- ANTRL и сопутствующая ему книга очень хороши. "Написание компиляторов и интерпретаторов" содержит примеры C ++, которые могут вам понравиться.
Шаблон интерпретатора GoF - это еще одна техника написания "маленьких языков".Взгляните на это.
Давайте создадим Компилятор это пошаговое руководство о том, как написать простой компилятор.Код написан на Delphi (Pascal), но он достаточно простой, чтобы его можно было легко перевести на большинство других языков.
Я бы серьезно взглянул на синтаксический анализ на основе монадических комбинаторов (который часто также имеет дело с лексическим анализом) в Haskell.Мне это открыло глаза;удивительно, как легко вы можете создать синтаксический анализатор с нуля, используя этот метод.На самом деле это настолько просто, что зачастую быстрее написать свой собственный анализатор, чем пытаться использовать существующие библиотеки.
Вероятно, самым известным примером является Парсек который обладает хорошим руководство пользователя это объясняет, как им пользоваться.Существует список портов этой библиотеки на другие языки (включая C++ и Рубин) , перечисленных на Страница Parsec в Haskell wiki, хотя я с ними не знаком и поэтому не могу сказать, насколько они близки к использованию Parsec в Haskell.
Если вы хотите узнать, как они работают внутри компании и как написать свои собственные, я рекомендую начать с главы 8 ("Функциональные анализаторы") из книги Грэма Хаттона Программирование на Haskell.Как только вы хорошо поймете эту главу (которая, вероятно, потребует нескольких прочтений), вы будете настроены.
В perl первым делом нужно начать с Parse::RecDescent modules.Добавьте учебник к названию модуля, и Google сможет найти множество руководств, которые помогут вам начать.
Определить грамматику с помощью BNF, EBNF или чего-то подобного проще, и позже вам будет легче поддерживать ее.Кроме того, вы можете найти множество примеров грамматических определений.И последнее, но не менее важное: если вы собираетесь рассказывать о своей грамматике кому-то еще на поле, лучше, если вы оба говорите на одном языке (BNF, EBNF и т.д.).
Написание собственного кода синтаксического анализа подобно изобретению колеса и чревато ошибками.Это также менее ремонтопригодно.Конечно, он может быть более гибким, и для небольших проектов это также может быть хорошим выбором, но использование существующего генератора синтаксического анализа, который использует грамматику и выдает код, должно удовлетворить большую часть наших потребностей.
Для C ++ я бы также предложил lex / yacc.Для Ruby это выглядит как достойный выбор: Кокос/R(uby)
Забавный момент:Я провел большую часть этого утра, размышляя о машинах состояний и синтаксических анализаторах и пытаясь понять, как я мог бы узнать о них больше.
Для 2, вы могли бы взглянуть на Ражель (это хорошо для C ++ и Ruby).
Вот руководство по автономному (10 страниц!), полностью переносимому компилятору-compiler который можно использовать для очень быстрой разработки и внедрения DSL с низкими накладными расходами:
http://www.bayfronttechnologies.com/mc_tutorial.html
Этот сайт познакомит вас со статьей Вэла Шорре о MetaII, опубликованной в 1964 году.Да, 1964 год.И это потрясающе.Вот как я узнал о компиляторах еще в 1970 году.
