ЯЗЫКИ ПРОГРАММИРОВАНИЯ И МЕТОДЫ ТРАНСЛЯЦИИ Рейн Т. С. Лексический анализ

Сущность лексического анализа Лексический анализ ( ЛА ) является первой фазой трансляции. Термин « лексика » в обычном языке подразумевает правила составления слов из букв. В языке программирования ЛА соответствует фаза трансляции, в которой из последовательности отдельных литер ( символов, букв языка ) выделяются слова ( лексемы или символы - как сони именуются на сходе следующей фазы - синтаксического анализа ). Типичными словами в языке программирования являются такие компоненты как комментарии, идентификаторы, константы, служебные слова, знаки операций.

Ограничения лексического анализа лексемы распознаются независимо друг от друга. Единственное, что возможно, это « перекрытие » процесса распознавания двух рядом расположенных лексем на заданное количество литер ; определение лексем включает элементы выбора одного из нескольких вариантов продолжения и повторения ; вложенность одной лексемы в другую или наличие произвольной вложенности элементов лексемы не допускается.

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

Задача лексического анализа Разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, то есть выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким - либо лексемам, и символы, разделяющие лексемы ( разделители ). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках лексемы могут содержать незначащие символы ( например, символ пробела в Фортране ). В Си разделительное значение символов - разделителей может блокироваться (" \ " в конце строки внутри "...").

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

Результат ЛА Для осуществления двух дальнейших фаз анализа ЛА выдает информацию двух типов : для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, для контекстного анализатора, работающего вслед за синтаксическим, существенна информация о конкретных значениях отдельных лексем ( идентификаторов, чисел и т. д.).

Схема ЛА Общая схема работы лексического анализатора такова. Выделяется отдельная лексема ( при этом, возможно, используются символы - разделители ). Ключевые слова распознаются явным выделением непосредственно из текста либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых слов.

Виды ЛА Лексический анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу " дай лексему ".

Простейший ЛА Простейший лексический анализатор можно построить, не прибегая ни к каким формальным методам, просто анализируя последовательности символов, образующих лексические единицы. В примере программа « зацепляет » первый символ, определяющий начало лексической единицы ( букву, цифру и т. д.) а затем просматривает строку до конца элемента лексики ( идентификатора, константы ). Некоторые лексические единицы при этом имеют еще и собственное значение, которое выходит за рамки алгоритма распознавания. Например, для идентификатора и константы важен не только факт их распознавания, но и их значение, заключенное в цепочке символов. Поэтому анализатор перед началом очередного цикла фиксирует начало распознаваемой последовательности символов, для сохранения ее значения.

while (1) { fix=i; switch(s[i]) { case '"': // Распознавание строковой константы "...« с двойными "" внутри mmm: i++; while (s[i] !='"') i++; i++; if (s[i]=='"') goto mmm; lexem(1); break; case '/': i++; // Распознавание / и /* if (s[i]!='*') { lexem(14); break; } // Распознавание комментария /*... */ n1: while (s[i] !='*') i++; i++; if (s[i]=='/') { i++; lexem(2); break; } goto n1; case '+': i++; // Распознавание += и + if (s[i]=='=') { i++; lexem(5); } else lexem(15); break; case '

Формализация ЛА Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата не всегда удобно с практической точки зрения. Поэтому для задания лексического анализатора, часто, используется либо регулярное выражение, либо праволинейная грамматика.

Формализация ЛА Все три формализма ( конечных автоматов, регулярных выражений и праволинейных грамматик ) имеют одинаковую выразительную мощность. В частности, по регулярному выражению или праволинейной грамматике можно сконструировать конечный автомат, распознающий тот же язык.

Регулярные выражения Регулярные выражения формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов. По сути это строка - образец ( англ. pattern, по - русски её часто называют « шаблоном », « маской »), состоящая из символов и метасимволов и задающая правило поиска. Регулярные выражения используются некоторыми текстовыми редакторами и утилитами для поиска и подстановки текста.

Регулярные выражения Регулярные выражения произвели прорыв в электронной обработке текстов в конце XX века. Набор утилит ( включая фильтр grep), поставляемых в дистрибутивах UNIX, одним из первых способствовал популяризации регулярных выражений для обработки текстов.grep Многие современные языки программирования имеют встроенную поддержку регулярных выражений. Среди них ActionScript, Perl, Java [1], HTML5, PHP, JavaScript, C++ ( стандарт 2011 года ), Delphi и др.ActionScriptPerlJava [1]HTML5PHP JavaScriptC++2011Delphi

Регулярные выражения При помощи регулярных выражений можно задать шаблоны, позволяющие : найти все последовательности символов « кот » в любом контексте, как то : « кот », « котлета », « терракотовый »; найти отдельно стоящее слово « кот » и заменить его на « кошка »; найти слово « кот », которому предшествует слово « персидский » или « чеширский »; убрать из текста все предложения, в которых упоминается слово кот или кошка. Регулярные выражения позволяют задавать и гораздо более сложные шаблоны поиска или замены.

Регулярные выражения. Определение Регулярные выражения состоят из констант и операторов, которые определяют множества строк и множества операций на них соответственно. На данном конечном алфавите Σ определены следующие константы : ( пустое множество ). ( пустая строка ) ε обозначает строку, не содержащую ни одного символа. Эквивалентно «». ( символьный литерал ) «a», где a символ алфавита Σ.

( сцепление, конкатенация ) RS обозначает множество { αβ | α R & β S}. Например, {"boy", "girl"}{"friend", "cott"} = {"boyfriend", "girlfriend", "boycott", "girlcott"}. сцепление, конкатенация ( дизъюнкция, чередование ) R|S обозначает объединение R и S. Например, {"ab", "c"}|{"ab", "d", "ef"} = {"ab", "c", "d", "ef"}. дизъюнкция ( замыкание Клини, звезда Клини ) R* обозначает минимальное надмножество множества R, которое содержит ε и замкнуто относительно конкатенации. Это есть множество всех строк, полученных конкатенацией нуля или более строк из R. Например, {"Go", "Russia"}* = { ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}. замыкание Клини, звезда Клини Регулярные выражения. Определение

Конечные автоматы Формальной основой ЛА являются конечные автоматы ( КА ). Конечный автомат является принципиально более простой формальной моделью, нежели компьютерная программа ( машина Тьюринга ). Программа включает в себя две компоненты : алгоритм и произвольным образом организованные неограниченного объема данные. Конечный автомат не содержит данных и представляет собой алгоритмическую часть программы в чистом виде.

Конечные автоматы КА представляет собой систему, которая реагирует только на изменение состояния внешней среды, но не способна к запоминанию. КА не имеет изменяемой памяти, сама управляющая информация о структуре автомата хранится в постоянной памяти ( обычно в табличной форме ). Единственным хранимым параметром автомата является его текущее состояние, которое характеризует текущий шаг выполняемого алгоритма ( аналог регистра процессора - IP).

Различия КА и программы конечный автомат моделирует « инстинктивное » поведение, основанное на воспроизведении программы действий, меняющейся в зависимости от последовательности внешних событий, но не запоминающей информации из внешней среды ; компьютерная программа моделирует « рефлекторное » поведение, принципиально связанное с запоминанием и обработкой информации о внешних событиях и настройкой ( адаптацией ) к ним.

Определение КА Конечный автомат – алгоритмическая компонента программы « без данных », моделирующая « инстинктивное » поведение, неадаптируемое к последовательности воздействий внешней среды.

Определение КА Конечный автомат абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию. абстрактный автомат конечно Абстрактный автомат математическая абстракция, модель дискретного устройства, имеющего один вход, один выход и в каждый момент времени находящегося в одном состоянии ( стабильных значений ) из множества возможных. На вход этому устройству поступают символы одного алфавита, на выходе оно выдаёт символы ( в общем случае ) другого алфавита.

Формальное определение КА Конечный автомат определяется шестью компонентами A = { I,O,S,S 0,P,D } множество ( алфавит ) входных символов I={I i }; множество ( алфавит ) входных символов O={O j }; множество состояний автомата S={S k }; начальное состояние S 0 ÍS; функция переходов P(S, I) S, ставящая в соответствие каждой паре « состояние - входной символ » новое состояние ; функция выходов D(S, I) O, ставящая в соответствие каждой паре « состояние - входной символ » выходной символ.

Работа КА КА является дискретной системой, работающей по тактам ( шагам ), в каждом из которых он получает на вход один из символов входного алфавита ; последовательность символов на входе КА образует входную цепочку ; на каждом шаге КА находится в одном из возможных состояний, которое называется текущим. Текущее состояние – единственная характеристика внутреннего описания КА, которая меняется при его работе ( изменяемая память ). Все остальные элементы его описания являются статическими ( т. е. в любой реализации представляют собой постоянную память );

Работа КА Шаг работы КА состоит в переходе из текущего состояния в новое состояние при получении на вход очередного символа входной цепочки. Этот переход определяется функцией переходов ; Результат работы КА заключается в записи в выходную цепочку символов, генерируемых функцией выходов КА. параллельно с переходом в новое состояние формируется выходной символ, определяемый парой « текущее состояние – входной символ ». Выходной символ может быть и пустым ;

Работа КА Работа КА заключается в преобразовании входной цепочки символов в выходную. Закон этого преобразования определяет поведение КА. Задача проектирования КА состоит в создании КА, обеспечивающем заданные правила преобразования цепочек.

Недетерменизм КА Недетерминизм автомата заключается в том, что, во - первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во - вторых, автомат может делать переходы по e.

Пример Пусть L = L(r), где r = (a|b) * a(a|b)(a|b). Недетерминированный конечный автомат M, допускающий язык L: M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}}, где функция переходов D определяется так :

