Теория, примеры обратимых парсеров? - PullRequest
4 голосов
/ 19 марта 2009

Кто-нибудь знает о примерах и теории парсеров, которые возьмут (может быть) абстрактное синтаксическое дерево и произведут код, а не наоборот. Математически, по крайней мере, интуитивно, я считаю, что функция code-> AST обратима, но я пытаюсь найти работу / примеры этого ... помимо обычных ресурсов, таких как книга Дракона и тому подобное. Есть идеи?

Ответы [ 11 ]

3 голосов
/ 19 марта 2009

Такая вещь называется посетителем. Обходит дерево и делает все, что нужно, например, оптимизирует или генерирует код.

1 голос
/ 19 февраля 2015

В Haskell есть теория, рабочие реализации и примеры обратимого анализа. Библиотека принадлежит Павлу Новаку. Пожалуйста, обратитесь к https://hackage.haskell.org/package/syntax в качестве отправной точки. Вы можете найти примеры по следующим ссылкам.

1 голос
/ 17 июня 2009

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

Книга Дракона дает хорошее описание теории парсеров.

1 голос
/ 19 марта 2009

Мне скорее нравится ответ lewap:

найти математический способ выразить посетитель, и у вас есть двойной парсер

Но вы попросили образец, так что попробуйте это по размеру: Visual Studio содержит UML-редактор с превосходной симметрией. То, как он и редакторы реализованы, представляют собой представления модели, и редактирование либо изменяет модель, в результате чего все остальное синхронизируется.

0 голосов
/ 19 сентября 2016

Существует несколько «языков линз», которые позволяют преобразование двунаправленного текста исходного кода.

Также возможно реализовать обратимые парсеры, используя грамматики определенных выражений в Прологе. В SWI-Prolog предикат фраза / 3 преобразует деревья разбора в текст и наоборот. Эта книга предоставляет некоторые дополнительные примеры обратимого анализа в Прологе.

0 голосов
/ 19 марта 2011

Идея "Шаблон посетителя" хороша. Но я должен рассматривать шаблон «Посетитель» как шаблон линейного списка или как общий шаблон и добавлять шаблоны для более конкретных случаев, таких как списки, матрицы и деревья.

Найдите в Интернете «Иерархический шаблон посетителей» или «Дерево шаблонов посетителей».

У вас есть древовидная структура данных («Коллекция»), и вы хотите что-то делать с данными, каждый раз, когда вы «посещаете», «повторяете» или «читаете» элемент из дерева.

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

0 голосов
/ 18 марта 2011

Наш инструментарий реинжиниринга программного обеспечения DMS настаивает на том, чтобы парсеры и инверторы парсеров (называемые "prettyprinters") использовались как "покер-анте" для механической обработки (анализа / преобразования) произвольных языков. Они обеспечивают полный круговой переход: исходный текст в AST с захваченной информацией о положении (файл / строка / столбец) и комментариями, а также AST - с легальным исходным текстом, включая восстановление исходных позиций токена («печать с точностью») или с хорошим форматированием («prettyprinting») ) варианты, включая регенерацию комментариев.

Парсеры часто задаются комбинацией грамматик и лексических определений токенов; эти нотации обычно компилируются в эффективные механизмы синтаксического анализа, и DMS делает это для стороны «синтаксического анализатора», как и следовало ожидать. Другие люди здесь предполагают, что «посетитель» - это способ сделать красивую печать, и, как и ассемблерный код, это правильный способ реализовать красивую печать на самом низком уровне абстракции. Однако симпатичные принтеры DMS указываются в терминах языка текстового поля над грамматическими терминами, например, латекс, что позволяет контролировать размещение различных языковых элементов по горизонтали, вертикали, встраивать, размещать, объединять, ламинировать и т. Д. Компиляция DMS они превращаются в эффективных посетителей низкого уровня (как предлагают другие ответы), которые реализуют генерацию блоков. Но, как генератор парсера, вам не нужно видеть все ужасные детали.

DMS имеет около 30+ наборов этих языковых интерфейсов для различных языков программирования и формальных нотаций, начиная от C ++, C, Java, C #, COBOL и т. Д. До HTML, XML, языков ассемблера из некоторых машин, спецификации временных свойств, спецификации составных абстрактных алгебр и т. д.

0 голосов
/ 21 марта 2009

Я делал это вечно и называл их «DeParse».

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

0 голосов
/ 20 марта 2009

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

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

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

Следует обратить внимание на инструменты автоматического рефакторинга кода.

0 голосов
/ 20 марта 2009

В дополнение к «Посетителю», «unparser» - еще одно хорошее ключевое слово для веб-поиска.

...