Интерпретатор выражений за 10 минут

Сегодняшняя статья будет посвящена интерпретаторам выражений. Примерно год назад я уже поднимал эту тему в статье Интерпретатор выражений за 15 минут. Сегодня я расскажу о способе разбора лексем, который позволит нам сэкономить немного времени. Этот способ, я думаю, можно считать позаимствованным у утилиты lex, поскольку описание лексем задаются аналогичным способом. Оговорюсь сразу, что этот способ не претендует на оптимальность и высокое быстродействие.

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

abstract class VLex
{
	const TOK_NONE = 'TOK_NONE';
	const TOK_ENDSTREAM = 'TOK_ENDSTREAM';
	const TOK_UNDEFINED = 'TOK_UNDEFINED';
	
	const ERR_SYNTAX = 'VSyntaxErrorException';
	
	protected $tokens = array();
	
	// регистрация списка лексем
	protected function registerTokens(array $tokens)
	{
		foreach ($tokens as $pattern => $token) {
			$this->tokens[$pattern] = $token;
		}
	}
	
	public function __construct()
	{
		$this->registerTokens(array(
			'[\s\n]+' => self::TOK_NONE,
			'.' => self::TOK_UNDEFINED,
		));
	}

	// начало разбора
	public function parse($text)
	{
		$this->text = $text;
		$this->line = 1;
		$this->start();
	}
	
	// метод, определяющий процесс разбора
	abstract protected function start();
	
	// обработка символов экранирования в строке
	protected function unescapeString($str)
	{
		$result = '';
		$len = strlen($str);
		$i = 0;
		while ($i < $len) {
			if ('\\' == $str{$i}) {
				$i++;
				switch ($str{$i}) {
					case 'n': $result .= "\n"; break;
					case 'r': $result .= "\r"; break;
					case 't': $result .= "\t"; break;
					default: $result .= $str{$i};
				}
			} else {
				$result .= $str{$i};
			}
			$i++;
		}
		return $result;
	}
	
	// получение лексемы из входного потока
	// $value - переменная для значения лексемы
	// возвращает тип лексемы
	protected function getToken(&$value=null, $skip_none=true)
	{
		while (true) {
			$token = $this->scanLex($this->text, $value, $scanned);
			$this->text = substr($this->text, strlen($scanned));
			$this->line += substr_count($scanned, "\n");
			if ($skip_none && self::TOK_NONE == $token) {
				continue;
			}
			return $token;
		}
	}
	
	// аналогичен методу getToken, но не сдвигает позицию курсора во 
	// входном потоке, позволяя заглянуть вперед
	protected function lookAhead(&$value=null, $skip_none=true)
	{
		$text = $this->text;
		while (true) {
			$token = $this->scanLex($text, $value, $scanned);
			$text = substr($text, strlen($scanned));
			if ($skip_none && self::TOK_NONE == $token) {
				continue;
			}
			return $token;
		}
	}
	
	// пропускает лексемы, на которые можно не обращать внимания
	protected function skipOptional($token)
	{
		$tok = $this->lookAhead();
		if (is_array($token) && in_array($tok, $token) || !is_array($token) && $tok === $token) {
			$this->getToken();
		}
	}
	
	// механизм идентификации лексемы, основа алгоритма
	protected function scanLex($text, &$value, &$scanned)
	{
		$value = '';
		$scanned = '';
		if (! empty($text)) {
			foreach ($this->tokens as $pattern => $token) {
				$re = "/^($pattern)/i";
				if (preg_match($re, $text, $match)) {
					$scanned = $match[0];
					if (is_array($token)) {
						list($token, $index) = $token;
						$value = isset($match[$index]) ? $match[$index] : '';
					} else {
						$value = $match[0];
					}
					return $token;
				}
			}
		}
		return self::TOK_ENDSTREAM;
	}
	
	// метод читает лексему, и если она не соответствует ожидаемой
	// бросает исключение
	protected function expect($token, &$value=null)
	{
		while (true) {
			$tok = $this->getToken($value);
			if (is_array($token) && in_array($tok, $token) || !is_array($token) && $tok === $token) {
				return $tok;
			}
			$this->unexpected($tok, $token);
		}
	}
	
	// сообщение о "неожиданной" лексеме
	protected function unexpected($given, $expect=null)
	{
		if (null !== $expect) {
			if (is_array($expect)) {
				$expect = implode(' or ', $expect);
			}
			$this->error("unexpected token: $given, expected: $expect");
		} else {
			$this->error("unexpected token: $given");
		}
	}
	
	// сообщение об ошибке
	protected function error($str, $exception=self::ERR_SYNTAX)
	{
		throw new $exception($str, $this->line);
	}
}

// далее - классы исключений
class VErrException extends CException
{
	public function __construct($message, $line=1)
	{
		$this->message = sprintf("Error on line %d : %s", $line, $message);
	}
}

class VSyntaxErrorException extends VErrException
{
	public function __construct($message, $line=1)
	{
		$this->message = sprintf("Syntax error on line %d : %s", $line, $message);
	}
}

Теперь по порядку, что все это значит и как это применять.

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

$this->registerTokens(array(
	'[a-z_][a-z0-9_]*' => self::TOK_IDENTIFIER,
	'[0-9]+[.][0-9]+' => self::TOK_DECIMAL_NUMBER,
	'[0-9]+' => self::TOK_NUMBER,
	'[.]' => self::TOK_DOT,
));

Чтобы распознать лексему, мы поочерёдно будем применять регулярные выражения ко входному потоку, пока не получим совпадения с одним из них. Последним должно идти выражение, подходящее под любую строку и обозначать неопределённую лексему (см. в коде TOK_UNDEFINED).

Далее мы вызываем метод parse, который в свою очередь вызовет метод start, являющийся отправной точкой в разборе. Этот метод абстрактный, его нужно определить в дочернем классе. Суть работы метода сводится к тому, чтобы поочередно считывать лексемы и, в зависимости от их типа, переходить к той или иной ветви алгоритма разбора.

Возьмем для примера язык программирования BASIC. Есть в нем команда PRINT. С помощью нее можно вывести на экран число, строку или значение переменной. Так же можно было задать позицию курсора перед выводом. Описать синтаксис команды можно примерно так:

'PRINT' ['AT' DIGIT ',' DIGIT] (NUMBER | DIGIT | VARIABLE)

Напишем для нее небольшой парсер.

class PrintParser extends VLex
{
	const TOK_IDENTIFIER = 'TOK_IDENTIFIER';
	// ......
	// определение остальных констант я, с вашего позволения, опущу.
	// впрочем, использую я их больше для красоты
	
	public function __construct()
	{
		// регистрируем лексемы
		$this->registerTokens(array(
			// сначала добавляем ключевые слова
			'PRINT\b' => self::TOK_PRINT,
			'AT\b' => self::TOK_AT,
			// потом переменные
			'[a-z_][a-z0-9_]*' => self::TOK_IDENTIFIER,
			// потом числа
			'[0-9]+' => self::TOK_NUMBER,
			// и строки, здесь 2 - это индекс совпадения в регулярке
			'"((\\\\"|[^"])*)"' => array(self::TOK_STRING, 2),
			"'((\\\\'|[^'])*)'" => array(self::TOK_STRING, 2),
		));
		
		parent::__construct();
	}
	
	protected function start()
	{
		// сразу ожидаем ключевое слово PRINT
		// если на входе что-то другое, будет брошено исключение
		$this->expect(self::TOK_PRINT);
		
		// смотрим, что у нас далее
		$tok = $this->getToken($value);
		if (self::TOK_AT == $tok) {
			// если дальше идет ключевое слово AT, то нужно считать 
			// позицию курсора
			$this->expect(self::TOK_NUMBER, $x);
			$this->expect(self::TOK_NUMBER, $y);
			// тут мы типа переводим курсор
			// .......
			
			// снова читаем лексему
			$tok = $this->getToken();
		}
		
		if (self::TOK_IDENTIFIER == $tok) {
			// выводим значение переменной
			print $$value;
		} elseif (self::TOK_NUMBER == $tok) {
			// выводим число
			print $value
		} elseif (self::TOK_STRING == $tok) {
			// выводим строку, обработав символы экранирования
			print $this->unescapeString($value);
		} else {
			// сообщаем об ошибке
			$this->unexpected($tok, array(self::TOK_IDENTIFIER, self::TOK_NUMBER, self::TOK_STRING));
		}
	}
}

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