Добрый ден, колеги!

Вопрос о возможностях ANTLR.
Интересно можно ли с его помощью сделать кодогенерацию на неизв. языке заданным кокой-то грамматикой?
В частности стоит задача сделать из SQL другое текстовое представление на другом формальном языке. Что мне придется таки делать руками, а чем я могу воспользоваться по максимуму в ANTLR?

В какую сторону копать?

Спасибо заранее

ANTLR по грамматике входного языка (наример, SQL) строит каркас проги на Java/C++, которая парсит текст на входном языке, строит дерево, а потом его обходит. Что именно делать при обходе дерева — генерить код или еще что — дело Ваше. Т.е. никто не мешает выдавать нечто на своем собственном языке.
Пример компилятора со своего языка в ассемблер малоизвестной виртуальной машины, сделанный с использованием ANTLR, можно найти у меня на сайте (см. профиль).

Здравствуйте, D. Mon, Вы писали:

Спасибо!
Т.е. ANTLR не решает сам проблему кодогенерации в язык отличный от целевого никак?

DM>ANTLR по грамматике входного языка (наример, SQL) строит каркас проги на Java/C++, которая парсит текст на входном языке, строит дерево, а потом его обходит. Что именно делать при обходе дерева — генерить код или еще что — дело Ваше. Т.е. никто не мешает выдавать нечто на своем собственном языке.
DM>Пример компилятора со своего языка в ассемблер малоизвестной виртуальной машины, сделанный с использованием ANTLR, можно найти у меня на сайте (см. профиль).

Я видел пару систем, которые генерят AST, трансформируют его по заданным правилам и генерят новый текст. К сожалению ссылок под рукой нет, но думаю, что гугл их знает.

_>Т.е. ANTLR не решает сам проблему кодогенерации в язык отличный от целевого никак?

А что Вы называете целевым языком?
В принципе, с тех пор как я с ним работал прошло не мало времени, может там чего добавили..

Здравствуйте, D. Mon, Вы писали:

