Комбинированный генератор unparser/parser

Ответ 1

Посмотрите Обратимые описания синтаксиса: Объединение синтаксического анализа и довольно печатная версия.

Ответ 2

Наш DMS Software Reengineering Toolkit делает именно это (и предоставляет много дополнительной поддержки для анализа/преобразования кода). Это достигается путем украшения языковой грамматики дополнительными атрибутами, создавая так называемую грамматику атрибутов. Мы используем специальный DSL для написания этих правил, чтобы их было удобно писать.

Это помогает знать, что DMS создает дерево, основанное непосредственно на грамматике.

Каждое правило грамматики DMS связано с так называемым правилом prettyprinting. Каждое правило prettyprinting описывает, как "prettyprint" синтаксический элемент и подэлементы распознаются соответствующим правилом грамматики. Процесс prettyprinting, по существу, создает или комбинирует прямоугольные блоки текста по горизонтали или вертикали (с необязательным отступом), а листы создают блоки с единичной высотой, содержащие буквальное значение листа (ключевое слово, оператор, идентификатор, константа и т.д.).

Например, можно написать следующее правило грамматики DMS и соответствующее правило prettyprinting:

statement = 'for' '(' assignment ';' assignment ';' conditional_expression ')'
            '{' sequence_of_statements '}' ;
<<PrettyPrinter>>: 
    { V(H('for','(',assignment[1],';','assignment[2],';',conditional_expression,')'),
        H('{', I(sequence_of_statements)),
        '}');

Это проанализирует следующее:

    for ( i=x*2;
       i--;  i>-2*x ) {  a[x]+=3; 
      b[x]=a[x]-1; }

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

    for (i=x*2;i--;i>-2*x)
    {   a[x]+=3;
        b[x]=a[x]-1;
    }

DMS также фиксирует комментарии, прикрепляет их к узлам AST и регенерирует их при выводе. Реализация немного экзотическая, потому что большинство парсеров не обрабатывают комментарии, но их использование легко, даже "бесплатно"; комментарии будут автоматически вставлены в довольно распечатанный результат в их исходных местах.

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

Более подробная информация о том, что должны делать prettyprinters, содержится в моем SO-ответе " Компиляция AST обратно в исходный код". DMS обращается ко всем темам чисто.

Эта возможность использовалась DMS на некоторых реальных языках 40+, включая полный IBM COBOL, PL/SQL, Java 1.8, С# 5.0, C (много диалектов) и С++ 14.

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

Ответ 3

Есть несколько генераторов синтаксических анализаторов, которые включают в себя реализацию unparser. Одним из них является генератор синтаксических анализаторов Nearley для контекстно-свободных грамматик.

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

Ответ 4

В общем случае это невозможно.

Что делает печать довольно красивой? Печать довольно красивая, если на этих позициях находятся пробелы, вкладки или символы новой строки, что делает печать красивой.

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

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

Ответ 5

Я реализовал набор Invertible Parser Combinators в Java и Kotlin. Парсер написан в значительной степени в стиле LL-1, и он предоставляет parse- и метод печати, где последний предоставляет симпатичный принтер.

Вы можете найти проект здесь: https://github.com/searles/parsing. Вот учебное пособие: https://github.com/searles/parsing/blob/master/tutorial.md. А вот и парсер/симпатичный принтер для математических выражений: https://github.com/searles/parsing/blob/master/src/main/java/at/searles/demo/DemoInvert.kt