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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

   | end;
   end;
   {входное слово выводимо <=> not error}

Алгоритм заканчивает работу, поскольку при появлении нетерминала
в начале слова S происходит чтение со  входа  или  остановка,  а
бесконечный  цикл сменяющих друг друга терминалов в начале S оз-
начал бы, что грамматика леворекурсивна.

     Замечания.  1.  Приведенный  алгоритм использует S как стек
(все действия производятся с левого конца).
     2. Действия двух последних вариантов внутри цикла не приво-
дят к чтению очередного символа со входа, поэтому их можно зара-
нее предвычислить для  каждого  нетерминала  и  каждого  символа
Next.  После этого на каждом шаге цикла будет читаться очередной
символ входа.
     3. При практической реализации удобно составить таблицу,  в
которой  записаны  варианты  действий  в зависимости от входного
символа и первого символа S, и небольшую программу,  выполняющую
действия в соответствии с этой таблицей.
      Глава 14. Синтаксический разбор слева направо (LR)

      Сейчас мы рассмотрим еще один метод синтаксического разбо-
ра,  называемый LR(1)-разбором, а также некоторые упрощенные его
варианты.

      14.1. LR-процессы

      Два отличия  LR(1)-разбора  от  LL(1)-разбора:  во-первых,
строится  не  левый вывод, а правый, во-вторых, он строится не с
начала, а с конца. (Вывод в КС-грамматике называется правым, ес-
ли на каждом шаге замене подвергается самый правый нетерминал.

     14.1.1. Доказать, что если слово, состоящее из  терминалов,
выводимо, то оно имеет правый вывод.

     Нам  будет удобно смотреть на правый вывод "задом наперед".
Определим понятие LR-процесса над словом A. В этом процессе, по-
мимо A, будет участвовать и другое слово S, которое может содер-
жать как терминалы, так и нетерминалы. Вначале слово S пусто.  В
ходе LR-процесса разрешены два вида действий:
     (1)  можно  перенести  первый  символ слова А (его называют
очередным символом и обозначают Next) в конец  слова  S,  удалив
его из A (это действие называют сдвигом);
     (2) если правая часть одного из правил грамматики оказалась
концом  слова  S, то разрешается заменить ее на нетерминал, сто-
ящий в левой части этого правила; при этом слово A не  меняется.
(Это действие называют сверткой, или приведением.)
     Отметим,  что  LR-процесс  не является детерминированным: в
одной и той же ситуации могут быть разрешены разные действия.
     Говорят, что LR-процесс на слове A успешно завершается, ес-
ли слово A становится пустым, а в слове S остается  единственный
нетерминал - начальный нетерминал грамматики.

     14.1.2.  Доказать,  что  для любого слова A (из терминалов)
успешно завершающийся LR-процесс существует тогда и только  тог-
да,  когда  слово A выводимо в грамматике. В ходе доказательства
установить взаимно однозначное соответствие между правыми  выво-
дами и успешно завершающимися LR-процессами.


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