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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



Этот день в истории
В 1681 году скончался(-лась) Педро Кальдерон


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

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

     (2) значение b становится истинным или ложным в зависимости
от того, является ли A выводимым из K или лишь невыводимым нача-
лом выводимого (из K) слова.

     Для удобства введем такую терминологию: выводимое из K сло-
во будем называть K-словом, а любое начало любого выводимого  из
K  слова - K-началом. Требования (1) и (2) вместе будем выражать
словами "ReadK корректна для K".

     Начнем с рассмотрения частного случая. Пусть правило
        K -> L M
является единственным правилом грамматики, содержащим K в  левой
части, пусть L, M - нетерминалы и ReadL, ReadM - корректные (для
них) процедуры.
     Рассмотрим такую процедуру:

     procedure ReadK;
     begin
     | ReadL;
     | if b then begin
     | | ReadM;
     | end;
     end;

     13.2.1.  Привести  пример, когда эта процедура будет некор-
ректной для K.
     Ответ. Пусть из L выводится любое слово вида 00..00, а из M
выводится лишь слово 01. Тогда из K выводится  слово  00001,  но
процедура ReadK этого не заметит.

     Укажем достаточноые условия корректности  процедуры  ReadK.
Для  этого нам понадобятся некоторые обозначения. Пусть фиксиро-
ваны КС-грамматика и некоторый  нетерминал  N  этой  грамматики.
Рассмотрим  N-слово A, которое имеет собственное начало B, также
являющееся N-словом (если такие есть). Для любой пары таких слов
A и B рассмотрим терминальный символ, идущий в A непосредственно
за B. Множество всех таких терминалов обозначим  Посл(N).  (Если
никакое N-слово не является собственным началом другого N-слова,
то множество Посл(N) пусто.)

     13.2.2. Указать (а) Посл(E) для примера 1;  (б)  Посл(E)  и
Посл(T)  для примера 2; (в) Посл(<слаг>) и Посл(<множ>) для при-
мера 3.
     Ответ.  (а)  Посл(e)  =  {  [, ( }. (б) Посл(e) = { [, ( };
Посл(t) пусто (никакое t-слово не является началом другого). (в)
Посл(<слаг>) = {*}; Посл(<множ>) пусто.

Кроме  того,  для  каждого  нетерминала N обозначим через Нач(N)
множество всех терминалов, являющихся первыми  буквами  непустых
N-слов.  Это  обозначение  - вместе с предыдущим - позволит дать
достаточное условие корректности процедуры ReadK в описанной вы-
ше ситуации.

     13.2.3.  Доказать,  что  если  Посл  (L)  не пересекается с
Нач(M) и множество всех M-слов непусто, то ReadK корректна.

     Решение. Рассмотрим два случая. (1) Пусть после ReadL  зна-
чение  переменной  b  ложно. В этом случае ReadM читает со входа
максимальное M-начало A, не являющееся  M-словом.  Оно  является
K-началом (здесь важно, что множество L-слов непусто.). Будет ли

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