В документации и примерах идущих вместе с АНТЛРом автора настоятельно рекомендуют строить транслятор из двух чстей:
1) парсер входного языка, который проверяет синтаксис и строит АSТ (Abstract Syntax Tree)
2) парсер этого АСТ, который выписывает результат на выходном языке

Вопрос: а где в такой схеме проверять семантику? Например двойное объявление переменной, соответствие значения нужному типу?

Пока что я написал, только парсер, в который запихнул семантический проверки. Но попути оказалось, что у меня в некоторой моей структуре данных уже есть вся информация нужная для представления на выходном языке. Зачем тогда нужен парсер дерева?

Кстати точно такая же технология используется в самом АНТЛРе, где есть только лексер и парсер, который наполняет какие то внутренние структуры

Кто что думает по этому поводу?

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

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

Недостаток --- потеря производительности и увеличение общего объема текста.
(Даже если использовать нечто вроде паттерна Visitor).

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

GA>Кто что думает по этому поводу?

Решая подобную задачу, я написал лексер и парсер входного языка при помощи которых построил AST на собственных классах (ANTLR это позволяет). Затем я написал несколько классов, каждый из которых представляет реализацию визитора для полученного дерева. Один из этих классов проверяет ошибки, такие как двойное объявление переменной или несоответсвие типа. Другие — транслируют разобранные и проверенные конструкции в другие представления.

Здравствуйте, swamper, Вы писали:
S>Решая подобную задачу, я написал лексер и парсер входного языка при помощи которых построил AST на собственных классах (ANTLR это позволяет).
А какова в данном случае полезная функция у АСТ? Если строить просто обычные классы-контейнеры?
S>Затем я написал несколько классов, каждый из которых представляет реализацию визитора для полученного дерева. Один из этих классов проверяет ошибки, такие как двойное объявление переменной или несоответсвие типа. Другие — транслируют разобранные и проверенные конструкции в другие представления.
переварил.... спасибо.... думаю как использовать...

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

SG>Иногда семантику можно проверять по ходу разбора (т.е. построения дерева), иногда можно, но сложно,
SG>а иногда просто нельзя. Если нельзя или сложно, то можно устроить отдельный рекурсивный обход по дереву
SG>только для семантики.
Тут как раз все просто и за один проход вся семантика проверяется.... Просто смутило, зачем они так настоятельно рекомендуют использовать Три-парсеры
SG>Недостаток --- потеря производительности и увеличение общего объема текста.
SG>(Даже если использовать нечто вроде паттерна Visitor).
Хорошо... а как быть если выходных языков 2? при чем один из них это ХМЛ, т.е. уже заведомо дерево...

Здравствуйте, Graf Alex, Вы писали:
GA>Хорошо... а как быть если выходных языков 2? при чем один из них это ХМЛ, т.е. уже заведомо дерево...
Я бы использовал Visitor, потому как где 2, там и больше, а собственно
действия обычно определяются самой вершиной и ее непосредственными соседями.

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

Здравствуйте, System Goose, Вы писали:
SG>Сопоставлять с образцом собственно дерево бывает полезно в кодогенераторах,
SG>но мне кажется, что там так легко не отделаться и придется свой
SG>алгоритм писать (во многих кодогенераторах ищется оптимальное
SG>покрытие дерева паттернами, соответственно приходится нечто вроде
SG>динамического программирования использовать, иначе перебор будет
SG>неприемлемо долгим).
А можно с этого места поподробнее?
Что значит покрытие дерева паттернами и где возникает перебор?

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

Для пирмера сузим задачу до следующей: входной язык — паскаль, выходной — С.

Как должна действовать схема транслятора?
предположим во входном языке нет синтаксических ошибок. В варианте без использования парсера дерева я получил пачку классов, которые описывают Типы юзерских данных, описание глобальных переменных их инициализация если есть. Попути я ругал пользователя, за то что он некорректно объявил некоторые куски. В принципе этой информации вполне достаточно, что бы тем же визитором выписать код на С. (процедуры и функции меня пока не волнуют)

Что я смогу выиграть, если в эту схему я включу парсер дерева?

Здравствуйте, Graf Alex, Вы писали:
GA>А можно с этого места поподробнее?
GA>Что значит покрытие дерева паттернами и где возникает перебор?

Это обычно актуально при генерации машинного кода. У нас для каждой машинной
инструкции имеется соответствующий ей паттерн в дереве. Если инструкция простая,
вроде add r0, r2, r3 --- то ей соответсвует просто одна вершина дерева (+ int:x1 int:x2),
а вот если это нечто вроде lea eax, dword ptr [edx + 4*edi + <offset>],
то такой инструкции соответствует целый фрагмент из 3-х узлов ---
(+ int:x1 (+ (* 4 int:x2) int:imm32)).
Тогда задача генерации машинного кода может быть представлена в виде нахождения
покрытия данного дерева паттернами минимальной стоимости.
Про это немного есть в "Красном Драконе" (Ахо, Сети, Ульман. Компиляторы. ...)
Примерно так работает кодогенератор gcc, хотя там все конечно куда как
сложнее.

GA>Ведь у нас все данные уже распаршены и находятся в некотором дереве, что нам из него мешает писать прямо выходной код?
GA>Или может мы говорим о разных видах входных данных?

GA>Для пирмера сузим задачу до следующей: входной язык — паскаль, выходной — С.

