- •Формальные грамматики и языки.
- •Задача разбора
- •Классификация грамматик по Холмскому.
- •Диаграмма состояний
- •Отношения предшествования
- •Распознаватель
- •Матрица предшествования
- •Некоторые приемы приведения к грамматикам простого предшествования.
- •Представление автоматов.
- •Концевые маркеры и выходы из распознавания.
- •Эквивалентность состояний.
- •Проверка эквивалентности двух состояний.
- •Недостижимые состояния.
- •Алгоритм составления списка достижимых состояний.
- •Приведённые автоматы.
- •Получение минимального автомата.
- •Недетерминированные автоматы.
- •Эквивалентность недетерминированных и детерминированных конечных распознавателей (нкр и дкр).
- •Задание:
- •Транслятор.
- •Введение таблицы символов.
- •Включение неявной информации.
- •Обнаружение ошибок.
- •Макрообработка и операции, выполняемые во время компиляции.
- •Синтез объектной программы.
- •Оптимизация.
- •Генерация кода.
- •Редактирование связей и загрузки.
- •Задача идентификации. Реализация ка при работе трансляторов.
- •Хранение информации о лексемах.
- •Механизм запоминания.
- •Метод хеширования.
- •Нисходящий разбор с возвратами.
- •Начальная установка.
- •Новый человек.
- •Неудача
- •Класс грамматик, допускающих нисходящий распознаватель.
- •Статистические управляемые схемы перевода и атрибутные грамматики.
- •Контекстные условия
Задача идентификации. Реализация ка при работе трансляторов.
Некоторые задачи, решаемые с помощью КА, заключаются всего лишь в распознавании конечного множества слов. Суть этих проблем в том, что компилятор должен обнаруживать появление некоторого слова из такого множества, и затем действовать в зависимости от того, какое это слово (if, while и т.д.) и для компилятора важно установить с какого из них (если оно есть) начинается строка и предпринять действие, соответствующее данному типу оператора. Задачу такого характера мы называем проблемой идентификации, т.к. действия компилятора зависят от идентичности некоторому известному слову данного слова, включенного во входную цепочку автомата. Т.к. для решения задач идентификации может потребоваться огромное число состояний, в подобных случаях часто приходится пользоваться специальными методами реализации. По этой причине нередко рекомендуется строит компилятор так, чтобы проблема идентификации решалась отдельным подпроцессором, специально предназначенного для этого.
Существуют проблемы идентификации, которые, строго говоря, не могут быть решены с помощью КА. Обратимся к часто встречающейся проблеме: распознавание переменных или идентификаторов некоторого языка и соотнесения их с соответствующими элементами таблицы имён. Решение этой проблемы обычным методом с помощью КА потребует несколько состояний и элемента таблицы имён для каждого допустимого идентификатора. Однако, множество допустимых идентификаторов в большинстве языков бесконечно или так велико, что его можно считать бесконечным. Это затруднение решается с помощью понятия расширяющегося конечного автомата. 07.12.2005.
При считывании своей входной цепочки, это автомат отводит для идентификатора необходимое место в памяти и элемент в таблице, как только тот впервые встречается в программе. Если этот идентификатор встречается в программе снова, то чтобы идентифицировать автомат использует технику идентификации слов с помощью КА. Когда появляется какой-то новый идентификатор автомат снова расширяется и т.д. Хотя этот автомат не является, строго говоря, конечным, к нему применимы многие принципы построения и анализы КА.
Чтобы смоделировать КА, мы должны каким-нибудь подходящим способом закодировать его входное множество. Наиболее гибкое решение состоит в представлении входного множества с помощью набора последовательности целых чисел, начиная с 0 или 1.
Если входом КА является выход какого-то другого блока компилятора, то обычно не трудно построить этот блок так, чтобы он подавал на вход КА цепочки в наиболее удобном для него виде. Единственное место при построении компилятора, где может возникнуть проблема кодировки – это процедура чтение символов исходной программы. Если бы множество символов исходной программы непосредственно служило входом для некоторого конечного процессора, содержащего много состояний, то автомат имел бы большую таблицу переходов, т.к. одни только цифры и латинские буквы образуют множество из 36 символов. Обычно же множество символов в несколько раз больше. Удобный способ уменьшения размера таблицы переходов заключается в обработке исходных символов двумя последовательно соединёнными автоматами. Первый автомат – это транслитератор, единственная задача которого – это сократить входное множество до приемлемых размеров. Второй автомат выполняет остальную часть работы (свёртка лексем и т.д.)
Зависимость между входом и выходом транслитератора можно выразить с помощью следующей таблицы:
символ |
Перевод |
a --- - - - z |
(буква,а) --- -- - (буква,z) |
0 --- - - - 9 |
(цифра,0) --- - - - (цифра,9) |
+ --- - - -
|
(операция,+) --- - - - И.т.д. |
Которая содержит перевод каждого символа исходного языка. Выход этого транслитератора будем называть символьной лексемой. Такая лексема обычно состоит из двух частей: класса и значения. Класс лексемы должен служить входом для второго автомата. Транслитератор – это просто процессор с одним состоянием. Он реализуется как процедура, которая находит в таблице перевод для каждого входного символа. Множество классов символьных лексем обычно представляется с помощью последовательности натуральных чисел, т.к. они являются возможными входными символами для второго автомата.
|
Литерные лексемы |
|
|
класс |
значение |
А В С D Е … X Y Z |
Буква Буква Буква Буква Буква ---- Буква Буква Буква
|
1 2 3 4 5 --- 24 25 26 |
0 1 2 3 -- 9
|
Цифра Цифра Цифра Цифра --- Цифра
|
0 1 2 3 --- 9 |
+ - * / ↑ |
Арифметический оператор --- Арифметический оператор
|
1 2 3 4 5 |
= < > |
Отношение Отношение Отношение
|
1 2 3
|
( |
Левая скобка |
- |
) |
Правая скобка |
- |
. |
точка |
- |
|
пробел |
- |
CR |
Конец строки |
- |
Х |
Конец файла |
|
Символьная лексема Буква используется для представления всех букв, а её значение указывает конкретную букву. Буквы объединены в один класс, поскольку они все более или менее взаимозаменяемые. Исключение составляет буква Е, т.к. она может использоваться для изображения порядка. Поэтому её можно выделить в специальный класс лексем, оставив её значение равным 5.
Таблица имён.
Таблицы, хранящие имена и информацию связанную с этими именами, называется таблицами имён. Таблицы имен используются практически во всех компиляторах.
Имя |
Данные |
I |
Целое |
LOOP |
Метка |
X |
Вещественный массив |
Элементами полей имён являются обычно идентификаторы. Если имена могут быть различной длинны, то удобнее, чтобы элементы полей имён были указателями на область памяти, фактически хранящую эти имена. Элементы полей данных, называемые иногда дескрипторами, дают информацию, которую надо собрать о каждом имени.
В некоторых ситуациях с данным именем можно связать дюжину или более элементов информации. Например, возможно, что надо знать тип данных (вещественный, строковый, целый и.т.д.) идентификатора; был ли он меткой, именем процедуры или формальным параметром процедуры; должен ли он распределяться в статической или динамической области памяти. Был ли он идентификатором, имеющим структуру (массив) и если да, то какую структуру ( ] размер массива). Если число элементов информации, связанное с даны именем переменно, то слова удобно хранить в поле данных – указатель на эту информацию.
