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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

и T должно заменяться по (3):
        E -> TE -> [E]E -> [TE]E -> [(E)E]E
Далее первое E должно замениться на пустое слово (иначе  третьей
буквой слова будет "(" или "[" - только на эти символы может на-
чинаться слово, выводимое из T):
        E -> TE -> [E]E -> [TE]E -> [(E)E]E -> [()E]E
и далее
  ...  ->  [()TE]E -> [()(E)E]E -> [()(TE)E]E -> [()([E]E)E]E ->
        -> [()([]E)E]E -> [()([])E]E -> [()([])]E -> [()([])].

     Что требуется от грамматики, чтобы такой метод поиска лево-
го вывода был применим? Пусть, например, на очередном шаге самым
левым  нетерминалом  оказался  нетерминал K, т.е. мы имеем слово
вида AKU, где A - слово из терминалов, а U - слово из терминалов
и нетерминалов. Пусть в грамматике есть правила
     K -> L M N
     K -> P Q
     K -> R
Нам надо выбрать одно из них. Мы будем пытаться сделать этот вы-
бор,  глядя  на  первый символ той части входного слова, которая
выводится из KU.
     Рассмотрим множество Нач(LMN) тех терминалов, с которых на-
чинаются непустые слова, выводимые из LMN. (Это множество  равно
Нач(L),  объединенному с Нач(M), если из L выводится пустое сло-
во, а также с Нач(N), если из L и из M выводится пустое  слово.)
Чтобы  описанный  метод  был  применим,  надо,  чтобы  Нач(LMN),
Нач(PQ) и Нач(R) не пересекались. Но этого мало. Ведь может быть
так, например, что из LMN будет выведено пустое слово, а из сло-
ва U будет выведено слово, начинающееся  на  букву  из  Нач(PQ).
Следующие определения учитывают эту проблему.

     Напомним,  что определение выводимости в КС-грамматике было
дано только для слова из терминалов. Оно очевидным образом обоб-
щается на случай слов из терминалов и нетерминалов. Можно  также
говорить о выводимости одного слова (содержащего терминалы и не-
терминалы)  из  другого. (Если говорится о выводимости слова без
указания того, откуда оно выводится, то  всегда  подразумевается
выводимость  в грамматике, т.е. выводимость из начального нетер-
минала.)
     Для каждого слова X  из  терминалов  и  нетерминалов  через
Нач(X) обозначаем множество всех терминалов, с которых начинают-
ся непустые слова из терминалов, выводимые из X. (В случае, если
из  любого  нетерминала выводится хоть одно слово из терминалов,
не играет роли, рассматриваем ли мы при определении Нач(X) слова
только из терминалов или любые слова. Мы будем предполагать  да-
лее, что это условие выполнено.)
    Для каждого нетерминала K  через  Послед(K)  обозначим  мно-
жество  терминалов, которые встречаются в выводимых словах сразу
же за K. Кроме того, в Послед(K) включается символ EOI, если су-
ществует выводимое слово, оканчивающееся на K.
     Для каждого правила
        K -> V
(где  K - нетерминал, V - слово, содержащее терминалы и нетерми-
налы) определим множество "направляющих  терминалов",  обознача-
емое Напр(K->V). По определению оно равно Нач(V), к которому до-
бавлено Послед(K), если из V выводится пустое слово.

     Определение.  Грамматика называется LL(1)-грамматикой, если
для любых правил K->V и K->W с одинаковыми левыми  частями  мно-
жества Напр(K->V) и Напр(K->W) не пересекаются.

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 Большая Одесская Библиотека.