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

T>Интересует что конкретно что ты пишешь и синтакс твоего языка.
Уфф... тут выше по треду я уже раза 3 ссылку на описание языка давал — это OIL.

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

VNN>Здравствуйте, Андрей Коростелев, Вы писали:

АК>>boost::spirit ?
АК>>Очень доходчивий и грамотно постренный туториал.

VNN>Оч интересно. Спасибо. Материала набрал море, успеть бы "зисть"

Совет от того кто пробовал это все — не трать времени на yacc, lex,
boost примочки. первые 2-е слишком плохо продуманы, и делание языка на них напоминает
создание ракеты, где ты сам закручиваешь каждый болтик.

boost — будешь копаться в темплайтах ошибках до опупения.
боост темплайты — это убийцы скорости компиляции.
wave c++ parser (основан на boost spirit) 1 рекомпиляция занимала у меня
2-5 минут без какий либо изменений в коде.
Ошибки boost темплайты выдают такие что хоть стой хоть падай.

perl / yapp самые простые в использовании.

wine (windows emulation) содержит какой то idl compiler,
и samba v4 (file sharing server) тоже содержит компилер.
(Оба основаны на yapp)

Внимательно смотри на лицензии которые там применяются,
очень часто если оттуда что то возмешь — потом надо будет весь
свой проэкт публиковать в инете (GPL лицензии).

Советую копировать идеи, но не их имплементации.

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

VNN>К сожалению, у меня не только небыло опыта написания подобных вещей, но и даже про теорию я не особо знал. Сейчас что-то поверхам похватал. Я до сих пор внятно не представляю КАК собствено использовать всевозможные Яки, Бизоны и прочих "копытных" в моем проекте. Как мне тут уже подсказали, нужно описать все BNF-выражения языка (они уже есть) сначала в виде своих классов, потом в виде некого кода Яка и прочих, а вот последующие шаги в тумане.

Дракона уже начал читать?
Попробую объяснить по другому. Генераторы парсеров, как тут уже справедливо заметили, порождают два куска кода. Кусок №1, принимая на вход некий поток сырых данных (в случае текстового языка это как правило поток символов) на выходе выдает поток лексем — минимальных частей языка. Как правило в качестве лексем фигурируют ключевые слова, операторы, знаки препинания, константы. К примеру, выражение 1+2*3 будет преобразовано в поток {константа1, оператор +, константа 2, оператор *, константа 3}. Как правило лексемы описываются регулярными грамматиками(это очень узкий класс простых грамматик), часто бывает, что внешний код умеет переключать режимы лексера, это позволяет делать ключевые слова, являющеиеся таковыми только в определенном контексте.
Т.е., упрощенно, лексер это такая функция, на входе которой текст,а на выходе набор примитивов, которые в этом тексте выявлены. Генератор может на основе регулярных выражений построить тебе такую функцию. А можешь ее реализовать самостоятельно — это, как правило, довольно несложно.
Как только мы получили поток лексем, нам необходимо этот поток проанализировать и выявить в нем структуру. Вот структура как раз и описывается ввиде BNF-правил. Генератор, пользуясь этими правилами, строит код, который эти правила выявляет, либо определяет факт того, что текст под эти правила не подходит. Алгоритмов наложения правил на поток лексем много, но для языков программирования наиболее часто используются http://en.wikipedia.org/wiki/LR_parser и LL алгоритмы. Подробности изучишь сам, здесь е замечу, что LL парсер значительно проще, но несколько медленнее и способен анализировать более узкий класс грамматик.
Но просто проанализировать недостаточно. Нужно еще эти результаты зафиксировать. Практически всегда для этого используют т.н. AST — абстрактное синтаксическое дерево, т.е. древовидная структура (часто немодифицируемая), описывающая выражения и конструкции языка программирования. В случае приведенного примера выражения обычно получится что то такое:

оператор +
    константа 1
    оператор *
        константа 2
        константа 3

В большинстве случаев за тебя никто это дерево не построит и ты должен будешь строит его самостоятельно на целевом языке программирования ввиде кусочков кода, привязанных к правилам грамматик. Т.е. код, написанный в правиле с оператором * вызовется, если таковой оператор будет обнаружен и корректно (с точки зрения грамматики) использован, и ты в этом коде должен будешь создать экземпляр узла "оператор", передав в качестве параметров тип оператора (*) и уже построенное AST обоих его операндов.
На следующем этапе, если язык это подразумевает, производится разрешение типов, т.е. в соответствие идентификаторам ставится некая информация, которая описывает что это за идентификатор — ссылка на тип в AST, ссылка на тип во внешней библиотеке, ссылка на объявление использованной переменной, параметра или поля и т.д. В примере с калькулятором это может быть связывание имени функции в выражении с описанием, какая у нее должна быть реализация.
Наконец, на последнем этапе ты должен по типизированному дереву построить либо код на другом языке (транслятор), либо исполняемый код (компилятор), либо просто начать исполнять программу (интерпретатор). В приведенном примере, если мы преобразуем его в IL, то получим примерно следующее:

ldc.i4 1
ldc.i4 2
ldc.i4 3
mul.ovf
add.ovf
ret

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

K>Тогда не совсем понятно, что именно тебя интересует? Диагностика ошибок? На этапе синтаксического анализа можно выявить синтаксические ошибки. Семантические ошибки выявляются в процессе дальнейшей обработки. Или ты не можешь организовать GUI? Что не получается?

Погодь. Опишу по пунктам что мне нужно:
1. Читать программу на OIL
1.1 Выявлять синтаксически ошибки
1.2 Выявлять семантические ошибки
2. Отображать визуальное представление программы (ну грубо говоря как форма представляется на C# или Builder/Delphi)
2.1 Визуальными средствами призводить редактирование.

В данный момент меня интересует не ГУЙ, тут как раз проблем мне видется меньше всего, а пункты 1.1 и 1.2. Я разработал свои собственные алгоритмы, чую сделал кривоватый велосипед, но вот куда в моей системе запихнуть Яка, Бизона или еще какого зверя я не пойму. Везде пишут про "генерацию компилятора" и как я понимаю результатом работы является исходный код, который нужно компилить уже обычным (ну С++ например) компилятором для получения чего-то... чего? Прошу прощения, что буквари так и не почитал, уже писал, что бросать наработки не хочется. Но вероятно, если нормально сдам первый этап программы, уже в более спокойной обстановке хочу передалать все по правильному, потому и тему активно развиваю.

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

> Везде пишут про "генерацию компилятора" и как я понимаю результатом работы является исходный код, который нужно компилить уже обычным (ну С++ например) компилятором для получения чего-то... чего?

Получишь код, который будет получать поток исходного кода, а на выходе будет выдавать статически типизованное AST. Ещё неплохо если будет подготовлена инфраструктура для обхода Посетителем. А там до интерпретатора уже рукой подать.

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

AVK>Это у тебя в LALR парсере контекстно зависимая грамматика???
AVK>Ты, видимо, перепутал контекстно-свободные и регулярные грамматики.

Очепятался. Должно было быть "контекстно-свободная грамматика"

K>>К сожалению, yacc не поддерживает BNF
AVK>http://en.wikipedia.org/wiki/Yacc
AVK>

It generates a parser (the part of a compiler that tries to make syntactic sense of the source code) based on an analytic grammar written in a notation similar to BNF.

Не на столько и similar. Многие фишки из EBNF яки не поддерживают.

K>>, и грамматику ему надо задавать практически в том же виде, как определено в математике.

AVK>В математике (если речь о теории формальных грамматик) как раз BNF чаще всего и используется.

В математике грамматика задаётся как множество пар цепочек символов. Если грамматика контекстно-свободная, то первые компоненты пары являются цепочками из одного нетерминала. В yacc используется похожая нотация.

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

D>Получишь код, который будет получать поток исходного кода
Не совсем себе представляю, как его потом обрабатывать в run-time?

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

VNN>Не совсем себе представляю, как его потом обрабатывать в run-time?

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

a = b + 1

Допустим раскладывается (упрощённо) на:
Statement
Assignment
LValue
Var // a
RValue
AddOp
Operands
Var //b
IntegerLiteral

Обходишь это дерево. Каждая нода вызывает посетителя для дочерних нод, а потом обрабатывает результат. Например обработчик Var(a) вернёт (type:double, value:2.0), a обработчик IntegerLiteral вернёт (type:integer, value:1). Обработчик AddOp берёт типы и значения операндов, обрабатывает их и возвращает результат.

Правильные генераторы добавляют вспомогательный код для обхода и можно сделать так (крайне упрощённо):
class MyAstVisitor {
public VisitorResult visitAddOp(AddOpNode node) {
VisitorResult result = new VisitorResult(double, 0.0);
for (Node childNode : node.getOperands()) {
VisitorResult childResult = childNode.visit(this);
// Тут разруливание типов с проверкой, приведением и т.п.
result.setValue(result.getValue() + childResult.getValue())
}
}

public VisitorResult visitIntegerLiteral(IntegerLiteralNode node) {
return new VisitorResult(integer, Integer.parse(node.text));
}
}

Ещё раз подчеркну, что это примитивное изложение, но очень быстро имплементируемое. Мне довелось сделать простой expression-evaluation-engine на Java с поддержкой массивов, функций, основных математических операций и типов данных за день.

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

VNN>Не совсем себе представляю, как его потом обрабатывать в run-time?

Всё зависит от того, какую именно часть семантики нужно проверить. Даже не знаю, что посоветовать. Лично у меня сложности с такими задачами закончились с изучениям ФЯ. Что тебе посоветовать, даже не знаю.

Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:

type operator =
    Return_op   of expr
  | If_of       of expr * operator * operator option
  | While_op    of expr * operator
  | Multiple_op of operator list
  | и т.д

let check_returns node = match node with 
    Return_op _                     -> true
  | If_op(_, first, Some second)    -> check_returns first && check_returns second
  | If_op(_, first, None)           -> check_returns first
  | While_op(_, op)                 -> check_returns op
  | Multiple_op lst                 -> List.fold_left (fun (acc, e) -> acc || check_returns e) false lst
  | _                               -> false

В терминах C превращается во что-то вроде:

#define TRUE          1
#define FALSE         0

#define NODE_IF       0
#define NODE_WHILE    1
#define NODE_RETURN   2
#define NODE_MULTIPLE 3
// и т.д

typedef union tag_OperatorData
{
    struct
    {
        struct tag_Expr *cond;
        struct tag_Operator *first;
        struct tag_Operator *second;
    } if_op;
    struct
    {
        struct tag_Expr *predicate;
        struct tag_Operator *op;
    } while_op;
    struct
    {
        struct tag_Expr *expr;
    } return_op;
    struct
    {
        struct tag_Operator **operators;
        int count;
    } multiple_op
} OperatorData;

typedef struct tag_Operator
{
    int type;
    OperatorData data;
} Operator;


int check_returns(Operator *op)
{
    switch (op->type)
    {
        case NODE_RETURN:
            return TRUE;
        case NODE_IF:
            if (op->data.if_op.second != NULL)
                return check_returns(op->data.if_op.first) && check_returns(op->data.if_op.second);
            else
                return check_returns(op->data.if_op.first);
        case NODE_WHILE:
            return check_returns(op->data.while_op.op);
        case NODE_MULTIPLE:
            for (int i = 0; i < op->data.multiple_op.count; ++i)
                if (check_returns(op->data.multiple_op.operators[i]))
                    return TRUE;
            return FALSE;
        default:
            return FALSE;
    }
}

Где-то так. Можно усложнить пример. Например, можно возвращать не bool, а список тех строк, в которых найдена ошибка. Или, что лучше в случае с C — завести императивную процедуру, которая просто добавляет сообщения об ошибке в лог. Сразу скажу: для этого нужно модифицировать структуру Operator, добавив туда информацию о координатах узла в тексте (начало, конец, имя файла), или в ML к каждому конструктору алгебраического типа добавить location в качестве параметра. Разумеется, надо будет соотв. образом модифицировать парсер.

VadNuNik wrote:
>
> K>Тогда не совсем понятно, что именно тебя интересует? Диагностика
> ошибок? На этапе синтаксического анализа можно выявить синтаксические
> ошибки. Семантические ошибки выявляются в процессе дальнейшей обработки.
> Или ты не можешь организовать GUI? Что не получается?
>
> Погодь. Опишу по пунктам что мне нужно:
> 1. Читать программу на OIL
> 1.1 Выявлять синтаксически ошибки
> 1.2 Выявлять семантические ошибки
> 2. Отображать визуальное представление программы (ну грубо говоря как
> форма представляется на C# или Builder/Delphi)
> 2.1 Визуальными средствами призводить редактирование.
>
> В данный момент меня интересует не ГУЙ, тут как раз проблем мне видется
> меньше всего, а пункты 1.1 и 1.2. Я разработал свои собственные
> алгоритмы, чую сделал кривоватый велосипед, но вот куда в моей системе
> запихнуть Яка, Бизона или еще какого зверя я не пойму. Везде пишут про

Весь вопрос заключается в том, как представлена (или предполагается быть
представленной) информация для пунктов 1.2 или 2.*. Что это — набор
связанных структур в памяти, внешнее структурированное хранилище? Но
что-то должно быть. А компилятор, на чем бы он не был написан, нужен,
чтобы транслировать внешнее (текстовое) представление во внутреннее — в
то, что используется для пунктов 1.2 и 2.*

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

D>Написал грамматику, сгенерил парсер, скомпилял его и добавил в основной проект. Самое примитивное — обход AST посетителем и вычисление результатов. Например имеешь код:
Да как писать все самостоятельно ясно :-) Тут же 4/5 треда о том, что самому давить клаву в этом деле следует только в учебных целях, а реальные пацаны используют уже готовые механизмы только обучая их своему языку. Вот я о том и спрашивал — как использовать yacc-образные механизмы в проекте, представляющем исходный код в некой промежуточной структуре данных, которую нужно редактировать в run-time. То, что посититель для анализа кода удобен я знаю, собственно, в "букваре" это даже в качестве примера рассмотрено :-)

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

