Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

20.06.2009, 20:03. Просмотров 194468. Ответов 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;
30
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.06.2009, 20:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пишем свой интерпретатор языка BASIC (C++):

Пишем свой чекер - C++
Я хочу написать свой чекер, но не знаю с чего начать? Кто знает основные принцип работы чекеров прошу объясните.

пишем свой троян с нуля - C++
Всем привет)))соглашусь, что изобретаю велосипед, но хочется сделать все своими ручками не прибегая к open source и т.п. для повышения...

Пишем свой класс, спецификатор доступа protected - C++
Всем привет! Из книги Р. Лафоре относительно спецификатора доступа protected: Далее пишется следующее: Возникает вопросы:...

Не удается откомпилировать интерпретатор М-языка - C++
Задача: взять интерпретатор М-языка на сайте http://cmcmsu.no-ip.info/2course/model.lang.parser.sample.htm и переработать его, добавив в...

Интерпретатор небольшого языка программирования на С++ - C++
Здравствуйте, уважаемые форумчане! Я тут где-то год назад прочитал тему Evg и #pragma о создании интерпретатора, меня эта тема очень...

Написать Интерпретатор Программного Языка(собственного) - C++
Здраствуйте! Кто знает C++ помогите пожалуйста с реализацией данного задания!!! Пожалуйста, очень надо. сроки поджимают. Есть...

464
silent_1991
Эксперт С++
4993 / 3051 / 149
Регистрация: 11.11.2009
Сообщений: 7,038
Завершенные тесты: 1
26.11.2011, 13:36 #451
taras atavin, первое предложение языка, задающегося данной грамматикой, а не statement - да, должно начинаться с начала файла, разумеется. Но к целевому символу это имеет мало отношения. Суть целевого символа в том, что анализатор в конечном итоге сможет свернуть корректную программу на языке, задаваемом грамматикой, к целевому символу proram. Потому он и называется целевым, что цель парсера - прийти к нему и только к нему одному в результате свёрток по правилам грамматики.

Добавлено через 1 час 21 минуту
Возьмём грамматику, предложенную Nameless One. Я дополню её, чтобы она была законченной:
Код
program -> definitions
definitions -> definitions definition | 'EPS'
definition -> prototype body
prototype -> typespec qualifier '(' paramlist ')'
paramlist -> param | paramlist ',' param | 'EPS'
param -> typespec qualifier
body -> '{' statements '}'
statements -> statement ';' | statements statement ';' | 'EPS'
typespec -> 'int' # Пусть в качестве типа выступает int и только он (для простоты)
statement -> 'return 0' # Предложением будет мифический терминал 'return 0' (также для простоты)
qualifier -> letters # Я немного изменил грамматику для простоты, теперь как funid, так и varid являются qualifier, который, в свою очередь - набор строчных букв латиницы (как минимум одна буква)
letters -> letter letters | letter 'EPS'
letter -> 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h' | 'i' | 'j' | 'k' | 'l' | 'm' | 'n' | 'o' | 'p' | 'q' | 'r' | 's' | 't' | 'u' | 'v' | 'w' | 'x' | 'y' | 'z'
Также для наглядности я позволил себе внести левую рекурсивность в грамматику. При построении парсера от неё надо избавляться (для этого существует простой алгоритм).

