Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/3: Рейтинг темы: голосов - 3, средняя оценка - 4.67
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
1

Неверная реализация синтаксического анализатора LR(1)-грамматики

01.12.2015, 15:24. Просмотров 533. Ответов 4
Метки нет (Все метки)

Здравствуйте.
Есть реализация синтаксического анализатора LR(1)-грамматики. Программа должна получить строку p$ или ivtpe$ и сообщить, что они правильные.
Но у меня сначала выводит "Применено правило R4" после чего выдает ошибку "string subscript out of range".
Мне кажется, это из-за неправильной реализации команды R4, так как четвертая грамматика - пустая строка, а значит просто записываться Х. Но я могу ошибаться.
Не могли бы вы подсказать, как поправить код.

LR(1)-грамматика:
1) O::=E
2) E::=XB
3) X::=StBeX
4) X::= Λ
5) S::=iV
6) B::=p

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
#include <iostream>
#include <stack>
#include <string>
#include <conio.h>
using namespace std;
 
void main()
{
    setlocale(LC_ALL, "");
    stack<int> stack1;
    stack<char> stack2;
    stack1.push(1);
    string s;
    char table1[11] = { 'O', 'E', 'X', 'B', 'S', 't', 'e', 'i', 'v', 'p', '$' };
 
    int table[13][11] =
    {
        //{  "O""E""X""B""S""t""e""i" "v""p", "$" },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 1, 2, 3, 0, 5, 0, 0, 10, 0, 400, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100 },
        { 0, 0, 0, 4, 0, 0, 0, 0, 0, 12, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 200 },
        { 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 7, 0, 0, 0, 0, 0, 12, 0 },
        { 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 0 },
        { 0, 0, 9, 0, 5, 0, 0, 10, 0, 400, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 300, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0 },
        { 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 600, 0, 0, 0, 600 }
    };
 
 
    cout << "Введите строку: ";
    getline(cin, s);
 
    if (s[s.length() - 1] != '$')
    {
        cout << "Введена неверная строка! Ожидался символ конца строки! - $" << endl;
        return;
    }
 
    int x = 0, y = 0, f;
    for (int i = 0; i < s.length(); i++)
    {
        for (int j = 0; j < 11; j++)
        {
            if (s[i] == table1[j])
            {
                x = j; break;
            }
        }
 
        y = stack1.top();
        f = table[y][x];
 
        switch (f)
        {
        case 2:
        {
                  cout << "Применено правило S2\n";
                  stack1.push(2);
                  stack2.push(table1[x]);
                  break;
        }
        case 3:
        {
                  cout << "Применено правило S3\n";
                  stack1.push(3);
                  stack2.push(table1[x]);
                  break;
        }
        case 4:
        {
                  cout << "Применено правило S4\n";
                  stack1.push(4);
                  stack2.push(table1[x]);
                  break;
        }
        case 5:
        {
                  cout << "Применено правило S5\n";
                  stack1.push(5);
                  stack2.push(table1[x]);
                  break;
        }
        case 6:
        {
                  cout << "Применено правило S6\n";
                  stack1.push(6);
                  stack2.push(table1[x]);
                  break;
        }
        case 7:
        {
                  cout << "Применено правило S7\n";
                  stack1.push(7);
                  stack2.push(table1[x]);
                  break;
        }
        case 8:
        {
                  cout << "Применено правило S8\n";
                  stack1.push(8);
                  stack2.push(table1[x]);
                  break;
        }
        case 9:
        {
                  cout << "Применено правило S9\n";
                  stack1.push(9);
                  stack2.push(table1[x]);
                  break;
        }
        case 10:
        {
                   cout << "Применено правило S10\n";
                   stack1.push(10);
                   stack2.push(table1[x]);
                   break;
        }
        case 11:
        {
                   cout << "Применено правило S11\n";
                   stack1.push(11);
                   stack2.push(table1[x]);
                   break;
        }
        case 12:
        {
                   cout << "Применено правило S12\n";
                   stack1.push(12);
                   stack2.push(table1[x]);
                   break;
        }
        case 100:
        {
                    cout << "Применено правило R1\n";
                    s[i - 1] = 'O';
                    stack1.pop();
                    stack2.pop();
                    i = i - 2;
                    break;
        }
        case 200:
        {
                    cout << "Применено правило R2\n";
                    s[i - 1] = 'E';
                    stack1.pop();
                    stack1.pop();
                    stack2.pop();
                    stack2.pop();
                    i = i - 2;
                    break;
        }
        case 300:
        {
                    cout << "Применено правило R3\n";
                    s[i - 1] = 'X';
                    stack1.pop();
                    stack1.pop();
                    stack1.pop();
                    stack1.pop();
                    stack1.pop();
                    stack2.pop();
                    stack2.pop();
                    stack2.pop();
                    stack2.pop();
                    stack2.pop();
                    i = i - 2;
                    break;
        }
        case 400:
        {
                    cout << "Применено правило R4\n";
                    s[i - 1] = 'X';
                    i = i - 1;
                    break;
        }
        case 500:
        {
                    cout << "Применено правило R5\n";
                    s[i - 1] = 'S';
                    stack1.pop();
                    stack1.pop();
                    stack2.pop();
                    stack2.pop();
                    i = i - 2;
                    break;
        }
        case 600:
        {
                    cout << "Применено правило R6\n";
                    s[i - 1] = 'B';
                    stack1.pop();
                    stack2.pop();
                    i = i - 2;
                    break;
        }
 
        case 1:
        {
                  cout << "Допуск\n";
                  cout << "Правильная строка" << endl; return;
        }
        default:
        {
                   cout << "Неправильная строка" << endl;  return;
        }
        }
    }
 
}
Добавлено через 13 часов 21 минуту
актуально
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2015, 15:24
Ответы с готовыми решениями:

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

