Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 15.12.08 10:33
Оценка: 9 (2)
Как-то заинтересовала меня тема языковых преобразований (source code transformation) и в качестве эксперимента я написал преобразователь из Java в Tcl на TXL:
java2tcl
В целом могу сказать что задумка получилась. Присутствуют много упрощений, которые в общем-то решаемы, но требуют перехода на другой уровень работы (например, построение справочника по конвертируемым и используемым классам).
Сам TXL будет немного сложноват для освоения в зависимости от предыдущего опыта работы с ФЯ, лиспом и т.п. Но после освоения все представляется намного проще.
Re: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 15.12.08 11:17
Оценка:
Здравствуйте, msorc, Вы писали:

M>Как-то заинтересовала меня тема языковых преобразований (source code transformation) и в качестве эксперимента я написал преобразователь из Java в Tcl на TXL:


Почему TXL? Я в свое время его смотрел и меня он не устроил тем что негибок (я долго пытался понять, что делать с частями грамматика, которые невыразимы в BNF) и закрыт.
Re[2]: Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 15.12.08 11:51
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Почему TXL? Я в свое время его смотрел и меня он не устроил тем что негибок (я долго пытался понять, что делать с частями грамматика, которые невыразимы в BNF) и закрыт.


Я критерий отбора средств для преобразования не строил. Все проверять, изучать и сравнивать — не хотел тратить время.
В конечном итоге выбор пал на TXL и StrategoXT. Они наиболее явно упоминались в сети как средства преобразования и документация, примеры, живое сообщество было в наличии у обоих. С TXL получилось быстрее разобраться "из коробки", поэтому остановился на нем. Довольно просто работать с деревом AST при преобразовании, когда более менее разобрался что к чему. С интересом бы поговорил с человеком, разбирающимся в StrategoXT или других подобных средствах, но тяжко найти такого по близости.
Закрытость меня не смущает, к тому же автор(ы) обещают вскоре открыть исходники.
По поводу частей невыразимых в ВNF — это надо смотреть на частный случай. Возможно какие-то части грамматики можно обработать сторонним препроцессором или сторонним преобразователем.
Re: Преобразование Java -> Tcl с помощью TXL
От: Victor Repetsky Украина  
Дата: 19.12.08 10:06
Оценка:
Здравствуйте, msorc, Вы писали:

M>Как-то заинтересовала меня тема языковых преобразований (source code transformation) и в качестве эксперимента я написал преобразователь из Java в Tcl на TXL:

M>java2tcl
M>В целом могу сказать что задумка получилась. Присутствуют много упрощений, которые в общем-то решаемы, но требуют перехода на другой уровень работы (например, построение справочника по конвертируемым и используемым классам).
M>Сам TXL будет немного сложноват для освоения в зависимости от предыдущего опыта работы с ФЯ, лиспом и т.п. Но после освоения все представляется намного проще.