Рассмотрим теперь простую программу на данном языке, состоящую из одной функции:
Код
int a(int b)
{
    return 0;
}
Для начала опишу упрощённую схему работы связки лексический анализатор-синтаксический анализатор. Лексический анализатор возвращает синтаксическому лексемы. Синтаксический (обычно реализуемый при помощи конечного автомата со стековой памятью, хотя есть и другий способы) заталкивает эту лексему в стек (т.н. сдвиг). В стеке хранятся как терминалы, так и нетерминалы (как они там появляются - далее). Если в стеке оказался набор символов (терминальных или нетерминальных), соответствующий какому-то правилу грамматики, эти символы удаляются из стека, а их место занимает нетерминал, порождающий удалённый набор символов. Так в стеке (на начальном этапе содержащем только лексемы) появляются нетерминалы.
А теперь заделаемся парсером и выполним его действия (примерно, лишь для пояснения):
Изначально стек пуст. Лексический анализатор вернул синтаксическому лексему 'int'. Произошёл сдвиг. В стеке
Код
'int'
Для данного терминала существует порождающее правило typespec -> 'int'. Поэтому происходит свёртка по этому правилу. В стеке
Код
typespec
Далее вернулась лексема a'. В стеке
Код
typespec 'a'
Терминал 'a' сворачивается к нетерминалу letter. Происходит свёртка. В стеке
Код
typespec letter
letter, в свою очередь, сворачивается к letters по правилу letters -> letter 'EPS'. Ну а letters сворачивается к qualifier (я объединил две свёртки для наглядности). В стеке
Код
typespec qualifier
Возвращается '('. В стеке
Код
typespec qualifier '('
Затем возвращается 'int', который можно свернуть к typespec. В стеке
Код
typespec qualifier '(' typespec
Возвращается 'b', который снова проводим через цепочку letter -> letters -> qualifier. В стеке
Код
typespec qualifier '(' typespec qualifier
Последовательность typespec qualifier можно свернуть к param, а его сразу можно свернуть к paramlist. В стеке
Код
typespec qualifier '(' paramlist
Возвращается ')' В стеке
Код
typespec qualifier '(' paramlist ')'
Данный набор символов можно свернуть к prototype, что и делает парсер. В стеке
Код
prototype
Возвращается '{', 'return 0', ';', '}'. 'return 0' и ';' можно свернуть к statement, а его с statements. Последовательность '{', statements, '}' сворачивается к body. В стеке
Код
prototype body
Это можно свернуть к definition, а его, в свою очередь, к definitions. В стеке
Код
definitions
Программа завершилась, поэтому definitions можно свернуть к program, к целевому символу. Целевой символ получается только если программа полностью разобрана и она корректна (т.е. удовлетворяет языку, определяемому грамматикой, по которой строился парсер).
Будь в программе две функции, после разбора первой в стеке оказалось бы
Код
definitions
, после разбора второй
Код
definitions definition
Который также свернулся бы к definitions, а только этот definitions в итоге свернулся бы к program. Т.е. целевой символ получатся только единожды, в конце разбора. Если парсер не смог дойти до него, или же после того, как он его получил, лексер продолжает возвращать лексемы, то это свидетельствует об ошибке.
4
taras atavin
3571 / 1755 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
26.11.2011, 13:58 #452
silent_1991, Эйси. А какое всё это имеет отношение к стартовому символу?
0
Jupiter
Каратель
Эксперт С++
6564 / 3985 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.11.2011, 14:20 #453
Цитата Сообщение от silent_1991 Посмотреть сообщение
к нему в конечном итоге должно "свернуться" корректное предложение грамматики
Цитата Сообщение от silent_1991 Посмотреть сообщение
Суть целевого символа в том, что анализатор в конечном итоге сможет свернуть корректную программу на языке, задаваемом грамматикой, к целевому символу proram.
сворачивать надо к аксиоме, а не к целевому символу
0
taras atavin
3571 / 1755 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
26.11.2011, 14:28 #454
С целевым понятно. Про стартовый растолкуйте.
1
silent_1991
Эксперт С++
4993 / 3051 / 149
Регистрация: 11.11.2009
Сообщений: 7,038
Завершенные тесты: 1
26.11.2011, 14:39 #455
Jupiter, хм, а разве это не синонимы?
0
taras atavin
3571 / 1755 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
26.11.2011, 14:46 #456
Нда. В такой терминологии не то что еврей, чёрт ногу сломит.
0
silent_1991
Эксперт С++
4993 / 3051 / 149
Регистрация: 11.11.2009
Сообщений: 7,038
Завершенные тесты: 1
26.11.2011, 14:49 #457
Насколько мне известно, аксиома грамматики, стартовый символ грамматики, целевой символ грамматики, начальный символ грамматики ("символ" также можно заменить на "нетерминал") - всё это одно и то же понятие - базис разбора, своего рода.

Добавлено через 2 минуты
taras atavin, похоже, вы не поняли, в каком контексте здесь понимается термин "символ". В данном случае символ - это не символ в общепринятом определении. Символом может быть терминал ('int', 'do', 'template'), или нетерминал (program, statement, typespec). Вот один такой нетерминальный (не конечный, промежуточный) символ является целевым (начальным, стартовым и т.д.), т .е. таким, к которому всё должно прийти в конце концов.
2
taras atavin
3571 / 1755 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
26.11.2011, 14:57 #458
int входит в алфавит?
0
Jupiter
Каратель
Эксперт С++
6564 / 3985 / 227
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.11.2011, 15:15 #459
Цитата Сообщение от taras atavin Посмотреть сообщение
int входит в алфавит?
алфавит - это множество символов(именно символов char), тобишь все буквы a-zA-Z, все цифры, и все символы допустимые в языке

