Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 1509, средняя оценка - 4.80
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
#1

Пишем свой интерпретатор языка BASIC - C++

20.06.2009, 20:03. Просмотров 189694. Ответов 464
Метки нет (Все метки)

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

Репозиторий с проектом находится тут, там же есть возможность в браузере посмотреть историю ревизий (английский в логах весьма примитивен,комментарии и рекомендации можете писать в личку),а также скачать самый последний архив репозитория в формате .tar.gz
Если кто-то пользуется Subversion,скачать исходники можно так:
Код
svn co https://basin.svn.sourceforge.net/svnroot/basin basin
Эти темы возникли в результате моих вопросов по ходу написания:
Технический приём для формирования согласованных данных
Makefile: как с использованием gcc строить автоматические зависимости от .h файлов?
Вопрос по svn (Subversion)
Создание системы тестирования ПО.
Вопрос про разные реализации бэйсиков
Можно ли выразить порядковый номер элемента массива через индексы?
[C++] Какие флаги указать линкеру для компиляции программы?
Как можно определить переменную в файле configure.in,чтобы её можно было использовать в Makefile?
Странный SIGSEGV, или что зависит от порядка написания интерфейса класса
[C++]Можно ли как-то указать в Makefile,чтобы часть файлов компилировал компилятор C?
Альтернативная версия интерпретатора от Evg на C
Это простая реализация разбора выражений, написанная Evg на C:
Представление выражения в двоичном дереве
*****************
Первое сообщение:
*****************
Задание(Страуструп,из книги,по готовому коду): Введите программу калькулятора и заставьте её работать.Например,при вводе
C++
1
2
r = 2.5
area = pi*r*r
Программа калькулятора выведет:
C++
1
2
2.5
19.635
Получили такой код:
LexicalAnalyzer.h
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// LexicalAnalyzer.h
#ifndef LEXICALANALYZER_H_INCLUDED
#define LEXICALANALYZER_H_INCLUDED
 
#include <cctype>
#include <string>
#include <map>
#include <iostream>
 
enum Token_value {
    NAME,       NUMBER,      END,
    PLUS = '+', MINUS = '-', MUL = '*', DIV = '/',
    PRINT = ';',ASSIGN = '=',LP = '(',  RP = ')'
};
extern Token_value curr_tok;
extern std::map<std::string,double>table;
extern int no_of_errors;
 
Token_value get_token();
 
double expr(bool);
double term (bool);
double prim (bool);
int error(const std::string&);
 
#endif // LEXICALANALYZER_H_INCLUDED

LexicalAnalyzer.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// LexicalAnalyzer.cpp
#include "LexicalAnalyzer.h"
 
 
std::map<std::string,double>table;
Token_value curr_tok=PRINT;
 
double expr (bool get)
{
    double left = term(get);
 
    for (;;)
        switch (curr_tok) {
            case PLUS:
                 left += term(true);
            break;
            case MINUS:
                 left-= term(true);
            break;
            default:
                 return left;
        }
}
 
double term (bool get)
{
    double left = prim (get);
 
    for (;;)
        switch (curr_tok) {
            case MUL:
                 left*=prim(true);
            break;
            case DIV:
                 if (double d = prim (true)) {
                     left /= prim (true);
                     break;
                 }
                 return error("Деление на ноль");
            default:
                 return left;
        }
}
 
double number_value;
std::string string_value;
 
double prim (bool get)
{
    if (get) get_token();
    switch (curr_tok){
        case NUMBER:{
            double& v = number_value;
            get_token();
            return v;
        }
        case NAME:{
            double& v = table[string_value];
            if (get_token()==ASSIGN) v = expr(true);
            return v;
        }
        case MINUS:
            return -prim(true);
        case LP:{
            double e = expr(true);
            if (curr_tok!=RP) return error("Ожидалась )");
            get_token();
            return e;
        }
        default:
            return error("Ожидалось первичное выражение");
    }
}
 
Token_value get_token()
{
    char ch = 0;
 
    do {
        if (!std::cin.get(ch)) return curr_tok = END;
    } while (ch!='\n'&&isspace(ch));
 
    switch (ch) {
        case 0:
             return curr_tok = END;
        case ';':case '\n':
             return curr_tok = PRINT;
        case '*':case'/':case '+':case '-':case '(':case ')':case '=':
             return Token_value(ch);
        case '0':case '1':case '2':case '3':case '4' :
        case '5':case '6':case '7':case '8':case '9':case '.':
             std::cin.putback(ch);
             std::cin>>number_value;
             return curr_tok=NUMBER;
        default:
             if (isalpha(ch)) {
                 string_value = ch;
                 while (std::cin.get(ch)&&isalnum(ch)) string_value.push_back(ch);
                 std::cin.putback(ch);
                 return curr_tok = NAME;
             }
             error ("Неправильная лексема");
             return curr_tok = PRINT;
    }
}
int no_of_errors=0;
int error (const std::string& s)
{
    no_of_errors++;
    std::cerr<<"Ошибка: "<<s<<'\n';
    return no_of_errors;
}

