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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     14.2.4. Пусть дана LR(0)-грамматика. Доказать, что у любого
слова существует не более одного правого вывода. Построить алго-
ритм проверки выводимости в LR(0)-грамматике.

     Решение.  Пусть  дано  произвольное  слово A. Будем строить
LR-процесс над A по шагам. Пусть текущее состояние стека LR-про-
цесса равно S. Нам надо решить, делать сдвиг или свертку (и если
сертку, то по какому правилу). Согласно определнию LR(0)-грамма-
тики в нашем состоянии S возможен либо только сдвиг, либо только
свертка (причем лишь по одному правилу).  Таким  образом,  поиск
возможных  продолжений  LR-процесса  происходит детерминированно
(на каждом шаге можно определить, какое действие только  и  воз-
можно).

     14.2.5.  Что  произойдет, если анализируемое слово не имеет
вывода в данной грамматике?

     Ответ. Либо на некотором шаге не будет возможен  ни  сдвиг,
ни  свертка,  либо все возможные сдвиги будет иметь неподходящий
очередной символ.

     Замечания. 1. При реализации этого алгоритма нет  необходи-
мости каждый раз заново вычислять множество Сост(S) для текущего
значения  S. Эти множества можно также хранить в стеке (в каждый
момент хранятся множества Сост(T) для всех начал текущего  слова
S).
     2. На самом деле само слово S можно не хранить - достаточно
хранить множества ситуаций Сост(T) для всех его начал T.

     В  алгоритме проверки выводимости в LR(0)-грамматике мы ис-
пользуем не всю информацию, которую могли бы. В  этом  алгоритме
для  каждого  состояния  известно  заранее,  что  в нем возможен
только сдвиг или только свертка (причем в последнем  случае  из-
вестно,  по  какому  правилу).  Более изощренный алгоритм мог бы
принимать решение о выборе между сдвигом и  сверткой,  посмотрев
на  очередной  символ (Next). Глядя на состояние, можно сказать,
при каких значениях Next возможен сдвиг (это те терминалы, кото-
рые в ситуациях этого состояния стоят непосреджственно  за  под-
черкиванием). Сложнее воспользоваться информацией о символе Next
для  решения  вопроса о том, возможна ли свертка. Для этого есть
упрощенный метод (грамматики, к которым  он  применим,  называют
SLR(1)-грамматиками [сокращение от Simple LR(1)]) и полный метод
(более  сложный, но использующий всю возможную информацию; грам-
матики, к которым  он  применим,  называют  LR(1)-грамматиками).
Есть и промежуточный класс грамматик, называемый LALR(1).

     14.3. SLR(1)-грамматики

     Напомним,  что  для любого нетерминала K мы определяли мно-
жество Послед(K) тех терминалов,  которые  могут  стоять  непос-
редственно за K в выводимом (из начального нетерминала) слове; в
это  множество  добавляют также специальный символ EOI, если не-
терминал K может стоять в конце выводимого слова.

     14.3.1. Доказать, что если в данный момент LR-процесса пос-
ледний символ стека S равен  K,  причем  процесс  этот  может  в
дальнейшем успешно завершиться, то Next принадлежит Послед(K).

     Решение. Этот факт является непосредственным следствием оп-
ределения   (вспомним  соответствие  между  правыми  выводами  и

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