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

Нужно посчитать деревья разбора

29.10.2018, 01:49. Просмотров 256. Ответов 0

Здравствуйте,

У меня есть программа на С++ которая считывает слово и контекстную свободную грамматику в нормальной форме хомского и использует алгоритм Кока-Ягнера-Касами чтобы определить возможно ли создать это слово с помощью данной грамматики. Например, если у меня на входе грамматика "S->SS S->a" и слово "аааа", то программа определяет что данное слово может быть создано с помощью этой грамматики.

Проблема в том, что мне нужно также посчитать колличество деревьев разбора (parse trees) и вывести на экран самый левый разбор (left-most derivation) (не знаю как термин будет по русски

Например, для грамматики "S->SS S->a" и слова "аааа" может быть 5 деревьев разбора. Самый левый разбор для этой грамматики и слова:
S->SS
S->SS
S->a
S->a
S->SS
S->a
S->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
#include <iostream>  
#include <string>
#include <iomanip>
#include <fstream>
using namespace std;
 
#define MAX 100
 
 
string gram[MAX][MAX];  //to store entered grammar
string dpr[MAX];
int p,np;       //np-> number of productions
 
string concat( string a, string b)   //concatenates unique non-terminals
{
    string r=a;
    for(int i = 0; i< b.length(); i++)
        if(r.find(b[i]) > r.length())
            r+=b[i];
    return (r);
}
 
void break_gram(string a)    //seperates right hand side of entered grammar
{
    int i;
    p=0;
    while(a.length())
    {
        i=a.find("|");
        if(i>a.length())
        {
            dpr[p++] = a;
            a="";
        }
        else
        {
            dpr[p++] = a.substr(0,i);
            a=a.substr(i+1,a.length());
        }
    }
}
 
 
string gen_comb(string a, string b)  //creates every combination of variables from a and b . For eg: BA * AB = {BA, BB, AA, BB}
{
    string pri=a,re="";
    for(int i =0; i<a.length();i++) {
 
        for(int j = 0; j<b.length(); j++)
        {
            pri="";
            pri=pri+a[i]+b[j];
          //  re=re+search_prod(pri);     //searches if the generated productions can be created or not
 
    string r="";
    for(int x=0; x<np; x++)
    {
        int k=1;
        while(gram[x][k] != "")
        {
            if(gram[x][k] == pri)
            {
                r=concat(r, gram[x][0]);
            }
            k++;
        }
    }   
       re += r;
        }   
 
    }    
    return re;
}
 
int main(int argc, char **argv)
{
 
    if(argc!=3) {
        cout<<"Error: enter 2 command line arguments"<<endl;
        exit(1);
    }
 
    ifstream grammarFile;
    grammarFile.open(argv[1]);
    int pt,l,k;
    string a,str,r,pr,start;
    start = "S";
    int counter = 0;
    while(1)
    {
        grammarFile >> a;
        cout<<a<<endl;
        cout<<"running "<<counter+1<<" times"<<endl;
        
 
        pt=a.find("->");
        gram[counter][0] = a.substr(0,pt);
        a = a.substr(pt+2, a.length());
        break_gram(a);
        for(int j = 0; j<p; j++)
        {
            gram[counter][j+1]=dpr[j];
        }
        ++counter;
          
          if(grammarFile.eof()) {
            break;
        }
    }
    np = counter+1;
    string matrix[MAX][MAX],st;
    str = argv[2];
 
    for(int i = 0; i<str.length(); i++)       //Assigns values to principal diagonal of matrix
    {
        r="";
        st = "";
        st+=str[i];
        for(int j=0; j < np; j++)
        {
            k=1;
            while(gram[j][k] != "")
            {
                if(gram[j][k] == st)
                {
                    r=concat(r,gram[j][0]);
                }
                k++;
            }
        }
        matrix[i][i]=r;
    }
 
 
    for(int k = 1; k<str.length(); k++)       //Assigns values to upper half of the matrix
    {
    
        for(int j = k; j<str.length(); j++)
        {
            r="";
 
            for(int l=(j-k); l<j; l++)
            {
  
                pr = gen_comb(matrix[j-k][l],matrix[l+1][j]);
              
                r = concat(r,pr);
      
            }
            matrix[j-k][j] = r;
        }
    }
 
 
    for(int i = 0; i<str.length(); i++)   //Prints the matrix
    {
        k=0;
        l=str.length()-i-1;
        for(int j=l; j<str.length();j++)
        {
            cout<<setw(5)<<matrix[k++][j]<<" ";
        }
        cout<<endl;
    }
 
 
        if(matrix[0][str.length()-1].find(start) <= matrix[0][str.length()-1].length())   //Checks if last element of first row contains a Start variable
        {
            cout<<"String can be generated\n";
            return 0;
        } else { 
            cout<<"String cannot be generated\n"; 
        }
 
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.10.2018, 01:49
Ответы с готовыми решениями:

Бинарные деревья: Посчитать количество дедов в бинарном дереве
Функция выбрасывает исключение. Что здесь неправильно,и как написать правильно? int...

Распечатать, посчитать среднее арифметическое, преобразовать в дерево поиска [Бинарные деревья]
Дано идеально сбалансированное дерево. Не выводиться дерево:(... Не понимаю как пройтись по...

Нужно 2 кода слепить в кучу (деревья)
нужно 2 кода слепить в кучу...чтоб получилось что-то существенное...ато я не понимаю....помогите...

Нужно посчитать сумму
Я только начал изучение С++ и вообще программирования поэтому не судите строго! Мне надо найти...

Нужно посчитать сложность алгоритма
Дорогие обитатели форума, нужно посчитать сложность рекурсивной функции удаления вершин из...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.10.2018, 01:49

Программа, считывающая диапазон и выдающая «OK» в случае успешного разбора или «FAIL» в случае неуспешного разбора
Здравствуйте! Недавно начал изучать Visual C++ и пока не получается сделать программу, а очень...

Построение решающих LR разбора и LL разбора
вообщем требуют сдачу долгов по учёбе..а я работаю некогда делать..поэтому обращаюсь сюда. скину...

Задача на деревья нужно переделать
Дано S-выражение, представляющее дерево вида «(РебенокЛевый Родитель РебенокПравый)». Определить...


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

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

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