Parsování pomocí regulárních výrazů

Školení, která pořádám

Pokud potřebujeme nějak zpracovat soubor v daném formátu, tak při jeho parsování potřebujeme prakticky vždy sledovat kontext, ve kterém se nacházíme. Např. v PHP nás /* přenese do komentáře a */ nás z něj zase dostane. Apostrof nás přenese do a z řetězce, ve kterém nás zpětné lomítko přenese do escape sekvence, ze které nás dostane libovolný znak. V řetězci se ale komentáře samozřejmě ignorují. A tímto způsobem lze v definici pravidel pokračovat. Pro přechodové sekvence je praktické používat regulární výrazy, protože nemusí být vždy konstantní. Dosud popsaná pravidla jdou zapsat takto:

<?php
$rules = array(
    'php' => array('com' => '/\\*', 'apo' => "'"),
    'com' => array(1 => '\\*/'),
    'apo' => array('esc' => '\\\\', 1 => "'"),
    'esc' => array(1 => '.'),
);
?>

A teď bychom těmito pravidly potřebovali procházet na základě toho, co nám přichází na vstupu:

<?php
/** Parse string according to given regexp rules
* @param array ('from state' => array('to state' => 'regexp', 1 => 'regexp', ...), ...), number to go out that number of levels
* @param array ('state1', ...) initial states
* @param string data to parse
* @param callable ($before, $operator, $state = null) function to call with each change of state, $state empty at end
* @return array final states
* @copyright Jakub Vrana, https://php.vrana.cz
*/
function parse($rules, $states, $s, $callback = null) {
    // create one regular expression for each state
    $patterns = array();
    foreach ($rules as $state => $val) {
        $find = array();
        foreach ($val as $k => $v) {
            $find[] = "(?P<" . (is_int($k) ? "_$k" : $k) . ">$v)";
        }
        $patterns[$state] = "(" . implode("|", $find) . ")";
    }
    // process input
    $offset = 0;
    while ($states && preg_match($patterns[end($states)], $s, $match, PREG_OFFSET_CAPTURE, $offset)) {
        foreach ($match as $key => $val) {
            if (is_string($key) && $val[1] >= 0) {
                if ($callback) {
                    $callback(substr($s, $offset, $val[1] - $offset), substr($s, $val[1], strlen($val[0])), ltrim($key, "_"));
                }
                $offset = $val[1] + strlen($val[0]);
                if ($key[0] == "_") {
                    $states = array_slice($states, 0, -ltrim($key, "_"));
                } else {
                    $states[] = $key;
                }
                break;
            }
        }
    }
    if ($callback) {
        $callback(substr($s, $offset), "");
    }
    return $states;
}
?>

Funkce pracuje takto:

Na začátku pro každé pravidlo vytvoří jeden regulární výraz, který bude hledat v textu. Pravidla by šla v tomto formátu rovnou předávat, ale jejich definice by nebyla tak pohodlná.
Pak vezme regulární výraz pro aktuální stav a hledá ho v řetězci od pozice, kde se právě nacházíme.
Když něco najde, tak se podívá, co vlastně našla, a skočí do daného stavu. Pokud ze stavu naopak odcházíme, tak ze zásobníku daný počet stavů odebere.
Pokud si to přejeme, tak zavolá obslužnou funkci a pokračuje znovu od bodu 2.
Na konci vrátí stavy, které zbyly na zásobníku.

Algoritmus je velmi jednoduchý, velmi rychlý a má široké možnosti. Můžeme ho použít třeba pro zvýrazňování syntaxe zdrojového kódu (to dělá JUSH), validaci řetězce podle pravidel (stačí porovnat vstupní a výstupní stavy) nebo pro postupné parsování obrovského dokumentu (dalším voláním funkce stačí předat ty stavy, které vrátilo minulé volání).

Závěrem jen doporučím použití stávajících parserů, pokud jsou k dispozici. Např. pro PHP je to token_get_all (pokud parsujeme skripty pro stejnou verzi PHP) nebo rovnou Reflection (pokud můžeme skript načíst). Pro HTML zase existuje DOMDocument::loadHTML. Definice pravidel jazyka totiž není vždy úplně jednoduchá.

Poznámka: Od Davida Majdy vím, že jde spíš o lexer než o parser. A taky vím, že existují generátory, které ta přechodová pravidla samy vygenerují na základě definice tokenů. Někdy ale může vyhovovat tento spíš nízkoúrovňový přístup.

Jakub Vrána, Řešení problému, 12.11.2010, diskuse: 1 (nové: 0)

Diskuse

koubel:

Psát lexikální analyzátor ručně je vhodné pouze pro optimalizaci, pro udržovatelnost a modifikovatelnost je určitě lepší nechat si ho vygenerovat podle definice. Bohužel v tomhle ohledu je dostupnost nástrojů ala flex pro PHP naprosto žalostná.

14.11.2010 13:30:57

Diskuse je zrušena z důvodu spamu.