Лексический анализ языков программирования. Лексемы. Регулярные языки и грамматики. Матрица переходов КА. (Глава 3)
Содержание
- 2. 3.1 Назначение и необходимость фазы лексического анализа Лексический анализ – первая фаза процесса трансляции, предназначенная для
- 3. 3.1 Назначение и необходимость фазы лексического анализа Задачи, решаемые сканером (преимущества сканера): представление элементарных конструкций языка
- 4. 3.2 Транслитератор Устройство, осуществляющее сопоставление класс с каждым отдельным символом, называется транслитератором. Наиболее типичными классами символов
- 5. 3.3 Регулярные языки и грамматики Пример. Классы лексем: идентификаторы; служебные слова (множество идентификаторов); целые числа, вещественные,
- 6. 3.3 Регулярные языки и грамматики Автоматные грамматики A -> Bt | t, где A, B ∈
- 7. 3.3 Регулярные языки и грамматики Доказано, что класс регулярной и автоматной грамматики почти эквиваленты. Любую регулярную
- 8. 3.4 КОНЕЧНЫЕ АВТОМАТЫ ГЛАВА 3. Лексический анализ
- 9. 3.4.1 Определение КА Конечный автомат (КА) – это пятерка (Q, V, δ, q0, F), где: Q
- 10. 3.4.1 Определение КА Конечный автомат называется полностью определенным, если в каждом его состоянии определена функция перехода
- 11. 3.4.2 Диаграмма переходов (состояний) Граф переходов (дерево, диаграмма) – направленный помеченный граф с символами состояний конечного
- 12. 3.5 Матрица переходов КА Каждая строка этой матрицы представляет состояние автомата, а каждый столбец соответствует возможному
- 13. 3.5 Матрица переходов КА ::= | фиксированной точкой > ::= ::= | | ::= . ::=
- 14. 3.5 Матрица переходов КА Матрица переходов состояний для распознавания десятичных чисел с фиксированной точкой
- 15. 3.5 Матрица переходов КА innum – значение следующей введенной цифры; insign – значение знака во входной
- 16. 3.5 Матрица переходов КА
- 17. 3.6 Детерминированный и недерминированный автомат Конечный автомат (Q, V, δ, q0, F) называется детерминированным конечным автоматом
- 18. 3.7 Лексический анализатор Лексический анализатор – программа, которая используя набор сканеров, преобразует исходный текст программы во
- 19. 3.7 Лексический анализатор ::= PROGRAM VAR BEGIN END. ::= id ::= ; | ; ::= :
- 20. 3.7 Лексический анализатор PROGRAM STATS VAR SUM, SUMSQ, I, VALUE, MEAN, VARIANCE: INTEGER; BEGIN SUM :=
- 21. 3.7 Лексический анализатор Таблица служебных слов TW 1 Таблица разделителей TD 2
- 22. 3.7 Лексический анализатор Таблица литералов (констант) TNUM 3 Таблица идентификаторов TID 4
- 23. 3.7 Лексический анализатор Переменные: buf – буфер для накопления символов лексем; с – очередной входной символ;
- 24. 3.7 Лексический анализатор Функции: void clear (void) – очистить буффер buf, void add (void) – добавление
- 25. 3.7 Лексический анализатор
- 26. 3.7 Лексический анализатор КА пользуясь набором сканера формирует набор лексем. PROGRAM STATS VAR SUM ... :
- 27. 3.7 Лексический анализатор F0={ gc() } F1={ clear(); add(); gc()} F3={ add(); gc() } F4={ j==look(TW)
- 28. 3.7 Лексический анализатор
- 29. 3.8 Связь регулярных грамматик КА На основании имеющейся регулярной грамматики можно построить эквивалентный ей КА, и
- 30. 3.8.1 Построение КА на основе леволинейной грамматики Необходимо построить КА M(Q, V, δ, q0, F), по
- 31. 3.8.1 Построение КА на основе леволинейной грамматики 3) Просматриваем все множество правил грамматики G. Если встречается
- 32. 3.8.1 Построение КА на основе леволинейной грамматики Построить автомат M(Q, V, δ, q0, F) на основе
- 33. 3.8.1 Построение КА на основе леволинейной грамматики Шаг 1. V = {0, 1} Шаг 2. Q
- 34. 3.8.1 Построение КА на основе леволинейной грамматики
- 35. 3.8.2 Построение леволинейной грамматики на основе КА 1) Множество терминальных символов строится на основании входных символов
- 36. 3.8.2 Построение леволинейной грамматики на основе КА 3) Просматриваем функции переходов автомата M для всех возможных
- 37. 3.8.2 Построение леволинейной грамматики на основе КА
- 39. Скачать презентацию