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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

сдвиг. (Это определение не изменилось по сравнению с SLR(1)-слу-
чаем - вторые компоненты пар из Сост(S) не учитываются.)
     Если в Сост(S) есть ситуация, в которой справа от подчерки-
вания ничего нет, а вторым членом пары является терминал  t,  то
говорят,  что  для  пары  (S,t) LR(1)-возможна свертка (по соот-
ветствующему правилу). Говорят, что  для  пары  (S,t)  возникает
конфликт  типа  сдвиг/свертка, если возможен и сдвиг, и свертка.
Говорят,  что   для   пары   (S,t)   возникает   конфликт   типа
свертка/свертка, если есть несколько правил, по которым возможна
свертка.
     Грамматика  называется  LR(1)-грамматикой,  если  в ней нет
конфликтов типа сдвиг/свертка и свертка/свертка  ни  для  одной
пары (S,t).

     14.4.6.  Построить  алгоритм  проверки  выводимости слова в
LR(1)-грамматике.

     Решение. Как и раньше, на каждом шаге LR-процесса можно од-
нозначно определить, какой шаг только и может быть следующим.

     Полезно (в частности, для LALR(1)-разбора, смотри ниже) по-
нять,  как  связаны понятия LR(0) и LR(1)-согласованности.

     14.4.7. Сформулировать и доказать соответствующее утвержде-
ние.

     Ответ. Пусть фиксирована некоторая грамматика. Слово  S  из
терминалов  и  нетерминалов является LR(0)-согласованным с ситу-
ацией K->U_V тогда и только тогда, когда оно LR(1)-согласовано с
парой [K->U_V,t] для некоторого терминала t (или для t=EOI).  То
же  самое  другими  словами: Лев(K) есть объединение Лев(K,t) по
всем t. В последней форме это совсем ясно.

     Замечание. Таким образом, функция  Сост(S)  в  LR(1)-смысле
является  расширением  функции  Сост(S) в LR(0)-смысле: Сост1(S)
получается из Сост0(S), если во всех парах выбросить вторые чле-
ны.

    Теперь мы можем дать определение  LALR(1)-грамматики.  Пусть
фиксирована  некоторая  грамматика,  S - слово из нетерминалов и
терминалов, t - некоторый терминал (или  EOI).  Будем  говорить,
что для пары (S,t) LALR(1)-возможна свертка по некоторому прави-
лу, если существует другое слово S1 с Сост0(S)=Сост0(S1), причем
для  пары (S1,t) LR(1)-возможна свертка по рассматриваемому пра-
вилу. Далее определяются  конфликты  (естественным  образом),  и
грамматика называется LALR(1)-грамматикой, если конфликтов нет.

    14.4.8.  Доказать,  что  всякая  SLR(1)-грамматика  является
LALR(1)-грамматикой,  а   всякая   LALR(1)-грамматика   является
LR(1)-грамматикой.
    Указание. Это - простое следствие определений.

    14.4.9.    Построить   алгоритм   проверки   выводимости   в
LALR(1)-грамматике, который хранит в  стеке  меньше  информации,
чем соответствующий LR(1)-алгоритм.
    Указание.  Достаточно  хранить  в  стеке множества Сост0(S),
поскольку согласно определению LALR(1)-возможность  свертки  ими
определяется.  (Так  что  сам  алгоритм  ничем  не отличается от
SLR(1)-случая, кроме таблицы возможных сверток.)


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