Разбор исходного кода и макроподобная обработка аналогичных конструкций

Question

TL; DR VERSION: Существует ли генератор синтаксического анализатора, который поддерживает следующее: когда некоторое правило уменьшается (я предполагаю, что парсер LALR (1)), то восстановление не выполняется , но парсер отступает и заменяет ввод другим кодом, используя значения из этого правила, и анализирует этот код. При необходимости повторите. Так что, если код «я ++» и правило «выраж POST_INCR», я могу сделать больше или меньше:

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)" 

Так basicaly код перезаписи с помощью макросов?

LONG VERSION:

я написал еще один простой интерпретируемый язык (в Java для простоты). Он работает нормально, но он поднял какой-то вопрос. Введение довольно длинное, но простое и помогает ясно показать мою проблему (я думаю).

У меня есть «while» loop. Это довольно просто, учитывая:

WHILE LPARE boolean_expression RPAREN statement 

я произвожу более или менее следующее:

new WhileNode(boolean_expression, statement); 

Это создает новый узел, при посещении позже, генерирует код для моей виртуальной машины. Но у меня есть следующие:

FOR LPAREN for_init_expr SEMICOLON boolean_expression SEMICOLON for_post_expr RPAREN statement 

Это «цикл» известно из Java или C. Из вышеуказанного правила создать более или менее следующее:

new ListNode(
    for_init_expr, 
    new WhileNode(
     boolean_expression, 
     new ListNode(
      statement, 
      new ListNode(for_post_expr, null)))) 

Это, конечно, простое преобразование от:

for (for_init ; boolean_expression ; for_post_expr) 
    statement 

к:

for_init 
while (boolean_expression) { 
    statement 
    for_post_expr; 
} 

Все это хорошо и денди, но все становится волосатым для следующего:

FOR LPAREN var_decl COLON expression RPAREN statement 

это, если хорошо известно и полюбились:

for (int x : new int[] { 1, 2 }) 
    print(x); 

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

int[] tmp = new int[] { 1, 2 }; 
for (int it = 0 ; it < tmp.length; it = it + 1) { 
    int x = tmp[it]; 
    print(x); 
} 

И так как я не использую типа, я просто предположим, что «выражение» (так с правой стороны, после двоеточия) является то, что я могу перебрать (и массивы не итерацию), Я вызываю функцию на результат этого «выражения», который возвращает экземпляр Iterable. Так, в самом деле, мой переписан код не так просто, как один выше, более или менее это:

Iterator it = makeIterable(new int[] { 1, 2 }); 
while (it.hasNext()) { 
    int x = it.next(); 
    print(x); 
} 

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

