Как реализовать компьютерный переводчик языка с использованием двух отдельных грамматик

Я хочу создать компьютерный переводчик языка между двумя языками LANG1 и LANG2. Более конкретно, я хочу перевести код, написанный на LANG1, в исходный код на LANG2.

У меня есть грамматика BNF для LANG1 и LANG2.

LANG1-это небольшой DSL, который я написал сам, и, по сути, является "более легкой" версией LANG2.

Я хочу иметь возможность генерировать операторы в LANG2, из входных операторов, написанных в LANG1.

Я нахожусь в процессе компиляции a компилятор для LANG1, но я не знаю, что делать дальше (для того, чтобы перевести операторы LANG1 в операторы LANG2).

Мое понимание соответствующих шагов таково: 

1. BNF for my DSL (LANG1)                                  DONE
2. Reverse engineered the BNF for LANG2                    DONE
3. Learning how to generate a compiler for LANG1           TODO
4. Translate LANG1 statements to LANG2 statements          ???

Каковы шаги, необходимые для генерации операторов LANG2 из операторов LANG1?

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

PS: Я буду использовать ANTLR3 для создания компилятора для LANG1

1 3
c++ compiler-construction antlr3

1 ответ:

В самом общем случае вы должны перевести каждый возможный раздел грамматики из LANG1 во что-то подходящее для LANG2, или вы должны заглушить простейшие возможные примитивы обоих языков, такие как ассемблеры или комбинаторы. Это немного отнимает время и не очень весело.

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

EDIT: поскольку я только что перечитал ваш вопрос, понял, что вы хотите перевести только один способ, вам нужно только беспокоиться о том, чтобы сделать форму дерева подходящей LANG1 и просто иметь свою функцию перевода для LANG2. Но я надеюсь, что мой пример все равно будет полезен.

Пример построения дерева:

Вот два различные грамматики ANTLR, которые производят один и тот же чрезвычайно простой AST:

Грамматика 1

Первый из них является стандартным способом выражения дополнение:

grammar simpleAdd;

options {output=AST;}

tokens {
    PLUS = '+';
}

expression : addition EOF!;
addition   : NUMBER (PLUS NUMBER)+ -> ^(PLUS NUMBER*);

NUMBER     :'0'..'9'+;
WHITESPACE : ( '\t' | ' ' | '\r' | '\n')+    { $channel = HIDDEN; } ;

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

1 + 1 + 2 + 3 + 5

Грамматика 2

Вторая грамматика принимает менее изящную форму: 

grammar horribleAdd;

options {output=AST;}

tokens {
    PLUS = '+';
    PLUS_FUNC = 'plus';
    COMMA = ',';
    LEFT_PARENS ='(';
    RIGHT_PARENS=')';
} 

expression : addition EOF!;
addition   : PLUS_FUNC LEFT_PARENS NUMBER (COMMA NUMBER)+ RIGHT_PARENS -> ^(PLUS NUMBER*);

NUMBER     :'0'..'9'+;
WHITESPACE : ( '\t' | ' ' | '\r' | '\n')+    { $channel = HIDDEN; } ;

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

plus(1, 1, 2, 3, 5)
Он производит точно такое же дерево, как и первая грамматика (плюс узел с числами в качестве потомков). Теперь вам не нужно беспокоиться о том, с какого языка пришли ваши инструкции, вы можете выводить их в любой форме, которая вам нравится. Все, что вам нужно сделать, это написать функцию, которая может преобразовать этот AST обратно в язык по вашему выбору.
4