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

Короче, нужны исходники с примерами и разъяснениями по этому всему на человеческом языке.
За**ся разбирать заумные стать про "слово, являющимся своим концом"! Начинают вообще с поиска подстроки.

Не надо ругаться, знаю что где-то об этом кучу написали, но сам найти не могу. Хелп мни!

Fixin, сам когда-то читал книжки по этой гадости и так же как и ты ничего не понял. Зато потом, примерно месяц назад захотелось написать свой язычок программирования и, без книг, сам во всём разобрался. Всё намного проще, чем они там расписывают..

Берём допустим выражение:

Цитата

1-(3+1)-(6+7)

И рассуждаем: как мы его считаем? Сначала считаем то, что в скобках, потом операции приоритетом ниже и так далее до самых простых - сложения и вычитания. Получаем такой алгоритм:
1. Выделяем все выражения с наивысшим приоритетом. В нашем примере: (3+1) и (6+7).
2. Откидываем скобки, для каждого запускаем пункт 1.
3. Если скобок больше нет - находим плюсы и минусы (умножение/деление и пр. прелести не описываю - додедуктируешь). Точнее нужно получить первое слагаемое, второе и операнд. Второе слагаемое - только последние части (в нашем примере в скобках из пункта 1 это 1 и 7). Для первого операнда - всё остальное.

[3+5] - [8]
^ 1-ое слагаемое ^ второе слагаемое

4. Для первого слагаемого запускаем пункт 3.
5. Считаем, подставляем вместо выражения результат. И так пока всё не посчитаем.

Коряво описал, но пока лучше не могу. С умножением и делением додумать несложно по тому же принципу. Оно будет между скобками и сложением/вычитанием.

Вот отрыл раннюю версию своего парсера, там только сложение/вычитание и скобки. Зато принцип.

Код

class QParser { public:     QParser();     QParser(const QString& sCode);// Авто вызов парсинг-функции          // Собственно парсинг     QString Parse(const QString& sCode);          // Получение результата     QString GetResult(Void_t) const { return m_sResult; }      private:     QString Level2(const QString& sCode);// Сложение/вычитание     QString Level1(QString sCode);// Скобки          // Непосредственно сумма операндов     QString DoSum(const QString& sLeftOp, const QString& sRightOp, Bool_t bMin);     QString m_sResult;// Результат }; QParser::QParser() { } QParser::QParser(const QString& sCode) {     // Здесь должон быть вызов парсинг-функции     Parse(sCode); } // Собственно парсинг QString QParser::Parse(const QString& sCode) {     return m_sResult = Level1(sCode); } QString QParser::Level2(const QString& sCode)// Сложение/вычитание {          UInt_t iOp = sCode.FindEndChs("+-");          if(iOp)// Есть сложения/вычитания     {         // Ищем вхождение '+' или '-' и получаем левую часть         QString sLeftOp = Level2(sCode.GetPart(1, iOp-1));         // Остальное - правая часть         QString sRightOp = sCode.GetPart(iOp+1);         // Смотрим тип операции         switch(sCode[iOp-1])         {         case '-':// Вычитание         case '+':// Сложение             return DoSum(sLeftOp, sRightOp, sCode[iOp-1]-'+');             break;         default:             // Здесь должна быть обработка ошибки             return "Error";             break;         }     }     // Нет сложений/вычитаний          return sCode; } QString QParser::Level1(QString sCode)// Скобки {     Char_t stmp[30];     UInt_t iOS = 0;          while(iOS = sCode.FindFirst('('))     {         // Если есть скобки         UInt_t iCS = sCode.FindFirst(')', iOS);         // Проверим порядок         if(!iCS) return "Error";         QString SubCode = sCode.GetPart(iOS+1, iCS-1);                  // Вычисляем выражение в скобке         sCode.Del(iOS, iCS);         sCode.Insert(Level1(SubCode), iOS-1);     }          return Level2(sCode); } QString QParser::DoSum(const QString& sLeftOp, const QString& sRightOp,     Bool_t bMin) {     // Сложение или вычитание двух операндов     Char_t stmp[0xFF];          UInt_t pl = sLeftOp.FindFirst('.');     UInt_t pr = sRightOp.FindFirst('.');          if(!pl)     {         UInt_t lVal = atoi(sLeftOp.MakeCStr(stmp));                  // 1 случай - оба операнда целые         if(!pr)         {             UInt_t rVal = atoi(sRightOp.MakeCStr(stmp));                          sprintf(stmp, "%i", bMin ? lVal - rVal : lVal + rVal);             return stmp;         }         else// 2 случай - слева целое, справа - с точкой         {             Real_t rVal = atof(sRightOp.MakeCStr(stmp));                          sprintf(stmp, "%f", bMin ?                 (Real_t)lVal - rVal : (Real_t)lVal + rVal);             return stmp;         }     }     else     {         Real_t lVal = atof(sLeftOp.MakeCStr(stmp));         // 3 случай - левый - с точкой, правый - целое         if(!pr)         {             UInt_t rVal = atoi(sRightOp.MakeCStr(stmp));             sprintf(stmp, "%f", bMin ?                 lVal - (Real_t)rVal : lVal + (Real_t)rVal);             return stmp;         }         else// 4 случай - оба с точкой         {             Real_t rVal = atof(sRightOp.MakeCStr(stmp));             sprintf(stmp, "%f", bMin ? lVal - rVal : lVal + rVal);             return stmp;         }     }          return "Error"; }

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

Я, конечно, не профи, но подобное писал, поэтому скажу кое-что. Во-первых, для выполнения скрипта есть 2 способа:
1. Преобразовать его во внутренний код (со всякими условными, безусловными переходами и пр.), а затем выполнить; я делал так.
2. Выполнять непосредственно команды скрипта.
Как я понял, тебе нужен 2ой способ.
При считывании скрипта из файла его не плохо бы сразу разбить на команды, получим массив команд. Тогда же надо отметить границы различных блоков (тех же циклов, например). То есть встречаем команду начала блока - кидаем её в стек (точнее её №), при закрытии блока ставим в команду его начлала адрес конца (№ элемента массива), добавляем команду конца, где указываем адрес начала (вроде ENDBLOCK 17) и убираем № из стека. Инициализируем счётчик команд 0 (№ следующей выполняемой команды). Выполняем циклом команды, пока счётчик не дойдёт до несуществующего эелемента (счётчик==количество_элементов_в_массиве) или очередной командой не будет завершение скрипта (вроде exit). После каждой команды, естественно, увеличиваем счётчик на 1.
Циклы при таком подходе работают довольно просто: при выполнении команды while (с другими циклами принцип тот же) вычисляем выражение, приводим его к целому типу, если оно равно 0, присваиваем счётчику команд номер команды конца блока (после добавления 1 это будет 1ая команда после цикла), иначе ничего не делаем (1 к счётчику команд прибавляется всегда). При выполнении команды ENDBLOCK, если она указывает на while присваиваем счётчику команд адрес While минус 1.
Выражения. Где-то на форуме (по-моему где-то в билдере) давали ссылку на страницу с обсуждением парсинга выражений. Я её тогда сохранил себе. Выкладываю здесь. Сам я, правда, не читал, что там есть. Как это делать по моему. Во-первых ищем открывающую скобку, ближайшая скобка после которой вообще - закрывающая. Если перед скобкой (пропуская пробелы, табы и пр.) стоит не знак операции, то это либо вызов функции (это отдельный вопрос), либо синткасическая ошибка. Если там знак операции, тогда вычисляем выражение в скобках (само оно бесскобочное) и заменяем всю эту скобку на значение. В итоге получим бесскобочное выражение. Самое главное - вычисление бесскобочного выражения. Первым делом надо вычислить однооперандовые операции (в порядке приоритета) и ?:. Затем есть много способов. С ипользованием внутреннего кода (как делал я) будет, конечно, по другому, а так можно сделать поиск всех операций (в порядке приоритета), учитывая всякие пробелы, вычислить простые бинарные операции (это, я думаю, не сложно) и заменить в выражении их значениями.
Вот, наверно, всё. Если тебе всё же интересно использование внутреннего кода, могу прислать setup от того, что я делал на выпускной экзамен по информатике 3 месяца назад, кстати написав программу на этом языке и скомпилировав, получим *.elic файл, который (если программа установлена setup-ом или корректно всё прописано вручную) запускается двойным кликом

Присоединённый файл ( Кол-во скачиваний: 8 )
 parsear.zip 3,12 Kb

помнится, в книге Страуструпа "Описание С++" парсер использовался в качестве примера...
...Глава 6

maxim1000 даже Страустроп не смог нормально объяснить, как этот алгоритм работает. Во всяком случае терминология в русской версии была чертовая...

Если просто потренироваться, то сюда: http://algolist.manual.ru/syntax/index.php

Может нужно что-либо вроде этого: http://root.cern.ch/ (С++ интерпретатор) ?

Хе , спасибо всем. Сейчас посмотрю ваши примеры и расскажу, что делаю я.

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

Есть выражение

Цитата

a+(b*c-d/e)/f

а будет

Цитата

bc*de/-f/a+

Те получили выражение которое, казалось бы, можно выполнить последовательно... но сначала нужно получить "произведение", "произведение" и вычесть из первого второе. Тут и получается неэффективность метода. Те в простые последовательные команде не переведешь .

А с циклами я разобрался, остались функции.
Добавлено @ 17:36
По этим ссылкам я был, когда искал. но Спасиб.

Цитата(Fixin @ 26.7.2005, 19:31)

Те получили выражение которое, казалось бы, можно выполнить последовательно... но сначала нужно получить "произведение", "произведение" и вычесть из первого второе. Тут и получается неэффективность метода. Те в простые последовательные команде не переведешь smile.

Еще как переведешь Генерируй байт-код для виртуальной стековой машины. Каждая команда берет операнды с вершины стека и кладет результат туда же. Тогда выражение:

Код

a+(b*c-d/e)/f <=> bc*de/-f/a+

будет переведено примерно в такую последовательность команд:

Код

push b push c mul push d push e div sub push f div push a add

Результат окажется на вершине стека.
Циклы и функции для такой виртуальной машины тоже реализуются сравнительно просто. (Параметры передавать на стеке, результат возвращать на вершине стека).

Вот пример маленького скриптового языка, реализованного с помощью Spirit: DScript

P.S.
А можно поинтересоваться для какой конкретной задачи это нужно? Может статься, удобнее будет прикрутить существующий скриптовый язык, например Lua с помощью Luabind.

Это сообщение отредактировал(а) Void - 26.7.2005, 19:32

Fixin а мы с тобой одной ерундой страдаем
Ты хотишь написать фактически транслятор в псевдокод? Дык может состыкуемся? Я в ближайший месяц только этим и заниматься буду (практически). "Вдвоём вселей"

Я пишу для Си++-подобного языка (синтаксис очень похож).
Добавлено @ 20:20
У меня идея на днях возникла: для каждой выполняемой такой проги полностью эмулировать 8086. Для моих задач больше возможностей не нужно, зато можно будет транслировать не в псевдокод, а даже во что-то осмысленное. Хотя это снижает эфективность - ведь в чистом псевдокоде можно своих команд понатыкать удобных...

Цитата

А можно поинтересоваться для какой конкретной задачи это нужно?

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

Цитата

Ты хотишь написать фактически транслятор в псевдокод? Дык может состыкуемся? Я в ближайший месяц только этим и заниматься буду

Отлично, проверь асю, если пользуешься, или пиши на "ЛС" ("ПМ"). Обмен опытом - очень классная штука!

Fixin
Существующие решения вполне бы подошли (тот же Lua или даже Prolog). Но раз уж "just for fun", то - святое дело

P.S.
Я надеюсь, генераторы парсеров - это не "не интересно" ИМХО, писать врукопашную даже простейший recursive-descent парсер - не самое интересное занятие, лучше запрячь lex+yacc/ANTLR/Spirit/whatever и сосредоточиться на самом языке

Это сообщение отредактировал(а) Void - 26.7.2005, 21:43

Не сказалбы, что сейчас весело

Возникла проблема с унарным минусом:

Цитата

a-(-b*c+d/e)*f+g*h

Получаем (по стековому алгоритму преобразования Дейкстрыописание):

Цитата

abc*-de/+f*-gh*+

- неправильно. Можно заранее просканировать выражение и заменить унарный минус в выходной строке на "~", которая будет обозначать знаковую инверсию числа на вершине стека:

Цитата

abc*~de/+f*-gh*+

Но я думаю есть более универсальные методы.

Теперб выходные строки исправил.

Это сообщение отредактировал(а) Fixin - 28.7.2005, 18:15

Fixin чем тебя не устроил мой метод, я не понимаю? Зачем дополнительно что-то во что-то преобразовывать, когда можно просто последовательно добавлять псевдоасмные команды. Глянь:

Код

class QParser     {     public:         QParser();         QParser(const QString& sCode);// Авто вызов парсинг-функции               // Собственно парсинг         QString Parse(const QString& sCode);               // Получение результата         QString GetResult(Void_t) const { return m_sResult; }           private:         QString Level2(const QString& sCode);// Сложение/вычитание         QString Level1(QString sCode);// Скобки               // Непосредственно сумма операндов         QString DoSum(const QString& sLeftOp, const QString& sRightOp, Bool_t bMin);         QString m_sResult;// Результат     };     QParser::QParser() { }     QParser::QParser(const QString& sCode) {         // Здесь должон быть вызов парсинг-функции         Parse(sCode);     }     // Собственно парсинг     QString QParser::Parse(const QString& sCode) {         return m_sResult = Level1(sCode);     }     QString QParser::Level2(const QString& sCode)// Сложение/вычитание     {               UInt_t iOp = sCode.FindEndChs("+-");               if(iOp)// Есть сложения/вычитания         {             // Ищем вхождение '+' или '-' и получаем левую часть             QString sLeftOp = Level2(sCode.GetPart(1, iOp-1));             // Остальное - правая часть             QString sRightOp = sCode.GetPart(iOp+1);             // Смотрим тип операции             switch(sCode[iOp-1])             {             case '-':// Вычитание             case '+':// Сложение        // !!! - ЗДЕСЬ В ОБЩИЙ ПСЕВДОКОД ДОБАВЛЯЕТСЯ КОМАНДА СЛОЖЕНИЯ/ВЫЧИТАНИЯ - !!!             return DoSum(sLeftOp, sRightOp, sCode[iOp-1]-'+');                 break;             default:                 // Здесь должна быть обработка ошибки                 return "Error";                 break;             }         }         // Нет сложений/вычитаний               return sCode;     }     QString QParser::Level1(QString sCode)// Скобки     {         Char_t stmp[30];         UInt_t iOS = 0;               while(iOS = sCode.FindFirst('('))         {             // Если есть скобки             UInt_t iCS = sCode.FindFirst(')', iOS);             // Проверим порядок             if(!iCS) return "Error";             QString SubCode = sCode.GetPart(iOS+1, iCS-1);                       // Вычисляем выражение в скобке             sCode.Del(iOS, iCS);             sCode.Insert(Level1(SubCode), iOS-1);         }               return Level2(sCode);     }     QString QParser::DoSum(const QString& sLeftOp, const QString& sRightOp,         Bool_t bMin)     {         // Сложение или вычитание двух операндов         Char_t stmp[0xFF];               UInt_t pl = sLeftOp.FindFirst('.');         UInt_t pr = sRightOp.FindFirst('.');               if(!pl)         {             UInt_t lVal = atoi(sLeftOp.MakeCStr(stmp));                       // 1 случай - оба операнда целые             if(!pr)             {                 UInt_t rVal = atoi(sRightOp.MakeCStr(stmp));                               sprintf(stmp, "%i", bMin ? lVal - rVal : lVal + rVal);                 return stmp;             }             else// 2 случай - слева целое, справа - с точкой             {                 Real_t rVal = atof(sRightOp.MakeCStr(stmp));                               sprintf(stmp, "%f", bMin ?                     (Real_t)lVal - rVal : (Real_t)lVal + rVal);                 return stmp;             }         }         else         {             Real_t lVal = atof(sLeftOp.MakeCStr(stmp));             // 3 случай - левый - с точкой, правый - целое             if(!pr)             {                 UInt_t rVal = atoi(sRightOp.MakeCStr(stmp));                 sprintf(stmp, "%f", bMin ?                     lVal - (Real_t)rVal : lVal + (Real_t)rVal);                 return stmp;             }             else// 4 случай - оба с точкой             {                 Real_t rVal = atof(sRightOp.MakeCStr(stmp));                 sprintf(stmp, "%f", bMin ? lVal - rVal : lVal + rVal);                 return stmp;             }         }               return "Error";     }

Сравни с тем, что я приводил сначала - один-в-один почти. Приоритеты, унарные операции работают сами собой. Этот алгоритм содран с человеческого; что думаем - то и пишем. Может я, конечно, что-то упустил...

Ну. да, метод хороший Нисходяще-рекурсивный-переделанный А я тоже хочу что-нить свое сочинить.

Цитата(Fixin @ 27.7.2005, 22:49)

А я тоже хочу что-нить свое сочинить.

А!! Молчу..

Цитата(Fixin @ 27.7.2005, 22:49)

Нисходяще-рекурсивный-переделанный

Терпеть не могу этого названия. "Бревно" и всё - что тут рекурсить!..

Цитата

"Бревно" и всё - что тут рекурсить!..

Чего? Это другое название?

Цитата(Fixin @ 27.7.2005, 22:57)

Чего? Это другое название?

Да это я его так... ласково окрестил

Без флема. (зарекалась свинья...) Есть предложения по вышеприведенной проблеме?

Цитата(Fixin @ 27.7.2005, 23:13)

Без флема.

"Извини Петька, не сдержался!.." (с) Василий Иваныч

Цитата(Fixin @ 27.7.2005, 23:13)

Есть предложения по вышеприведенной проблеме?

Ест. После стакана они не могут не ест Писать при обходе дерева не в строку, а в "стек" и не куски строк, а тип вроде этого:

Код

struct token {     Byte_t TokType;// Тип: 0 - оператор, 1 - операнд     char data;// Строковое представление };

Проще говоря, чётко разделить понятия операнд и оператор. На типовОм уровне.

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

"Толи я тупой, толи лыжи не едут..."

Цитата(Fixin @ 27.7.2005, 18:26)

a-(-b*c+d/e)*f+g*h

Цитата(Fixin @ 27.7.2005, 18:26)

abc*-de/+f*-gh*+

Это как?? Может там такое исходное выражение:

Цитата(Fixin @ 27.7.2005, 18:26)

a*(-b*c+d/e)*f+g*h

Добавлено @ 23:00
Унарный + или - может быть только в двух случаях:
1) В самом начале выражения.
2) В самом начале подвыражения (того, что в скобке).

Так какие проблемы отловить этот случай и при транслировании в выходную строку не определять символ как оператор, а определять как часть операнда?..

Нет, так и есть. Ошибка была в моей версии выхода.

Про добавление: так и собиоался сканировать, но искал более универсальный метод. Но он есть только в "бревне".

Вобщем вот мой "вырванный" парсер. Правда, корявый, но для примера думаю пойдёт. Сражу скажу, что при считывании файла строки заносятся в массив Strings, а в тексте заменяются на $индекс_в_массиве.

Присоединённый файл ( Кол-во скачиваний: 9 )
 parser.cpp 8,46 Kb

А бинарик (сетапка)? без него не интересно...

Народ что такое "Операнда?"

http://www.webopedia.com/TERM/o/operand.html