Конечный автомат состоит только из входной ленты и управляющего устройства с конечной памятью. Управляющее устройство может быть недетерминированным, но входная головка является односторонней; входная головка сдвигается вправо на каждом такте. Можно определить конечный автомат, задав конечное множество его управляющих состояний, допустимые входные символы, начальное состояние и множество заключительных состояний, то есть состояний, указывающих, что входная цепочка допускается. Задается также функция переходов состояний, которая по данному “текущему” состоянию и “текущему” входному символу указывает все возможные следующие состояния. Недетерминизм конечного автомата не следует смешивать со “случайностью”, при которой автомат может случайно выбрать одно из следующих состояний с фиксированными вероятностями.
Работу конечного автомата можно представить в виде некоторой последовательности шагов или тактов. Такт определяется входным символом, обозреваемым в данный момент входной головкой, и текущим состоянием управляющего устройства. Сам шаг состоит из изменения состояния и сдвига входной головки на одну ячейку вправо.
Для того чтобы определить будущее поведение конечного автомата, нужно знать лишь
1. Текущее состояние управляющего устройства.
2. Цепочку символов на входной ленте, состоящую из символа под головкой и всех символов, расположенных справа от него.
Эти два элемента информации дают мгновенное описание конечного автомата, которое мы будем называть конфигурацией.
Читать дальше
Для того, чтобы проверить правильность семантики и сгенерировать код, необходимо знать определенные характеристики переменных, констант, функций и других элементов, которые могут встречаться в программе. Данные элементы, обычно, обозначаются идентификаторами. У компилятора должна быть возможность хранить найденные идентификаторы и связанные с ними характеристики в течение процесса компиляции. Для данной цели используются таблицы символов и таблицы идентификаторов – специальные хранилища данных. Для каждого элемента исходной программы состав информации в таблице идентификаторов различается, в зависимости от семантики входного языка и типа элемента.
Например:
• для переменных:
o имя
o тип
o область памяти
• для констант:
o название
o значение
o тип
• для функций:
o имя
o количество и типы аргументов
o тип возвращаемого значения
o адрес кода
Принцип работы компилятора с таблицей идентификаторов вне зависимости от его реализации остается одним и тем же – компилятор вынужден многократно обращаться к таблице на различных фазах для поиска информации и записи новых данных. Как правило, каждый эллемент в исходной программе однозначно идентифицируется своим именем. Именно поэтому компилятору часто приходится выполнять поиск необходимо элемента в таблице идентификаторов по его имени, в то время как процесс заполнения таблицы выполняется нечасто – новые идентификаторы описываются в программе гораздо реже, чем используются. Отсюда можно сделать вывод, что таблицы идентификаторов должны быть организованны таким образом, чтобы компилятор имел возможность максимально быстрого поиска нужного ему элемента.
Читать дальше
Детерминированный автомат с магазинной памятью
Будем использовать следующие условне обозначения:
α/β/γ – α – символ, по которому осуществляется переход; β – символ, вынятый из стека; γ – символ, помещаемый в стек (в магазинную память).
Схема...
Читать дальше
7 страниц
70% уникальность
2013 год
18 просмотров
