Принципы работы лексического анализатора
Поскольку в данной курсовой работе входной язык является регулярным и может быть задан с помощью регулярной грамматики, распознавателем для него будет служить конечный автомат.
Конечный автомат задается пятеркой:
M=(Q,S,d,q0,F), где:
Q - конечное множество состояний автомата;
S - конечное множество допустимых входных символов;
d – множество функций перехода автомата;
q0ÎQ - начальное состояние автомата;
FÎQ - множество конечных состояний автомата.
Работа автомата выполняется по тактам. На каждом очередном такте i автомат, находясь в некотором состоянии qiÎQ, считывает очередной символ vÎV из входной цепочки символов и изменяет свое состояние на qi+1=d(qi,v), после чего указатель в цепочке входных символов передвигается на следующий символ и начинается такт i+1. Так продолжается до тех пор, пока цепочка входных символов не закончится. Конец цепочки символов часто помечают особым символом ^. Считается также, что перед тактом 1 автомат находится в начальном состоянии q0.
Графически автомат отображается нагруженным однонаправленным графом, в котором вершины представляют состояния, дуги отображают переходы из одного состояния в другое, а символы нагрузки (пометки) дуг соответствуют входному символу. Если функция перехода предусматривает переход из состояния q в q’ по нескольким символам, то между ними строится одна дуга, которая помечается всеми символами, по которым происходит переход из q в q’.
|
|
Схема распознавателя
Граф конечного автомата, используемого для распознавания входных цепочек языка, представлен на рис. 1 в приложении Б.
Начальное состояние автомата на рисунке обозначено "Н". В случае ошибочной входной цепочки автомат попадает в состояние ошибки E. При этом работа автомата останавливается.
Кроме того, типичными для автомата являются состояния I (переменная) и G (константа). Остальные состояния автомата определяются допустимыми для компилятора исходного языка лексемами.
Каждый переход в конечное состояние "S" сообщает о конце текущей входной цепочки. В этом случае производится анализ распознанной цепочки и перезапуск автомата для очередной входной цепочки символов. Заметим также, что возможна повторная обработка некоторых символов входной цепочки символов. Это необходимо в тех случаях, когда символ, приведший к переходу автомата в конечное состояние, является началом следующей цепочки символов.
Результаты
На основе сравнения методов организации таблиц идентификаторов, проведенного в первой части курсовой работы, выбран метод цепочек. На основе таблицы идентификаторов, заполненной по методу цепочек, организована таблица лексем. На рис. 5 и рис. 6 представлены таблица идентификаторов и таблица лексем, построенные при обработке следующего текстового файла:
|
|
prog ttt;
Begin
for j:=p7p downto 1001b do begin
if(t<f)and t then {rt rrrr}
c:=c*111111111b
else 5jhg;
End.
Содержимое файла:
Рис. 5. Результат работы лексического анализатора - таблица идентификаторов.
Содержимое файла: Неизвестные лексемы:
Рис. 6. Результат работы лексического анализатора - таблица лексем.
Дата добавления: 2018-02-15; просмотров: 943; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!