main.cpp
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// main.cpp
#include "LexicalAnalyzer.h"
 
 
int main()
{
    table["pi"]=3.1415926535897932385;
    table["e"]=2.7182818284590452354;
    while (std::cin) {
        get_token();
        if (curr_tok==END) break;
        if (curr_tok==PRINT) continue;
        std::cout<<expr(false)<<'\n';
    }
    return no_of_errors;
}

Анализатор-то работает,но конечное значение не вычисляется.Более того,если вводим
C++
1
a = 3 + 6
,то получаем "a", равное первому элементу в выражении,то есть 3.В чём логическая ошибка данной программы?С этими каскадными вызовами она слегка запутана.Уверен,что кто-то уже делал это задание.

Добавлено через 2 часа 5 минут 30 секунд
Пришлось решать влоб с дебаггером.У Страуструпа опечатка (или намеренная ошибка,что более вероятно ) Вот в этом куске кода в функции get_token():
C++
1
2
        case '*':case'/':case '+':case '-':case '(':case ')':case '=':
             return Token_value(ch);
Нехватает смены значения curr_tok,что и приводит к ошибочной работе.
C++
1
2
        case '*':case'/':case '+':case '-':case '(':case ')':case '=':
             return curr_tok=Token_value(ch);
Теперь всё пашет,всем спасибо,вопрос можно считать закрытым,но есть вопрос поважнее: В функциях prim и term возвращается int при ошибке,но ведь они имеют тип double,как вообще это работает?Происходит неявное преобразование типа,так?Мне интересно,почему Страуструп прибег к такому способу,это распространённая практика?

