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

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

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

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

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

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