AVK>Дракона уже начал читать?
Ага :-)

AVK>Попробую объяснить по другому.
Примерно понял, собственно, за это время я уже сам накропал алогоритмы разбора кода на лексемы и сборки из лексем выражени языка. Описание языка есть, его модель то же, худо бедно, надеюсь работать оно станет. Позже освою "дракона", еще доков и переделаю уже как положено.

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

K>Всё зависит от того, какую именно часть семантики нужно проверить.
Проверять надо бы все и синтаксическую верность кода и потом уже семантику языка — правильное использование типов данных, правильность их определения и пр.

K>Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:
Это что-то типа yacc-а?

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

K>>Всё зависит от того, какую именно часть семантики нужно проверить.
VNN>Проверять надо бы все и синтаксическую верность кода и потом уже семантику языка — правильное использование типов данных, правильность их определения и пр.

Синтаксическая корректность кода проверяется парсером, сгенерённым yacc'ом. Правда, для этого в самом y-файле, скармливаемому yacc'у надо сделать некоторые спец. указания с символом error. Как это делается — см. в документации по yacc'у (а лучше, по bison'у).

K>>Ну, например, в том же околопаскале можно такми образом проверить наличие return'ов во всех ветвях:
VNN>Это что-то типа yacc-а?

Околопаскаль — это выдуманный язык, предназначенный для иллюстрации того, как пишется парсер. Код приведён на ML — таком же ЯП, как C, Pascal и т.п. Ещё ниже приведён абсолютно аналогичный код на Pascal. Ты же спросил — что делать с результатом, выданным yacc'ом, я и показал пример. А так, зависит от задачи.

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

VNN>как использовать yacc-образные механизмы в проекте, представляющем исходный код в некой промежуточной структуре данных, которую нужно редактировать в run-time

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

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

Ладно, спасибо большое за совет, чую без прочтения букваря более внятного вопроса я сформулировать не смогу :)

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

H>Весь вопрос заключается в том, как представлена (или предполагается быть
H>представленной) информация для пунктов 1.2 или 2.*. Что это — набор
H>связанных структур в памяти, внешнее структурированное хранилище?
Какая именно информация? У меня есть файлы на OIL (ну и моя программ должа уметь сама их конструировать), есть мной созданное описание языка в виде XML-документа, есть модель языка, которая читает этот XML. Есть код очищающий исходники от "мусора", долизываю алгоритмы (начал кодить потехоньку) разбора кода на лексемы и последующего семантического анализа выражений языка, ко всему этому приделана примитивная сигнализация об ошибках — на первой же синтаксической ошибке парсер остановится, семантические пойдут типа как предупреждения.

H>что-то должно быть. А компилятор, на чем бы он не был написан, нужен,
H>чтобы транслировать внешнее (текстовое) представление во внутреннее — в
H>то, что используется для пунктов 1.2 и 2.*
Для этого мне нужно его:
1. Обучить грамматике исходного языка
2. Обучить моим внутренним моделям данных
3. Каким-то образом все интегрировать в одну программу

Я правильно понял?

Видимо я неправильно понял вопрос. Или он был недостаточно конкретен.

Насчёт конкретно yacc — не подскажу. Он уже давно вымыт из мозга. Я предпочитаю LL-грамматики.

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

VNN>Пишу на С++ за еду Парсеры и компиляторы никогда не писал, даже во время учебы — не входило в скудный курс программирования (АСУ).

Тогда восаользуйся Бизоном.

VD>>Мой тебе совет. Выбери построитель парсеров наиболее подхдящий для языка реализации и используй его.
VNN>Вот, опять. КАК "использовать"-то? Можно в 3-4-х пунктах описать как оно ваще работает?

В 3-4 Нельзя. Это целая наука. Знаю только, что изобретать ее самому еще более бессмысленно нежели пытаться посигнуть ее за два дня.

Могу только в общих чертах описать то что тебе нужно узнать.
1. Следует изучить BNF (см. Википедию).
2. Следует освоить метод парсинга рекурсивным спуском. В общем-то, для твоей задачи его за глаза хватит. Тогда можно и без построителей парсеров обойтись.
3. Желательно своить построитель парсеров (Бизон в твоем случае будет, пожалуй, оптимальным выбором). Можно попытаться использовать Spirit из boost — это построитель парсеров реализованный в рамках С++ средствами метапрограммирования на шаблонах. Минусы Спирита: замедляет компиляцию проекта, порождает слишком большие бинарники и (особенно) промежуточные файлы (под несколько гиг для весьма скромной грамматики), имеет плохие диагностические сообщения (так как шаблоны С++ не предоставляют средств для выдачи оных). Зато не прийдется искать генераторы кода. Все есть в рамках буста.

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

ЗЫ

Откровенно говоря делать свои языки — это не благодарная задача.