Добавлено через 16 минут 19 секунд
И ещё опечатка была
C++
1
2
3
                 if (double d = prim (true)) {
                     left /= d;// было left /= prim (true)
                     break;
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2009, 20:03     Пишем свой интерпретатор языка BASIC
Посмотрите здесь:
Пишем свой чекер C++
C++ пишем свой троян с нуля
Пишем свой класс, спецификатор доступа protected C++
C++ Интерпретатор небольшого языка программирования на С++
Не удается откомпилировать интерпретатор М-языка C++
Написать Интерпретатор Программного Языка(собственного) C++
Интерпретатор/компилятор ассемблер-подобного языка C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
13.08.2009, 21:51  [ТС]     Пишем свой интерпретатор языка BASIC #76
Я тут немного подзастрял на функциях.Система тестирования ещё в процессе.
Я сделал определение функции,и поскольку мало смыслю в работе с буферизацией(попробовал и так и так,но в итоге решил,что проще отказаться от этого варианта),я подумал будет проще просто запоминать место в коде,где начинается тело функции,а после разбора тела функции и получения результата возвращаться назад в то же место в коде,где были раньше.Что-то вроде того.Написал всё,поменял функцию,отвечающую за rValue в выражениях,чтобы сделать возможным вызов функций в выражениях.Дошёл до реализации разбора самого тела внутри экземпляра класса.И вот тут встал такой вопрос: привызове функции ведь нужно использовать локальные переменные,поэтому получается,что нельзя использовать syntax_parser,ведь он работает с глобальными переменными программы,или тогда придётся отказаться от идеи локальных переменных,но тогда будет не так интересно,или,как второй вариант,писать отдельный парсер специально для функций,так,получается?Иначе как объяснить парсеру,что он работает внутри тела функции и все переменные находятся внутри экземпляра класса,который его вызвал?
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
14.08.2009, 09:53     Пишем свой интерпретатор языка BASIC #77
Насколько я понял, вызов функции ты хочешь инерпретировать прямо из файла. Но при таком варианте задолбаешься с этим работать и вскоре интерпретатор превратится в болото. Полезно было бы это попробовать, дабы поиметь негативный опыт, но тут слишком много времени уйдёт в пустую, а последствия разгребать будет сложно

Тут надо работать через промежуточное представление. Хотя всё равно будет возникать вопрос о заведении переменной - в глобальной части или в локальной. Вообще, об этом я уже писал (пост 37, предпоследний абзац). Если перевести на текущее положение дел, то фактически тебе надо будет иметь две таблицы переменных (два вектора, или как у тебя называется). Локалы записываешь в локальную таблицу,глобалы в глобальную. При поиске переменной по имени сначала проверяешь в локальной таблице (если ты внутри процедуры), а потом в глобальной. При завершении работы процедуры локальная таблица удаляется

Если делать промежуточное представление, тот это место немного меняется. У тебя появляются три вещи. Таблицы переменных непосредственно, которые будут жить на протяжении времени жизни всей программы. А из промежуточного представления будут торчать обращения в одну из таблиц переменных. Второе - таблица символьных имён (о ней чуть ниже). И третье - таблица текущих значений: у тебя же процедура может рекурсивно саму себя вызывать, а у каждой активации процедуры своё значение переменных (об этом тоже ниже)

В итоге будем иметь что-то типа того в качестве промежуточного представления. Я пишу в своих упрощённых терминах, а дальше ты корячься со своими Си++'ными векторами и т.п.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// Описание переменной
struct Variable
{
  // Условно провязываю в список все переменные текущего контекста.
  // Т.е. глобальные переменные будут в одном списке, локальные переменные
  // процедуры - в другом (в каждой процедуре будет свой список)
  variable *next;
 
  // Имя переменной. Для исполнения промежуточного представление не нужно.
  // Нужно только для отладки и, вероятно, для выдачи ошибок
  char *name;
 
  // Дальше тип, может что-то ещё нужно
 
  // Текущее значение переменной (об этом ниже)
  Value *value;
}
 
// Описание процедуры
struct Procedure
{
  // Процедуры тоже условно провязываем в список
  Procedure *next;
 
  // Аналогично, для исполнения представления имя уже неважно, только
  // для отладки и выдачи ошибок
  char *name;
 
  // Информация о типе процедуры, ещё какая-то информация
 
  // Список параметров процедуры
  Variable *params;
 
  // Список локальных переменных процедуры
  Variable *locals;
 
  // Список операторов
  Statement *statement;
}
 
// Описание всей программы
struct Program
{
  // Список глобальных переменных
  Variable *globals;
 
  // Список процедур
  Procedure *procedures;
 
  // Список операторов
  Stetement *statement;
 
  // Может быть, что-то ещё
}
По поводу таблицы имён. На первом проходе парсера ты читаешь исходник и строишь промежуточное представление. При этом в процессе работы ты будешь строить конструкции Variable промежуточного представления. И будет возникать вопрос, как одно сдругим связывать по имени. Для этого нужно будет иметь таблицу имён, которая есть по сути набор пар { символьное имя, ссылка struct Variable* }. При этом пока ты работаешь в глобальной части, ты работаешь только с глобальной таблицей (т.е. таблица, в которой прописаны соотвествия для глобальных имён), а когда начинаешь парсить внутренности процедуры, то заводишь вторую дополнительную таблицу для имён локалов процедуры (включая параметры). Когда встречаешь имя - сначала проверяешь в таблице локалов, если там нет - в таблице глобалов. После того, как по имени нашёл соотвествующую struct Variable*, ссылку на эту переменную втыкаешь в представление. После того, как закончил парсить процедуру, таблицу локалов очищаешь. Понятно, что при таком раскладе процедура внутри процедуры не будет строиться. Да и большинство современных языков такое не позволяют, а потому думаю, что такое ограничение будет нормальным

Теперь таблица значений. В чём-то смысл похож на таблицу имён, только таблица о сути хранит набор всех значений (struct Value) для переменных текущего контекста. Одна таблица будет хранить набор значений для глобалов и будет жить всегда. В глобальной переменной будет торчать ссылка на struct Value, которая за всё время работы не поменяется (имею ввиду, что из переменной всегда будет торчать ссылка на одну и ту же запись Value). При входе в процедуру в момент ИНТЕРПРЕТАЦИИ (не парсенья) заводится новая таблица значений (каждое значение прописывается как Неинициализированное), а в представлении обходятся все локалы процедуры и поля value замыкаются на соответсвующую запись в твблице значений. При выходе из процедуры таблица значений удаляется (а ссылки на Value внутри локальных переменных на всякий случай устанваливается в NULL). Таким образом мы сможем рекурсивно вызывать процедуру? при каждой активации будет заводиться новая таблица значений (которая по большому счёту выполняет роль окна в стеке, как если бы это был код из-под компилятора). Тут есть тонкий момент: при рекурсивном возврате нам нужно уметь восстанавливать правильные связки "переменная-значение". Т.е. в момент интерпретации операции CALL нужно каким-то образом сохранить эти привязки переменной к значению, а после возврата - восстановить.Смысл этого понятен - в представлении (как и в тексте программы), локальная переменная присуствует в количестве одной штуки, но в момент исполнения их может быть несколько (из-за того, что может быть несколько активаций процедуры)

После всего написанного - ты ещё горишь желанием связываться с процедурами (и локальными объектами в них)? Потому как есть простые версии бейсика, где процедур как таковых нет. Формально они есть - за счёт оператора GOSUB (уход на подпрограмму), но при этом нет понятия локльной переменной, а потому работа ведётся через глобальные. Для использования это неудобно, т.к. не является полноценной процедурой, но очень и очень сильно упрощает интерпретатор. Именно поэтому я тебе изначально предлагал не связываться с процедурами. Не потому что это трудно по своей сути, а потому что для начинающего слишком большой объём работ, который тяжело выполнить аккуратно
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
14.08.2009, 13:23  [ТС]     Пишем свой интерпретатор языка BASIC #78
Тут еще есть одна неувязка.Я почитал,что ты писал про промежуточное представление,а также последний пост,и подумал,а ведь промежуточное представление это не меньший геморрой,ведь внутри некоторых стэйтментов могут быть вложенные инструкции,а сколько их,заранее не известно.. Есть такая идея - просто модифицировать синтаксический парсер так,чтобы он проходил исходник 2 раза,используя некое логическое значение.Просто нужно хорошенько подумать,какие операции делать в первом проходе(то есть создавать ли переменные,ведь нужно проверять их на инициализацию и т.д.).Или просто сделать какие-то исключения только для пропускаемых блоков,и проходить по блоку в любом случае,просто затем освобождать переменные и не делать печати и т.д.Это бы позволило сократить объём работы,и продвигаться в чём-то ещё(например интерпретация различных вариантов ошибок и т.д.).Или ты считаешь,что без промежуточного представления невозможно двигаться дальше,и переделка начинки необходима ?
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
14.08.2009, 13:43     Пишем свой интерпретатор языка BASIC #79
Цитата Сообщение от #pragma Посмотреть сообщение
ведь внутри некоторых стэйтментов могут быть вложенные инструкции,а сколько их,заранее не известно..
Например?

Цитата Сообщение от #pragma Посмотреть сообщение
Есть такая идея - просто модифицировать синтаксический парсер так,чтобы он проходил исходник 2 раза,используя некое логическое значение
Конечно же, можно делать и так. Но ведь при этом проблемы с локальными переменными и обеспечением нормальной работы рекурсивных процедур никуда не денутся.

Цитата Сообщение от #pragma Посмотреть сообщение
Или ты считаешь,что без промежуточного представления невозможно двигаться дальше,и переделка начинки необходима ?
Нет, так я не считаю. Мне просто кажется, что при поддержке нормальных процедурных механизмов работать с промежуточным представлением удобнее. Точно я этого знать не могу, так же как и ты, ибо интерпретаторов не писал Но пока мне кажется именно так. К тому же в таком варианте гораздо проще приделать встроенный отладчик (понятно, что довод про отладчик не стОит учитывать при выборе метода, ибо хз когда до него доберёмся, если доберёмся вообще)

Сейчас как бы не получилось так, что ты замахнулся слишком высоко, а потом это реализоватьне получится. Вариант с двумя проходами по файлу вот ещё чем хорош. Поскольку нет промежуточного представления, то внутренние структуры данных не будут претерпевать сильных изменений, в случае если делать язык без процедур, а потом добавить процедуры. В идеале меняться не должо ничего, только добавляться
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
14.08.2009, 14:18  [ТС]     Пишем свой интерпретатор языка BASIC #80
Цитата Сообщение от Evg Посмотреть сообщение
Например?
Ну например
PureBasic
1
2
3
4
IF () {
     IF (){
          IF(){
#   Неизвестное количество раз
Цитата Сообщение от Evg Посмотреть сообщение
Сейчас как бы не получилось так, что ты замахнулся слишком высоко, а потом это реализоватьне получится. Вариант с двумя проходами по файлу вот ещё чем хорош. Поскольку нет промежуточного представления, то внутренние структуры данных не будут претерпевать сильных изменений, в случае если делать язык без процедур, а потом добавить процедуры. В идеале меняться не должо ничего, только добавляться
Я уже понял,что процедуры пока слишком сложно(то есть много работы,просто неохота долго работать над чем-то,что не знаешь,будет ли работать вообще,и требует переделки программы).Есть такое поверье-фирмы хайтек падают не при создании первой версии,а при переходе на вторую,иногда получается,что переделывать слишком много .Так что я за парсинг два раза,просто пока отказываемся от процедур.Я пока стараюсь немного причесать код,кое-где подправил условия,как ты предложил,так действительно лучше(проинвертированные условия),также добавил работу с препроцессором,что немного уменьшило выходной файл.Ещё я поубавил отступы,код выглядит поплотнее,но не знаю,я только надеюсь,что это не ухудшило читабельность,мне то трудно судить,я его уже знаю от и до ..
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
14.08.2009, 20:43     Пишем свой интерпретатор языка BASIC #81
Цитата Сообщение от #pragma Посмотреть сообщение
Ну например
PureBasic
1
2
3
4
IF () {
     IF (){
          IF(){
#   Неизвестное количество раз
Но ведь тебе никто не мешает распарсить выражение a+a+a+...<неизвестное количество раз> и построить его в виде дерева. Так же и здесь если в лоб, что всё будет в виде дерева (без бумажки нарисовать трудно). Либо всё делать линейно (т.е. вообще отказаться от оператора IF в промежуточном представлении, заменив егона пару операций BRANCH и COND_BRANCH). В любом случае в процессе распарсивания у тебя будет рекурсивный вызов одного и того же синтаксического правила, а за счёт этого построится либо нужное количество уровней в дереве, либо нужное количество операций перехода

Цитата Сообщение от #pragma Посмотреть сообщение
Есть такое поверье-фирмы хайтек падают не при создании первой версии,а при переходе на вторую,иногда получается,что переделывать слишком много
Я потому тебя и веду по тому пути, чтобы пришлось переделывать. Ибо только занимаясь этим на практике можно реально понять КАК надо писать программу, чтобы она в будущем легко переделывалась, а так же сразу закладываться на какие-то переделки, которые сейчас не нужны, но теоретически могут понадобиться в будущем

Цитата Сообщение от #pragma Посмотреть сообщение
Так что я за парсинг два раза,просто пока отказываемся от процедур.Я пока стараюсь немного причесать код,кое-где подправил условия,как ты предложил,так действительно лучше(проинвертированные условия),также добавил работу с препроцессором,что немного уменьшило выходной файл.Ещё я поубавил отступы,код выглядит поплотнее,но не знаю,я только надеюсь,что это не ухудшило читабельность,мне то трудно судить,я его уже знаю от и до ..
Значит пока одна большая проблема снимается с повестки дня. ТОгда надо взять за основу какой-то из существующих бэйсиков. Если все они с процедурами, то просто выкидываем поддержку процедур. Тестовых примеров насребём в соотвествующем разделе форума. Щас я туда закину вопрос по поводу всех этих бэйсиков

Добавлено через 5 минут 26 секунд
Закинул сюда Вопрос про разные реализации бэйсиков

Добавлено через 1 час 16 минут 21 секунду
Пока не забыл. Функции тем не менее остаются, но только встроенные (SIN, COS и т.п.). С точки зрения парсера удобнее считать, что это keyword'ы - проще получается разбор. С точки зрения дальнейшей поддержки функций лучше считать, что это IDENT, а дальше уже разбираться, у нас идёт обращение к переменной или вызов функции

Добавлено через 4 часа 31 минуту 32 секунды
Кстати, звучит как парадокс, но вариант с промежуточным представлением проще, чем с двумя проходами. Хотя тебе полезно сделать оба варианта (сначала "плохой")
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
15.08.2009, 23:25  [ТС]     Пишем свой интерпретатор языка BASIC #82
Так,думаю,нужно подвести некоторые итоги.Я сейчас недаром застрял,я думал над реализацией промежуточного представления,но что-то никак не укладывается в голове,как вообще это организовать,то есть не вижу реализации за идеей.Вот смотрю на твой пример реализации и просто не понимаю,что с чем там будет связываться,если будет строиться дерево,то есть как после построения дерева его потом разгребать.Самое непонятное для меня это то,что переменные по ходу работы программы могу меняться,и как это связывается с деревом,вообщем бардак полный в голове Вариант с пропуском кода не лучше,то есть как-то не видится вариант реализации,делать флаги какие-то,что-ли,что-бы передавались в функции,а потом их менять после выхода из пропускаемого блока... это тоже не так просто.Это надо тогда подпортить все функции этими флагами. Понять бы получше механизм промежуточного представления,в каком точно виде всё это дерево будет и что будет его читать.

Насчёт системы тестирования-реально полезная вещь,которая позволила мне исправить кучу логических ошибок без особых затрат!Теперь даже можно сделать такой исходник
PureBasic
1
DIM int a,int b,int c;LET a = 6;LET b = 3;IF (b>2){WHILE (b<4){IF (b<4){PRINT a;}ELSE{PRINT "Hello";}FI;PRINT b," ";PRINT " ",a," ";}LOOP}ELSE{PRINT b;}FI
То есть главное,чтобы были разделители команд,или перевод строки.
Правда пришлось делать скидку на то,что блоки в IF и WHILE пропускаются без разбора,но даже и так много изменил всяких мелочей.Пока ещё вложенность условий не поменял везде(имею ввиду непроинвертированные),но кое-что подправил.Код прилагаю,посмотри,как выглядит syntax_parser.cpp,там я поменял больше всего с точки зрения отступов и т.д.Меня очень интересует мнение по оформлению,стал ли код менее читабельным.Я расположил строки немного плотнее.
Вложения
Тип файла: rar Interpreter.rar (12.9 Кб, 47 просмотров)
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
16.08.2009, 00:27     Пишем свой интерпретатор языка BASIC #83
Я вроде уже писал. Посмотри тут посты 3 и 5. Фактически там у меня сначала строится промежуточное представление (когда выражение представлено в виде дерева), а потом обходится и обсчитывается (по сути происходит исполнение)

В данном примере по сути делается то, что должно быть в промежуточном представлении на тех местах, где идёт выражение. Если опять непонятно, буду думать, как объяснять. Проще всего было бы набросать рабочий исходник на Си для демонстрации. Может, если не поленюсь, набросаю какой-нибудь кастрированный вариант

Добавлено через 11 минут 13 секунд
Исходники потом гляну
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
17.08.2009, 16:55  [ТС]     Пишем свой интерпретатор языка BASIC #84
Я посмотрел твои исходники,вроде всё понятно,но я не представляю,что изменить именно в моей реализации,как-то смутно всё.Как будто снова вернулся к отправной точке,когда только начинал перекраивать калькулятор.Просто не могу представить механизм работы после промежуточного представления. Может,я просто морально не готов писать всё заново Но если бы точно представлял,что и как сделать,то наверное переделал бы.
Я решил проблему с динамической памятью,оказалось,всё просто.С самого начала я не пользовался динамической памятью,но тогда прога вылетала,и я ошибочно подумал,что это необходимо,использовать new.Теперь я просто передаю сами объекты из функций.Всё использование динамической памяти было полностью убрано из программы.
Ещё я добавил оператор GOTO.
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
17.08.2009, 17:52     Пишем свой интерпретатор языка BASIC #85
Цитата Сообщение от #pragma Посмотреть сообщение
Я посмотрел твои исходники,вроде всё понятно,но я не представляю,что изменить именно в моей реализации,как-то смутно всё.Как будто снова вернулся к отправной точке,когда только начинал перекраивать калькулятор.Просто не могу представить механизм работы после промежуточного представления. Может,я просто морально не готов писать всё заново Но если бы точно представлял,что и как сделать,то наверное переделал бы.
Морально быть готовым написать заново - тоже важно И в этом вопросе я тебя понимаю.

Промежуточное представление - это некий набор структур данных, связанных между собой, которые отражают исходную программу. Пример отображения выражения ты уже видел - это дерево. Сейчас попробую на пальцах объяснить, как хранить операторы и пока не забыл, скажу: про непонятки лучше спрашивать максимально конкретно, а то какие-то вещи для меня слишком очевидны, что я за общими вопросами могу и не увидеть проблему

Программа у тебя состоит из цепочки операторов. Нам всю эту цепочку надо иметь в некотором внутреннем виде, который мы затем будем интерпретировать. Если помнишь мои предыдущие пояснения, то структуры, хрянащиеся в списке, я хранил в одном флаконе: данные и топологию (т.е. как элементы связаны между собой). Мне такой вариант кажется более удобным, но я его не навязываю. Просто я сам не смогу внятно написать всё это с использованием stl'ских контейнеров, поэтому напишу именно по-своему - так хоть есть вероятность, что поймёшь

Рассмотрим для начала простой код. Если ты это не поймёшь, будем жевать подробнее, если поймёшь - попробуем двигаться дальше. Поэтому для начала простой пример

PureBasic
1
2
3
4
LET a = 5
LET b = 3
PRINT a
PRINT b
Считаем, что у анс есть простая реализация языка, в которой в переменную можно присвоить значение (пока без выражения), и можно распечатать переменную. Итого, у нас есть два оператора: "LET <var> = <value>" и "PRINT <var>". Теперь нам эту программу нужно сохранить в некотором внутреннем виде, чтобы дальше можно было работать без файла.

Промежуточное представление будет состоять из statement'ов. Все они провязаны в список по очереди через поле next (см. ниже). Структура для хранения представления statement'а в таком упрощённом случае следующая

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
enum StatementKind
{
  STMK_LET,
  STMK_PRINT
};
 
struct Statement
{
  // Через это поле мы провязываем всё в список
  struct Statement *next;
 
  // Тип statement'а
  StatementKind kind;
 
  union
  {
    // Данные для LET
    struct
    {
      Variable *var; // левая часть присваивания
      Value *val;  // правая часть присваивания
    } let;
 
    // Данные для PRINT
    struct
    {
      Variable *var; // в простейшем случае у нас только один аргумент в виде переменной
    } print;
  } data;
}
Я здесь для переменных испольхзую ссылку Variable. Ты у себя в коде использовал некое целое число, которое определяет положение в векторе. Можно хранить и число, но на мой взгляд удобнее хранить непосредственно ссылку на Variable. Ты для начала делай так, как тебе более понятно, а потом уже будем пределывать "как правильно"

При таком раскладе привожу код, который "вручную" создаёт промежуточное представление. Чтобы понятно было, что у нас в итоге получится. Понятно, что аналогичное представление у тебя будет строиться в процессе работы парсера. Разделяю построение каждого оператора отдельно (ибо реально они будут отдельно), перменная Last моделирует некую глобальную переменную

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Statement *s1 = new (хз как там правильно), *s2, *s3, *s4 - создаются аналогично динамически
Statement *Last = NULL;
 
// Создание промежуточного представдения оператора "LET a=5"
s1->next = NULL;
s1->kind = STMK_LET;
s1->data.let.var = var; // подразумеваем, что в 'var' уже лежит указаель на созданную Variable, соотвествующую нашей 'a'
s1->data.let.val = val; // подразумеваем, что в 'val' уже создана Value, соотвествующая константе 5
Last = s1;
 
// Создание промежуточного представдения оператора "LET b=3"
s2->next = NULL;
s2->kind = STMK_LET;
s2->data.let.var = var; // подразумеваем, что в 'var' уже лежит указаель на созданную Variable, соотвествующую нашей 'b'
s2->data.let.val = val; // подразумеваем, что в 'val' уже создана Value, соотвествующая константе 3
Last->next = s2; // прицепляем к последнему оператору
Last = s2;
 
// Создание промежуточного представдения оператора "PRINT a"
s3->next = NULL;
s3->kind = STMK_PRINT;
s3->data.print.var = var; // подразумеваем, что в 'var' уже лежит указаель на созданную Variable, соотвествующую нашей 'a' (точно такой же указатель, как и в "LET a=5")
Last->next = s3; // прицепляем к последнему оператору
Last = s3;
 
// Создание промежуточного представдения оператора "PRINT b"
s4->next = NULL;
s4->kind = STMK_PRINT;
s4->data.print.var = var; // подразумеваем, что в 'var' уже лежит указаель на созданную Variable, соотвествующую нашей 'b' (точно такой же указатель, как и в "LET b=3")
Last->next = s4; // прицепляем к последнему оператору
Last = s4;
В итоге мы получили в памяти интерпретатора некий набор данных, который целиком отразил нашу исходную программу. С этого момента файл нам больше не нужен. После построения промежточного представления запускается второй проход, который его интерпретирует. В нашем простом случае мы просто проходимся по цепочке операций, в каждой операции смотрим поле kind, понимаем, что это за операция, смотрим в data для соотвествующего типа (kind) операции. Когда мы видим операцию присваивания, мы понимаем, что нам нужно исполнить что-то типа "s->data.let.var->SetValue(s->data.let.val)" (ну или как там оно у тебя реализовано, с ходу не помню). Когда мы видим операцию печати, то делаем "(s->data.print.var->GetValue()).PrintValue". Я всё это пишу условно, без детальной привязки к тому, как у тебя реализованы сейчас Variable и Value

Давай пока на этом остановлюсь. И жду уже более конкретных вопросов

Цитата Сообщение от #pragma Посмотреть сообщение
Я решил проблему с динамической памятью,оказалось,всё просто.С самого начала я не пользовался динамической памятью,но тогда прога вылетала,и я ошибочно подумал,что это необходимо,использовать new.Теперь я просто передаю сами объекты из функций.Всё использование динамической памяти было полностью убрано из программы.
Ну подобные моменты я видел, планировал устранить это в процессе капитальной чистки мусора после того, как наметится окончательная схема. Ну если сам разобрался - одной проблемой меньше

Цитата Сообщение от #pragma Посмотреть сообщение
Ещё я добавил оператор GOTO.
Вперёд он тоже прыгает? И приведи пример исходника, который уже работает (попробуй включить GOTO вовнутрь IF'а)
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
17.08.2009, 18:35  [ТС]     Пишем свой интерпретатор языка BASIC #86
Пыгает вроде.. у меня сами метки создаются в глобальной таблице,так что неважно,куда прыгать..В сообщение твоё сейчас буду вникать.
А вот пример:
PureBasic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#
# Это пример небольшой программы
# на языке,подражающем
# языку BASIC.
#
#
 
DIM int a,int b,int c;
 
LET a = 6;
LET b = 3;
 
 
 
IF (b>2)
{   label:;
    INPUT "Введите значение с : ",c;
    WHILE (b<4)
    {
        IF (b<4)
        {
            PRINT a;
            GOTO label:;
        }
        ELSE
        {
            PRINT "Hello";
        }
        FI;
        PRINT "Значение b: ",b;
        PRINT "Значение a: ",a;
    }
    LOOP
}
ELSE
{
    LET b=b+1;
    PRINT b;
    GOTO label;
}
FI
Реализация такая:
В главной функции:
C++
1
2
3
                 case TOKEN_KW_GOTO:
                     syntax_parserStmtKwGOTO ();
                 break;
сама таблица:
C++
1
map <const std::string,s_count> parser_GotoCases;
Поместил её в парсер вместе с другими..s_count это порядковый номер символа в коде,где находится метка(typedef long s_count)
А это в syntax_parser.cpp:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/* ************************************************************************** */
   static void syntax_parserStmtKwGOTO ()
   {
       StmtKwGOTO1:;
       switch (parser_GetToken())
       {
           case TOKEN_EOL:   goto StmtKwGOTO1;
           case TOKEN_IDENT: {
               map <const string,s_count>::iterator i =
                                    parser_GotoCases.find(::parser_CurTokenStr);
               if (i == parser_GotoCases.end())
                   error(UNKNOWN_CASE_LABEL,::parser_CurTokenStr);
               // Goto symbol that label pointing to
               source.seekg(parser_GotoCases[::parser_CurTokenStr]);
               ::parser_CurSymbol = source.tellg();
           break;
           }
           default: error(IDENTIFIER_EXPECTED);
       }
       // Now token is label name
       // in place of label creation.
       // Need to skip it and colon
       // will be skipped in Main cycle
       parser_GetToken();
   }
/* ************************************************************************** */
   static void syntax_parserLabelCreate ()
   {
       map <const string,s_count>::iterator i =
                                    parser_GotoCases.find(::parser_CurTokenStr);
       if (i != parser_GotoCases.end())
           error(DUPLICATE_CASE_LABEL,::parser_CurTokenStr);
       parser_GotoCases[::parser_CurTokenStr] = ::parser_CurSymbol;
 
       LabelCreate1:;
       switch(parser_GetToken())
       {
           case TOKEN_EOL:   goto LabelCreate1;
           case TOKEN_COLON: parser_GetToken();
                             break;
           default: error(COLON_EXPECTED);
       }
   }
/* ************************************************************************** */
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
17.08.2009, 18:51  [ТС]     Пишем свой интерпретатор языка BASIC #87
А да,та версия,что я выкладывал,ещё без GOTO,так что вот новая
Вложения
Тип файла: rar Interpreter.rar (13.2 Кб, 47 просмотров)
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
17.08.2009, 19:41  [ТС]     Пишем свой интерпретатор языка BASIC #88
Да,теперь мне понятна идея реализации,по крайней мере,направление.Незнаю почему,но когда кто-то целенаправленно объясняет,мозг воспринимает лучше,хотя в исходниках было то же самое.))
Что мне не понятно: как будет организован while ,а также goto при такой реализации?Мы же уже не будем работать с файлом,тогда как узнать,на какую строку/символ прыгать? А так вроде доходит потихоньку,что у нас будут данные,но присваивания и вообще опрерации над ними ещё не произведены,и будут сделаны после.
Как всегда,перекраивать надо с ног до головы

Добавлено через 19 минут 44 секунды
P.S.GOTO прыгает только вперёд.Потому что сначала ему надо узнать метку и создать её,а уже потом прыгать .Я понял о чём ты,скорее всего это разрешается промежуточным представлением.

Добавлено через 19 минут 45 секунды
Я кажется понимаю,goto просто будет хранить порядковый номер следующей инструкции.
Evg
Эксперт CАвтор FAQ
17546 / 5784 / 370
Регистрация: 30.03.2009
Сообщений: 15,931
Записей в блоге: 26
17.08.2009, 19:52     Пишем свой интерпретатор языка BASIC #89
Цитата Сообщение от #pragma Посмотреть сообщение
Пыгает вроде.. у меня сами метки создаются в глобальной таблице,так что неважно,куда прыгать..
Я почему спросил. Если идёт GOTO вперёд, то в момент, когда ты его парсишь, метка ещё не создана, а потому куда переходить пока непонятно. Это тоже непростой момент

Цитата Сообщение от #pragma Посмотреть сообщение
Да,теперь мне понятна идея реализации,по крайней мере,направление.Незнаю почему,но когда кто-то целенаправленно объясняет,мозг воспринимает лучше,хотя в исходниках было то же самое.))
Интерпретатор - это всё-таки не программа школьного уровня по сортировке массива. Тут всё-таки нужны специфические навыки. Ну а в качестве первой серьёзной программы не каждый потянет. Собственно, никто не обещал, что будет легко

Цитата Сообщение от #pragma Посмотреть сообщение
Что мне не понятно: как будет организован while ,а также goto при такой реализации?
Если идея более-меняя ясна, сейчас попробую про операции передачи управления пояснить (чуть позже)

Цитата Сообщение от #pragma Посмотреть сообщение
А так вроде доходит потихоньку,что у нас будут данные,но присваивания и вообще опрерации над ними ещё не произведены,и будут сделаны после.
Промежуточное представление, это некий набор данных, который больше не будет меняться. Если бы мы писали компилятор, то с этого предстваления мы бы строили непосредственно код. Но поскольку у нас интерпретатор, то небольшая часть промежуточного представления будет меняться, а именно - значения переменных. Больше меняться ничего не должно. В своих примерах я Value делал в виде указателя (на некий динамический объект), но технически скорее всего будет удобнее внутри Variable хранить Value по значению (а не по ссылке)

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

Цитата Сообщение от #pragma Посмотреть сообщение
Как всегда,перекраивать надо с ног до головы
Я ж говорю, по большому счёту структура парсера особо и не менялась. Поменяется начинка. Один раз сделав ты на своей шкуре немного лучше начнёшь понимать, как изначально писать программу, пригодную для дальнейшей безболезненной перестановки с ног на голову

Добавлено через 6 минут 35 секунд
Вот так выглядят метка и операция GOTO. Всё это так же является частью поля Statement.data

C
1
2
3
4
5
6
7
8
9
10
11
struct
{
  // Тут по большому счёту для интерпретации ничего не надо, т.к. метка по своей
  // сути это пустой оператор, выполняющий точку привязки. Тут всякая отладочная
  // информация и больше ничего
} label;
struct
{
  // Указатель на statement, на который мы переходим
  Satament *label;
} goto;
Тут вроде бы с одной стороны просто, с другой стороны может показаться чемто нетривиальным и непонятным. Этот момент дальше нужно пояснять?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.08.2009, 20:05     Пишем свой интерпретатор языка BASIC
Еще ссылки по теме:
C++ Написать интерпретатор программного языка -помощь
C++ Интерпретатор музыки стандарта BASIC PLAY на С++
Задание: разработать "Интерпретатор языка". С чего начать? C++
C++ Перепишите пожалуйста код программы с языка Visual Basic в C++
По русскому названию языка программирования определить английское название этого языка C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
#pragma
Временно недоступен
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
17.08.2009, 20:05  [ТС]     Пишем свой интерпретатор языка BASIC #90
Да,всё вроде понятно теперь. Пока что у меня GOTO действительно только назад прыгает.
Yandex
Объявления
17.08.2009, 20:05     Пишем свой интерпретатор языка BASIC
Закрытая тема Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru