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

Реализация анализатора LL(1)-грамматики

28.10.2015, 01:21. Просмотров 1834. Ответов 8
Метки нет (Все метки)

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

У меня есть такой код, но единственная строка, которую он считает верной - i. Не могу найти косяк в программе. Помогите, пожалуйста.
LL(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
#include <iostream>
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "rus");
                         // p  t  e  i  v  $
    char table[11][6] = { { 1, 0, 0, 1, 0, 0 },  //O
                          { 2, 0, 0, 2, 0, 0 },  //E
                          { 4, 0, 0, 3, 0, 0 },  //X
                          { 0, 0, 0, 5, 0, 0 },  //S
                          { 6, 0, 0, 0, 0, 0 },  //B
                          { 7, 0, 0, 0, 0, 0 },  //p
                          { 0, 7, 0, 0, 0, 0 },  //t
                          { 0, 0, 7, 0, 0, 0 },  //e
                          { 0, 0, 0, 7, 0, 0 },  //i
                          { 0, 0, 0, 0, 7, 0 },  //v
                          { 0, 0, 0, 0, 0, 8 }}, //$
 
    str[50], stack[50] = "$S", lenta[50] = " ",
    iset[12] = "OEXSBpteiv$", jset[7] = "pteiv$";
    int x, ilenta = 0, istack = 1, istr = 0, i = 0, j = 0;
    cout << "Введите строку" << endl;
    cin >> str;
    x = strlen(str);
    str[x] = '$';
    str[x + 1] = 0;
    while (str[istr] && stack[0] && table[i][j])
    {
        //cout<<str[istr]<<endl;
        for (j = 0; str[istr] != jset[j] && jset[j]; j++);
        for (i = 0; stack[istack] != iset[i] && iset[i]; i++);
        //cout<<i<<" "<<j<<endl;
        if (j == 6)
            break;
        if (1 <= table[i][j] && table[i][j] <= 6){
            lenta[ilenta++] = table[i][j] + 48
                
                ;
            lenta[ilenta] = 0;
        }
        //cout<<lenta<<endl;
        switch (table[i][j]){
        case 0:
            break;
        case 1:
            stack[istack++] = 'E';
            stack[istack + 1] = 0;
            break;
        case 2:
            stack[istack++] = 'B';
            stack[istack++] = 'X';
            stack[istack + 1] = 0;
            break;
        case 3:
            stack[istack++] = 'X';
            stack[istack] = 'e';
            stack[istack++] = 'B';
            stack[istack] = 't';
            stack[istack++] = 'S';
            stack[istack + 1] = 0;
            break;
        case 4:
            stack[istack--] = 0;
            break;
        case 5:
            stack[istack] = 'v';
            stack[istack] = 'i';
            stack[istack + 1] = 0;
            break;
        case 6:
            stack[istack] = 'p';
            stack[istack + 1] = 0;
            break;
        case 7:
        case 8:
            stack[istack--] = 0;
            istr++;
            break;
        default:
            cout << "Error" << endl;
        }
        //cout<<stack<<endl;
    }
    if (!str[istr] && !stack[0])
        cout << "Верная строка" << endl;
    else
        cout << "Неверная строка" << endl
        << "Ошибка при обработке " << istr + 1 << "-го символа" << endl
        << "В стеке осталось:" << endl
        << stack << endl;
    cout << "Выходная лента:" << endl
        << lenta << endl;
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2015, 01:21
Ответы с готовыми решениями:

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

Исходный код лексического анализатора
Может есть у кого то исходник по ООП программы лексического анализатора Очень...

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

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

Друзья, подскажите где найти исходник лексического анализатора для языка C++!
Очень нужен исходник лексического анализатора языка С++. Есть он где-то в...

8
EVP
502 / 265 / 59
Регистрация: 14.12.2010
Сообщений: 530
28.10.2015, 18:36 2
Лучший ответ Сообщение было отмечено Старый как решение

Решение