GA>Как должна действовать схема транслятора?
GA>предположим во входном языке нет синтаксических ошибок. В варианте без использования парсера дерева я получил пачку классов, которые описывают Типы юзерских данных, описание глобальных переменных их инициализация если есть. Попути я ругал пользователя, за то что он некорректно объявил некоторые куски. В принципе этой информации вполне достаточно, что бы тем же визитором выписать код на С. (процедуры и функции меня пока не волнуют)

Вполне так можно сделать. Особенно если не стоит задача получения красивого года на выходе.
Впрочем, если стоит, то это все равно надо делать пo другому. Я подобную вещь делал,
и она была довольно сложной.
Между прочим, если Вам и впрямь паскаль в Си превратить надо, есть open-source конвертор,
поищите на http://www.garret.ru/~knizhnik/lang.html (Это мой бывший ученик и впоследствии
коллега по работе делал).
Если напрямую не сумеете применить, то хоть некоторые идеи сможете использовать.
Там, правда, на си все написано.

GA>Что я смогу выиграть, если в эту схему я включу парсер дерева?

В данном случае, думаю, надо делать без парсера.

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

GA>>Что значит покрытие дерева паттернами и где возникает перебор?
SG>Это обычно актуально при генерации машинного кода. У нас для каждой машинной
SG>инструкции имеется соответствующий ей паттерн в дереве. Если инструкция простая,
SG>вроде add r0, r2, r3 --- то ей соответсвует просто одна вершина дерева (+ int:x1 int:x2),
SG>а вот если это нечто вроде lea eax, dword ptr [edx + 4*edi + <offset>],
SG>то такой инструкции соответствует целый фрагмент из 3-х узлов ---
SG>(+ int:x1 (+ (* 4 int:x2) int:imm32)).
Помоему нужно быть диким извращенцем, что бы писать на входном языке так, что получаются такие деревья
Насколько я понял это пример уже модифицированого дерева, а в оригинале было чтото попроще?
GA>>Для пирмера сузим задачу до следующей: входной язык — паскаль, выходной — С.

GA>>Как должна действовать схема транслятора?
SG>Вполне так можно сделать. Особенно если не стоит задача получения красивого года на выходе.
Сишный код является промежуточным, между входным текстом ибинарником.... как правило его никто не видит...
SG>Между прочим, если Вам и впрямь паскаль в Си превратить надо, есть open-source конвертор,
SG>поищите на http://www.garret.ru/~knizhnik/lang.html (Это мой бывший ученик и впоследствии
SG>коллега по работе делал).
SG>Если напрямую не сумеете применить, то хоть некоторые идеи сможете использовать.
SG>Там, правда, на си все написано.
Ну на самом деле мой входной язык ничего общего с паскалем не имеет. Так просто декларативный язык для описания переменных и типов данных в системе... Паскаль я привел для примера...
Впрочем за ссылку пасиба.... Действительно полезная весч... хотя бизоновские грамматики как по мне читать сложнее....

Вот только никак не могу понять одного: почему если во входном языке идет объявление существующей переменной или переменной необъявленого типа, то ее все равно пихают в дерево?
Я имею в виду языки которые можно проверять одним проходом (аля С)
GA>>Что я смогу выиграть, если в эту схему я включу парсер дерева?
SG>В данном случае, думаю, надо делать без парсера.
Помоему тоже...

Здравствуйте, Graf Alex, Вы писали:
.
GA>Помоему нужно быть диким извращенцем, что бы писать на входном языке так, что получаются такие деревья
GA>Насколько я понял это пример уже модифицированого дерева, а в оригинале было чтото попроще?
Дерево конечно обычно перетрясенное порядком, но, если мы собираемся генерировать машинный код,
там таких фрагментов как раз куча --- они вылезают из доступа к массивам.

GA>Вот только никак не могу понять одного: почему если во входном языке идет объявление существующей переменной или переменной необъявленого типа, то ее все равно пихают в дерево?

Потому, что проще вынести в отдельный проход всю семантику. Когда я пишу разбор умеренно сложного языка,
типа Java, то в действих парсера у меня обычно построение вершин дерева. Тогда получается один,
все равно довольно увесистый, файл с грамматикой. А вот семантические действия обычно довольно сложные,
и они разнесены по отдельным файлам (или пакетам, если на Java пишем). Хотя бы отдельно пойдут
объявления, выражения и операторы.

GA>Я имею в виду языки которые можно проверять одним проходом (аля С)
С тех пор, как мы можем себе позволить держать дерево для программы в
памяти, большого смысла делать все за один проход уже нет. Тут выступают
вперед соображения удобочитаемости и модульности кода.

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

Здравствуйте, System Goose, Вы писали:
GA>>Вот только никак не могу понять одного: почему если во входном языке идет объявление существующей переменной или переменной необъявленого типа, то ее все равно пихают в дерево?
SG>Потому, что проще вынести в отдельный проход всю семантику. Когда я пишу разбор умеренно сложного языка,
SG>типа Java, то в действих парсера у меня обычно построение вершин дерева. Тогда получается один,
SG>все равно довольно увесистый, файл с грамматикой. А вот семантические действия обычно довольно сложные,
SG>и они разнесены по отдельным файлам (или пакетам, если на Java пишем). Хотя бы отдельно пойдут
SG>объявления, выражения и операторы.
Переварил... пасибо.... Видимо у меня пока все просто...
Формулы будут в отдельных файлах со своим форматом — там наверное придется помучаться....
А пока только объявление переменных и типов

Осталась только проблема хранения этих вот данных, для передачи между разными парсерами (которых по предварительной оценке должно быть около 6-7). Но об этой проблеме в другой теме...