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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 1509, средняя оценка - 4.80
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
20.06.2009, 20:03     Пишем свой интерпретатор языка BASIC #1
*****************
Благодаря форуму и Evg в частности интерпретатор развивается, потихоньку превращаясь в простенький интерпретатор QBASIC.
Некоторые из самых старых версий сохранились в теме и ссылки на них будут добавлены в это сообщение,а также ссылки на другие темы,связанные с этой.

Репозиторий с проектом находится тут, там же есть возможность в браузере посмотреть историю ревизий (английский в логах весьма примитивен,комментарии и рекомендации можете писать в личку),а также скачать самый последний архив репозитория в формате .tar.gz
Если кто-то пользуется Subversion,скачать исходники можно так:
Код
svn co https://basin.svn.sourceforge.net/svnroot/basin basin
Эти темы возникли в результате моих вопросов по ходу написания:
Технический приём для формирования согласованных данных
Makefile: как с использованием gcc строить автоматические зависимости от .h файлов?
Вопрос по svn (Subversion)
Создание системы тестирования ПО.
Вопрос про разные реализации бэйсиков
[C/C++] Можно ли выразить порядковый номер элемента массива через индексы?
[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)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.11.2011, 17:56     Пишем свой интерпретатор языка BASIC #441
Цитата Сообщение от taras atavin Посмотреть сообщение
Ну слаг же предлагают, а цитаты с вики я дал.
или ты прикидываешь, или второе.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.11.2011, 17:57     Пишем свой интерпретатор языка BASIC #442
Цитата Сообщение от taras atavin Посмотреть сообщение
Почему нельзя получение каждого следующего предложения начинать просто по факту окончания предыдущего? Зачем нужен именно стартовый символ?
чтобы иметь именно входную точку парсера. Ты же не будешь (возвращаясь к моему примеру) начинать синтаксический анализ твоей программы с парсинга списка параметров функции
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
25.11.2011, 17:58     Пишем свой интерпретатор языка BASIC #443
Цитата Сообщение от Nameless One Посмотреть сообщение
если непонятно, представь, что у тебя каждый нетерминал грамматики представлен в виде функции компилятора/интерпретатора, которая принимает исходный код (или, если у тебя есть лексер, поток лексем) и возвращает, к примеру, синтаксическое дерево. Стартовому символу (стартовому нетерминалу) будет соответствовать некоторая функция. Так вот, если передать этой функции исходный код программы (или поток лексем), то она (если код корректен синтаксически) вернет тебе синтаксическое дерево, которое и будет представлять тебе программу
Эйси. А символ то какую роль выполняет? Почему нельзя эту функцию подразумевать без всякого символа?
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.11.2011, 17:58     Пишем свой интерпретатор языка BASIC #444
Nameless One, то, о чем ты говоришь, называется контекстом парсера. я об этом несколькими постами ранее сказал. но ТС походу в танке.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
25.11.2011, 18:01     Пишем свой интерпретатор языка BASIC #445
Цитата Сообщение от Nameless One Посмотреть сообщение
Ты же не будешь (возвращаясь к моему примеру) начинать синтаксический анализ твоей программы с парсинга списка параметров функции
А как я на него с бухты барахты попаду? Предыдущее предложение ведь не посреди текущего закончилось.

Добавлено через 1 минуту
Цитата Сообщение от niXman Посмотреть сообщение
Nameless One, то, о чем ты говоришь, называется контекстом парсера. я об этом несколькими постами ранее сказал. но ТС походу в танке.
А что такое контекст парсера? Сам прасер вроде понятно что такое. Но что такое его контекст?
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.11.2011, 18:04     Пишем свой интерпретатор языка BASIC #446
Цитата Сообщение от taras atavin Посмотреть сообщение
Предыдущее предложение ведь не посреди текущего закончилось.
какое "предыдущее"? Ключевыми словами в моем высказывании было слова "начинать" и "входная точка"
niXman
Эксперт C++
 Аватар для niXman
