Форум программистов, компьютерный форум CyberForum.ru

Синтаксический анализатор понятия "скобки" (рекурсия) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
Тома1993
0 / 0 / 0
Регистрация: 17.03.2011
Сообщений: 13
05.10.2011, 19:18     Синтаксический анализатор понятия "скобки" (рекурсия) #1
Здравствуйте, уже замучалась с программой. Нужно построить синтаксический анализатор для понятия скобки.
скобки::=квадратные | круглые
квадратные:: = [ [ квадратные ] ( круглые ) ] | B
круглые::=( ( круглые ) [ квадратные ] ) | А
Моя попытка просто ужасна, но не могу ничего придумать.

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
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
 
bool Square ( string str );
 
main()
{
      
      string str;
      
      cout << "Welcome to program Syntax Analysis of Bracket!" << endl;
      
      cout << "Input your string: " << endl;
      
      cin >> str;
      
      bool Bracket = false;
      
      int i = 0;
      
      if ( (str[i] == 'B') || ( str[i] == '[' )) 
         Bracket = Square ( str );
         
      if ( (str[i] == 'A') || ( str[i] == '(' )) 
         Bracket = Round ( str );
      
 
      system ("pause");
      return 0;     
}
 
bool Square ( string str )
 
{
    bool indSquare = false;
    
    bool indRound = false;
    
    bool Square = false;
    
    int i = 0;
    
    if ( !(str.length()-1))
       {
            if  ( str[i] == 'B' )
                Square = true;
            else //if ( str[i] != 'B' )
            
            {
                 
                 if ( (str[i] == '[') )
                    {
                        i++;
                        while ( str[i] == ' ' )
                              i++;
                            
                        //Check of '[square]'      
                        if ( str[i] == '[' )
                        {
                        
                          while ( str[i] != ']' )
                          {
                             i++; //ÏåðåäâèãГ*åìñÿ ГЇГ® âûðГ*æåГ*ГЁГѕ ГўГ® âëîæåГ*Г*ûõ ГЄГўГ*äðГ*ГІГ*ûõ ñêîáêГ*Гµ  
                             Square ( str );
                          }
                          indSquare = Square;
                          if ( indSquare == true ) 
                             {
                              
                               indSquare = Square;
                              
                             } 
                          else //if ( indSquare != true )
                              {
                                    cout << "There are no square brackets inside the main '[ ]'" << endl;  
                                    cout << "This isn't a brackets" << endl;     
                                    exit;
                              }
                          if ( indSquare == true ) //both square brackets inside the main are right
                             {
                                 i++;    
                                 while ( str[i] == ' ' )
                                       i++;
                                 if ( str[i] == ']' )
                                    indSquare = true;
                                 else
                                     {
                                            cout << "This isn't a brackets, there are no second ']' inside the main brackets" << endl;
                                            exit;  
                                     }
                             }//if ( indSquare == true )
                             
                             
                     }//if ( str[i] != '[') second square bracket
                 else
                     {
                       cout >> "This isn't a brackets, there are no second '['" << endl;
                       exit;
                     }
                 //End of check '(square')    
                     
                 //Check of '(round)'
                         i++;
                         
                         while ( str[i] == ' ' )
                               i++; 
                                
                         if ( str[i] == '(' )
                        {
                        
                          while ( str[i] != ')' )
                          {
                             i++;  
                            Round ( str[i], Square );
                          }
                          indRound = Round;
                          if ( indRound == true ) 
                             {
                              
                               indRound = Round;
                              
                             } 
                          else //if ( indRound != true )
                              {
                                    cout << "There are no second round brackets inside the main '[ ]'" << endl;  
                                    cout << "This isn't a brackets" << endl;     
                                    exit;
                              }
                          if ( indRound == true ) //both square brackets inside the main are right
                             {
                                 i++;    
                                 while ( str[i] == ' ' )
                                       i++;
                                 if ( str[i] == ')' )
                                    indRound = true;
                                 else
                                     {
                                            cout << "This isn't a brackets, there are no second ')' inside the main brackets" << endl;
                                            exit;  
                                     }
                             }//if ( indRound == true )
                             
                             
                     }//if ( str[i] != '(') second round bracket
                 else
                     {
                       cout >> "This isn't a brackets, there are no second '(' inside the main brackets" << endl;
                       exit;
                     }    
                     
                 //End of check '(round)'    
                 
                 
                 }
                 else //if ( str[i] != '[' ) main square bracket
                 {
                      cout << "There are no '[' " << endl;  
                      cout << "This isn't a brackets" << endl;     
                      exit;
                 }
            }    
            
                             
       }//{{if( i <= (string1.length()-1))}     
           
            if ( Square == true ) || ( ( indSquare == true ) && ( indRound == true ) )
               Square = true;
               else
               Square = false;
               
           return Square;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2011, 19:18     Синтаксический анализатор понятия "скобки" (рекурсия)
Посмотрите здесь:

C++ класс для представления понятия "контроллер видеомагнитофона"
C++ Синтаксический анализатор. Рекурсия
Синтаксический анализатор C++
C++ Разработать класс для понятия "Генератор шума"
синтаксический анализатор C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.10.2011, 19:26     Синтаксический анализатор понятия "скобки" (рекурсия) #2
Тома1993, четно говоря лень разбираться в коде, но могу точно сказать, что решение этой задачи есть здесь на форуме. Попробуй воспользоваться поиском
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
05.10.2011, 19:32     Синтаксический анализатор понятия "скобки" (рекурсия) #3
Цитата Сообщение от Тома1993 Посмотреть сообщение
скобки::=квадратные | круглые
квадратные:: = [ [ квадратные ] ( круглые ) ] | B
круглые::=( ( круглые ) [ квадратные ] ) | А
грамматика странная, мб так?

Код
скобки     ::= квадратные | круглые
квадратные ::= [ ] | [ скобки ]
круглые    ::= ( ) | ( скобки )
Тома1993
0 / 0 / 0
Регистрация: 17.03.2011
Сообщений: 13
05.10.2011, 19:35  [ТС]     Синтаксический анализатор понятия "скобки" (рекурсия) #4
Jupiter, задание я скопировала из учебного пособия.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
05.10.2011, 20:41     Синтаксический анализатор понятия "скобки" (рекурсия) #5
Jupiter, ваша грамматика и грамматика ТС не эквивалентны. Например, в грамматике ТС невозможны цепочки [], (), [[]], (()) и тому подобные. У него получаются только цепочки специального вида, вроде [[B](A)], ((A)[B]) и так далее.

Добавлено через 5 минут
Тома1993, вам тут лучше всего воспользоваться рекурсивным спуском, поскольку грамматика не сложная. Функции строятся ровно так, как описана грамматика. Базисы рекурсии соответствующих функций - 'A' и 'B'. Соответственно если в базисе одной функции встретили что-то иное - синтаксическая ошибка. Ну и если на месте ожидаемой скобки тоже встретили что-то другое - синтаксическая ошибка.
Тома1993
0 / 0 / 0
Регистрация: 17.03.2011
Сообщений: 13
07.10.2011, 00:48  [ТС]     Синтаксический анализатор понятия "скобки" (рекурсия) #6
Почти доделала программу, думаю, функции правильные, но с выводом возникли проблемы
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
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
using namespace std;
 
bool Brackets ( istream &is );
 
bool Square ( istream &is );
 
bool Round ( istream &is );
 
int main()
 
{
      string str;
      
      cout << "Welcome to program Syntax Analysis of Bracket!" << endl;
      
      cout << "Input your string: " << endl;
      
      cin >> str; 
 
      stringstream is(str);
      
      Brackets(is);
      if (!Brackets(is))
            cout << "This isn't a brackets" << endl; //Brackets = false
      if (is.peek() >= 0) //есть что-то лишнее в строке
            cout << "This isn't a brackets" << endl;
 
      /*if ( Brackets ( is ) == true )
      {
         if ( Round ( is ) == true )
         cout << "This is round brackets" << endl;
         
         if ( Square ( is ) == true )
         cout << "This is square brackets" << endl;
 
         if ( (Round (is) != true) && (Square(is) != true) )
         {
            if ( is.peek() == 'A' )
                cout << "This is round brackets" << endl;
            else
                cout << "This is square brackets" << endl;
         }
      }
    */
      
      system ("pause");
      return 0;     
}
 
bool Brackets( istream &is )
    {
            
                if (is.peek() == '(')
                    return Round( is );
                else if (is.peek() == '[')
                    return Square( is );
                else if ((is.peek() == 'A') || (is.peek() == 'B'))
                     return true;
                else
                    return false;
    }
     
bool Round( istream &is )
    {
         
              if (is.peek() == 'A')
              {
                    is.get();
                    return true;
                    
              }
     
            if (is.get() != '(')  return false;
            if (is.get() != '(')  return false;
            if (!Round( is ))     return false;
            if (is.get() != ')')  return false;
            if (is.get() != '[')  return false;
            if (!Square( is ))    return false;
            if (is.get() != ']')  return false;
            if (is.get() != ')')  return false;
         
  }
     
bool Square( istream &is )
    {
            
                 if (is.peek() == 'B')
                 {
                    is.get();
                    return true;
 
                 }
     
                    if (is.get() != '[') return false;
                    if (is.get()!= '[')  return false;
                    if (!Square( is ))   return false;
                    if (is.get() != ']') return false;
                    if (is.get() != '(') return false;
                    if (!Round( is ))    return false;
                    if (is.get() != ')') return false;
                    if (is.get() != ']') return false;
        
    }
Yandex
Объявления
07.10.2011, 00:48     Синтаксический анализатор понятия "скобки" (рекурсия)
Ответ Создать тему
Опции темы

Текущее время: 12:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru