Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Пример 27




Построение таблицы разбора SLR-анализа

Рассмотрим, как построить функции action и goto SLR-анализа по детерминированному конечному автомату, распознающему активные префиксы. Грамматику G расширяем до грамматики G’, и на основе G’ строим каноническую систему множеств пунктов для G’. Строим action, функцию действий синтаксического анализа, и goto, функцию переходов. Потребуется множество FOLLOW(A) для каждого нетерминала А грамматики.

Алгоритм построение таблицы SLR-анализа

Вход. Расширенная грамматика G’.

Выход. Функции action и goto таблицы SLR-анализа для грамматики G’.

Метод.

1. Построим С = {I0,I1,...,In} — систему множеств LR(0)-пунктов для грамматики G’.

2. Состояние i строится на основе Ii. Действия синтаксического анализа для состояния i определяются следующим образом:

a) если [А → αaβ]є Ii, и goto( Ii, a)=Ij, то определить action[i, а] как "перенос j"; здесь а – терминальный символ;

b) если [А → α Ii, то определить action[i, а] как "свертка А → α " для всех а из FOLLOW(A); здесь А не должно быть S’;

c) если [S’ S•] є Ii, то определить action[i, $] как "допуск".

Если по этим правилам генерируются конфликтующие действия, то грамматика не является SLR(l). Алгоритм не в состоянии построить синтаксический анализатор для нее.

3. Переходы goto для состояния i и всех нетерминалов А строятся по правилу: если goto(Ii, A)= Ij, то goto[i, A]=j.

4. Все записи, не определенные по правилам (2) и (3), указываются как "ошибка".

5. Начальное состояние синтаксического анализатора представляет собой состояние, построенное из множества пунктов, содержащего [ S’ S• ] [3].

Построим SLR-таблицу для грамматики (7.2).

Вначале рассматривается множество пунктов I0:

Е’→ •E

Е → •Е+Т

Е → •Т

Т → •T*F

Т → •F

F → •(E)

F → • id

Пункт F → •(E) дает запись action[0, (] = "перенос 4", пункт F → •id — запись action[0, id]= "перенос 5". Другие пункты I0 к записям action не приводят.

Рас­сматривается I1:

Е→ E•

E → Е•+Т

Первый пункт дает action[1, $] - "допуск", а второй — action[1, +] - "перенос б". Переход к I2 дает:

Е→ T•

T→ T•*F

Поскольку FOLLOW(E) ={$,+,)}, из первого пункта следует action[2, $] = action[2, +] = action[2,)] = "свертка E T". Второй пункт дает action[2, *] = "перенос". Продолжая таким образом, рассмотрение множеств пунктов, получаем таблицу, показанную на рис. 39. В ней номера продукций в свертках те же, что и номера, под которыми продукции приведены в исходной грамматике, т.е. E E+T имеет номер 1, E → Т — номер 2 и т.д.

 

СОСТОЯНИЕ action goto
id + * ( ) $ E T F
  p5     p4       2  
    p6       acc      
    s2 s7   s2 s2      
    s4 s4   s4 s4      
  p5     p4       2  
    s6 s6   s6 s6      
  p5             9  
  p5     p4          
    s6   p4 p11        
    s1 s7   s1 s1      
    s3 s3   s3 S3      
    s5 s5   s5 s5      

 

Рис. 39. Таблица синтаксического анализа грамматики арифметических выражений

 

На рисунке использованы следующие обозначения действий:

1. pi означает перенос и i-е состояние на вершине стека,

2. sj означает свертку в соответствии с продукцией номер j,

3. acc означает допуск входной строки,

4. пустая ячейка означает ошибку.

Значение goto[s, а] для терминала а находится в поле action, связанном с переносом для входного символа а и состояния s. Поле goto дает значения goto[s, А] для нетерминалов А.

Для входной строки id*id+id последовательность содержимого стека и входной стро­ки показана на рис. 40. Например, в строке (1) LR-анализатор находится в состоянии 0 с первым входным символом id. Действие в строке 0 и столбце id таблицы action на рис. 39 — p5, означающее перенос и внесение в стек состояния 5. В строке (2) выпол­няется внесение в стек id и p5 и удаление id из входного потока.

После этого текущим входным символом становится *; действие длясостояния p5 и входного символа * — s6, т.е. свертка согласно продукции F → id. Co стека при этом снимаются два символа (символ состояния и символ грамматики), ина вершине стека появляется состояние 0. Поскольку goto[0, F] равно p3, в стек вносятся F и 3; получа­ется конфигурация, показанная в строке (3). Остальные строки на рис. 40 получены аналогично.

 

  Стек Входной поток Действие
(1)   id * id + id $ Перенос
(2) 0 id 5 * id + id $ Свертка по F → id
(3) 0 F 3 * id + id $ Свертка по T F
(4) 0 Т 2 * id + id $ Перенос
(5) 0 Т 2 * 7 id + id $ Перенос
(6) 0 Т 2 * 7 id 5 + id $ Свертка по F→ id
(7) 0 Т 2 * 7 F 10 + id $ Свертка по T T*F
(8) 0 Т 2 + id $ Свертка по E T
(9) 0 E 1 + id $ Перенос
(10) 0 E 1 + 6 id $ Перенос
(11) 0 E 1 + 6 id 5 $ Свертка по F id
(12) 0 E 1 + 6 F 3 $ Свертка по Т→ F
(13) 0 E 1 + 6 Т 9 $ E E+T
(14) 0 E 1 $ Допуск

Рис. 40. Действия LR-анализатора no разбору строки id*id+id

 




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 839; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.01 сек.