Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
erikar1
0 / 0 / 0
Регистрация: 11.11.2014
Сообщений: 38
#1

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

11.11.2014, 21:55. Просмотров 1356. Ответов 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
Ответы с готовыми решениями:

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

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

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

Создание правильной грамматики
Сделал простой парсер с действиями + и - .(Максимально следовал Страуструпу) ...

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

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

Для начала неплохо было бы подробно пояснить, что программа должна делать, какие данные получать на входе и какие выдавать на выходе - и лучше всего показать это на примере.
1
Kastaneda
Jesus loves me
Эксперт С++
4824 / 2998 / 345
Регистрация: 12.12.2009
Сообщений: 7,564
Записей в блоге: 2
Завершенные тесты: 1
12.11.2014, 15:20 #3
Я так понимаю a и b - это "терминаторы" (точного названия не помню), а A, B, S - не терминаторы. Могу предположить, что вводится строка вида "aaabbbabababaabbb", нужно вывести что-то типа "SBABBAS".
Рекурсия в помощь. Задача не сложная, если иметь некоторый опыт в написании подобных вещей.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 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
492 / 260 / 58
Регистрация: 14.12.2010
Сообщений: 524
12.11.2014, 19:37 #6
Лучший ответ Сообщение было отмечено Kastaneda как решение

Решение

Цитата Сообщение от 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

Не по теме:

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

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

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

Неверная реализация синтаксического анализатора LR(1)-грамматики
Здравствуйте. Есть реализация синтаксического анализатора LR(1)-грамматики....

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


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

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

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