Делал несколько похожих проектов (не на TXL). Сложилось следующее категорическое мнение оп поводу используемых средств.
Преобразование можно условно разделить на этапы
1. Лексический и синтаксический разбор.
2. Многоэтапный анализ-обогащение (сбор информации о типах, об истории использования переменных, установка всевозможных взаимосвязей, и т.п.).
3. Синтез целевого кода.
По сложности и временным затратам если писать с нуля, то отношение приблизительно 10%-88%-2%. Так вот по поводу средств:
1. Нужно брать готовый парсер, для большинства современных языков есть выбор качественных парсеров. Писать парсер на TXL только чтобы получить AST пригодное для обработки этим же TXL по-моему не рационально.
2. Здесь нужен эффективный язык запросов и набор рулов в стиле запрос->действие или запрос->данные. Причем запросы могут быть как по исходному AST, так и промежуточным данным. Опять же по субъективному мнению лучший язык запросов по древовидным данным — XPath, подход запрос->действие удобнее где-то в 7 из 10 случаев. Использовал успешно комбинацию XSLT и императивных скриптов с поддержкой XPath, также использовал Visitor для AST в виде объектов — не так удобно, но тоже жить можно. Рулы в TXL мне показались менее выразительным из-за многословного where (возможно ошибаюсь, сразу вопрос как будет выглядеть, например, поиск throw в finaly (XPath://FinallyStatement[descendant::ThrowStatement]), или поиск пустых catch (XPath://CatchStatement[count(Block/BlockStatement) = 0])).
3. Если есть вся необходимая информация (целевой AST), то почти все равно на чем делать. Сам успешно использовал XSLT, и (где целевое AST было в виде дерева объектов) паттерны Composite и Visitor.
SCJP, SCEA
Re[2]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 19.12.08 14:14
Оценка:
Здравствуйте, Victor Repetsky, Вы писали:

VR>Преобразование можно условно разделить на этапы

VR>1. Лексический и синтаксический разбор.
VR>2. Многоэтапный анализ-обогащение (сбор информации о типах, об истории использования переменных, установка всевозможных взаимосвязей, и т.п.).
VR>3. Синтез целевого кода.
VR>По сложности и временным затратам если писать с нуля, то отношение приблизительно 10%-88%-2%.

У меня в свое время другие числа получились, где то 30-20-50.
... << RSDN@Home 1.2.0 alpha 4 rev. 1127 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[3]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 19.12.08 18:19
Оценка:
Здравствуйте, AndrewVK, Вы писали:

VR>>По сложности и временным затратам если писать с нуля, то отношение приблизительно 10%-88%-2%.


AVK>У меня в свое время другие числа получились, где то 30-20-50.


То есть ты писал pretty-printer.
У меня ближе к 5%-90%-5%, если учитывать весь вспомогательный код по работе с деревом.
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[4]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 20.12.08 00:57
Оценка:
Здравствуйте, mkizub, Вы писали:

M>То есть ты писал pretty-printer.


Нет, транслятор с одного языка на другой.
... << RSDN@Home 1.2.0 alpha 4 rev. 1127 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[3]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 20.12.08 01:25
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>У меня в свое время другие числа получились, где то ..-..-50.


Оп-па! А что так?. Я для своего луа-компилятора тупо переписал на Scala PPrint (это Wadler's "prettier printer") ~ 250 строк. Сам претти принтер всего языка занял ~220 строк. При этом он довольно непрост — учитывает при форматировании ширину листа и процент заполнения строки.

Больше всего я просидел с парсером, потому-что перепробывал Ocaml, Haskell, ASF+SDF, смотрел на TXL. Мне хотелось в будущем свободно расширять грамматику, поэтому LALR отпал почти сразу, SDF2 (и весь этот комплекс в целом ASF/SDF/Stratego) — показался излишне монстуозным. Остановился в конце-концов на PEG парсере из XTS Rats! Тут все работало как обещали, но я решил не трогать эти ужасные визиторы — засосал parsing-tree в Scala, преобразовал там в типизированное AST, по которому ходил паттерн-матчингом. Преимущества терм-рерайтинга (как в TXL или Stratego) перед паттерн-матчингом мне до сих пор непонятны.
Re[4]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 20.12.08 01:38
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Оп-па! А что так?. Я для своего луа-компилятора тупо переписал на Scala PPrint (это Wadler's "prettier printer") ~ 250 строк. Сам претти принтер всего языка занял ~220 строк.


Мне вот интересно, с чего вы оба решили, что синтез целевого языка это всегда исключительно претти принтер? Это так только в случае крайней близости языков. А, к примеру, для трансляции C++ в С# на этапе синтеза придется полностью реализовать движок плюсовых шаблонов, а в обратном направлении механику преобразования итераторов в стейт машину.
... << RSDN@Home 1.2.0 alpha 4 rev. 1127 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[5]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 20.12.08 01:52
Оценка:
Здравствуйте, AndrewVK, Вы писали:

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


AVK>Мне вот интересно, с чего вы оба решили, что синтез целевого языка это всегда исключительно претти принтер? Это так только в случае крайней близости языков. А, к примеру, для трансляции C++ в С# на этапе синтеза придется полностью реализовать движок плюсовых шаблонов, а в обратном направлении механику преобразования итераторов в стейт машину.


VR>По сложности и временным затратам если писать с нуля, то отношение приблизительно 10%-88%-2%.
VR>3. Если есть вся необходимая информация (целевой AST), то почти все равно на чем делать. Сам успешно использовал XSLT, и (где VR>целевое AST было в виде дерева объектов) паттерны Composite и Visitor.


"Синтез целевого языка" — ввел VR — это не то чтобы устоявшийся термин. Он очевидно назвал так претти-принтинг, поскольку "[уже] есть вся необходимая информация (целевой AST)" и заняло это 2% времени.
Re[6]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 20.12.08 02:39
Оценка:
Здравствуйте, z00n, Вы писали:

Z>"Синтез целевого языка" — ввел VR — это не то чтобы устоявшийся термин. Он очевидно назвал так претти-принтинг


ИМХО совсем не очевидно.

Z>, поскольку "[уже] есть вся необходимая информация (целевой AST)" и заняло это 2% времени.


Где тогда преобразование из AST одного языка в AST другого?
... << RSDN@Home 1.2.0 alpha 4 rev. 1127 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[7]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 20.12.08 06:08
Оценка:
Здравствуйте, AndrewVK, Вы писали:

Z>>, поскольку "[уже] есть вся необходимая информация (целевой AST)" и заняло это 2% времени.


AVK>Где тогда преобразование из AST одного языка в AST другого?


Я бы поставил на пункт 2.
Re[4]: Преобразование Java -> Tcl с помощью TXL
От: mkizub Литва http://symade.tigris.org
Дата: 20.12.08 08:39
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Мне хотелось в будущем свободно расширять грамматику,


Наверное, для расширения языка?

Z>Преимущества терм-рерайтинга (как в TXL или Stratego) перед паттерн-матчингом мне до сих пор непонятны.


Видимо, потому, что расширять язык ты так и не начал.
Паттерн-мэтчинг работает только в нерасширяемом языке. Если ты туда что-то добавляешь — тебе надо перелопатить весь код. После 3-4-х подобных добавлений ты и добъёшься просветления в ответе на этот вопрос.
SOP & SymADE: http://symade.tigris.org , блог http://mkizub.livejournal.com
Re[7]: Преобразование Java -> Tcl с помощью TXL
От: Victor Repetsky Украина  
Дата: 20.12.08 09:30
Оценка:
Здравствуйте, AndrewVK, Вы писали:

Z>>, поскольку "[уже] есть вся необходимая информация (целевой AST)" и заняло это 2% времени.

AVK>Где тогда преобразование из AST одного языка в AST другого?

Прошу прощения за неточные термины. Имел ввиду, что вся информация для генерации целевого кода, то есть целевой AST, собрана на 2 этапе. Выделил отдельно прити-принт для того что бы указать что это можно делать отдельным механизмом (в TXL все делается его средствами).
SCJP, SCEA
Re[5]: Преобразование Java -> Tcl с помощью TXL
От: z00n  
Дата: 20.12.08 10:24
Оценка:
Здравствуйте, mkizub, Вы писали:

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


Z>>Мне хотелось в будущем свободно расширять грамматику,


M>Наверное, для расширения языка?

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

Z>>Преимущества терм-рерайтинга (как в TXL или Stratego) перед паттерн-матчингом мне до сих пор непонятны.


M>Видимо, потому, что расширять язык ты так и не начал.

M>Паттерн-мэтчинг работает только в нерасширяемом языке. Если ты туда что-то добавляешь — тебе надо перелопатить весь код. После 3-4-х подобных добавлений ты и добъёшься просветления в ответе на этот вопрос.

Грамматика расширений, которую я дописал, уже превосходит в размерах оригинальную грамматику луа. К 240 строкам оригинальной грамматики я дописал 350 строк расширений. Богатый паттерн-матчинг, функции задаваемые паттерн матчингом, списки в стиле ML: x::y::[], инфиксные и префиксные операторы, '$' оператор как в Haskell, короткая запись лямбд, имена бинарных функций как инфиксные операторы и еще что-то по мелочи (например опциональная совместимость вывода с Lua 5.0.x).

Писал я на Scala и сделал следующее:
— Унаследовал HyperAST от LuaAST
— Функция "compile" — неявное преобразование расширенного AST в оригинальное(на самом деле это 2 функции совокупным весом 40 строк).

Перелопачивать ничего не нужно. Единственное место — преобразование parse-tree -> AST — дописываются новые клаузы, и все. От этого тоже можно было избавиться, но я от лени использую "generic" parse-tree от XTC Rats!, а можно было бы все это в грамматике описывать как semantic actions.

Я постоянно дописываю всякую фигню и переписываю старую. Просветления все нет
Re[2]: Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 20.12.08 15:13
Оценка:
Здравствуйте, Victor Repetsky, Вы писали:

VR>Преобразование можно условно разделить на этапы

В TXL работа делиться на три этапа: парсинг, преобразование, синтез (они их называют — parse, transform, unparse). Причем вручную парсингом и синтезом заниматься не приходится, TXL сам проводит парсинг и pretty-printing по грамматике. Грамматика включает в себя символы управления печати — смещение, перевод строки, пробелы, поэтому код после преобразования из AST форматируется автоматом.

VR>По сложности и временным затратам если писать с нуля, то отношение приблизительно 10%-88%-2%.

Если для входного языка уже есть готовая грамматика для TXL, то я бы оценил первый этап в 0%. Третий этап тоже в общем-то от 0 процентов до 10, в зависимости от того была ли грамматика для целевого языка и как делались преобразования.

VR>1. Нужно брать готовый парсер, для большинства современных языков есть выбор качественных парсеров. Писать парсер на TXL только чтобы получить AST пригодное для обработки этим же TXL по-моему не рационально.

Как я уже говорил парсер писать не нужно.

VR>2. Здесь нужен эффективный язык запросов и набор рулов в стиле запрос->действие или запрос->данные. Причем запросы могут быть как по исходному AST, так и промежуточным данным. Опять же по субъективному мнению лучший язык запросов по древовидным данным — XPath, подход запрос->действие удобнее где-то в 7 из 10 случаев. Использовал успешно комбинацию XSLT и императивных скриптов с поддержкой XPath, также использовал Visitor для AST в виде объектов — не так удобно, но тоже жить можно. Рулы в TXL мне показались менее выразительным из-за многословного where (возможно ошибаюсь, сразу вопрос как будет выглядеть, например, поиск throw в finaly (XPath://FinallyStatement[descendant::ThrowStatement]), или поиск пустых catch (XPath://CatchStatement[count(Block/BlockStatement) = 0])).

В TXL в основном преобразования задаются правилами шаблон->действия->замена. Вопрос запросов тоже решаем подобным образом. В некоторых случаях правила на TXL кажутся избыточными и могли бы быть описаны более компактно, если бы язык обладал свойствами языка более высокого уровня.
Да, правила в TXL выглядят не так выразительно и наверное будут зависеть от целей который преследуются при поиске. Например, пустой catch (если я правильно понял что такое пустой catch):
rule doSomethingWithEmptyCatch
  replace [catch_statement]
    'catch '( _ [repeat modifier] _ [type_specifier] _ [variable_name] ') '{ '}
  % необходимые действия

Затем это правило применяется к требуемой ветви дерева или всей программе.
Re[8]: Преобразование Java -> Tcl с помощью TXL
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 20.12.08 15:33
Оценка:
Здравствуйте, Victor Repetsky, Вы писали:

VR>Прошу прощения за неточные термины. Имел ввиду, что вся информация для генерации целевого кода, то есть целевой AST, собрана на 2 этапе. Выделил отдельно прити-принт для того что бы указать что это можно делать отдельным механизмом (в TXL все делается его средствами).


Просто у меня структура преобразователя несколько иная была. Она состояла из 3 больших частей:
1) Парсер. Просто преобразует исходный код в AST. Проверяет синтаксическую корректность входного кода.
2) Компилятор. Преобразует AST в специальное промежуточное представление, в котором разресолвлены символьные ссылки и устранена избыточность в некоторых случаях. Кроме того, компилятор проверяет семантическую корректность (к примеру, контроллирует соответствие типов). Промежуточное представление может быть сохранено на диск, так как на этапе компиляции диалект целевого языка может быть неизвестен.
3) Генератор. Формирует из промежуточного кода код на целевом языке. При этом синтез конструкций целевого языка происходит именно на этом этапе. Отдельного претти принтера как такового просто нет, так как особая нужда в нем просто отсутствует.
Соответственно, по объему работ для каждой части и получается 20-30-50.
... << RSDN@Home 1.2.0 alpha 4 rev. 1132 on Windows Vista 6.0.6001.65536>>
AVK Blog
Re[3]: Преобразование Java -> Tcl с помощью TXL
От: msorc Грузия  
Дата: 20.12.08 15:38
Оценка:
M> Грамматика включает в себя символы управления печати — смещение, перевод строки, пробелы, поэтому код после преобразования из AST форматируется автоматом.
Вот пример из грамматики Java.
define switch_alternative
    [switch_label]                             [IN][NL]
        [repeat declaration_or_statement]      [EX]
end define

Управляющие символы INdent, EXdent, NewLine, в соответствии с которыми и выводится результат. Например такой:

case 'A':
  i = 9;
Re[3]: Предлагают работу: два дня в растерянности:(
От: msorc Грузия  
Дата: 20.12.08 15:39
Оценка:
M> Грамматика включает в себя символы управления печати — смещение, перевод строки, пробелы, поэтому код после преобразования из AST форматируется автоматом.
Вот пример из грамматики Java.
define switch_alternative
    [switch_label]                             [IN][NL]
        [repeat declaration_or_statement]      [EX]
end define

Управляющие символы INdent, EXdent, NewLine, в соответствии с которыми и выводится результат. Например такой:

case 'A':
  i = 9;
Re[3]: Преобразование Java -> Tcl с помощью TXL
От: Victor Repetsky Украина  
Дата: 22.12.08 08:58
Оценка:
Здравствуйте, msorc, Вы писали:


M>Да, правила в TXL выглядят не так выразительно и наверное будут зависеть от целей который преследуются при поиске. Например, пустой catch (если я правильно понял что такое пустой catch):

M>
M>rule doSomethingWithEmptyCatch
M>  replace [catch_statement]
M>    'catch '( _ [repeat modifier] _ [type_specifier] _ [variable_name] ') '{ '}
M>  % необходимые действия
M>

M>Затем это правило применяется к требуемой ветви дерева или всей программе.

Не совсем понятно, по виду этого правила кажется что мы оперируем на уровне текста а не AST?
SCJP, SCEA
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.