Цитата Сообщение от Старый Посмотреть сообщение
LL(1)-грамматика:
1) O::=E
2) E::=XB
3) X::=StBeX
4) X::=B
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
#include <iostream>
#include <utility>
using namespace std;
 
/*
1) O::=E
2) E::=XB
3) X::=StBeX
4) X::=B
5) S::=iv
6) B::=p
*/
 
bool check(const char* _str)
{
    char table[11][6] = {
        //p  t  e  i  v  $
        { 1, 0, 0, 1, 0, 0 },  //O
        { 2, 0, 0, 2, 0, 0 },  //E
        { 4, 0, 0, 3, 0, 0 },  //X
        { 0, 0, 0, 5, 0, 0 },  //S
        { 6, 0, 0, 0, 0, 0 },  //B
        { 7, 0, 0, 0, 0, 0 },  //p
        { 0, 7, 0, 0, 0, 0 },  //t
        { 0, 0, 7, 0, 0, 0 },  //e
        { 0, 0, 0, 7, 0, 0 },  //i
        { 0, 0, 0, 0, 7, 0 },  //v
        { 0, 0, 0, 0, 0, 8 }   //$
    },
        str[50], stack[50] = "$O"/*<<< стартовое правило - O*/, lenta[50] = " ",
        iset[12] = "OEXSBpteiv$", jset[7] = "pteiv$";
    int x, ilenta = 0, istack = 1, istr = 0, i = 0, j = 0;
 
    strcpy(str, _str);
 
    x = strlen(str);
    str[x] = '$';
    str[x + 1] = 0;
    while (str[istr] && stack[0] && table[i][j])
    {
        //cout<<str[istr]<<endl;
        for (j = 0; str[istr] != jset[j] && jset[j]; j++);
        for (i = 0; stack[istack] != iset[i] && iset[i]; i++);
        //cout<<i<<" "<<j<<endl;
        if (j == 6)
            break;
        if (1 <= table[i][j] && table[i][j] <= 6) {
            lenta[ilenta++] = table[i][j] + 48;
            lenta[ilenta] = 0;
        }
        //cout<<lenta<<endl;
        switch (table[i][j]) {
        case 0:
            break;
        case 1:
            stack[istack]       = 'E';
            stack[istack + 1]   = 0;
            break;
        case 2:
            stack[istack]       = 'B';
            stack[++istack]     = 'X';
            stack[istack + 1]   = 0;
            break;
        case 3:
            stack[istack]       = 'X';
            stack[++istack]     = 'e';
            stack[++istack]     = 'B';
            stack[++istack]     = 't';
            stack[++istack]     = 'S';
            stack[istack + 1]   = 0;
            break;
        case 4:
            stack[istack]       = 'B';
            stack[istack + 1]   = 0;
            break;
        case 5:
            stack[istack]       = 'v';
            stack[++istack]     = 'i';
            stack[istack + 1]   = 0;
            break;
        case 6:
            stack[istack]       = 'p';
            stack[istack + 1]   = 0;
            break;
        case 7:
        case 8:
            stack[istack--]     = 0;
            istr++;
            break;
        default:
            cout << "Error" << endl;
        }
        //cout<<stack<<endl;
    }
    bool result = !str[istr] && !stack[0];
    if (result)
        cout << "Верная строка" << endl;
    else
        cout << "Неверная строка" << endl
        << "Ошибка при обработке " << istr + 1 << "-го символа" << endl
        << "В стеке осталось:" << endl
        << stack << endl;
    cout << "Выходная лента:" << endl
        << lenta << endl;
    return result;
}
 
template<typename T, size_t N>
void run(T(&_array)[N])
{
    int allTestsCount = 0;
    int failCount = 0;
 
    for (size_t i = 0; i < N; ++i)
    {
        T& s = _array[i];
        allTestsCount++;
        cout << "Строка: " << s.second << endl;
        if (s.first != check(s.second))
            failCount++;
        cout << "----------------" << endl;
    }
 
    if (!failCount)
        cout << "Все тесты (" << allTestsCount << ") пройдены успешно." << endl;
    else
        cout << "Провалено " << failCount << " из " << allTestsCount << " тестов." << endl;
}
 
int main()
{
    setlocale(LC_ALL, "rus");
 
    std::pair<bool,const char*> tests[] = {
        {true,"pp"},
        {false,"pp2"},
        {true,"ivtpepp"},
        {true,"ivtpeivtpepp"},
        {true,"ivtpeivtpeivtpepp"},
        {false,"ivtpeivtpeivtpeppp"}
    };
 
    run(tests);
 
    system("pause");
    return 0;
}
1
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
28.10.2015, 19:39  [ТС] 3
EVP, спасибо огромное, все поправил.

Функцией run вы проверили как проходят правильные строки?
0
EVP
502 / 265 / 59
Регистрация: 14.12.2010
Сообщений: 530
28.10.2015, 21:56 4
Цитата Сообщение от Старый Посмотреть сообщение
Функцией run вы проверили как проходят правильные строки?
Да.
Сделал для отладки набор тестов, которые либо должны проходить(true), либо нет(false).
И передаю их в метод run(..), который проверяет результат с заданным.
Чтобы не вбивать всё каждый раз заново, всегда надо тесты делать.
1
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
28.10.2015, 22:02  [ТС] 5
EVP, спасибо за разъяснение. Просто преподаватель хочет, чтобы именно каждый раз нужно было вводить. Ну раз, хочет, то сделал. Спасибо еще раз.

И еще вопрос, она мне говорила, что данная грамматика должна принимать строку р как правильную. Она ошибается? У меня тоже не получалось просто ее получить, но я человек доверчивый :/
0
EVP
502 / 265 / 59
Регистрация: 14.12.2010
Сообщений: 530
28.10.2015, 22:26 6
Цитата Сообщение от Старый Посмотреть сообщение
И еще вопрос, она мне говорила, что данная грамматика должна принимать строку р как правильную. Она ошибается?
Чтобы "p" была правильной строкой, второе правило должно быть E::=X или E::=B (но тогда правила X и S ненужны).
А так минимально "pp" правильная строка.
Возможно, она говорила про другую грамматику.

Цитата Сообщение от Старый Посмотреть сообщение
но я человек доверчивый
Книга Компиляторы. Принципы, технологии и инструментарий сделает тебя рассудительным
1
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
28.10.2015, 22:50  [ТС] 7
EVP, нет, про эту. Другой вопрос, что до приведения к свойству LL1(1) первым выражением стояло O::=р, но она сказала, что ее можно и нужно убрать.

За книгу спасибо.
0
Старый
2 / 2 / 0
Регистрация: 24.01.2012
Сообщений: 96
29.10.2015, 23:24  [ТС] 8
EVP, сегодня еще раз говори с преподом, сказала, что эта грамматика точно должна пропускать р.
По идее и вправду должна: От О идем к Е, Х - пустая строка, ее не нужно заносить в стек. А дальше по В - один символ р.

А в коде по четвертой грамматике мы почему-то идем к шестой:
C++
1
2
3
4
case 4:
            stack[istack]       = 'B';
            stack[istack + 1]   = 0;
            break;
В любом случае, требуют, чтобы р пропускали как правильную строку.

Добавлено через 9 минут
Сделал четвертую грамматику так, вроде теперь работает так, как хотят. Надеюсь, примут.

C++
1
2
case 4:
stack[istack--] = 0;
1
EVP
502 / 265 / 59
Регистрация: 14.12.2010
Сообщений: 530
04.11.2015, 13:40 9
Цитата Сообщение от Старый Посмотреть сообщение
Х - пустая строка, ее не нужно заносить в стек.
Да, я четвёртое правило изменил (неправильно интерпретировал). Мой косяк .
0
04.11.2015, 13:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.11.2015, 13:40

Сделать вывод КС-грамматики
Помогите пожалуйста реализовать программу 1. S-&gt;SaS ...

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

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


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

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

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