Пример Детерминированный конечный автомат M, допускающий язык L: M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}} где функция переходов D определяется так :

Работа КА Очевидно, что отсутствие у КА внутренней памяти ограничивает его возможности по преобразованию цепочек ( моделирующая способность ). С другой стороны, эти же ограничения позволяют решать в общем случае многие проблемы ( алгоритмическая разрешимость ).

Представление КА Наиболее удобной формой представления КА для человека является графическая - диаграмма состояний - переходов, а для программирования и формальных преобразований – табличная. Основные элементы диаграммы состояний – переходов : состояние представляет собой окружность, содержащую номер или наименование состояния ; направленная дуга, соединяющая состояния S k и S m, определяется значениями функций переходов и действий : если S m =P(S k, I i ) и O n =D(S k, I i ), то имеется переход КА из S k в S m, который обозначается дугой, соединяющей эти вершины. Дуга подписывается парой символов I i /O n. Это означает, что переход по дуге при поступлении на вход символа I i сопровождается формированием выходного символа O n.

Если поведение какого-либо объекта можно описать набором предложений вида: «Находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D», то такая система будет представлять собой конечный автомат.

Представление КА Анализируя диаграмму состояний - переходов и вид преобразования цепочек, можно сделать вывод о поведении автомата и сущности выполняемых им преобразований. Можно заметить, что получая входные цепочки, содержащие символы a и b в произвольном порядке, КА формирует аналогичные цепочки более регулярного вида.

Представление КА Так, из подряд идущих символов b КА оставляет один, а в последовательности символов a оставляет все нечетные, кроме первого. При нечетном количестве символов a на входе КА добавляет еще один символ a в выходную последовательность. Отсюда можно вычислить закон преобразования длины входной цепочки символов a - N a(out) = (N a(in) +1)/2

Пример Анализируя состояния и условия переходов в них, можно определить их содержательный « смысл »: состояния S 1, S 2 обозначают нечетное и четное число подряд прочитанных символов a.

Представление КА Табличная форма представления КА включает в себя представление функций переходов и выходов виде таблиц. Pab S010 S120 S210 Dab S0b S1 a S2a На диаграмме состояний-переходов не может быть двух и более дуг из одного состояния, помеченных одним и тем же входным символом. Если это не так, то такая неканоническая форма называется недетерминарованным КА. Такой КА не имеет адекватного табличного (функционального) представления, но может быть преобразован в обычный детерминированный.

Автоматные модели в программировании При разработке программ, характеризующейся сложной логикой управления, можно применять автоматный подход, который позволяет сделать текст программы более регулярным и компактным. То же самое решение можно применить, если программа активизируется внешними событиями ( событийное программирование ) и требуется отследить заданную последовательность наступления событий.