Целевой язык — это тот я зык к которому выполнено преобразование (C#,Java,C++). Т.е. на каком языке получился результирующий код.

_>>Т.е. ANTLR не решает сам проблему кодогенерации в язык отличный от целевого никак?

DM>А что Вы называете целевым языком?
DM>В принципе, с тех пор как я с ним работал прошло не мало времени, может там чего добавили..

Здравствуйте, Delight, Вы писали:

Ясно. Меня больше интересуют возможности ANTLR в этом отношении. Самому из дерева можно чето сгенерить можно после любого генератора компиляторов.
Т.е. можно ли добиться от ANTLR большего нежели дерева?

D>Я видел пару систем, которые генерят AST, трансформируют его по заданным правилам и генерят новый текст. К сожалению ссылок под рукой нет, но думаю, что гугл их знает.

Здравствуйте, slava_529872, Вы писали:

_>Здравствуйте, Delight, Вы писали:

_>Ясно. Меня больше интересуют возможности ANTLR в этом отношении. Самому из дерева можно чето сгенерить можно после любого генератора компиляторов.
_>Т.е. можно ли добиться от ANTLR большего нежели дерева?

Сам ANTLR до третьей версии использовал для собственной кодогенерации паттерн Визитор. Сейчас они перешли на StringTemplate — тулзу вроде тех, которые используют для генерации веб страниц. Автоматизации вроде до сих пор нигде нет.
Я в свое время смотрел на ANTLR — но мне не понравилось — все очень сложно и запутанно на ровном месте. Из плюсов — ANTLR печатает AST в виде лисповских S-expressions — т.е. при определенной ловкости можно загрузить это в интерпретатор Scheme прямо "с листа" — для отладки может быть полезно.

Если у вас есть дерево — получить из него текстовое представление программы очень просто — это называется pretty-printing или unparsing.
Я, как раз на днях закончил подобную штуку — source-to-source компилятор Lua. Я просто переписал на Scala(язык на котором я преобразовывал AST) Вадлеровский pretty-printer — взял реализацию на Ocaml из Quest, и добавил в нее все фичи из ленивой Haskell PPrint. Цена вопроса — 200 строк библиотека, собственно принтер 100 строк, примерно одна строка на ноду. В результате я не просто печатаю код, а со всеми отступами, 78 колонок в ширину, при том каждая строка не длинее 40 символов и все сгруппировано.

Для парсера я взял XTC Rats! — генератор PEG парсеров на java. Он, как и ANTLR, умеет генерировать дерево прямо из граматтики, умеет сохранять parse-tree, что может быть полезно для рефакторинга (ANTLR использует для этого token-streams), дает расширять грамматику внешними модулями и содержит парсеры и претти-принтеры для Java и C(и еще кучу других прибамбасов, вроде генератора тип-чекеров). Единственное — документирован он сухо.

http://homepages.inf.ed.ac.uk/wadler/papers/prettier/prettier.pdf
http://legacy.cs.uu.nl/daan/download/pprint/pprint.html
http://www.st.cs.uni-sb.de/~lindig/#quest
http://cs.nyu.edu/rgrimm/xtc/rats.html

Здравствуйте, z00n, Вы писали:

Z>Если у вас есть дерево — получить из него текстовое представление програмhttp://www.rsdn.ru/Info/Howtoask.xml
Как правильно задавать вопросымы очень просто — это называется pretty-printing или unparsing.
Z>Я, как раз на днях закончил подобную штуку — source-to-source компилятор Lua. Я просто переписал на Scala(язык на котором я преобразовывал AST) Вадлеровский pretty-printer — взял реализацию на Ocaml из Quest, и добавил в нее все фичи из ленивой Haskell PPrint. Цена вопроса — 200 строк библиотека, собственно принтер 100 строк, примерно одна строка на ноду. В результате я не просто печатаю код, а со всеми отступами, 78 колонок в ширину, при том каждая строка не длинее 40 символов и все сгруппировано.

А где можно посмотреть пример pretty-printing и unparsing?

Здравствуйте, Аноним, Вы писали:
А>А где можно посмотреть пример pretty-printing и unparsing?

Возьмем для примера Lua, конструкция "Numeric For":

for i=1,10,5 do
  print(i)
end

Фрагмент грамматики (http://www.lua.org/manual/5.1/manual.html#8):

    
    chunk ::= {stat [';']} [laststat [';']]
    block ::= chunk

    stat  ::=  ...
          for Name '=' exp ',' exp [',' exp] do block end

AST node для него (на Scala) выглядит как-то так

case class ForNum(i:Id, x1:Expr, x2:Expr, step:Option[Expr], body:Block)  extends Stmt

Самый простой способ(и самый популярный) превратить AST обратно в код — просто
рекурсивно печатать его визитором, паттерн матчингом и.т.д

Т.е. заведем глобальную переменную "indent" и вспомогательную функцию spaces:
spaces(n:Int):String // выдает строку пробелов длинной 'n'

def printStmt(tree:Stmt) = tree match{
    ...
    ...
    case ForNum(i,x1,x2,opt_step,body) => {
        print(spaces(indent)); print("for ")
        printExpr(i); print("="); printExpr(x1); print(","); printExpr(x2);
        if (!opt_step.isEmpty){ print(","); printExpr(opt_step.get);}
        print("do"); print("\n");
        indent += indentStep;
        printBlock(body);
        indent -= indentStep;   
        print("\n");
        print(spaces(indent));
        print("end");
        print("\n")
    }
}

Примеры подобного кода можно найти в исходниках любого компилятора.


Теперь, способ, который нравится мне. Помимо всего прочего, он следит за шириной страницы и
автоматически напечатает пример в одну строку если места много.

-- много места:
for i=1,10 do A[i]=42; B[i]=0; end 

-- мало места:
for i=1,10 do 
    A[i]=42;
    B[i]=0;
end

Печататель дерева — функция из примено таких фрагментов, большинство из них намного короче:

implicit def pprintAST(tree:AST):Doc = tree match {
    ...
    ...
    case ForNum(i,x1,x2,opt_step,body) => {
    val step = opt_step match {case None => empty; case Some(x) => comma <> x}
    val header = i <> assign <> x1 <> comma <> x2 <> step
        enclose_br("for" <+> header <+> "do", body, "end")
    }
}

Комбинатор 'enclose_br', который годится для 90% стейтментов в Lua, выглядит так:

 def enclose_br(left:Doc,x:Doc,right:Doc):Doc = 
    align(left <> group(znest(line <> x) <$> right))

 def znest = nest(4, _:Doc) // indent - 4 spaces

Что означают комбинаторы nest, align, group, empty, <>, <+>, <$> etc, а также
другие интересные примеры можно посмотреть в документации к библиотеке Haskell PPrint, ссылку я уже давал: http://research.microsoft.com/users/daan/pprint.html

Здравствуйте, z00n, Вы писали:

Скажите пожалуйста, а есть ли языки для распечатки дерева или другие наработки, чтобы не печатать вручную. Т.к. входной и целевой языки не мапятся однозначно. Например оператору for во входном языке соответствует оператор while & for& do в выходном?

Z>Здравствуйте, Аноним, Вы писали:
А>>А где можно посмотреть пример pretty-printing и unparsing?

Z>Возьмем для примера Lua, конструкция "Numeric For":

Z>

Z>for i=1,10,5 do
Z>  print(i)
Z>end
Z>

Z>Фрагмент грамматики (http://www.lua.org/manual/5.1/manual.html#8):

Z>

    
Z>    chunk ::= {stat [';']} [laststat [';']]
Z>    block ::= chunk

Z>    stat  ::=  ...
Z>          for Name '=' exp ',' exp [',' exp] do block end
Z>

Z>AST node для него (на Scala) выглядит как-то так
Z>

Z>case class ForNum(i:Id, x1:Expr, x2:Expr, step:Option[Expr], body:Block)  extends Stmt
Z>

Z>Самый простой способ(и самый популярный) превратить AST обратно в код — просто
Z>рекурсивно печатать его визитором, паттерн матчингом и.т.д

Z>Т.е. заведем глобальную переменную "indent" и вспомогательную функцию spaces:
Z>spaces(n:Int):String // выдает строку пробелов длинной 'n'

Z>

Z>def printStmt(tree:Stmt) = tree match{
Z>    ...
Z>    ...
Z>    case ForNum(i,x1,x2,opt_step,body) => {
Z>        print(spaces(indent)); print("for ")
Z>        printExpr(i); print("="); printExpr(x1); print(","); printExpr(x2);
Z>        if (!opt_step.isEmpty){ print(","); printExpr(opt_step.get);}
Z>        print("do"); print("\n");
Z>        indent += indentStep;
Z>        printBlock(body);
Z>        indent -= indentStep;   
Z>        print("\n");
Z>        print(spaces(indent));
Z>        print("end");
Z>        print("\n")
Z>    }
Z>}
Z>

Z>Примеры подобного кода можно найти в исходниках любого компилятора.


Z>Теперь, способ, который нравится мне. Помимо всего прочего, он следит за шириной страницы и
Z>автоматически напечатает пример в одну строку если места много.
Z>

Z>-- много места:
Z>for i=1,10 do A[i]=42; B[i]=0; end 

Z>-- мало места:
Z>for i=1,10 do 
Z>    A[i]=42;
Z>    B[i]=0;
Z>end
Z>

Z>Печататель дерева — функция из примено таких фрагментов, большинство из них намного короче:
Z>

Z>implicit def pprintAST(tree:AST):Doc = tree match {
Z>    ...
Z>    ...
Z>    case ForNum(i,x1,x2,opt_step,body) => {
Z>    val step = opt_step match {case None => empty; case Some(x) => comma <> x}
Z>    val header = i <> assign <> x1 <> comma <> x2 <> step
Z>        enclose_br("for" <+> header <+> "do", body, "end")
Z>    }
Z>}
Z>

Z>Комбинатор 'enclose_br', который годится для 90% стейтментов в Lua, выглядит так:
Z>

Z> def enclose_br(left:Doc,x:Doc,right:Doc):Doc = 
Z>    align(left <> group(znest(line <> x) <$> right))

Z> def znest = nest(4, _:Doc) // indent - 4 spaces
Z>

Z>Что означают комбинаторы nest, align, group, empty, <>, <+>, <$> etc, а также
Z>другие интересные примеры можно посмотреть в документации к библиотеке Haskell PPrint, ссылку я уже давал: http://research.microsoft.com/users/daan/pprint.html

Здравствуйте, slava_529872, Вы писали:

_>Здравствуйте, z00n, Вы писали:

_>Скажите пожалуйста, а есть ли языки для распечатки дерева или другие наработки, чтобы не печатать вручную. Т.к. входной и целевой языки не мапятся однозначно. Например оператору for во входном языке соответствует оператор while & for& do в выходном?

Переписывание программы с одного языка на другой — это и есть компиляция. Например компилятор С++ переписывает программу на ассемблере, возможно(но не обязательно) попутно выполняя некоторые оптимизации.
For с одного языка, как раз скорее всего совершенно одназначно семантически соответствует while for и do на другом. Любой императивный цикл — это if + goto.
В вашем случае вам, наверное, придется воспроизвести сл. цепочку:
text1 -> parse -> parse_tree1 -> AST1 -> compile(tree:AST1):AST2 -> AST2 -> unparse -> text2

Насчет автоматизации: генераторы парсеров автоматизируют text->parse_tree, иногда сразу строят AST в некой общей форме (тогда может понадобится его упрощение, небольшие трансформации). Некоторые системы имеют в своем составе DSL позволяющие описать трансформации AST, но сколько-нибудь нетривиальный компилятор вам придется писать самому. Анпарсер, в случае, если AST1 и AST2 разные — скорее всего тоже самому. Готовые решения есть для популярных языков — С, Java, в Lisp оно встроено be design. Но врядли это то, что вам нужно.

Из 'тонкого' могу посоветовать почитать
http://www.itu.dk/courses/PFOO/F2006/
http://www.itu.dk/people/sestoft/papers/plc-0.34-2up.pdf