Случайный афоризм
Подлинно великие писатели - те, чья мысль проникает во все изгибы их стиля. Виктор Мари Гюго
 
новости
поиск по автору
поиск по тематике
поиск по ключевому слову
проба пера
энциклопедия авторов
словарь терминов
программы
начинающим авторам
ваша помощь
о проекте
Книжный магазин
Главная витрина
Книги компьютерные
Книги по психологии
Книги серии "Для чайников"
Книги по лингвистике
ЧАВо
Разные Статьи
Статьи по литературе

Форма пользователя
Логин:
Пароль:
регистрация
 детектив



 драмма



 животные



 история



 компьютерная документация



 медицина



 научно-популярная



 очередная история



 очерк



 повесть



 политика



 поэзия и лирика



 приключения



 психология



 религия



 студенту



 технические руководства



 фантастика



 философия и мистика



 художественная литература



 энциклопедии, словари



 эротика, любовные романы



в избранноеконтакты

Параметры текста
Шрифт:
Размер шрифта: Высота строки:
Цвет шрифта:
Цвет фона:

няется  сбалансированность  только в одной вершине.) Реализовать
на основе этой  идеи  способ  хранения  множеств,  гарантирующий
оценку  в  C*log(n)  действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие  и  малые
вращения.  Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)
     Глава 13. Контекстно-свободные грамматики.

     13.1. Контекстно-свободные грамматики. Общий алгоритм  раз-
          бора.

     Чтобы  определить  то,  что  называют  контекстно-свободной
грамматикой (КС-грамматикой), надо:
     (а) указать конечное множество A, называемое алфавитом; его
элементы  называют символами; конечные последовательности симво-
лов называют словами (в данном алфавите);
     (б) разделить все символы алфавита A на две группы:  терми-
нальные ("окончательные") и нетерминальные ("промежуточные");
     (в)  выбрать среди нетерминальных символов один, называемый
начальным;
     (г) указать конечное число правил грамматики, каждое из ко-
торых должно иметь вид
     K -> X
где K - некоторый нетерминальный символ, а X - слово (в него мо-
гут входить и терминальные, и нетерминальные символы).

     Пусть  фиксирована  КС-грамматика  (мы часто будем опускать
приставку "КС-", так как других грамматик у нас не будет). Выво-
дом в этой грамматике называется последовательность  слов  X[0],
X[1],..., X[n], в которой X[0] состоит из одного символа, и этот
символ  - начальный, а X[i+1] получается из X[i] заменой некото-
рого нетерминального символа K на слово X по  одному  из  правил
грамматики.  Слово, составленное из терминальных символов, назы-
вается выводимым, если существует вывод, который  им  кончается.
Множество всех выводимых слов (из терминальных символов) называ-
ется языком, порождаемым данной грамматикой.
     В  этой  и следующих главах мы будем ходить вокруг да около
такого вопроса: дана КС-грамматика; построить алгоритм,  который
по любому слову проверяет, выводимо ли оно в этой грамматике.

     Пример 1.   Алфавит:

            ( ) [ ] E

(четыре  терминальных  символа  и один нетерминальный символ E).
Начальный символ: e.
Правила:
                E -> (E)
                E -> [E]
                E -> EE
                E ->

(в последнем правиле справа стоит пустое слово).

     Примеры выводимых слов:

                     (пустое слово)
                ()
                ([])
                ()[([])]

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 : 240 : 241 : 242 : 243 : 244 : 245 : 246 : 247 : 248 : 249 : 250 : 251 : 252 : 253 : 254 : 255 : 256 : 257 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 271 : 272 : 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 281 : 282 : 283 : 284 : 285 : 286 : 287 : 288 : 289 : 290 : 291 : 292 : 293 : 294 : 295 : 296 : 297 : 298 : 299 : 300 : 301 : 302 : 303 : 304 : 305 : 306 : 307 : 308 : 309 : 310 : 311 : 312 : 313 : 314 : 315 : 316 : 317 : 318 : 319 : 320 : 321 : 322 : 323 : 324 : 325 : 326 : 327 : 328 : 329 : 330 : 331 : 332 : 333 : 334 : 335 : 336 : 337 : 338 : 339 : 340 : 341 : 342 : 343 : 344 : 345 : 346 : 347 : 348 : 349 : 350 : 351 : 352 : 353 : 354 : 355 : 356 : 357 : 358 : 359 : 360 : 361 : 362 : 363 : 364 : 365 : 366 : 367 : 368 : 369 : 370 : 371 : 372 : 373 : 374 : 375 : 376 : 377 : 378 : 379 : 380 : 381 : 382 : 383 : 384 : 385 : 386 : 387 : 388 : 389 : 390 : 391 : 392 : 393 : 394 : 395 : 396 : 397 : 398 : 399 : 400 : 401 : 402 : 403 : 404 : 405 : 406 : 407 : 408 : 409 : 410 : 411 : 412 : 413 : 414 : 415 : 416 : 417 : 418 : 419 : 420 : 421 : 422 : 423 : 424 : 425 :
главная наверх

(c) 2008 Большая Одесская Библиотека.