Лексический анализатор

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

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

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

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

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

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

Пример

Для примера, исходный код следующей строки программы

net_worth_future = (assets - liabilities);

может быть преобразован в следующий поток токенов:

ИМЯ "net_worth_future" 
РАВЕНСТВО 
ОТКРЫВАЮЩАЯ_СКОБКА 
ИМЯ "assets" 
МИНУС 
ИМЯ "liabilities" 
ЗАКРЫВАЮЩАЯ_СКОБКА 
ТОЧКА_С_ЗАПЯТОЙ

Пример такого парсера на языке PHP:

 class tokenstream {
   // Входной поток
   private $input_stream;
   // Указатель позиции во входном потоке
   public $seek = 0;
   // Конструктор
   public function __construct ( $input ) {
      // Инициализируем входной поток
      $this -> input_stream = $input;
   }
   // Возвращает очередной символ из входного потока
   public function readChar ( ) {
      $char = ( isset ( $this -> input_stream [ $this -> seek ] ) ? $this -> input_stream [ $this -> seek ] : false );
      $this -> seek++;
      return $char;
   }
   // Производит токенизацию
   public function tokenize ( ) {
      $output = array ( );
      while ( ( $char = $this -> readChar ( ) ) !== false ) {
         if ( preg_match ( '/\s/', $char ) ) { // Неотображаемые символы
         } elseif ( preg_match ( '/\"/', $char ) ) { // Кавычки
            $output [ ] = 'T_QUOTE';
         } elseif ( условие ) {
            $output [ ] = 'T_...';
         }
      }
      return $output;
   }
 }
 // Исходный код для разбора
 $my_source = '
  function foo ( ) {
   $my_var = "foo-bar";
  }  
 ';
 // Создаем экземпляр класса парсера
 $tokenstream = new tokenstream ( $my_source );
 // Парсим исходный код и распечатываем результат
 print_r ( $tokenstream -> tokenize ( ) );

Лексический анализатор

Схема лексического анализатора

Лексический анализатор (англ. lexical analyzer или коротко lexer) — это программа или часть программы, выполняющая лексический анализ. Лексический анализатор обычно работает в две стадии: сканирование и оценка.

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

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

Токен с типом и соответственно подготовленным значением передаётся на вход грамматического анализатора.

Генераторы лексических анализаторов

• Jlex — генератор на Java
• Quex
• gplex — генератор лексических анализаторов для С#
• OOLEX — объектно-ориентированный генератор анализаторов
• re2c

Литература

• Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е изд. — М.: Вильямс, 2008. — ISBN 978-5-8459-1349-4
• Робин Хантер Основные концепции компиляторов = The Essence of Compilers. — М.: «Вильямс», 2002. — С. 256. — ISBN 5-8459-0360-2