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

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

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

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

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

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

Пример:

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

Решение:

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

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

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

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

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

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

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