3133 / 1445 / 49
Регистрация: 09.08.2009
Сообщений: 3,441
Записей в блоге: 2
25.11.2011, 18:08     Пишем свой интерпретатор языка BASIC #447
Цитата Сообщение от taras atavin Посмотреть сообщение
А что такое контекст парсера? Сам прасер вроде понятно что такое. Но что такое его контекст?
http://ru.wikipedia.org/wiki/%D0%9A%...B8%D0%BA%D0%B0

Добавлено через 42 секунды
и в добавок: http://ru.wikipedia.org/wiki/%D0%9A%...B8%D0%BA%D0%B0
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
25.11.2011, 19:53     Пишем свой интерпретатор языка BASIC #448
Цитата Сообщение от Nameless One Посмотреть сообщение
какое "предыдущее"? Ключевыми словами в моем высказывании было слова "начинать" и "входная точка"
То есть это первое предложение? Тогда тем более как ты сразу попадёшь на параметры?

Добавлено через 8 минут
А пример чего нибудь контекстно-зависимого для сравнения с арифметическим выражением?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
25.11.2011, 21:00     Пишем свой интерпретатор языка BASIC #449
Цитата Сообщение от taras atavin Посмотреть сообщение
То есть это первое предложение?
Да, это своего рода базис, к нему в конечном итоге должно "свернуться" корректное предложение грамматики.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2011, 07:39     Пишем свой интерпретатор языка BASIC #450
Я кажется понял, о чём речь. О слове
Pascal
1
program
. Первое предложение должно начинаться с начала файла.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2011, 13:36     Пишем свой интерпретатор языка BASIC #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. Т.е. целевой символ получатся только единожды, в конце разбора. Если парсер не смог дойти до него, или же после того, как он его получил, лексер продолжает возвращать лексемы, то это свидетельствует об ошибке.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2011, 13:58     Пишем свой интерпретатор языка BASIC #452
silent_1991, Эйси. А какое всё это имеет отношение к стартовому символу?
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
26.11.2011, 14:20     Пишем свой интерпретатор языка BASIC #453
Цитата Сообщение от silent_1991 Посмотреть сообщение
к нему в конечном итоге должно "свернуться" корректное предложение грамматики
Цитата Сообщение от silent_1991 Посмотреть сообщение
Суть целевого символа в том, что анализатор в конечном итоге сможет свернуть корректную программу на языке, задаваемом грамматикой, к целевому символу proram.
сворачивать надо к аксиоме, а не к целевому символу
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2011, 14:28     Пишем свой интерпретатор языка BASIC #454
С целевым понятно. Про стартовый растолкуйте.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2011, 14:39     Пишем свой интерпретатор языка BASIC #455
Jupiter, хм, а разве это не синонимы?
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.11.2011, 14:46     Пишем свой интерпретатор языка BASIC #456
Нда. В такой терминологии не то что еврей, чёрт ногу сломит.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.11.2011, 14:49     Пишем свой интерпретатор языка BASIC #457
Насколько мне известно, аксиома грамматики, стартовый символ грамматики, целевой символ грамматики, начальный символ грамматики ("символ" также можно заменить на "нетерминал") - всё это одно и то же понятие - базис разбора, своего рода.

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

int - это терминал => int - цепочка символы которой входят в алфавит
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2013, 20:37     Пишем свой интерпретатор языка BASIC
Еще ссылки по теме:

Пишем свой чекер C++
Не удается откомпилировать интерпретатор М-языка C++
Пишем свой класс, спецификатор доступа protected C++

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

Или воспользуйтесь поиском по форуму:
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.01.2013, 20:37     Пишем свой интерпретатор языка BASIC #460
Пару вопросов - оно собирается под виндой? и что нужно сделать, чтоб коммитить? Всмысле зарегистрироваться на sourceforge или может меня кто-то должен в проект добавить?
Yandex
Объявления
05.01.2013, 20:37     Пишем свой интерпретатор языка BASIC
Закрытая тема Создать тему
Опции темы

Текущее время: 22:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru