Курсовая работа теория автоматов и формальных языков. Булычев отчет. Разработка компилятора модельного языка программирования
 Скачать 1.38 Mb.
|
Семантический анализ Описание алгоритмов Как работает лексический анализатор. Цель анализатора считать все символы программы и перевести их в лексемы (наборы пар цифр вида "(n, i)" где i это индекс лексемы в n разделе. 1 раздел - служебные слова, 2 раздел - разделители, 3 - числа, 4 - остальные). В это же время проверить на правильность числа. Алгоритм: 1. Считываем символ - gc() а) если это буква - считываем цифры и буквы пока не встретим разделитель и проверяем на вхождение в служебные слова (1, i). Если это не служебное слово, то это идентификатор (остальные) (4, i) б) если это цифра - считываем пока не встретим разделитель и проверяем на лишние символы. Для 2ичной лишние все кроме 0 и 1. Для 8ричной все кроме 0-7. Для 16ричной - все кроме 0..9 и a-F. В конце добавляется лексема вида (3, i) B,b - это показатель двоичного числа H,h - 16-ричного числа O,o - 8-ричного числа Отдельной веткой 16-ричных чисел могут быть числа вида 1e+10, поэтому есть ветка с символом e. Число может начинаться с точки, например .1 соответствует числу 0.1, поэтому есть ветка с точкой в) если это знак начала комментария, то пропускаем символы пока не встретим знак конца комментария г) если это разделитель - то добавляем его в таблицу разделителей. Лексема вида (i, 2) д) если это символ разделителя, то добавляем его как разделитель (2, i) е) если это неизвестный символ, то ошибка Состояния: ER - ошибка I - считывание служебных слов или остальных слов C - считывание комментария H - просто считывание следующего символа Рекурсивный спуск - это вызов функции самой себя. Чем больше раз она себя сама вызывает - тем ниже мы находимся. Как только мы встречаем ошибку - начинается обратный процесс - рекурсивное восхождение. Для хранения таблиц лексем, чисел, идентификаторов и пр. используется структура HashMap. Класс HashMap использует хеш-таблицу для хранения карточки, обеспечивая быстрое время выполнения запросов get() и put() при больших наборах. Класс реализует интерфейс Map (хранение данных в виде пар ключ/значение). Ключи и значения могут быть любых типов, в том числе и null. При этом все ключи обязательно должны быть уникальны, а значения могут повторяться. Данная реализация не гарантирует порядка элементов. Общий вид HashMap: // K - это Key (ключ), V - Value (значение) class HashMap Сложность доступа к элементу и любой операции в такой структуре – константная и совершается за одну операцию. Это позволяет осуществлять поиск лексем в таблице очень быстро и эффективно. Более того, в случае хранения чисел HashMap не допускает хранения дубликатов. Такое свойство полезно также при обнаружении необъявленных идентификаторов или повторно объявленных. Для семантических проверок в программе реализовано объектное представление программы в Java-классах. Это позволяет осуществлять нужную проверку в соответствующей синтаксической конструкции и хранить ее содержимое. Структура классов представлена на рис. ниже.  Рис. – Структура классов для семантического анализа |