Теория языков программирования и методы трансляции Тема №5 Восходящий синтаксический анализ (down-top)
Содержание
- 2. Вопросы В данной теме описывается восходящий синтаксический анализ и его реализация. В частности, будут рассмотрены следующие
- 3. Восходящий синтаксический анализ. Основные понятия. Задача синтаксического анализа состоит в нахождении порождения конкретного выражения с использованием
- 4. Восходящий синтаксический анализ. Основные понятия. Рассмотрим язык {xnym|n,m>0}, генерируемый следующими продукциями: предложение языка xxxyy можно сгенерировать
- 5. Восходящий синтаксический анализ. Основные понятия. При восходящем синтаксическом анализе этапы порождения определяются не в показанном, а
- 6. Восходящий синтаксический анализ. Основные понятия. Пусть предложение хххуу читается слева направо, тогда совсем не очевидно, почему
- 7. Восходящий синтаксический анализ. Критерии принятия решений. При восходящем синтаксическом анализе правые части продукций не распознаются, пока
- 8. Восходящий синтаксический анализ. Критерии принятия решений. Этапы процесса синтаксического анализа могут рассматриваться как состоящие из двух
- 9. Восходящий синтаксический анализ. Критерии принятия решений.
- 10. Восходящий синтаксический анализ. Критерии принятия решений. В приведенном выше примере не ясно, когда должны применяться действия
- 11. Восходящий синтаксический анализ. Основные понятия. В строке символов на вершине стека возможно будут определены правые части
- 12. Восходящий синтаксический анализ. Основные понятия. Как и при нисходящем синтаксическом анализе, для разрешения конфликтов обычно используется
- 13. Восходящий синтаксический анализ. LR(k)-грамматика. Грамматика, все конфликты которой, возникающие при восходящем синтаксическом анализе слева направо, могут
- 14. Восходящий синтаксический анализ. Критерии принятия решений. Рассмотрим пример. Пусть имеется грамматика со следующими продукциями. 1. E→E+T
- 15. Восходящий синтаксический анализ. Критерии принятия решений.
- 16. Восходящий синтаксический анализ. Критерии принятия решений. Первый х, помещаемый в стек, сворачивается в F, затем в
- 17. Восходящий синтаксический анализ. Таблица синтаксического анализа. Таблица синтаксического анализа, которая используется в восходящем синтаксическом анализе, является
- 18. Восходящий синтаксический анализ. Таблица синтаксического анализа. В начале процесса синтаксического анализа анализатор находится в состоянии 1,
- 19. Восходящий синтаксический анализ. Таблица синтаксического анализа. Пустые позиции таблицы соответствуют синтаксическим ошибкам во вводе, и, при
- 20. Восходящий синтаксический анализ. Таблица синтаксического анализа. Таблица синтаксического анализа представляет зависимую от языка часть синтаксического анализатора,
- 21. Восходящий синтаксический анализ. Таблица синтаксического анализа. На каждом этапе синтаксического анализа анализатор находится в одном из
- 22. Восходящий синтаксический анализ. Таблица синтаксического анализа. Если позиция таблицы определяет действие свертки, имеют место следующие операции.
- 23. Восходящий синтаксический анализ. Таблица синтаксического анализа. Таблица 1
- 24. Восходящий синтаксический анализ. Таблица синтаксического анализа. Проследим анализ следующего предложения. х + х + х*х
- 25. Восходящий синтаксический анализ. Таблица синтаксического анализа. Рассмотрев, как синтаксический анализатор использует одноименную таблицу, пришло время определить
- 26. Восходящий синтаксический анализ. Таблица синтаксического анализа. Как обычно, предполагается, что синтаксический анализатор изначально находится в состоянии
- 27. Восходящий синтаксический анализ. Таблица синтаксического анализа. Анализатор находится в состоянии 2 до распознавания символа D, так
- 28. Восходящий синтаксический анализ. Таблица синтаксического анализа. Подобным образом вводим еще восемь состояний, в которых может находиться
- 29. Восходящий синтаксический анализ. Таблица синтаксического анализа. Позиции переноса заносятся в таблицу легко. Например, из начала правой
- 30. Восходящий синтаксический анализ. Таблица синтаксического анализа.
- 31. Восходящий синтаксический анализ. Таблица синтаксического анализа. Другим способом представления таблицы синтаксического анализа является ориентированный граф. Это
- 32. Восходящий синтаксический анализ. Таблица синтаксического анализа.
- 33. Восходящий синтаксический анализ. Таблица синтаксического анализа. В большинстве случаев действия свертки поместить в таблицу не так
- 34. Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E→1E+T 2. E→1T 3. T→1T*F 4. T→1F 5. F→1(E)
- 35. Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E→1E2+T 2. E→1T 3. T→1T*F 4. T→1F 5. F→1(E)
- 36. Восходящий синтаксический анализ. Таблица синтаксического анализа. На первый взгляд может показаться странным наличие двух состояний, соответствующих
- 37. Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 4 появляется в двух местах: в конце продукции 1,
- 38. Восходящий синтаксический анализ. Таблица синтаксического анализа. 1. E→1E2+3T4 2. E→1T5 3. T→1,3T5,4*F 4. T→1,3F 5. F→1,3(E)
- 39. Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 9 несколько сложнее, так как оно появляется перед нетерминалом,
- 40. Восходящий синтаксический анализ. Таблица синтаксического анализа. Состояние 10 следует вводить аккуратно. Состояние 10 следует после Е
- 41. Восходящий синтаксический анализ. Таблица синтаксического анализа. В продукциях 4-6 уже не требуются новые состояния, следующие за
- 42. Восходящий синтаксический анализ. Таблица синтаксического анализа.
- 43. Восходящий синтаксический анализ. Таблица синтаксического анализа. Переносы легко получаются из грамматики или из ХКА. Таблица 2
- 44. Восходящий синтаксический анализ. Таблица синтаксического анализа. Кроме того, в таблицу просто (не порождая конфликтов) вводятся некоторые
- 45. Восходящий синтаксический анализ. Таблица синтаксического анализа. Замечаем, что свертки в состояниях 4 и 5 не являются
- 46. Восходящий синтаксический анализ. Таблица синтаксического анализа. Из продукции 1 получаем, что за Е может следовать символ
- 47. Восходящий синтаксический анализ. Таблица синтаксического анализа. Таблица 4
- 48. Восходящий синтаксический анализ. Таблица синтаксического анализа. Хотя строго это и не обязательно, позиции других действий свертки
- 49. Восходящий синтаксический анализ. Таблица синтаксического анализа. В состояниях 11 и 12 свертка производится в символ F,
- 50. Восходящий синтаксический анализ. SLR(1)-грамматика. Если для внесения в таблицу синтаксического анализа действий свертки учитываются все возможные
- 51. Восходящий синтаксический анализ. LALR(1)-грамматика. Как было показано ранее, алгоритм LR(0) успешен, если вообще нет нужды рассматривать
- 52. Восходящий синтаксический анализ. LALR(1)-грамматика. Все конфликты может не разрешить даже алгоритм LALR(1). Это, разумеется, объясняться тем,
- 53. Восходящий синтаксический анализ. Рассмотрим общий алгоритм формирования таблицы LR(1)-анализа, Он имеет несколько этапов. 1. Для создания
- 54. Восходящий синтаксический анализ. Основная идея описанного подхода: первым применяется простейший алгоритм, далее сложность алгоритмов идет по
- 55. Восходящий синтаксический анализ. Особенности LR-анализа. На данном этапе стоит упомянуть некоторые теоретические результаты. Существует алгоритм определения,
- 56. Восходящий синтаксический анализ. Особенности LR-анализа. Впрочем, ни один из приведенных результатов не является особенно важным с
- 57. Восходящий синтаксический анализ. Введение в YACC. YACC (Yet Another Compiler-Compiler — "еще один компилятор компиляторов") был
- 58. Восходящий синтаксический анализ. Введение в YACC. Выход YACC – это программа на языке С, компилировать которую
- 59. Восходящий синтаксический анализ. Введение в YACC. %left ‘+’ ‘-’ %left ‘*’ ‘/’ %% exp : exp
- 60. Восходящий синтаксический анализ. Введение в YACC. Приведенный выше пример можно расширить, включив унарные операторы, приоритет которых
- 61. Восходящий синтаксический анализ. Введение в YACC. Как и для Lex, действия пишутся на С и обычно
- 62. Вход YACC, включающий комментарии, которые выделены знаками /* и */, имеет следующий вид. %token NUMBER %left
- 63. Восходящий синтаксический анализ. Введение в YACC. Для связи с лексическим анализатором, созданным Lex, перед пользовательскими функциями
- 64. Восходящий синтаксический анализ. Введение в YACC. Здесь yytext — массив, содержащий знаки символа, с которым только
- 65. Восходящий синтаксический анализ. Введение в YACC. Предполагая, что входами Lex и YACC являются, соответственно, nums.l и
- 66. Восходящий синтаксический анализ. Использование YACC. Больше узнать о том, как YACC формирует таблицу синтаксического анализа, можно,
- 67. Восходящий синтаксический анализ. Использование YACC. Как упоминалось выше, интересная и широко известная неоднозначность появляется при использовании
- 69. Скачать презентацию