2.1.2.1. Непрямой лексический анализ

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

Сигналом, очевидно, служит само заключительное состояние. Однако лексическому анализатору, возможно, требуется исследовать один или более символов, стоящих после правого конца лексемы. Простой пример: мы не можем определить правый конец идентификатора языка Object Pascal или Cи, пока не встретим символ, который не является ни буквой, ни цифрой, т.е. обычно не считается частью идентификатора.

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

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

2.1.2.2. Прямой лексический анализ

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

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

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

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

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

Пример :

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

Решение:

Упрощенное множество идентификаторов (включающее и ) распознается конечным автоматом, изображенным на рис. 2.1.а, цепочка – автоматом на рис. 2.1.б, a – автоматом на рис. 2.1.в. (Здесь все автоматы детерминированные, хотя в общем случае это, разумеется, не обязательно.)

Рис. 2.1. Автоматы для лексического анализа:

а) – идентификаторы; б) – ; в) –

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

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

Рис. 2.2. Автоматы для лексического анализа: