Лексический анализ с использованием конечного автомата

Помечено: 

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 неделя, 5 дней назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6286
      @admin

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

      Так, например, определение идентификатора как последовательности произвольной длины букв и цифр, начинающейся с буквы, при условии, что буквами считаются a и b, цифрами — 1 и 2, формализуется следующими правилами Бэкуса-Наура:

      <идентификатор>::=a|b|< идентификатор >a|< идентификатор >b|< идентификатор>1|< идентификатор >2

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

      Формально детерминированный конечный автомат задаётся:

      • множеством Σ входных символов,
      • множеством V внутренних состояний,
      • множеством P переходов между внутренними состояниями под воздействием входных символов,
      • начальным состоянием F,
      • множеством S последних состояний.

      При этом:
      $$F \in V \\
      S \subseteq V$$

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

      Управляющая таблица конечного автомата, распознающего идентификаторы в соответствии с вышеприведёнными правилами, выглядит так:

      Пустые ячейки таблицы считаются содержащими команду «ошибка».

      Нетрудно видеть, что содержание управляющей таблицы определено в соответствии с правилами грамматики. В общем случае при наличии в грамматике правила вида X ::= t, где t — терминальный символ, в ячейку управляющей таблицы с координатами (начальное состояние,t) следует поместить X, что будет рассматриваться как команда перехода в состояние X из начального состояния под воздействием входного символа t. Правило же вида X ::= Y t, где Y — нетерминальный символ, предписывает поместить ту же команду X в ячейку с координатами (Y,t), что будет соответствовать переходу автомата в состояние X из состояния Y под воздействием входного символа t. Последнее состояние автомата обычно определяется аксиомой грамматики.

      $$t \in \sum \\
      Y \in V$$

      В примере с идентификатором правила используют единственный нетерминальный символ — <идентификатор>, а значит, он же в простейшей грамматике является и аксиомой, а при построении конечного автомата соответствующее обозначение ("идентификатор") приобретает последнее состояние.

      Распознавание, например, слова a21 построенным автоматом будет выполнена за 3 шага:

      Анализируя идентификатор a21, как и любой другой, соответствующий определению идентификатора, автомат по первой букве исходного текста из начального состояния попадает в состояние "идентификатор" и остается в нём, пока на его вход продолжают поступать буквы (a или b) и цифры (1 или 2). Поскольку состояние "идентификатор" является последним состоянием автомата, автомат вправе остановиться на любом символе из этого потока букв и цифр. Эти остановки могли бы свидетельствовать о том, что любая подстрока, начинающаяся с первой буквы идентификатора, тоже является идентификатором. Если, всё же, речь идет об идентификаторах текстов программ на языках высокого уровня, как правило, требуется в текущей позиции анализируемого текста выявить самое длинное слово, являющееся идентификатором.

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

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

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

      В процессе функционирования конечного автомата происходит неявное выстраивание структуры распознаваемого слова в виде дерева разбора. Для идентификатора a21 дерево разбора выглядит так:

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

      Направление, в котором выполняется неявное построение дерева разбора конечным автоматом, определяет принадлежность этого способа решения задачи разбора к восходящим алгоритмам.

      Что же касается семантического анализа, представляется естественным связать его с последними состояниями автомата и подключать семантическую обработку в моменты окончания распознавания лексем. Одна из задач (а в некоторых случаях и единственная задача) семантической обработки обнаруженной лексемы — генерация токена. Обычно для разных лексем генерируются разные токены, для одинаковых — одни и те же. Но возможны и варианты.

      Поясним их на примере расширения возможностей изображения сумм, рассмотренном ранее. Пусть это расширение возможностей заключается в том, что слагаемым позволено быть произвольными идентификаторами (в соответствии с только что рассмотренным определением идентификатора), а не только односимвольными a, b и с. Если распознавание этих слагаемых-идентификаторов возложить на лексический анализатор, то его семантическая поддержка должна обеспечить генерацию токенов, которые были бы одинаковыми для всех обнаруженных в исходным тексте идентификаторов. Этот токен, с точки зрения синтаксиса изображения сумм, будет единственным терминальным символом, обозначающим слагаемые. Пусть, например, такой токен будет представлен символом Ω. Тогда грамматика языка изображения сумм идентификаторов будет содержать только 2 правила:

      <сумма> ::= <сумма> + Ω |Ω

      С точки зрения синтаксиса языка изображения сумм неважно, какие именно идентификаторы участвуют в сумме, важно только то, что все они являются идентификаторами. Это последнее обстоятельство гарантируется лексическим анализатором, сгенерировавшим токен Ω. Для предложения

      a21 + b1 + ab

      , например, будет построено дерево:

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

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

      Программная реализации «лексически управляемой трансляции» может быть выполнена с помощью специально разработанных для этой цели средств, примером которых является утилита Flex. Утилита является генератором C/C++- кода, представляющего собой алгоритм функционирования конечного автомата по встроенной управляющей таблице с чтением символов исходного текста и исполнением действий семантической части лексического анализатора, приписанным последним состояниям автомата. На вход Flex следует подать описание синтаксиса лексем и, при необходимости, описания действий семантической обработки также в виде C/C++- кода.

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

      Это обстоятельство даёт возможность утилите Flex защититься от некорректных входных данных: описания языка, для распознавания которого невозможно построить конечной автомат.

      В записи регулярных выражений операндами являются символы алфавита исходного языка, операциями — конкатенация, объединение (дизъюнкция) и итерация. В языке Flex знак конкатенации опускается, дизъюнкция обозначается символом ‘|’, итерация — символом ‘*’. Заметим, что символ ‘*’ здесь, по-прежнему, имеет смысл звездочки Клини, так как результат итерации — ноль или более вхождений операнда.

      Правила образования идентификатора из букв a и b и цифр 1 и 2, о котором шла речь в этом разделе, в виде регулярного выражения выглядит так: (a|b)(a|b|1|2)*.

      Круглые скобки в записи выражения используются для повышения приоритета операции дизъюнкции. Прочесть эту запись можно следующим образом: «Первый символ идентификатора — a или b, а за ним может следовать произвольное количество символов a,b, 1 или 2».

      Входной язык Flex, помимо основных операций над регулярными выражениями, содержит дополнительные средства для более удобной записи регулярных выражений.

      Что же касается семантической обработки лексемы, соответствующие действия в виде C/C++- кода заключаются в скобки {} и помещаются напротив регулярного выражения. При этом токен, как основной результат трансляции лексемы, чаще всего указывается в качестве операнда return. Например:

      (a|b)(a|b|1|2)* { return Omega;}

      Оператор return, как и любой другой текст, описывающий семантическую обработку лексемы, заносится утилитой Flex в генерируемый ею лексический анализатор таким образом, чтобы исполнение этой семантической обработки в процессе лексического анализа началось по достижении конечным автоматом последнего состояния, соответствующего окончанию распознавания данной лексемы. C/C++- код лексического анализа оформляется утилитой Flex в виде функции int yylex(). Оператор return, таким образом, предназначен для выхода из этой функции с возвращением целочисленного результата, который снаружи этой функции интерпретируется как токен распознанной лексемы. При использовании символьных имён для обозначения токенов (в примере с лексемой-идентификатором – Omega) следует позаботиться о том, чтобы в исполняемом коде эти имена приобрели целочисленные значения. Семантическая обработка распознанной лексемы имеет возможность доступа к этой лексеме как к последовательности символов исходного текста. Лексема помещается функцией yylex в локальную переменную char* yytext. Кроме того, на этапе лексического анализа можно сформировать некое внутреннее представление обнаруженной лексемы и записать его во внешнюю переменную yylval, имея в виду, что оно пригодится на следующем этапе синтаксически управляемой трансляции. По умолчанию эта переменная имеет тип int, но при необходимости может быть переопределена. К вопросу о деталях переопределения вернёмся позже.

      Если, например, обнаружение идентификатора требуется сопровождать выводом его на экран, а его атрибутом (внутренним представлением) по какой-либо причине должна считаться его длина, то вышеприведённую строку регулярного выражения можно дополнить соответствующими семантическими действиями:

      (a|b)(a|b|1|2)*          { cout<<”обнаружен идентификатор: ”<<yytext<<’\n’;
                                 yylval=strlen(yytext); return Omega; }

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.