113  | FOR LPAREN var_decl_name.v PIPE simple_value_field_or_call.o RPAREN statement.s 
114           {: Symbol sv = ext(_symbol_v, _symbol_o); 
115           String autoVarName = generateAutoVariableName(); 
116           Node iter = new StatementEndNode(sv, "", 
117            new BinNode(sv, CMD.SET, "=", 
118             new VarDeclNode(sv, autoVarName), 
119             new CallNode(sv, "()", 
120              new BinNode(sv, CMD.DOT, ".", 
121               new MkIterNode(sv, o), 
122               new PushConstNode(sv, "iterator"))))); 
123           Node varinit = new StatementEndNode(sv, "", 
124            new BinNode(sv, CMD.SET, "=", 
125             v, 
126             new PushConstNode(sv, "null"))); 
127           Node hasnext = new CallNode(sv, "()", 
128            new BinNode(sv, CMD.DOT, ".", 
129             new VarNode(sv, autoVarName), 
130             new PushConstNode(sv, "hasNext"))); 
131           Node vargennext = new StatementEndNode(sv, "", 
132            new BinNode(sv, CMD.SET, "=", 
133             new VarNode(sv, v.name), 
134             new CallNode(sv, "()", 
135              new BinNode(sv, CMD.DOT, ".", 
136               new VarNode(sv, autoVarName), 
137               new PushConstNode(sv, "next"))))); 
138           return new ListNode(sv, "", 
139            new ListNode(sv, "", 
140             new ListNode(sv, "", 
141              iter 
142             ), 
143             varinit 
144            ), 
145            new WhileNode(sv, "while", 
146             hasnext, 
147             new ListNode(sv, "", 
148              new ListNode(sv, "", 
149               vargennext 
150              ), 
151              s))); 

Чтобы ответить на ваши вопросы: да, я стыжусь этого кода.

ВОПРОС: Есть генератор синтаксических анализаторов, пусть это мне сделать что-то об этом, а именно данное правило:

FOR LPAREN var_decl COLON expr RPAREN statement 

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

FOR LPAREN var_decl COLON expr RPAREN statement = 
    { with [ x = generateAutoName(); ] 
     emit [ "Iterator $x = makeIterable($expr).iterator();" 
       "while (${x}.hasNext()) {" 
       "$var_decl = ${x}.next();" 
       "$statement" 
       "}" 
     ] 
    } 

Я не знаю, если это хорошо известно проблема или нет, я просто даже не знаю, что искать - самый похожий вопрос, который я нашел, это один: Any software for pattern-matching and -rewriting source code?, но он нигде не близок к тому, что мне нужно, поскольку он должен работать как отдельный шаг а не во время компиляции, поэтому он не подходит.

Любая помощь будет оценена по достоинству.

Answer 1

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

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

Если вам нужен более структурированный подход, вы можете построить свой АСТ, а затем использовать преобразования источника в источник, чтобы «переписать» макросы в их содержимое. DMS Software Reengineering Toolkit можете сделать это, вы можете прочитать подробнее о том, что transforms look like.

Используя подход DMS, ваша концепция:

expr POST_INCR -> "(tmp = expr; expr = expr + 1; tmp)" 

требует разбора исходного текста в обычном способом с грамматическим правилом:

term = expr POST_INCR ; 

Вы бы дать все эти правила грамматики к DMS и пусть он разобрать источник и построить свой АСТ в соответствии с грамматикой.

Затем нанесите переписывают DMS к полученному дереву:

domain MyToyLanguage; -- tells DMS to use your grammar to process the rule below 

rule replace_POST_INCR(e: expr): term->term 
    = "\e POST_INCR" -> " (tmp = \e; \e = \e + 1; tmp) "; 

Кавычки здесь «домен мета кавычки», а не строковый литерал кавычки. Текст за пределами двойных кавычек - это синтаксис правила DMS. Текст внутри кавычек является синтаксисом вашего языка (MyToyLangauge) и анализируется с использованием предоставленного вами парсера, а также некоторых специальных экранов для переменных шаблона, таких как \ e. (Вам не нужно ничего делать с грамматикой, чтобы получить эту возможность разбора шаблонов, DMS позаботится об этом).

По соглашению с DMS мы часто называем буквенные жетоны, такие как POST_INCR с цитированным эквивалентом «++» в лексере, вместо использования такого имени. Вместо

#token POST_INCR "\+\+" 

правило лексера тогда выглядит следующим образом:

#token '++' "\+\+" 

Если вы сделаете это, то ваше правило грамматики читается как:

term = expr '++' ; 

и ваше правило переписывания теперь выглядит следующим образом :

rule replace_POST_INCR(e: expr): term->term 
    = "\e++" -> " (tmp = \e; \e = \e + 1; tmp) "; 

Следуя этому соглашению, грамматика (lexer и BNF) (IMHO) намного читаема, и правила перезаписи также более читаемы, так как они остаются чрезвычайно близкими к фактическому синтаксису языка.

Answer 2

Возможно, вы ищете что-то вроде правил перезаписи дерева ANTLR.

Возможно, вы можете улучшить свой синтаксис конструкции AST, определив некоторые вспомогательные функции. На мой взгляд, существует много избыточности (зачем вам нужно перечисление и строку символов для оператора?), Но я не программист на Java.

Один из подходов можно принять:

Пуск с анализатором, который уже продуцирует AST. Добавьте лексический синтаксис или два для обработки аргументов шаблона и gensyms. Затем напишите AST Walker, который сериализует AST в код (Java или байт-код), необходимый для восстановления AST. Используя это, вы можете генерировать функции шаблонов макросов, используя собственный синтаксический анализатор, что означает, что он будет автоматически синхронизироваться с любыми изменениями, которые могут быть внесены в ваш АСТ.