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

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

Войти
Регистрация
Восстановить пароль
 
erikar1
0 / 0 / 0
Регистрация: 11.11.2014
Сообщений: 38
#1

Сделать вывод КС-грамматики - C++

11.11.2014, 21:55. Просмотров 1291. Ответов 6
Метки нет (Все метки)

Помогите пожалуйста реализовать программу
1. S->SaS 5. A->b
2. S->A 6. B->Bb
3. A->Aa 7. B->BaBb
4. A->BA 8. B->a
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.11.2014, 21:55
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сделать вывод КС-грамматики (C++):

Составление грамматики - C++
Кто делал задачу из книги Страуструпа "Принципы и практика использования С++": Напишите программу, проверяющую корректность...

По поводу грамматики - C++
Поясните почему следующее не правильно #define TEXT_HELLOW(name) '\"' ## HELLOW##name ## '\"' ... main(...){ ... ...

Страуструп. Грамматики. Парсер - C++
Собственно начал читать этого дядьку и наткнулся на парсер. Он объясняет суть парсинга с использование грамматик. Однако с грамматиками я...

Реализация анализатора LL(1)-грамматики - C++
Доброго времени суток! Необходимо разработать программную реализацию синтаксического анализатора LL(1)-грамматики и соответствующей...

Создание правильной грамматики - C++
Сделал простой парсер с действиями + и - .(Максимально следовал Страуструпу) Но выражение типа 10-2+2 считается как 10-(2+2) и в итогк...

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

6
BRcr
4015 / 2305 / 156
Регистрация: 03.02.2011
Сообщений: 5,064
Записей в блоге: 10
12.11.2014, 11:34 #2
Не стоит, наверно, рассчитывать на толпу знатоков формальной грамматики.

Для начала неплохо было бы подробно пояснить, что программа должна делать, какие данные получать на входе и какие выдавать на выходе - и лучше всего показать это на примере.
1
Kastaneda
Jesus loves me
Эксперт С++
4756 / 2960 / 243
Регистрация: 12.12.2009
Сообщений: 7,516
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 15:20 #3
Я так понимаю a и b - это "терминаторы" (точного названия не помню), а A, B, S - не терминаторы. Могу предположить, что вводится строка вида "aaabbbabababaabbb", нужно вывести что-то типа "SBABBAS".
Рекурсия в помощь. Задача не сложная, если иметь некоторый опыт в написании подобных вещей.
0
silent_1991
Эксперт С++
5006 / 3064 / 149
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
12.11.2014, 15:29 #4
Цитата Сообщение от Kastaneda Посмотреть сообщение
Я так понимаю a и b - это "терминаторы"
Терминалы
Цитата Сообщение от Kastaneda Посмотреть сообщение
A, B, S - не терминаторы
Соответственно, нетерминалы.
Цитата Сообщение от Kastaneda Посмотреть сообщение
Могу предположить, что вводится строка вида "aaabbbabababaabbb", нужно вывести что-то типа "SBABBAS".
Думаю, не совсем так. Скорее нужно для введённого слова построить дерево вывода. Т.е. цепочку замен одних последовательностей смеси терминалов и нетерминалов другими, причём так, чтобы в конце получилась аксиома грамматики (т.е. нетерминал S в данном случае). Таким образом мы проверим, принадлежит ли введённое слово грамматике, и в то же время покажем, как его можно получить, просто проиграв полученную цепочку наоборот (от S к введённому слову).
0
Kastaneda
12.11.2014, 15:43
  #5

Не по теме:

Цитата Сообщение от silent_1991 Посмотреть сообщение
Терминалы
я еще подумал об этом, сомнения меня взяли что-то.

0
EVP
489 / 257 / 44
Регистрация: 14.12.2010
Сообщений: 515
12.11.2014, 19:37 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от erikar1 Посмотреть сообщение
Помогите пожалуйста реализовать программу
1. S->SaS 5. A->b
2. S->A 6. B->Bb
3. A->Aa 7. B->BaBb
4. A->BA 8. B->a
Так? :
Кликните здесь для просмотра всего текста
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
/*
S->SaS
S->A
A->Aa
A->BA
A->b
B->Bb
B->BaBb
B->a
 
S->SaS->AaA->AaaAa->BAaaBAa->BbaaBba->BbbaaBbba->BaBbbbaaBaBbbba->aaabbbaaaaabbba
         S
         |
S    -   a   -  S
|               |
A               A
|               |
A - a           A - a
|               |
B - A           B - A
|   |           |   |
|   b           |   b
|               |
B - b           B - b
|               |
B - a - B - b   B - a - B - b
|       |       |       |
a       a       a       a
 
 
S->SaS->AaA->BAaBA->BAaaBAa->BbaaBba->BaBbbaaBaBbba->BbaBbbbaaBbaBbbba->abaabbbaaabaabbba
         S
         |
S    -   a   -  S
|               |
A               A
|               |
B - A           B - A
|   |           |   |
|   A - a       |   A - a
|   |           |   |
|   b           |   b
|               |
B - a - B - b   B - a - B - b
|       |       |       |
B - b   B - b   B - b   B - b
|       |       |       |
a       a       a       a
 
*/
 
#include <iostream>
#include <string>
 
enum ES{
    S_1 = 0x1,//S->SaS
    S_2 = 0x2,//S->A
    SStateDefault = 0xF,
};
enum EA{
    A_1 = 0x1,//A->Aa
    A_2 = 0x2,//A->BA
    A_3 = 0x4,//A->b
    AStateDefault = 0xF,
};
enum EB{
    B_1 = 0x1,//B->Bb
    B_2 = 0x2,//B->BaBb
    B_3 = 0x4,//B->a
    BStateDefault = 0xF,
};
 
std::string input;
int position = 0;
 
void setInput(const std::string& _input)
{
    input = _input;
    position = 0;
}
 
int getPosition()
{
    return position;
}
 
void setPosition(int pos)
{
    position = pos;
}
 
std::string::value_type next()
{
    if (input.size() > position)
        return input[position++];
    return '?';
}
 
bool B(int state)
{
    int resPos = -1;
    int pos = getPosition();
    if (state & B_1)//B->Bb
    {
        int ns = state & (~B_1);
        do{
            if (!B(ns))
                break;
            if (next() != 'b')
                break;
            resPos = getPosition();
        } while (false);
        setPosition(pos);
    }
    if (state & B_2)//B->BaBb
    {
        int ns = state & (~B_2);
        do{
            if (!B(ns))
                break;
            if (next() != 'a')
                break;
            if (!B(ns))
                break;
            if (next() != 'b')
                break;
            if (resPos < getPosition())
                resPos = getPosition();
        } while (false);
        setPosition(pos);
    }
    if (next() == 'a')//B->a
    {
        if (resPos < getPosition())
            resPos = getPosition();
    }
    if (resPos > 0)
    {
        setPosition(resPos);
        return true;
    }
    setPosition(pos);
    return false;
}
 
bool A(int state)
{
    int resPos = -1;
    int pos = getPosition();
    if (state & A_1)//A->Aa
    {
        int ns = state & (~A_1);
        do{
            if (!A(ns))
                break;
            if (next() != 'a')
                break;
            resPos = getPosition();
            //return true;
        } while (false);
        setPosition(pos);
    }
    if (state & A_2)//A->BA
    {
        int ns = state & (~A_2);
        do{
            if (!B(BStateDefault))
                break;
            if (!A(ns))
                break;
            if (resPos < getPosition())
                resPos = getPosition();
            //return true;
        } while (false);
        setPosition(pos);
    }
    if (next() == 'b')
    {
        if (resPos < getPosition())
            resPos = getPosition();
    }
    if (resPos > 0)//A->b
    {
        setPosition(resPos);
        return true;
    }
    setPosition(pos);
    return false;
}
 
bool S(int state)
{
    if (state & S_1)//S->SaS
    {
        int ns = state & (~S_1);
        int pos = getPosition();
        do{
            if (!S(ns))
                break;
            if (next() != 'a')
                break;
            if (!S(ns))
                break;
            return true;
        } while (false);
        setPosition(pos);
    }
    return A(AStateDefault);//S->A
}
 
void check(const char* str)
{
    setInput(str);
    bool result = S(SStateDefault);
    if (result)
        std::cout << input << ((input.size() == position) ? " : OK." : " : FAILED.") << std::endl;
    else
        std::cout << input << " : FAILED." << std::endl;
}
 
int main()
{
    //OK:
    check("aaabbbaaaaabbba");
    check("abaabbbaaabaabbba");
    check("aaabbba");
    check("abaabbba");
    //FAILED:
    check("abaabbbab");
    check("babaabbbaaabaabbba");
}
/*Output:
aaabbbaaaaabbba : OK.
abaabbbaaabaabbba : OK.
aaabbba : OK.
abaabbba : OK.
abaabbbab : FAILED.
babaabbbaaabaabbba : FAILED.
*/
1
BRcr
12.11.2014, 20:03     Сделать вывод КС-грамматики
  #7

Не по теме:

Надо же. Беру тогда обратно слова насчет знатоков...

0
12.11.2014, 20:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.11.2014, 20:03
Привет! Вот еще темы с ответами:

Конечные автоматы и грамматики - разобрать код - C++
Доброе утро!Добрые люди сделали программу построения конечных автоматов по регулярным грамматикам.Она рабочая,просто я не могу разобраться...

Неверная реализация синтаксического анализатора LR(1)-грамматики - C++
Здравствуйте. Есть реализация синтаксического анализатора LR(1)-грамматики. Программа должна получить строку p$ или ivtpe$ и сообщить,...

Как выглядит код грамматики Хомского? - C++
Как выглядит код грамматики Хомского?

Организация регулярной грамматики используя конечный автомат, представленный в виде графа - C++
Доброй ночи! Организация регулярной грамматики с помощью конечного автомата, представленного в виде графа. Хочу попросить у вас помощи....


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

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