Программная реализация алгоритмов лексического и синтаксического анализа
В общем, есть вот такое задание: разработать язык и порождающую грамматику для...

Технологии синтаксического анализа и интерпретации команд
Составить программу, которая проверяет корректность арифметических выражений, в...

Как называется алгоритм для синтаксического анализа?
Всем добрый вечер :) Ищу, значит, алгоритм, который разбирает математическое...

Реализация синтаксического анализатора
Здравствуйте. Необходимо реализовать синтаксический анализатор, который...

4
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
01.12.2015, 15:33 2
В коде разбираться нет желание, строить таблицу вручную - тоже, но чисто по коду (с учётом того, что вы вводите p$), у вас и должно отработать R4. Смотрите, в стеке у вас изначально 1. Во вложенном цикле вы идёте по строке и ищете индекс символа в первой таблице. Символ 'p' расположен по индексу 9, так что x стал равен 9. y стал равен 1, потому что в стеке у вас 1. Во второй таблице по индексу (1, 9) лежит значение 400, что и соответствует R4. Если вы говорите, что это правило не должно быть применено - значит, вы ошиблись при составлении таблицы переходов.
0
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
01.12.2015, 16:04  [ТС] 3
silent_1991, видно коряво написала. Правило R4 как раз должно быть применено, но я не понимаю, как его правильно запрограммировать.
0
silent_1991
Эксперт С++
5009 / 3069 / 270
Регистрация: 11.11.2009
Сообщений: 7,043
Завершенные тесты: 1
01.12.2015, 16:11 4
Цитата Сообщение от Старый Посмотреть сообщение
но я не понимаю, как его правильно запрограммировать
Этого не подскажу, но скажу, откуда ошибка. У вас это правило применяется уже на первой итерации внешнего цикла, i в этот момент равна 0. Вы же в коде обработки правила пытаетесь записать в i-1 элемент строки некий символ. -1 индекса в строке не существует, отсюда исключение. Если вы это и без меня уже поняли, прошу прощения, но только вы понимаете, как работает ваш код, а я уже забыл, как вручную автомат с магазинной памятью для парсинга реализуется.
0
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
01.12.2015, 16:30  [ТС] 5
silent_1991, да знаю, спасибо. Видно буду весь код переписывать.
0
01.12.2015, 16:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.12.2015, 16:30

Построение синтаксического анализатора
Здравствуйте, помогите, пожалуйста, решить задачу: В базе данных Пролога...

Ошибка! Рекурсивный спуск для построения синтаксического анализатора
Запускается, но никаких действий не выполняет. Помогите пожалуйста...

Ошибка! Использование метода рекурсивного спуска для построения синтаксического анализатора
unit Unit1; interface uses Windows, Messages, SysUtils, Variants,...


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

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

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