Компиляторы. Лексический анализ. Преобразования грамматик

Для грамматик, например леволинейного типа, существует алгоритм определения того, принадлежит ли анализируемая цепочка языку, порождаемому этой грамматикой. Алгоритм заключается в слудйющем: 1-й символ исходной цепочки a1a2a3a….an# заменяетися нетерминальным символом А, для которого в грамматике есть правило вывода A->ai, т.е. производится свертка терминала a1 к нетерминальному A. Затем многократно до тех пор, пока не считан признак конца цепочка, выполняется следующие шаги. Полученный на предыдущем шаге нетерминал A и расположенный непосредственно справа это него очередной терминал ai исх цеп, заменяется нетерминалом B, для которого в грамматике есть правило вывода вида B->Aai. Это эквивалентно построению дерева разбора методом снизу вверх. При работе алгоритма возможны слуд ситуации:

1. Прочитана вся цепочка, на каждом шаге находилась единственная нужная свертка, на последнем шаге свертка произошла к символу S. Это значит, что цепочка принадлежит языку. a1a2a3…an#ЄL(G).

2. Прочитана вся цепочка. На каждом шаге находилась единственная нужная свертка, на последнем шаге – свертка произошла к символу, отличному от S. Это означает, что исх цепочка не принадлежит языку a.

3.На некотором шаге не нашлаось нужной свертки, т.е. для полученного на предыдущем шаге нетерминала A и расположенного непосредственно справа от него очередного терминала ai исх цепочки, не нашлось нетерминала B, для которого в грамматикае было бы правило вывода B->Aai. Это означает, что исх цепочка не принадлежит языку.

4. На некотором шаге работы алгоритма оказалось, что есть более одной подходящей свертки, т.е. в грамматике разные нетерминалы имеют правила вывода с одинаковыми правыми частями и поэтому не понятно к которому из них производить свертку. Это говорит о недетерминированности разбора. Для того, чтобы при лексическом разборе быстрее находить правила с подходящей правой частью фиксируют все возможные свертки в описании грамматики. Это определяется только грамматикой и не зависит от вида анализируемой цепочки.

Диаграмма определяет конечный автомат, построенный по регулярной грамматике, который допускает множество цепочек составляющих язык, определяемый этой грамматикой. Среди всех состояний выделяются начальные и конечные. По мере считывания каждой литеры строки контроль передается от состояния к состоянию в соответствие с заданным множеством переходов. Если после считывания последней литеры строки автомат будет находится в одном из последних состояний, то строка принадлежит языку, принимаемому автоматом. Формально конечный автомат определяется 5-ю хар-ками:

1) Конечным множеством состояний K. 2) Конечным множеством входным алфавитом. 3)множеством переходом. 4)Начальным состоянием. 5)Множеством последних сотояний.

M=(K,VT,F,H,S)

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами. Это означает, что для любого недетерминированного конечного автомата всегда можно построить детерминированный конечный автомат, определяющий тот же язык. Соответствие лексическому анализу заключается в том, что каждому языку 3-его типа соответствует детерминированный конечный автомат, распознающий строки этого языка. Исходя из этого, можно сказать, что написание лексического анализатора частично сводится к моделированию различных автоматов для распознавания конструкций языка, таких как идентификаторы, числа, ключевые слова и т.д. Лексический анализ вкл в себя просмотр компилируемой программы и распознавание лексем, составляющих предложение исходного текста. Точный перечень лексем, которые нужно распознать, зависит от ЯП и от грамматики, используемой для описания этого языка.

Лексический анализатор преобразовывает исх программу в последовтельность символов. При этом идентификаторы и константы производной длины заменяются символами фиксированной длины. Слова языка также заменяются какими-нибудь стандартными представлениями. Для повышения эффективности последних действий, каждая лексема обычно определяется кодом. Коды, создаваемые для слов языка, не должны зависеть от программы. В случае же идентификатора дополнительно необходимо конкретное имя распознаваемого идентификатора. Получение кодов-идентификаторов производится последовательно, начиная с начала по тексту проги. Кадый экземпляр определенного идентификатора на любом уровне заменяется одним и тем же кодом. Из этого следует необходимость создания таблицы идентификаторов, где будут храниться соответствия кодов и самих идентификаторов.

Аналогично таблиза необходима и для констант. Некоторые компиляторы проверяют длину констант и вычисляют их в процессе лексического анализа. Однако табл констант используется на более поздних стадиях компиляции, и поэтому ее обычно просто заполняют на этапе лексического анализа.

Сущ проблема с именами идентификаторов в том случае, если переменная с одинаковым именем присутствует в процедуре и в основной программе. В этом случае необходимо создавать столько строк в таблице идентификаторов, сколько раз определена данная переменная, кроме того нужно к таблице добавить поле для занесения информации о том, какой процедуре принадлежит идентификатор. При лексическом анализе базовым терминальным символом является буква, что вытекает их традиционного определения идентификаторов как последовательности букв и цифр, начинающихся с буквы. Еще более важным фактором является необходимое во всех языках наличие разделитилей или пробела между лексемами. Сам этот пробел и недопустимые буквы тяжелее всего распознать традиционными средствами грамматики. В дополнение к своей основной функции лексический анализатор обычно также выполняет чтение строк исходной программы и возможно печать листинга исходной программы. Многие языки имеют специфические особенности, которые должны учитываться при программировании лексического анализатора.

Дата добавления: 2014-01-07