1. ТеореТическое введение
1.1. Задача лексического анализа.
использование автоматной модели
для лексического анализа
лексический анализ (сканер) представляет собой первую фазу
процесса компиляции, при которой отдельные литеры входной цепочки группируются в слова (лексемы). Каждому распознанному
слову входного языка ставится в соответствие некоторое внутреннее представление. Часто термин «лексема» относят и к этому внутреннему представлению. во избежание двусмысленности будем называть внутреннее представление лексемы кодом лексемы.
например, если предложения входного языка представляют собой списки идентификаторов, разделенных запятыми, то результатом лексического анализа предложения abc,d1,ef2 при условии, что
коды лексем зафиксированы в таблице лексем (табл. 1), будет следующий список кодов: 2 1 3 1 4.
Множество различных лексем языка программирования обычно
бесконечно. поэтому формирование таблицы лексем выполняется
в процессе анализа конкретной входной цепочки. при этом каждый экземпляр определенной лексемы, присутствующий во входной цепочке,
должен получить в выходном списке один и тот же код, что обеспечивается наличием таблицы. Код лексемы обычно представляет собой пару
вида (тип лексемы, некоторые данные). первая компонента пары является синтаксической категорией, указывая принадлежность лексемы
какой-либо непосредственной составляющей грамматики. в грамматиках языков программирования, как правило, к таким непосредственным составляющим относятся: иден
тификатор, константа, разделитель и др.
вторая компонента кода может быть ука
Таблица 1. Таблица лексем
лексема Код лексемы
обозначим в вышерассмотренном примере тип лексемы символом «r», если она является запятой, и символом «i», если она относится к категории . тогда код лексемы «,» приобретет вид: r1, а коды лексем «abc», «d1» и «ef2» соответственно: i2,
i3 и i4. при этом вторая компонента кода является указателем на
соответствующую запись таблицы лексем. синтаксис лексем, как
правило, описывается в рамках автоматной грамматики, или грамматики типа 3 в соответствии с классификацией Хомского. Это означает, что лексический анализатор (сканер) может быть организован в виде модели конечного автомата. так, если порождающие
правила грамматики имеют вид: ::=N и ::=N, где ,
– нетерминальные, а N – терминальный символы грамматики, то соответствующий автомат определяется пятеркой:
1) конечное множество V внутренних состояний, каждое из которых, за исключением одного (обозначим его – F), соответствует нетерминальному символу грамматики;
2) конечный входной алфавит T, каждый символ которого соответствует терминальному символу грамматики;
3) множество P переходов;