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

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



 драмма



 животные



 история



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



 медицина



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



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



 очерк



 повесть



 политика



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



 приключения



 психология



 религия



 студенту



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



 фантастика



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



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



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



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



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

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

     14.1.6. Построить грамматику, содержащую для каждого нетер-
минала K исходной граммaтики нетерминал <ЛевK>, причем следующее
свойство должно выполняться для любого  нетерминала  K  исходной
грамматики:  в  новой грамматике из <ЛевK> выводимы все элементы
Лев(K) и только они.

     Решение. Пусть P - начальный нетерминал грамматики. Тогда в
новой грамматике будет правило
     <ЛевP> ->       (пустое слово)
Для каждого правила исходной грамматики, например, правила

      K -> L t M N (L, M, N - нетерминалы, t - терминал),

в новую грамматику мы добавим правила
      <ЛевL> -> <ЛевK>
      <ЛевM> -> <ЛевК> L t
      <ЛевN> -> <ЛевK> L t M
и аналогично поступим с другими правилами.  Смысл  новых  правил
таков: пустое слово может появиться слева от P; если слово X мо-
жет  появиться  слева от K, то X может появиться слева от L, XLt
может появиться слева от M, XLtM - слева от N. Индукцией по дли-
не правого вывода легко проверить, что все, что может  появиться
слева от какого-то нетерминала, появляется в соответствии с эти-
ми правилами.

     14.1.7. Почему в предыдущей задаче важно, что мы рассматри-
ваем только правые выводы?

     Ответ. В противном случае следовало бы учитывать преобразо-
вания, происходящие внутри слова, стоящего слева от K.

     14.1.8.  Для  данной грамматики построить алгоритм, который
по любому слову выясняет, каким из множеств Лев(K) оно принадле-
жит.

     (Замечание для знатоков. Существование такого алгоритма - и
даже конечного автомата, т.е. индуктивного расширения с конечным
числом значений, - вытекает из предыдущей задачи, т.к. построен-
ная в ней грамматика имеет специальный вид: в правых  частях  ее
всего один нетерминал, причем он стоит у левого края. Тем не ме-
нее мы приведем явное построение.)

     Решение. Будем называть ситуацией данной грамматики одно из
ее  правил, в правой части которого отмечена одна из позиций (до
первой буквы, между первой и второй буквой,..., последY  последней
буквы). Например, правило
     K -> L t M N   (K, L, M, N - нетерминалы, t - терминал)
порождает пять ситуаций
     К -> _LtMN, K-> L_tMN, K-> Lt_MN, K-> LtM_N, K -> LtMN_.
(позиция указывается знаком подчеркивания).
     Будем говорить, что слово S согласовано с ситуацией K->U_V,
если  S  кончается  на U, то есть S=TU при некотором T, и, кроме
того, T принадлежит Лев(K). (Смысл  этого  определения  примерно
таков:  в  стеке S подготовлена часть U для будущей свертки UV в
K.) В этих терминах ЛевКонт(K->X) -  это  множество  всех  слов,
согласованных  с  ситуацией K->X_, а Лев(К) - это множество всех
слов, согласованных с ситуацией K->_X (где K->_X - любое правило
для нетерминала K).
     Эквивалентное  определение в терминах LR-процесса: S согла-
совано с ситуацией K->U_V, если существует успешный  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 Большая Одесская Библиотека.