Курсовая: LL(k)-грамматики - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

LL(k)-грамматики

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 399 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

8 LL(k)- грамматики LL(k) - Грамма тики . Определение LL(k) -грамматик. Для начала предположим , что G =( N , E , P , S ) - однозначная грамматика и w=a 1 ,a 2... a n - цепочка из L ( G ). Тогда существует единственная последовательность левовыводимых цепочек b 0 ,b 1 ..b m , для котор ой S =b 0 ,b i , pi Ю b i +1 при 0<=i), если A ® a` - единственное правило из P , для которо го FIRST k ( a` ) Е k L содержит u; (3) не определено , если в множестве н айдутся два и более правила (эту ситуацию называют кон фликтом между правилами ) На нормальном языке это означает что вырабатывается значение ошибка , если u вообще не является цепочкой грамматики , возвращается правило ес ли оно существует и только одно и если несколько правил - то значение не определяется. АЛГ 2: Постр оение LL (k)- таблиц. Вход : LL (k)- грамматика G =( N , E , P , S ) . Выход : Множ ество T G LL (k)- таблиц , необходимых для построения у правляющей таблицы для G . Метод : (1) Построить LL (k)- таблицу T 0 , со ответс твующую S и e . (2) Положить вначале T G = T 0 . (3) Для каждой LL(k) -таблицы T О T G , содержащей элемент T(u) =(A ® x 0 B 1 x 1 ...B m x m ,) включить в T G LL (k)- таблицу T для 1 Ј i Ј m , если T еще не входит в TG. (4) Повторять шаг 3 пока в T G мо жно включать новые таблицы. ПРМ : Построим соответствующее множество LL (2)- таблиц для грамматики S ® aAaa|bAba и A ® b| e . Начнем с T G = T S , e . Так как T S , e ( aa )= ( S ® aAaa, aa ), то в T G надо включить T A , aa . Аналогично , так как T 0 (bb)=( S ® bAba , ba ) , то в T G нужно так же вкл ючить . ( Элементы LL (2)- таблиц T A , aa и T A , ba , отличные от значения ошибка , приведены в таблице ниже ) . Сейчас T G = T S, e ,T A, aa ,T A, ba , и алгоритм уже не может в ключить в T G новых табли ц , так что это три LL (2)- таблицы образуют м ножество соот ветствующее грамматике. T A, aa T A, ba u правило множества u правило множества ba A ® b - ba A ® e - aa A ® e - aa A ® b - Теперь дадим алгоритм , кото рым можно построить корректную управляющую таблицу по соответствующему множ еству LL (k)- таблиц . Управляемый этой таблицей k- предсказывающий алгоритм будет в ка честве магазинных символов употреблять вместо нетерминалов LL (k)- таблицы. АЛГ 3: Постр оение управляющей таблицы для LL (k)- грамматики. Вход : LL (k)- грамматика и соответс твующ ее множество T G LL (k)- таблиц. Выход : Кор ректная управляющая таблица M для G . Метод : M определяется на множестве ( T G И E И $ ) ґ E*k следующим образом : (1) Если A ® x 0 B 1 x 1 ...B m x m - правило из P с номером i и T A,L О T G , то для вс ех u , д ля которых T A,L (u)=(A ® x 0 B 1 x 1 ...B m x m ,) полагаем M[T A,L ,u]=(x 0 T B1,Y1 ...T Bm,Ym x m ,i). (2) M[a,av]= выброс для всех v О E*(k-1) . (3) M[$, e ]= допуск. (4) В остальных слу чаях M[X,u]= ошибка (5) T S, e - начальная таблица. ПРМ : Построим управляющ ую таблицу для LL (2)- грамм атики (1) S ® aAaa (2) S ® bAba (3) A ® b (4) A ® e используя соо тветствующее ей множество LL (2)- таблиц , найденное в предыдущем примере . Алгоритм должен выдать таблицу : aa ab a ba bb b e T 0 aT 1 aa,1 aT 1 aa,1 bT 2 ba,2 T 1 e ,4 b,3 T 2 e ,4 b,3 a выброс выброс выброс b выброс выброс выброс $ допуск * где T 0 =T S, e , T 1 =T A, aa и T 2 =T A, ba . Подразумеваетс я , что в пустых ячейках - ошибка . Допуск * находится в последней колонке . Для вх одной цепочки bba 2-предсказыв ающий алгоритм выда ст такую последовательность тактов : ( bba,T 0 $, e ) | - (bba,bT 2 ba$, 2 ) |- (ba,T 2 ba$, 2 ) |- ( ba,ba$, 24) |- ( a,a$, 24) |- ( e ,$, 24) ТРМ : Описанный алгоритм строит для LL (k) - грамматики G =( N , E , P , S ) корректную таблицу , управляющую работой соответс твующе го k- п редсказывающего алгоритма. ПРМ : Рассмо трим LL (2)- грамматику G с правилами : (1) S ® e (2) S ® abA (3) A ® S aa (4) A ® b Построим соот ветствующие LL (2) -таблицы . Начн ем с T 0 =T S, e . Затем по T0 найдем T 1 =T A, e , далее T 2 =T S, aa и T 3 =T A, aa : T 0 T 2 u правило множества u правило множества e S ® e - aa S ® e - ab S ® abA e ab S ® abA aa T 1 T 3 u правило множества u правило множества b A ® b - aa A ® S aa aa aa A ® S aa aa ab A ® S aa aa ab A ® S aa aa ba A ® b - По этим таблицам построим управляющую таблицу : aa ab a ba bb b e T 0 abT 1 ,2 e ,1 T 1 T 2 aa,3 T 2 aa,3 b,4 T 2 e ,1 abT 3 ,2 T 3 T 2 aa,3 T 2 aa,3 b,4 a выброс выброс выброс b выброс выбр ос выброс $ допуск Алгоритм пост роенный по т аблице разберет цепочку abaa следующи м образом : ( abaa,T 0 $, e ) |- (abaa,abT 1 $,2) |- (baa,bT 1 $,2) |- (aa,T 1 $,2) |- (aa,T 2 aa$,23) |- (aa,aa$,231) |- (a,a$,231) |- ( e ,$,231) ТРМ : Число шагов , выполняемых k- предсказывающим алгоритмом с управляющей таблице й , построенной предыдущим алгоритмом по LL (k)- грамматике G, линейно зависит от n, где n - длинна входно й цепочки. Проверка LL(k)- условия. По отношению к произвольной данной грамматике G возникает ряд естественных вопросов : (1) Является ли G LL ( k ) - г рамматикой для данного k ? (2) Существует ли т акое k, ч то G - LL (k)- грамматика ? (3) Так как для LL (1) левые разборы строятся особенно просто , то если G не LL (1)- грамматика , то существует ли э квивалентная ей LL (1)- грамматика G ’ , для которой L( G ) = L( G ’ )? К сожалению , только для первого вопроса есть отвеч ающий на него алгоритм . Можно показать , что вторая и третья проблемы алгоритмическ и не разрешимы , но это доказательство н е приводится . Приведем алгоритм проверки LL (k)- условия : АЛГ 4: Прове рка L L (k)- условия. Вход : КС - грамматика G =( N , E , P , S ) и целое число k. Выход : «Да» - если G - LL (k)- грамматика и «Нет» в противном случае. Метод : Суть алгоритма сводится к следующему : Для каждого нетерминала , имеюще го два или более правила раскрутки выч исляетс я пересечение первых k- символов всех возможных цепочек раскрутки . Если это множество пусто , то переходят к следующему терминалу , иначе заканчивают со значением «Нет» . Если все пересечения пусты - зак анчивают со значением «Да» . Для получения пересечения дв ух правил можно вос пользоваться записью : (FIRST k ( b` ) Е k L) З (FIRST k ( c` ) Е k L) , где L=FIRST k ( a` ) и a` - цепочка симво лов после терминала.
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Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Директор школы, коллектив которой состоял из 50 человек, увеличил себе зарплату на 150 тысяч в месяц и благополучно отчитался, что средняя зарплата учителей в его школе выросла на 3 тысячи!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по программированию "LL(k)-грамматики", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru