[PCRE] Jak przyspieszyć lekser?, Inna alternatywa dla wyrażeń regularnych? Opcje

[WebCM]

Wyodrębnienie jednostek leksykalnych z kodu o zajętości 123 KB trwa ponad 20 sekund. Kod jest następujący:

[PHP] pobierz, plaintext 
const TOKEN_STRING = 1;
const TOKEN_COMMENT = 2;
const TOKEN_OBJECT = 3;
const TOKEN_MAP = 4;
const TOKEN_DESCRIPTION = 6;
const TOKEN_IF = 9;
const TOKEN_ELSE = 10;
const TOKEN_FOR = 11;
const TOKEN_LEFT_PARENTHESIS = 15;
const TOKEN_RIGHT_PARENTHESIS = 16;
const TOKEN_INT = 20;
const TOKEN_FLOAT = 21;
const TOKEN_BOOL = 22;
const TOKEN_COLON = 26;
const TOKEN_SEMICOLON = 27;
const TOKEN_DATA_TYPE = 39;
const TOKEN_NAME = 32;
const TOKEN_COMMA = 33;
const TOKEN_LEFT_BRACE = 34;
const TOKEN_RIGHT_BRACE = 35;
// to 1 połowa typów jednostek, a jest jeszcze druga połowa
 
class Token
{
	public $type;
	public $text;
	public function __construct($token, $sequence)
	{
		$this->type = $token;
		$this->text = $sequence;
	}
}
 
class Parser
{
	private $tokens = []; //tu będą nasze jednostki
	private $objects = []; //obiekty
	private $maps = [];  //mapy
	private $object; //opracowywany obiekt
 
	public function parse($input)
	{
		$lexer = new Lexer;
		$lexer->add('"(?:[^"\\\\]|\\.)*"', TOKEN_STRING);
		$lexer->add('//.*?\n', TOKEN_COMMENT);
		$lexer->add('OBJECT', TOKEN_OBJECT);
		$lexer->add('MAP', TOKEN_MAP);
		$lexer->add('DESCRIPTION', TOKEN_DESCRIPTION);
		$lexer->add('if', TOKEN_IF);
		$lexer->add('else', TOKEN_ELSE);
		$lexer->add('for', TOKEN_FOR);
		$lexer->add('string\b|int\b|float\b|bool\b', TOKEN_DATA_TYPE);
		$lexer->add('[0-9]+\\.[0-9]+', TOKEN_FLOAT);
		$lexer->add('0x[0-9A-F]+', TOKEN_INT);
		$lexer->add('[0-9]+', TOKEN_INT);
		$lexer->add('true|false', TOKEN_BOOL);		
		$lexer->add('[a-zA-Z_$][a-zA-Z0-9_$]*', TOKEN_NAME); //zmienne
		//i cała reszta
 
		$this->tokens = $lexer->tokenize($input);
	}
}
 
class Lexer
{
	private $regexs = [];
	public function add($regex, $token)
	{
		$this->regexs['~'.$regex.'~iA'] = $token; //flaga A to samo co ^ na początku
	}
	public function tokenize($input)
	{
		$tokens = [];
		$bom = pack('H*','EFBBBF');
		$input = preg_replace("/^$bom/", '', trim($input));
		while($input !== '')
		{
			$match = false;
			foreach($this->regexs as $regex=>$token)
			{
				if(preg_match($regex, $input, $matches))
				{					
					$match = true;
					$input = trim(preg_replace($regex, '', $input, 1));
					if($token === TOKEN_COMMENT)
					{
						break;  //rozwiązanie tymczasowe
					}
					elseif($token === TOKEN_STRING)
					{
						$matches[0] = substr($matches[0], 1, -1);
					}
					$tokens[] = new Token($token, $matches[0]);
					break;
				}
			}
			if(!$match)
			{
				throw new \Exception(sprintf('Invalid character %s', $input));
			}
		}
		return $tokens;
	}
}
[PHP] pobierz, plaintext 

Jak widać, skrypt używa wyrażeń regularnych do wyodrębniania jednostek leksykalnych w natępujący sposób:

1. Wczytaj kod.
2. Dopóki kod nie jest pusty:
2.1. Przejedź po wszystkich zdefiniowanych typach jednostek:
2.1.1. Jeśli jednostka jest na początku kodu, wyodrębnij ją i usuń z kodu.
2.1.2. Jeśli nie dopasowano żadnej jednostki, rzuć wyjątek.

Czas zależy od liczby zdefiniowanych typów jednostek i ilości jednostek w analizowanym kodzie.

Większość jednostek można znaleźć za pomocą funkcji str_* ale czy uzyskamy duże przyspieszenie w stosunku do wyrażeń regularnych? Pojawi się wtedy inny problem.

Kod

int INTRO

Zakładając kolejność i nierozróżnianie wielkości znaków:

Kod

TYP : string|int|float|bool
NAZWA : [a-zA-Z_$][a-zA-Z0-9_$]*

Uzyskamy 3 jednostki - int (typ), INT (typ), RO (nazwa)
Na odwrót - int (nazwa), INTRO (nazwa)

Oba wyniki są błędne. Na szczęście PCRE wykrywa krawędzie słów za pomocą \b. Bez PCRE trzeba by badać to ręcznie. A może to błędne podejście do budowy analizatora leksykalnego? Jak go należy prawidłowo napisać?

Czy potrzebujemy aż tyle jednostek? Może wystarczy tylko kilka:
1) ciąg znaków (wszystko w cudzysłowach)
2) stała / zmienna (tekst bez cudzysłowów)
3) liczba
4) operatory - można rozbić na osobne typy jednostek
5) przecinek, nawiasy - jak wyżej

Co do (2) to byłoby już zadanie parsera, aby wykrywał słowa kluczowe.