Источник + (E)BNF = ast.json

Есть ли способ проанализировать исходную строку с помощью пользовательского (e) bnf и получить AST как json? Поясню, что мне нужно:

  • У меня есть исходная строка и грамматика bnf (тоже как строка).
  • Я поставил EBNF как лексер.
  • Добавить источник.
  • Получите AST и сохраните его как JSON.

ebnf abstract-syntax-tree bnf
person Paul Rumkin    schedule 15.11.2013    source источник

Ответы (1)


arrow_upward
1
arrow_downward

«EBNF как лексер» бессмысленно. Но остальную часть вашего вопроса можно интерпретировать так: «Могу ли я получить синтаксический анализатор, управляемый EBNF, для создания AST в форме JSON?»

Конечно.

Большинство генераторов парсеров принимают (E)BNF и "parse". Большинство из них не производят AST автоматически; они заставляют программиста определять, как каждое правило должно генерировать узлы дерева. Они не будут работать для вашей задачи.

Некоторые генерируют AST как структуры данных автоматически, используя только BNF и исходный файл: ANTLR4 (я думаю) и наш набор инструментов для реинжиниринга программного обеспечения DMS. Ни один из них не создает JSON напрямую, но в обоих случаях должно быть просто написать (один раз) общий обходчик дерева, который выплевывает JSON.

BNF DMS будет обрабатывать любую контекстно-свободную грамматику, используя просто правила BNF. ANTLR4 обрабатывает большинство грамматик, но имеет ограничения на то, что вы можете писать (например, некоторые виды левой рекурсии запрещены), и требует от вас добавления дополнительной информации, устраняющей неоднозначность, если грамматика не является LL(1).

DMS будет экспортировать XML напрямую. См. этот пример.

person Ira Baxter    schedule 15.11.2013
comment
Так что, если мне нужно написать обход дерева, то не имеет смысла, какое программное обеспечение использовать, даже YACC с кодом C. Я прав? - person Paul Rumkin; 15.11.2013
comment
Если не случится чудо и кто-нибудь не предложит вам пакет, который делает именно то, что вы указали (я довольно хорошо знаком с миром парсеров; я думаю, что это маловероятно), вы не избежите выполнения некоторой работы. YACC хуже, чем ANTLR/DMS, потому что он вообще не строит деревья для вашей грамматики без существенной помощи для вас. Ходока по дереву довольно легко построить, если у вас есть AST. Если для вас это не очевидно, то я сомневаюсь, что вы сможете использовать результат JSON. - person Ira Baxter; 15.11.2013
comment
Итак, нет ли программного обеспечения для преобразования исходного кода в плоский список лексем, который можно было бы использовать для построения AST? - person Paul Rumkin; 15.11.2013
comment
Это не тот вопрос, который вы задали. (Моя компания предлагает программное обеспечение, которое генерирует именно такой список лексем для ряда широко используемых языков и легко для лексического bnf). Если бы у вас была такая вещь, вам все еще нужна грамматика, чтобы определить, что будет принимать синтаксический анализатор, и минимально определить, как будет выглядеть AST, и вам все еще нужен механизм для построения AST, чтобы ответить на ваш первоначальный вопрос (в нашем случае, это то, что делает DMS). Вы, кажется, не хотите делать какую-либо работу, а затем задаете вопрос, который требует дополнительной работы. Какова ваша настоящая цель? - person Ira Baxter; 15.11.2013
comment
Моя реальная цель - решить проблему преобразования нескольких файлов с разным синтаксисом в один формат AST (или любой другой), который можно было бы использовать в моей программе (для любых целей: выделение, минимизация, стилизация, diff и т. д.). Решение, которое я ищу, должно быть портативным и простым. Я не хочу избегать какой-либо работы, но я хочу ее сократить. - person Paul Rumkin; 18.11.2013
comment
DMS — это унифицированный механизм, который анализирует многие языки и создает AST с использованием единого стиля. Написание JSON — тривиальное упражнение. Похоже, он удовлетворяет все ваши потребности, за исключением, возможно, переносимости; DMS работает только в Windows (но будет работать и в Linux) под Wine. Подобных инструментов нет, за исключением TXL и Stratego, которые менее зрелы для этой цели (ANTLR4 занимает далекое четвертое место)... - person Ira Baxter; 18.11.2013
comment
... Цель таких инструментов - минимизировать работу, необходимую для произвольного манипулирования исходным кодом; они включают в себя не только механизм синтаксического анализа в AST, но и множество других полезных способов обхода/проверки/модификации AST. Вы обнаружите, что задачи, которые вы хотите выполнить, лучше выполнять внутри этих инструментов, а не экспортировать AST в ваш инструмент, где вам придется дублировать все дополнительные механизмы манипуляции с AST, которые они уже предлагают. - person Ira Baxter; 18.11.2013