int - это терминал => int - цепочка символы которой входят в алфавит
1
Kastaneda
Jesus loves me
Эксперт С++
4701 / 2905 / 239
Регистрация: 12.12.2009
Сообщений: 7,399
Записей в блоге: 2
Завершенные тесты: 1
05.01.2013, 20:37 #460
Пару вопросов - оно собирается под виндой? и что нужно сделать, чтоб коммитить? Всмысле зарегистрироваться на sourceforge или может меня кто-то должен в проект добавить?
0
Evg
Эксперт CАвтор FAQ
18449 / 6499 / 454
Регистрация: 30.03.2009
Сообщений: 18,129
Записей в блоге: 29
05.01.2013, 23:07 #461
Мне кажется, что проблема под виндами может быть исключительно с библиотекой SDL, всё остальное - стандартный Си++. Насчёт commit'а - надо у #pragma'ы спрашивать и вкуривать в настройки sourceforge, как там формируются svn-пользователи. #pragma учится, но, судя по профилю, форум посещает. Но для подстраховки спроси его в личку
0
Tochka
0 / 0 / 0
Регистрация: 31.07.2012
Сообщений: 6
10.01.2013, 18:13 #462
Добрый день.
Решил оживить тему ещё одним вопросом про написание интерпретатора.

У меня есть компилятор, который формирует байт код, и ВМ, которая его читает из файла. Я не могу сообразить как к моей ВМ с байт кодом прикрутить работу с остальным миром (окнами и файловой системой). А то получается она работает в сферическом вакууме.
Вариант предложенный здесь (выделить отдельную лексему) не подходит. Хочется сделать реализацию на подобие Java, .NET. Хотелось бы услышать идею реализации.

Заранее спасибо всем откликнувшимся.
0
Evg
Эксперт CАвтор FAQ
18449 / 6499 / 454
Регистрация: 30.03.2009
Сообщений: 18,129
Записей в блоге: 29
10.01.2013, 18:46 #463
В любой реализации байт-кода на самом нижнием уровне должен быть выход на родную операционную систему. Потому что 100%-ых байт-кодов не бывает. В случае java есть какая-то одна (а может несколько библиотек), в процессе исполнения которых вместо байт-кода начинают запускаться родные коды на host'овой машине.

Как технически реализована библиотека - не знаю. Маловероятно, что в язык была внесена какая-то конструкция. Скорее всего библиотека как-то реализована на Си и вокруг неё ручками сделан обвес для виртуальной машины
0
silent_1991
Эксперт С++
4993 / 3051 / 149
Регистрация: 11.11.2009
Сообщений: 7,038
Завершенные тесты: 1
10.01.2013, 20:39 #464
Цитата Сообщение от Tochka Посмотреть сообщение
Хочется сделать реализацию на подобие Java
В джвае такие вещи реализуются через вызовы нативного кода из динамических библиотек. Некоторый метод джава объявляется как native, что говорит виртуальной машине, что он реализован на С/С++/Ассемблере и расположен в динамической библиотеке. Сигнатура метода на языке С++ может быть сгенерирована из файла класса утилитой javah, программист реализует тело метода, компилирует его в динамическую библиотеку, в программе на джава (например, в области статической инициализации класса, содержащего нативный метод) эта библиотека загружается стандартными средствами (через System.load()), и вуаля - метод можно вызывать.
Думаю, в .NET это реализовано идейно так же.
Как видно, без нативного кода не обойтись. Виртуальная машина - всего лишь программа, и доступ к внешнему миру из неё можно получить только так же, как из любой другой программы - через системные вызовы ОС. Их же, в свою очередь, сам программист помещает в разделяемые библиотеки, при этом они должны иметь строго согласованную с ВМ сигнатуру, чтобы ВМ могла их вызвать (фактически, всё это напоминает плагины).
5
Nameless One
13.04.2013, 10:51     Пишем свой интерпретатор языка BASIC
  #465
 Комментарий модератора 
Закрыто. Если кто-то хочет высказаться по теме, пишите в личку.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.04.2013, 10:51
Привет! Вот еще темы с ответами:

Написать интерпретатор программного языка -помощь - C++
Здраствуйте! Ребят, кто хорошо разбирается в C++ помогите пожалуйста с реализацией данного задания или хотя бы подтолкните к решению,...

Интерпретатор/компилятор ассемблер-подобного языка - C++
Привет! Чую, что изобрёл велисипед, даже скорее велопарк, но всё же, поделюсь: Некоторое время назад начал изучать кресты, в целом...

Интерпретатор музыки стандарта BASIC PLAY на С++ - C++
У кого нибудь есть функция или класс, который сможет воспроизводить в С++ напрямую музыкальные строки, записанные в стандарте оператора...

Задание: разработать "Интерпретатор языка". С чего начать? - C++
Здравствуйте, вручили темку на курсовик, ну точнее как вручили, не успел взять то, что хотел - пришлось брать то, что осталось. Плоховато...


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

Или воспользуйтесь поиском по форуму:
465
13.04.2013, 10:51
Закрытая тема Создать тему
Опции темы

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