Пример В качестве примера, реализованного в виде автоматной модели, рассмотрим функцию, которая исключает из строки комментарии вида /*... */ Прежде всего, необходимо определить состояния автомата, возможные при просмотре очередного символа строки : состояние 0 - идет обычный текст ; состояние 1 - обнаружен символ /; состояние 2 - обнаружено начало комментария /*; состояние 3 - в комментарии обнаружен символ *.

Пример. Вид программы void f(char in[ ],char out[ ]) {int i, s, j; // s – текущее состояние автомата for(i=0,s=0,j=0; in[i]!=0; i++) // i - индекс текущего символа входной строки switch(s) // j – индекс текущего символа выходной строки { case 0: if (in[i])!=/ out[j++] = in[i]; // символы копируются только в состоянии 0 else s=1; break; case 1: if (in[i]!=*) { out[j++]=in[i-1]; out[j++]=in[i]; s=0; } else s=2; break; case 2: if (in[i]==*) s=3; break; case 3: if (in[i]==/) s=0; break; }}

Характеристики программы программа представляет собой цикл, в каждом шаге которой анализируется очередной символ из входной строки. только текущий. Программа принципиально не анализирует ни предыдущих, ни последующих символов. Текущий символ играет, таким образом роль входного сигнала, по которому автомат переходит из одного состояния в другое. программа имеет переменную s, которая и представляет собой текущее состояние КА. В теле основного цикла программы выполняется переключение (swit с h) по всем возможным значениям этой переменной - состояниям КА.

Характеристики программы в каждом состоянии реализуется логика его перехода в другие состояния на основе анализа текущего символа - входного сигнала и вырабатывается соответствующее действие. Например, в состоянии 1, когда программа уже обнаружила символ / - возможное начало комментария, она проверяет, не является ли текущий символ *. Если это так, автомат переводится в состояние 2 - нахождение внутри комментария, Если нет, то в выходную строку переписывается предыдущий / и текущий символы, а автомат возвращается в состояние 0.

Конечные автоматы в лексическом анализе Конечные автоматы ( КА ) являются основой построения лексических анализаторов. В реальном проектировании трансляторов в качестве языка описания лексики используются регулярные выражения, которые « транслируются » сначала в неканонические ( недетерминированные ) КА, которые затем преобразуются в обычные КА, минимизируются и т. п..

В простых случаях, когда требуется распознаватель для лексики ограниченного объема, можно использовать формализм КА для непосредственного проектирования распознавателя. При этом технология проектирования такого КА в системе состояний - переходов имеет много общего с « историческим подходом » при разработке алгоритмов с использованием блок - схем. Конечные автоматы в лексическом анализе

В процессе рисования блок - схемы ставится вопрос « Куда направить дугу от текущего блока при выполнении заданного условия ?». « Перевод стрелок » на уже нарисованные элементы блок - схемы ( переход в уже известную часть алгоритма ) или рисование нового элемента ( планирование нового действия ) является основным технологическим элементом проектирования. При разработке диаграммы состояний - переходов КА требуется выполнять аналогичные действия, проводя дугу из одного состояния в другое при появлении на входе КА определенного символа ; Конечные автоматы в лексическом анализе

Любой элемент блок - схемы является точкой алгоритма, которую можно содержательно сформулировать в терминах текущего состояния ( например, « в этой точке программы при получении символа a алгоритм завершает цикл, а для остальных символов – продолжает его »). Аналогично, каждое состояние КА имеет свою « смысловую » нагрузку Например « накопление идентификатора », « ожидание символа * после /» и т. п.. Конечные автоматы в лексическом анализе

Проектирование КА с помощью диаграммы состояний - переходов происходит содержательно. Определяются состояния КА, им присваивается « смысл », а затем определяется, при каких условиях происходит переход из одного в другое. Конечные автоматы в лексическом анализе

Особенностью реализации КА в лексическом анализе является то, что каждой лексеме соответствует свой независимый цикл ( последовательность состояний КА ). Для этого в КА вводятся особые заключительные состояния : Особенности автоматов для лексического анализа

достижение автоматом заключительного состояния рассматривается как факт обнаружения некоторой лексемы. Каждому заключительному состояния соответствует своя распознанная лексема. Это позволяет отказаться от выходных сигналов ; значением накопленной лексемы является часть входной строки, просмотренная автоматом при его работе от начального до конечного состояния ; при достижении конечного состояния КА принудительно сбрасывается в начальное состояние. Заключительные состояния КА

Особенности КА для лексического анализа Введение заключительных состояний приводит к появлению еще одного неканонического действия, обусловленного разделением процессов распознавания лексем. С каждым заключительным состоянием КА необходимо связать фиксированное число возвращаемых символов. процесс распознавания лексем, не имеющих явно заданных ограничителей, завершается чтением символов, являющихся началом следующей. Их необходимо возвратить во входную последовательность ( произвести « откат » автомата на фиксированное число символов назад ).

На диаграмме состояний переходов это отображается так : заключительные состояния обозначаются особенно ( например, выделяются цветом ), именуются или нумеруются отдельно ( например, отрицательными числами ); рядом с каждым заключительным состоянием записывается количество возвращаемых символов ; каждая дуга помечается только одним символом ( или группой символов ) перехода, выходных символов КА не продуцирует.

Пример Полученный КА можно представить и в табличной форме - в виде таблицы переходов и таблицы заключительных состояний. Для этого всё множество входных символов разбивается на непересекающиеся множества - классы. Классы выбираются таким образом, чтобы обеспечивалось однозначное переключение КА по каждому из них : цифры 0-9. буква a буквы b-z. символ /. символ *. символ. остальные символы.

Пример Символы, на которые КА должен обеспечивать различную реакцию, должны быть разнесены в отдельные классы. Далее каждому заключительному состоянию ставится в соответствие константа – количество символов, возвращаемых в выходной поток.

Пример Номер состоянияЛексемаВозврат символов Идентификатор с двумя a 1 -2 Идентификатор 1 -3 Константа десятичная 1 -4 Комментарий 0 -5 Символ / 1 -6 Символ * 0 -7 Константа строковая 1

Пример Ост 0-9ab-z/* S S S S3333 S4-34 S5-5 6 S S S S9-7 8

Требования к КА В табличной форме все клетки должны быть заполнены : это означает полную определенность автомата – в любом состоянии известна его реакция на любой из входных символов. С этих позиций следует рассматривать переходы по « остальным » символам, обычно это понимается в самом широком смысле как переход по всем символам, кроме явно обозначенных в диаграмме для данного состояния.

Требования и характеристики Полученный КА включается в программу - распознаватель лексики в табличной форме, что позволяет сделать универсальным алгоритм работы КА, не зависящим от программируемой лексики, которая становится в программе компонентой данных.

Программная реализация В программе определяется переменная - текущее состояние КА ( переменная ST). Определением класса символа занимается отдельная функция. Функция возвращает номер класса символов, к которому относится ее входной символ, что соответствует номеру столбца матрицы переходов. Матрица переходов в программе - это двумерный массив, который для каждой пары « состояние ( строка ) и класс символа ( столбец )» определяет новое состояние, в которое он переводится. Номер этого состояния и находится в матрице. Принцип заполнения матицы прост : если в состоянии S1 и входном символе L1 на диаграмме имеется дуга ( переход ) в состояние S2 то элемент массива D[S1][K1] должен быть инициализирован значением S2, где K1=class(L1).

Пример 2. Лексический анализ Цепочка из символов a,b,c,+. Лексемами считаются отдельные знаки +, цепочки из букв, в которых нет пар одинаковых. Отдельными лексемами считаются цепочки одинаковых букв. Если за ней идет пара ++, то она также считаются частью лексемы, например : abc|bbb|+|ab++|a|bbb++|b|aa|+|aaa++|a

Пример 2. Лексический анализ Внутренние состояния автомата и запоминаемые в них события : первая буква лексемы (3 состояния ); повторение буквы (3 состояния ); отсутствие повторения буквы (3 состояния ); был + после цепочки одинаковых или неодинаковых букв (2 состояния ). При обнаружении одинарного + после цепочки одинаковых букв – возврат 2 символов.

Программирование ЛА Лексический анализатор ( ЛА ) может быть оформлен как подпрограмма. При обращении к ЛА, вырабатываются как минимум два результата : тип выбранной лексемы и ее значение ( если оно есть ).

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

Программирование ЛА В основе ЛА лежит диаграмма переходов соответствующего конечного автомата. Отдельная проблема здесь - анализ ключевых слов. Как правило, ключевые слова - это выделенные идентификаторы. Поэтому возможны два основных способа распознавания ключевых слов : либо очередная лексема сначала диагностируется на совпадение с каким - либо ключевым словом и в случае неуспеха делается попытка выделить лексему из какого - либо класса, либо, наоборот, после выборки лексемы идентификатора происходит обращение к таблице ключевых слов на предмет сравнения.

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

Программирование ЛА Основная операция ЛА, на которую уходит большая часть времени его работы - это взятие очередного символа и проверка на принадлежность его некоторому диапазону. Например, основной цикл при выборке числа в простейшем случае может выглядеть следующим образом : while (Insym ='0'){... }

Выделение ключевых слов может осуществляться после выделения идентификаторов. ЛА работает быстрее, если ключевые слова выделяются непосредственно. Для этого строится конечный автомат, описывающий множество ключевых слов.

case 'i': if (cp[0]=='f' &&!(map[cp[2]] & (DIGIT | LETTER))) {cp++, return IF,} if (cp[0]=='n' && cp[1]=='t &&!(map[cp] & (DIGIT | LETTER))) {cp+=2, return INT,}{ обработка идентификатора } Здесь cp - указатель текущего символа. В массиве map классы символов кодируются битами.