Динамический (?) Парсер

Question

Существует ли анализатор, который генерирует AST / дерево разбора во время выполнения? Вроде как библиотека, которая будет принимать строку грамматики EBNF или что-то аналогичное и выкладывать структуру данных?

• Мне известны antlr, jlex и тому подобное. Они генерируют исходный код, который может сделать это. (хотел бы пропустить шаг компиляции)
• Мне известно о Boost :: Spirit, который использует некоторую чёрную магию с синтаксисом C ++ для генерации таких вещей во время выполнения (определенно намного ближе к тому, что я хочу, но я не уверен, когда дело доходит до C ++. И это все еще несколько ограничивает, потому что ваша грамматика жестко закодирована)
• Я ничего не знаю в python или ruby, хотя компилятор компилятора вполне может быть эффективным на таком языке ...

Теперь я знаю о комбинаторах синтаксического анализа. (спасибо, Джонас) И некоторые библиотеки (спасибо, Элибен)

между прочим, я также заметил Грамматики синтаксического анализа выражений в последнее время, что звучит круто, если бы кто-то это реализовал (говорят, что Perl 6 получит его, но Perl уклоняется от моего понимания)

Answer 1

Взгляните на комбинаторы парсеров , которые, я думаю, могут вам помочь. С помощью этой техники можно создавать парсеры во время выполнения. Одним из популярных комбинаторов синтаксического анализа является Parsec , который использует Haskell в качестве основного языка. Из документации parsec :

Парсеры Combinator написаны и используются на том же языке программирования, что и остальная часть программы. Между грамматическим формализмом (Yacc) и используемым языком программирования нет разрыва (C)

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

Если вы используете .NET, взгляните на библиотеку комбинатора синтаксического анализатора для F # .

Answer 2

Если вам подходит Java, есть порт библиотеки Haskell Parsec - JParsec . Очень мощный, хотя документация не велика.

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

Скручивание головы.

Поскольку все это на Java (ваш Parser - POJO), вы можете выполнять рефакторинг и выполнять TDD, и все, что вы привыкли делать в Java. Это главное преимущество более традиционного подхода ANTLR / JavaCC / JJTree.

Answer 3

Да, конечно!

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

• В Perl используйте Parse :: RecDescent. Он берет свою грамматику из строки, и вы определенно можете попросить его сгенерировать новый синтаксический анализатор из новой строки во время выполнения.
• В Python рассмотрим PLY. Вы можете легко сгенерировать функции с помощью строк документации во время выполнения и запустить PLY.

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

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

Удачи.

Answer 4

Lambda the Ultimate обсуждала синтаксический анализатор , который допускает расширения синтаксиса .

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

{syntax: while (condition) do code}
while (condition, code) => // actual execution

и замените каждый шаблон, соответствующий синтаксису, вызовом функции. Однако я не знаю, с чего начать запуск лексера и анализатора, потому что обычные инструменты, такие как Flex / Bison или ANTLR (я хотел бы написать компилятор на C #), похоже, не позволяют этого.

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

Answer 5

[Dropincc.java] http://pfmiles.github.com/blog/dropincc-dot-java-the-ultimate-tool-to-create-dsls-in-java/ "Dropincc.java - генератор динамического синтаксического анализатора в чистом Java".

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

Проверьте ссылку там, чтобы получить больше информации.

[Домашняя страница проекта] https://github.com/pfmiles/dropincc.java

Answer 6

Что вы собираетесь анализировать? В C или C ++ у вас не будет парсера во время выполнения, поэтому он не доступен без дополнительной библиотеки. Для многих языков программирования это правда.

Все парсеры по умолчанию являются «динамическими» при их реализации. Даже в с.

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

Answer 7

JFlex , расширение JLex Java, позволяет выполнять компиляцию во время выполнения, но это довольно сложная вещь.