[CamlP4] О лексерах, парсерах и CamlP4

 
0
 
Functional languages
ava
Void | 06.01.2006, 17:19
 
Цитата (svg @  6.1.2006,  18:35 findReferencedText)
Есть и нерегулярные лексеры (в ANTLR, например), кодируются как LALR парсеры

Поправочка: ANTLR генерирует LL(k) лексеры.

Кстати, для Python есть интересная библиотека PyParsing, которая позволяет описывать грамматики непосредственно в коде. Какого именно рода, из описания не понятно, но скорее всего LL(1), потому что ничего, кроме recursive-descent parsing при таком подходе применять невозможно, а факторизацей там не пахнет.
(Подобная вещь есть и для C++ - Spirit. Но лично я после CamlP4 на эти попытки без улыбки смотреть не могу smile ) 
Comments (18)
ava
Sardar | 06.01.2006, 17:25 #
 
Цитата (svg @  6.1.2006,  15:35 findReferencedText)
Google можно попытать на предмет "deterministic finite automata" и

"nondeterministic finite automata".


Полученный автомат как направленный граф в скриптовом языке держать и использовать эффективно не получиться, всё равно окажуться реги быстрее smile
Цитата (svg @  6.1.2006,  15:35 findReferencedText)
кодируются как

LALR парсеры, но я такие никогда сам не программировал.

Цитата (Void @  6.1.2006,  16:19 findReferencedText)
Поправочка: ANTLR генерирует LL(k) лексеры.


Это уже полноценные парсеры, не путаем с лексерами - генератор потока символов для синтаксического анализатора. 
ava
Void | 06.01.2006, 17:36 #
 
Цитата (Sardar @  6.1.2006,  19:25 findReferencedText)
Это уже полноценные парсеры, не путаем с лексерами - генератор потока символов для синтаксического анализатора.

Спасибо, я понимаю разницу между лексическим и синтаксическим анализом smile См. http://www.antlr.org/doc/lexer.html

По поводу XML (да простит меня setq и все остальные, что я занимаюсь пропагандой в неподобающем разделе smile ): есть такое CamlP4 расширение для OCaml - OX, с которым можно запросто писать вот такие вещи:
let rec nbtag t = 
  XML match t with
  | CDATA           -> 0
  | <_> _* as c </> -> 1 + (nbtag c)
  | _*              -> Xml.fold_left (fun i e -> i + (nbtag e)) 0 t


Чем больше я вожусь с OCaml и CamlP4 в частности, тем больше убеждаюсь, что для задач парсинга пока ничего лучше не придумано :)

 
ava
Sardar | 06.01.2006, 18:16 #
 
Цитата (Void @  6.1.2006,  16:36 findReferencedText)


Чем больше я вожусь с OCaml и CamlP4 в частности, тем больше убеждаюсь, что для задач парсинга пока ничего лучше не придумано smile


Млин ну почему такой убийственный синтаксис у большинства "редких" языков... :)

На счёт XML, задача не читать XML как поток элементов, а как поток событий твоей логики. Обычно многие вещи сериализуем в XML, только эти вещи не всегда DOM деревья по определению, а обьект с точно известным структурой, его нужно "разбудить" из ранее записанного файла. WDDX не подходят, т.к. файл составляеться человеком, а человеку приятно работать с вещами имеющими смысл в контексте задачи, а не <var><number><string> и т.д.

SAX парсер выполняет роль лексического анализатора, далее чем угодно превращаем поток "open element", "close element", "character data" (остальное игнорируем) в поток событий "делай XXX". Xорошо бы увидеть пример такого на OCaml.
У меня это базовый класс SaxAnalyzer и его потомки, дефинирующие автомат и реализующие методы "делай XXX", PHP.

А вообще жестокий offtop это всё, 2модератор хорошо бы тему поделить smile 
ava
Void | 06.01.2006, 18:28 #
 
Цитата (Sardar @  6.1.2006,  20:16 findReferencedText)
Млин ну почему такой убийственный синтаксис у большинства "редких" языков...

Дело привычки smile У ML-оидов как раз сравнительно привычный синтаксис.
(Why ML is good for writing compilers? - ППКС)

Цитата (Sardar @  6.1.2006,  20:16 findReferencedText)
На счёт XML, задача не читать XML как поток элементов, а как поток событий твоей логики.

Ну так легче наверное написать собственную тонкую обертку над высокоуровневым чтением XML, чем вручную парсить его :)

Цитата (Sardar @  6.1.2006,  20:16 findReferencedText)
Вообщем offtop это всё

Хачу форум, где это не будет оффтопом! smile
added later:
Sardar Мне показалось, или твое сообщение изменилось? Давно хотел обратиться к модераторам с просьбой не пользоваться возможностью редактировать сообщения, не оставляя следов smile

Цитата (Sardar @  6.1.2006,  20:16 findReferencedText)
Xорошо бы увидеть пример такого на OCaml.

Попробую. 
ava
setq | 06.01.2006, 19:01 #
 да. пожалуй пора делить.

вы где предпочетаете продолжить дискуссию: в Питоне или в Разном? 
ava
Void | 06.01.2006, 19:16 #
 setq
По-моему, к Питону тема имеет минимальное отношение. 
ava
Void | 06.01.2006, 23:27 #
 Sardar
Можно привести минимальный примерчик XML, который надо распарсить, и что по нему желательно сделать? SAX-парсеров для OCaml достаточно, как оберток над C-библиотеками (expat, libxml), так и нативных, но мне интересно, обязательна ли здесь event-driven модель? 
ava
Sardar | 07.01.2006, 03:49 #
 
Цитата (Void @  6.1.2006,  17:28 findReferencedText)


Sardar Мне показалось, или твое сообщение изменилось? Давно хотел обратиться к модераторам с просьбой не пользоваться возможностью редактировать сообщения, не оставляя следов 


Привычка у меня набить пост, отправить, а потом в первые минуты корректировать и убирать ошибки... :)

Вот реальный:
<?xml version="1.0" encoding="UTF-8"?>
<resource-map>
    <resource id="static-page">
        <scheme name="simple">
        <!-- http://eurogates.ru/index.php?act=static-page&showpage=name&pagenum=0&pagelang=ru
        -->
            <part>http://eurogates.ru/index.php?act=static-page</part>
            <part param="showpage">&amp;showpage=<value/></part>
            <part param="pagenum" default="0">&amp;pagenum=<value/></part>
            <part param="pagelang" default="{$enviroment.language}">&amp;pagelang=<value/></part>
        </scheme>
        <scheme name="rewrite">
            <!-- http://eurogates.ru/showpage/name/0/ru,
                 http://eurogates.ru/showpage/name/2
                 http://eurogates.ru/showpage/name
            -->
            <part>http://eurogates.ru/showpage</part>
            <part param="showpage">/<value/></part>
            <part param="pagenum" default="0">/<value/></part>
            <part param="pagelang" default="{$enviroment.language}">/<value/></part>
        </scheme>
    </resource>

    <resource id="test">
        <scheme name="simple">
        <!-- http://eurogates.ru/index.php?act=static-page&showpage=name&pagenum=0&pagelang=ru
        -->
            <part>http://eurogates.ru/index.php?act=static-page</part>
            <part param="showpage">&amp;showpage=<value/></part>
            <part param="pagenum" default="0">&amp;pagenum=<value/></part>
            <part param="pagelang" default="{$enviroment.language}">&amp;pagelang=<value/></part>
        </scheme>
        <scheme name="rewrite">
            <!-- http://eurogates.ru/showpage/name/0/ru,
                 http://eurogates.ru/showpage/name/2
                 http://eurogates.ru/showpage/name
            -->
            <part>http://eurogates.ru/showpage</part>
            <part param="showpage">/<value/></part>
            <part param="pagenum" default="0">/<value/></part>
            <part param="pagelang" default="{$enviroment.language}">/<value/></part>
        </scheme>
    </resource>
</resource-map>

А собрать это дело нужно в ассоциативный (id-ключ) список контейнеров resource, каждый из которых содержит ассоциативный (name-ключ) список scheme, каждая схема это массив обьектов part. Идея в том что бы по запросу:

$map->buildURL({имя ресурса}, [{параметры}=>{значение}...]);

Генерить ссылки, simple как обычные URL, под схемой rewrite красивые ЧПУ.

Сразу приведу свой код загрузчика:
require_once('SaxAnalyzer.php');

/**
* Загрузчик XML файла для карты ресурсов.
* XML файл всегда читаеться как UTF-8 под PHP4. На момент чтения все
* строки декодируються в ISO-8859-1, что убьёт все не латинские символы.
* Поэтому русский и другие языки задаём в UTF-8, после закодировав
* каждый байт в URL мнемоники %HH!
*
* Формат файла прост, в порядке иерархии:
* -  resource-map  - это корневой элемент, не содержит аттрибутов
* -  resource - элемент второго уровня, аттрибут id указывает идентификатор ресурса
* -  scheme  - схема URL, аттрибут name задаёт имя схемы
* -  part - элемент задающий часть URL, содержит в себе текст или элемент value.
*           Аттрибут param указывает имя формального праметра, что будет связанно
*           со значением из массива параметров переданных в buildURL.
*           Аттрибут default задаёт дефолтовое значение.
* -  value - полученное или дефолтовое значение будет вставленно в part вместо этого
*            элемента. Не парный тег, не содержит аттрибутов.
*
* Аттрибут default у part элемента может содержать метаинформацию в виде {$имя} строк.
* Эти строки заменяються на значения. Массивы и обьекты разграничиваються точкой:
*  {$enviroment.language} - в массиве enviroment под ключём language
*  {$somearray.0.obj_field} - в массиве somearray под ключём 0 поле obj_field.
*
* Допустимые обьекты это enviroment, config, также можно добавить к списку ещё
* значения используя addContextVariable метод.
* Все значения эвалюируються в момент вызова buildURL и содержат актуальное значение
* запрашиваемых переменных.
*
* @author Sardar Yumatov <[email protected]>
* @copyright Copyright 2005 Sardar Yumatov
* @version 0.1
*/
class ResourceMapFile extends SaxAnalyzer {
    
    /**
    * Временный контейнер для карты
    * @var array
    * @access private
    */
    var $map;
    
    /**
    * Временный контейнер для ресурса
    * @var array
    * @access private
    */
    var $resource;
    
    /**
    * Временный контейнер для схемы
    * @var array
    * @access private
    */
    var $scheme;
    
    /**
    * Временный контейнер для части URL
    * @var object
    * @access private
    */
    var $part;
    
    /**
    * Конструктор файла конфигурации ResourceMap.
    * @access public
    */
    function ResourceMapFile() {
        parent::SaxAnalyzer();
        $this->ignorecase=true;
        
        //транслитератор
        $this->tagmap=array(
            '<>'=>'text', //text
            'resource-map'=>'map',
            '/resource-map'=>'end map',
        
            'resource'=>'resource',
            '/resource'=>'end resource',
        
            'scheme'=>'scheme',
            '/scheme'=>'end scheme',
        
            'part'=>'part',
            '/part'=>'end part',
        
            'value'=>'value',
            '/value'=>'end value',
        );
        
        //логика магазиного автомата
        $this->automat=array(
            //resource-map -> resource
            '*:map'=>array('+','close map', 'wait resource'), //open resource map
            'wait resource:end map'=>array(''), //end of resources, eat up pending resource
            'close map:end map'=>array('$'), //end of file, done
        
            //resource -> scheme
            'wait resource:resource'=>array('+', 'close resource', 'wait first scheme'), //open resource
            'wait first scheme:text'=>array('+', 'wait first scheme'), //ignore spaces
            'wait next scheme:end resource'=>array(''), //end of resource, eat up pending scheme
            'close resource:end resource'=>array('+', 'wait resource'), //end of resource, go back
            'wait resource:text'=>array('+', 'wait resource'), //eat up spaces
        
            //scheme -> part
            'wait next scheme:scheme'=>array('+', 'wait next scheme', 'close scheme', 'wait first part'), //open scheme+
            'wait first scheme:scheme'=>array('+', 'wait next scheme', 'close scheme', 'wait first part'), //open scheme
            'wait first part:text'=>array('+', 'wait first part'), //ignore spaces
            'wait next part:end scheme'=>array(''), //close scheme, pending
            'close scheme:end scheme'=>array('+'), //close scheme, already have 'next scheme' pending
            'wait next scheme:text'=>array('+', 'wait next scheme'), //ignore spaces
        
            //part
            'wait next part:part'=>array('+', 'wait next part', 'close part', 'wait content'), //open part+
            'wait first part:part'=>array('+', 'wait next part', 'close part', 'wait content'), //open part
            'wait content:text'=>array('+', 'wait content'), //colect text
            'wait content:value'=>array('+', 'wait content', 'close value'), //collect value marker
            'close value:end value'=>array('+'), //close empty value, do not allow anything in value!
            'wait content:end part'=>array(''), //end of part, false step
            'close part:end part'=>array('+'), //end of part, just fetch next, we have already 'next part' pending
            'wait next part:text'=>array('+', 'wait next part'), //ignore spaces
        );
        
        $this->actions=array(
            'wait resource:resource'=>'createResource',
//            'close resource:end resource'=>'endCreateResource',
        
            'wait next scheme:scheme'=>'createScheme',
            'wait first scheme:scheme'=>'createScheme',
//            'close scheme:end scheme'=>'endCreateScheme',
        
            'wait next part:part'=>'createPart',
            'wait first part:part'=>'createPart',
            'wait content:text'=>'addText',
            'wait content:value'=>'addValueMarker',
//            'close part:end part'=>'endCreatePart',
        );
        
        $this->map=array();
    }

    /**
    * Вернуть загруженную карту ресурсов как многоуровневый ассоциативный массив.
    * @return array загруженная карта ресурсов
    * @access public
    */    
    function getResources() {
        return $this->map;
    }
    
//========- Sax Analyzer events -===================

    /**
    * Создаём запись ресурса.
    * @access private
    */
    function createResource($attrs) {
        $attrs=array_change_key_case($attrs, CASE_LOWER);
        if(!isset($attrs['id'])) {
            trigger_error('ResourceMapFile.createResource: no id attribute was spcifed for resource element!', E_USER_WARNING);
            $this->error=true;
        } elseif(isset($this->map[$attrs['id']])) trigger_error("ResourceMapFile.createResource: resource with id '{$attrs['id']}' is already defined! Overwriting...", E_USER_NOTICE);
        $this->map[$attrs['id']]=array();
        $this->resource=&$this->map[$attrs['id']];
    }
    
    /**
    * Создаём запись схемы.
    * @access private
    */
    function createScheme($attrs) {
        $attrs=array_change_key_case($attrs, CASE_LOWER);
        if(!isset($attrs['name'])) {
            trigger_error('ResourceMapFile.createScheme: no name attribute was spcifed for scheme element!', E_USER_WARNING);
            $this->error=true;
        } elseif(isset($this->resource[$attrs['name']])) trigger_error("ResourceMapFile.createScheme: scheme with name '{$attrs['name']}' is already defined! Overwriting...", E_USER_NOTICE);
        $this->resource[$attrs['name']]=array();
        $this->scheme=&$this->resource[$attrs['name']];
    }
    
    /**
    * Собираем обьект part
    * @access private
    */
    function createPart($attrs) {
        $attrs=array_change_key_case($attrs, CASE_LOWER);
        $obj=new stdClass();
        $this->part=&$obj; //relink
        if(isset($attrs['param']) && trim($attrs['param'])!='') {
            $this->part->param=trim($attrs['param']);
            if(isset($attrs['default']) && trim($attrs['default'])!='') $this->part->default=trim($attrs['default']);
            $this->part->strings=array();
        } else $this->part->string='';
        $this->scheme[]=&$this->part;
    }
    
    /**
    * Собираем строки
    * @access private
    */
    function addText($text) {
        $text=utf8_decode($text);
        if(isset($this->part->param)) { //fix rare SAX bechavior, it splits text in chunks...
            $sz=sizeof($this->part->strings)-1;
            if($sz>=0 && $this->part->strings[$sz]!==null) $this->part->strings[$sz].=$text;
            else $this->part->strings[]=$text;
        }
        else $this->part->string.=$text;
    }
    
    /**
    * Ставим маркер значения
    * @access private
    */
    function addValueMarker() {
        if(isset($this->part->param)) $this->part->strings[]=null;
    }
}


Громоздко, но работает smile
Кстати почти всё у меня в текущем проекте лежит в XML, удобно очень для человека. В то же время читать это при каждом запросе не очень приятно, потому все прочитанные XML кешируються в нативный для PHP формат (функцией serialize). В результате компромис между удобством и эффективностью smile 
ava
Sardar | 07.01.2006, 04:16 #
 Сам SaxAnalyzer, базовый абстрактный класс.
/**
* Простой анализатор потока элементов от SAX парсера на основе магазинного автомата.
* Класс не создаёт автомат, а использует данные от дочернего класса,
* потому клласс не прост в использовании.
*
* Магазин это массив состояний, где каждое состояние что угодно, способное
* конвертнуться в строку. Поступающие на вход теги пропускаються через карту,
* что бы определить класс элемента (транслитератор), который после
* пойдёт как входной символ к автомату. Все замыкающие теги имеют префикс '/'.
* Строка текста всегда поступает к карте тегов под ключём '<>'.
*
* Автомат представляет собой список пар ключь=>цепочка, где каждый ключь
* это строка из состояния и входного элемента:
*
* <code>$state:$symbol</code>
*
* Таким образом описываем классический автомат (направленный граф).
* Самое первое состояние автомата всегда символ '*'.
*
* Получаемая цепочка по ключу это массив, первый элемент которого метасимвол
* управления входным потоком, а остальные элементы это цепочка состояний, где
* последний элемент ляжет на верхушку магазина. Определены два метасимвола
* управляющих потоком:
*
* # '+' - символ останавливает шаг и ожидает на вход следующего элемента из потока.
* # '$' - символ обьявляющий конец разбора. При получении остаток цепочки игнорируеться,
*         если магазин содержит ещё элементы, то выбрасываеться ошибка типа e_USER_NOTICE,
*         но при этом разбор считаеться успешно завершённым, буффер обнуляеться.
*
* Полученная ранее пара [состояние:входной_символ] используеться как ключь к
* массиву actions, в котором указаны пары ключь=>имя_метода. Если строка под
* заданным ключём существует, то она используеться как имя метода.
* Требуемые методы должны реализовывать дочерние классы. Таким образом логика
* дочернего класса выходит на уровень выше работая со своим потоком событий,
* а не с потоком элементов XML. В зависимости от какого SAX события был шаг,
* метод может получать имя тега, его атррибуты или текст.
*
* <b>SaxAnalyzer это абстрактный класс, от которого должны наследовать дочерние
* классы реализующие автоматы и методы принимающие события.</b>
*
* Из-за кривой реализации SAX парсера в PHP, нет другого способа остановить парсера,
* чем просто подождать пока XML файл закончиться. По этому при любой ошибке
* выставляться внутренний флаг error, который отменяет все действия и заставляет
* все методы слушающие SAX события их игнорировать.
*
* @author Sardar Yumatov <[email protected]>
* @copyright Copyright 2005 Sardar Yumatov
* @version 0.1
* @abstract
*/
class SaxAnalyzer {

    /**
    * Ссылка на используемый сейчас парсер, этим классом не используеться.
    * @var resource
    * @access protected
    */
    var $parser;
    
    /**
    * Флаг ошибки.
    * @var boolean
    * @access protected
    */
    var $error;
    
    /**
    * Карта xml тегов в символы автомата, таким образом можно
    * обьеденять множество тегов под одним символом.
    * @var array
    * @access protected
    */
    var $tagmap;
    
    /**
    * Автомат как список пар состояние_шага => цепочка.
    * @var array
    * @access protected
    */
    var $automat;
    
    /**
    * Требуемые события как список пар состояние_шага => имя_метода.
    * @var array
    * @access protected
    */
    var $actions;
    
    /**
    * Магазин.
    * @var array
    * @access protected
    */
    var $buffer;
    
    /**
    * Флаг игнорирования регистра, если установлен, то все поступающие
    * теги приводяться к нижнему регистру. Это  важно для карты тегов.
    * По умолчанию true.
    * Флаг устанавливаеться дочерним классом.
    * @var boolean
    * @access protected
    */
    var $ignorecase;
    
    /**
    * Конструктор класса.
    * Создаёт и иницализирует SAX парсер.
    * @access protected
    */
    function SaxAnalyzer() {
        $parser = xml_parser_create('UTF-8');
        xml_parser_set_option($parser, XML_OPTION_CASE_FOLDING, false);
        xml_set_object ($parser, $this);
        xml_set_element_handler($parser, "startElement", "endElement");
        xml_set_character_data_handler($parser, "characterData");
        $this->parser=$parser;
        $this->error=false;
        $this->buffer=array('*');
        $this->ignorecase=true;
    }
    
    /**
    * Разобрать XML данные из строки.
    * Функция предпологает что переданная строка содержит весь XML файл целиком.
    * @param string $data XML данные в строке
    * @param boolean true если разбор прошёл успешно, иначе false
    * @access public
    */
    function parseData($data) {
        $this->error=false;
        $this->buffer=array('*');
      if(!xml_parse($this->parser, trim($data), true)) {
       trigger_error(sprintf('SaxAnalyzer.parseData: XML error: %s at line %d',
                  xml_error_string(xml_get_error_code($this->parser)),
                  xml_get_current_line_number($this->parser)), E_USER_WARNING);
            $this->error=true;
     }
        xml_parser_free($this->parser);
        return !$this->error;
    }
    
    /**
    * Разбор файла.
    * Функция считывает файл частями по 4кб, таким образом можно эффективно
    * обрабатывать файлы большого размера без надобности загружать его в память.
    * @param string $file имя считываемого XML файла
    * @param boolean true если разбор прошёл успешно, иначе false
    * @access public
    */
    function parseFile($file) {
        if(!file_exists($file) || !is_resource($fp=fopen($file, 'rb'))) {
            trigger_error("SaxAnalyzer.parseFile: Can't read file '{$file}'", E_USER_WARNING);
            return !($this->error=true);
        }
        
        $this->error=false;
        $this->buffer=array('*');
        while($data = fread($fp, 4096)) {
         if(!xml_parse($this->parser, trim($data), feof($fp))) {
          trigger_error(sprintf('SaxAnalyzer.parseData: XML error: %s at line %d',
                 xml_error_string(xml_get_error_code($this->parser)),
                   xml_get_current_line_number($this->parser)), E_USER_WARNING
                 );
             $this->error=true;
             break;
         }
     }
        xml_parser_free($this->parser);
        return !$this->error;
    }
    
    /**
    * Метод возвращает состояние анализатора после разбора данных.
    * Флаг ошибочного состояния сбрасываеться при чтении нового XML.
    * @return boolean true если последнее чтение было с ошибками, иначе false
    */
    function isError() {
        return $this->error;
    }
    
    /**
    * Транслитератор.
    * Мепит приходящие теги во внутренние символы. Метод может быть
    * переопределён потомками если должен считываеться поток не указанных
    * в карте элементов.
    * @return string отображение тега во внутренний символ или null если тег не принят
    */
    function mapTag($name) {
        return isset($this->tagmap[$name])? $this->tagmap[$name]: null;
    }
    
//============- Sax event handlers -================

    /**
    * Обработчик открывающихся тегов.
    * @access private
    */
    function startElement($parser, $name, $attrs) {
        if($this->error) return;
        if($this->ignorecase) $name=strtolower($name);
        if(($sym=$this->mapTag($name))==null) {
            trigger_error("SaxAnalyzer.startElement: Unknown open tag '{$name}'", E_USER_WARNING);
            $this->error=true;
            return;
        }
     if(!$ret=$this->nextStep($sym)) return; //error
     if(isset($this->actions[$ret])) {
       $mname=$this->actions[$ret];
       $this->$mname($attrs, $name);
     }
    }

    /**
    * Обработчик закрывающихся тегов
    * @access private
    */
    function endElement($parser, $name) {
        if($this->error) return;
        if($this->ignorecase) $name=strtolower($name);
        if(($sym=$this->mapTag('/'.$name))==null) {
            trigger_error("SaxAnalyzer.endElement: Unknown close tag '{$name}'", E_USER_WARNING);
            $this->error=true;
            return;
        }
     if(!$ret=$this->nextStep($sym)) return; //error
     if(isset($this->actions[$ret])) {
       $mname=$this->actions[$ret];
       $this->$mname($name);
     }
    }

    /**
    * Обработчик текстовых данных.
    * @access private
    */
    function characterData($parser, $data) {
        if($this->error) return;
     if(($sym=$this->mapTag('<>'))==null || !($ret=$this->nextStep($sym))) return; //error
     if(isset($this->actions[$ret])) {
       $mname=$this->actions[$ret];
       $this->$mname($data);
     }
    }
    
    /**
    * Вычисление следующего шага автомата.
    * @param $sym следующий символ от транслитератора
    * @return string состояние шага
    * @access protected
    */
    function nextStep($sym) {
        if($sym==''||sizeof($this->buffer)==0) {
            trigger_error(
                $sym==''? 'SaxAnalyzer.nextStep: empty step symbol is not allowed!':
                          'SaxAnalyzer.nextStep: buffer is empty, no input allowed!'            
                , E_USER_WARNING);
            $this->error=true;
            return false;
        }
//        echo 'Symbol: '.$sym."\n";
//        print_r($this->buffer);
        
        while(sizeof($this->buffer)>0) { //just ensure we never go to endless loop because of bad automate
            $state=array_pop($this->buffer).':'.$sym;
            if(!isset($this->automat[$state])) {
                trigger_error("SaxAnalyzer.nextStep: uknown state '{$state}'", E_USER_WARNING);
                $this->error=true;
                return false;
            }
            
            $ret=$this->automat[$state];
            for($i=1; $i<sizeof($ret); $i++) array_push($this->buffer, $ret[$i]);
            switch($ret[0]) { //meta commands
                case '+': return $state; //next symbol from input
                case '$':  //end of input
                    if(sizeof($this->buffer)>0) trigger_error("SaxAnalyzer.nextStep: got end of input char, but buffer is not empty! Review your automate, state '{$state}'", E_USER_NOTICE);
                    $this->buffer=array(); //empty buffer
                    return $state;
            }
        }
        //something goes wrong...
        trigger_error("SaxAnalyzer.nextStep: buffer is empty, auto-loop is broken, review your automate! Previous state: '{$state}'", E_USER_WARNING);
        $this->error=true;
        return false;
    }
}
 
ava
Sardar | 07.01.2006, 05:09 #
 
Цитата (Void @  6.1.2006,  17:28 findReferencedText)
(Why ML is good for writing compilers? - ППКС)

Не понял что есть "type inference", это вроде обьявление переменной, не указывая типа, а её тип точно определяеться по операторам что ты используешь, операторы для разных типов разные (для целых одни, для вещественных другие, строки третьи и т.д.) ? По моему это большая лажа...

Также я понял списки могут хранить значения только одного типа...  Мне после скриптового мира сложно понять как с таким ограничением жить...

На счёт библиотек это явное ИМXО автора, считаю либы в Java хорошим примером как нужно вообще либы делать, сюда же припишем модульность.

По словам автора ML (OCaml) это язык для работы со сложными структурами данных(списки, деревья и т.д.), при чём всё это реализованно в языке. Основной способ работы с данными в языке это рекурсивные функции. Вообще звучит очень не плохо, когда нужно реализовать сам компилер, но что будет когда встанут такие задачи как зачитать файл, удобная работа с бинарными файлами(считать смещения и генерить байты самим не есть удобно), работа по сети, вычисление в несколько потоков на нескольких процах (хотя это функциональный язык, тут by design распаралеллить выполнение можно), высокоуровневая работа с памятью (фантомные обьекты, сериализация, свопить по запросу и т.д.), да вообще много задачь встанет на пути построения компилера, помимо самой логики компилера... ;-) 
ava
Void | 07.01.2006, 14:26 #
 Ага, вижу smile Постараюсь улучить минутку и показать реализацию подобной функциональности.

Цитата (Sardar @  7.1.2006,  07:09 findReferencedText)
Не понял что есть "type inference", это вроде обьявление переменной, не указывая типа, а её тип точно определяеться по операторам что ты используешь, операторы для разных типов разные (для целых одни, для вещественных другие, строки третьи и т.д.) ? По моему это большая лажа...

Ну-ну... Хиндли и Милнер отнюдь не дураками были. Разные операторы - это действительно иногда неудобно, но и эта проблема вполне решается - см. type classes в Haskell. После некоторого привыкания наоборот раздражает необходимость везде писать явные определения типов.

Цитата (Sardar @  7.1.2006,  07:09 findReferencedText)
Также я понял списки могут хранить значения только одного типа... Мне после скриптового мира сложно понять как с таким ограничением жить...

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

Цитата (Sardar @  7.1.2006,  07:09 findReferencedText)
На счёт библиотек это явное ИМXО автора, считаю либы в Java хорошим примером как нужно вообще либы делать, сюда же припишем модульность.

Библиотеки имелись в виду именно работающие со структурами данных. В принципе, да, ничего действительно выдающегося в них нет - но эти библиотеки по крайней мере не хуже существующих сегодня аналогов в других языках.
По поводу модульности: это писалось в 1998 году, никакими дженериками тогда и не пахло, и экспортировать из модуля полиморфные функции не мог ни один ИЯ (Ада, maybe?). А аналогов функторам по-прежнему нет.

Цитата (Sardar @  7.1.2006,  07:09 findReferencedText)
что будет когда встанут такие задачи как зачитать файл, удобная работа с бинарными файлами(считать смещения и генерить байты самим не есть удобно)

А в чем проблема? Средстав для работы с бинарным файлами есть в любых языках.

Цитата (Sardar @  7.1.2006,  07:09 findReferencedText)
высокоуровневая работа с памятью (фантомные обьекты, сериализация, свопить по запросу и т.д.)

Стандартная сериализация произвольных данных в OCaml есть. Явное управление памятью затруднено (GC как никак), так что если стоит задача жесткой экономии памяти при компиляции, то будут затруднения. Но предполагается, что на этапе программирования основной логики мы выиграли столько времени по сравнению с традиционными языками, что есть возможность и потюнить :)


Я отнюдь не считаю, что OCaml - идеальный язык. О нет. В нем есть масса вещей, которые мне не нравятся и даже раздражают. Это касается и принципов языка, и особенностей единственной существующей реализации от INRIA. Но конкретно в области парсинга и создания DSL большинство из этих неудобств не проявляются. 
ava
[email protected]&#036;h | 07.01.2006, 17:32 #
 
Цитата (Void @  7.1.2006,  15:26 findReferencedText)


Это касается и принципов языка, и особенностей единственной существующей реализации от INRIA.


Может F# понравится еще больше -- посмотри здесь. Разработан Microsoft. Интересно, что для "функционального" языка, а F# -- это от functional, был выбран фирмой именно OCalm, а не что-то из семейства LISP'а или Mirand'ы. Естественно, OCalm не только функциональный (декларативный, как я люблю употреблять), но и императивный и даже ООП-язык! 
ava
Void | 07.01.2006, 19:12 #
 [email protected]$h
Спасибо, F# я смотрел уже давно. Вещь интересная, но до оригинального OCaml кое в чем не дотягивает, увы.
added later:
Цитата ([email protected]$h @  7.1.2006,  19:32 findReferencedText)
был выбран фирмой именно OCalm, а не что-то из семейства LISP'а или Mirand'ы.

Зато автор GHC - лучшего компилятора Haskell - работает в Microsoft :)

Но OCaml действительно наиболее практичный из ныне существующих декларативных языков, не считая Erlang, занимающего свою особую нишу. 
ava
Void | 08.01.2006, 13:48 #
 Итак, как и обещал, разбор XML на OCaml.

Сразу скажу, что если бы это было реальное приложение, я бы взял более надежный и проверенный временем парсер XML для OCaml - PXP, например. А так это получается proof of concept декларативного разбора XML.
Я не реализовал разворот переменных окружения в default и перекодировку не-ASCII символов. В остальном все вроде работает одинаково. Документации тоже нет, но названия функций и исключений вроде говорят сами за себя.

Модуль Util. То, что его пришлось написать, целиком на совести автора OX smile (Надо будет связаться с ним - странно, что он забросил столь интересную библиотеку).
Интерфейс:
(* util.mli *)

exception Unterminated_entity

val string_of_cdata : Xml.xml -> string

Реализация:
(* util.ml *)
let idents = Hashtbl.create 7

let _ = List.iter (function k, v -> Hashtbl.add idents k v)
    [("gt", ">"); ("lt", "<"); ("amp", "&"); ("apos", "'"); ("quot", "\"")]

exception Unterminated_entity

let escaped_xml_string s =
    let buf = Buffer.create (String.length s)
    and len = String.length s in
    let rec loop pos =
        if pos < len then
        begin
            match s.[pos] with
              '&' ->
                let newpos =
                    try
                        String.index_from s pos ';'
                    with Not_found ->
                        raise Unterminated_entity in
                let entity = String.sub s (pos + 1) (newpos - pos - 1) in
                Buffer.add_string buf (
                    try
                        Hashtbl.find idents (String.lowercase entity)
                    with Not_found ->
                        "&" ^ entity);
                loop (newpos + 1)
            | c ->
                Buffer.add_char buf c;
                loop (pos + 1)
        end
    in
    loop 0;
    Buffer.contents buf

let string_of_cdata = function
    [| Xml.CDATA s |] -> escaped_xml_string s


Собственно основной модуль Urlbuilder.
Интерфейс:
(* urlbuilder.mli *)

type t

exception Invalid_resource of string
exception Invalid_scheme of string
exception Missing_parameter of string
exception Xml_Parse_error

val build_url : t -> scheme:string -> resource:string ->
    params:(string * string) list -> string

val of_xml : Xml.xml -> t

Реализация:
(* urlbuilder.ml *)
open Util

type t = (string, resource) Hashtbl.t
and resource = (string, scheme) Hashtbl.t
and scheme = part list
and part = ConstPart of string | VarPart of param
and param = {
    name : string;
    default : string option }

exception Invalid_resource of string
exception Invalid_scheme of string
exception Missing_parameter of string
exception Xml_Parse_error

let build_url urlmap ~scheme:scheme ~resource:resource ~params:params =
    let flatten_parts parts =
        let buf = Buffer.create 32 in
        List.iter (function
                  ConstPart s -> Buffer.add_string buf s
                | VarPart { name = name; default = default } ->
                    let value =
                        try
                            List.assoc name params
                        with Not_found ->
                            match default with
                              Some value -> value
                            | None -> raise (Missing_parameter name) in
                    Buffer.add_string buf value)
                parts;
        Buffer.contents buf
    in
    try
        let scheme_map = Hashtbl.find urlmap resource in
        begin
            try
                let scheme = Hashtbl.find scheme_map scheme
                in flatten_parts scheme
            with Not_found ->
                raise (Invalid_scheme scheme)
        end
    with Not_found ->
        raise (Invalid_resource resource)

let of_xml xml =
    let urlmap = Hashtbl.create 17 in
    let parse_part xml =
        let parse_content param xml =
            XML match xml with
            | CDATA as s -> ConstPart(string_of_cdata s)
            | <value> </> -> VarPart param
        in
        XML match xml with
        | <part param=param default=default> _* as content </> ->
            Xml.map (parse_content { name = string_of_cdata param;
                default = Some(string_of_cdata default)}) content
        | <part param=param> _* as content </> ->
            Xml.map (parse_content { name = string_of_cdata param;
                default = None }) content
        | <part> CDATA as content </> ->
            [ConstPart(string_of_cdata content)]
    in
    let parse_scheme xml =
        XML match xml with
        | <scheme name=name> _+ as parts </> ->
            (string_of_cdata name), List.flatten (Xml.map parse_part parts)
    in
    let parse_resource xml =
        let scheme_map = Hashtbl.create 5 in
        XML match xml with
        | <resource id=id> _+ as schemes </> ->
            Xml.iter (fun entry ->
                    let name, scheme = parse_scheme entry in
                    Hashtbl.add scheme_map name scheme)
                schemes;
                (string_of_cdata id), scheme_map
    in
    try
        XML match xml with
        | <resource-map> _* as resources </> ->
            Xml.iter (fun entry ->
                    let name, resource = parse_resource entry in
                    Hashtbl.add urlmap name resource)
                resources;
                urlmap
    with Xml.NFFXmlStream | Xml.MatchingFailure | Xml.ParseException _
        | Util.Unterminated_entity ->
        raise Xml_Parse_error


Пример использования:
let xml = Xml.of_in_channel (open_in Sys.argv.(1)) in
let urlmap = Urlbuilder.of_xml xml in
print_string (Urlbuilder.build_url urlmap ~scheme:"simple"
    ~resource:"static-page"
    ~params:[("showpage", "main"); ("pagelang", "ru")]);;
 
ava
Sardar | 10.01.2006, 05:28 #
 Ого... у меня обычно получаеться читать код на не знакомом языке сразу и без проблем, но такой код... млин убил целый вечер, потому сначала о языке :)

Возможно буду говорить глупости, прошу прощения, впервые вижу OCaml и вообще с подобными мозгодробильными вещами не знаком :)

OCaml ставят как функциональный язык ООП "фичами". Как то не проходит "workaround" чувство, как будто OOП притянуто за уши. По коду вижу обьектов "нет", есть классы/модули с функциями принимающими обьекты своих типов, так и C можно назвать ООП языком...

Синтаксис убойный, особено добило отсутсвие явной return операции, надо постоянно думать что последнее выражение и есть возвращаемое, если я правильно понял...
В сборке строк flatten_parts вижу Buffer.create 32, это случайно не ограниченный по размеру буффер? Тогда PHP рулит smile
И Hashtbl.create принимает аргумент число, это что, количество ковшей или максимальная длина ключа? Здесь PHP рулит, он лимитов вроде не имеет :)

Вся прога это туева хуча closures, что правильно, это же функциональный язык. А в практическом плане, проц не любит прыжки по коду, как эффективно тогда исполняеться код?

Вся сила как я понял в match ... with конструкции, что очень загадочна, т.к. принимает строки, типы и даже... собсно
<scheme name=name> _+ as parts </>
что это? Не строка, видел что строки (по крайней мере один символ) в кавычках должны быть. Также не хороший это парсер если парой пробелов больше между <scheme и name и он не сможет найти. match принимает слева XML, видать какая то либа, что логику поиска и реализует, а match "перевызовет" эти функции из XML. А что тогда возвращаеться и вообще что это в языке <...>, какая то особая структура?

Млин теперь вопросов море(конкретно возможности match и её возможные формы), а разбираться с OCaml нет времени/возможности, да и язык своим синтаксисом не приятен. Особено добило правило именования, нафига сокращать имя хеш-таблицы и писать функции/замыкания через '_'... не привычно smile 
ava
Void | 10.01.2006, 12:23 #
 
Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
OCaml ставят как функциональный язык ООП "фичами". Как то не проходит "workaround" чувство, как будто OOП притянуто за уши.

Не то чтобы за уши... Говорят, ООП в OCaml появилось, чтобы Didier Remy защитил диссертацию smile В каждой шутке есть доля... шутки. Сейчас многие OCaml библиотеки, прежде всего, обертки для GUI, используют его. Тот же PXP (Polymorphic XML Parser) полностью объектный.

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
По коду вижу обьектов "нет", есть классы/модули с функциями принимающими обьекты своих типов, так и C можно назвать ООП языком...

Слово "нет" можно без кавычек smile Объектов в моем коде действительно нет, не пригодились. Полиморфизм и инкапсуляцию здесь обеспечивают вариантные типы и модули.
Вообще, ООП в OCaml достаточно интересное... Отношение наследования (is-a) нет, есть отношение subtyping'а (like-a); все методы всегда виртуальны. Т.е. получается такая статическая утиная типизация.

Впрочем, без лишних разговоров пример ООП на OCaml (прим.: private здесь эквивалентно protected в C++/Java):
class virtual expression = object
    method virtual eval : unit -> float
end

class constant value = object
    inherit expression
    method eval () = value
end

class virtual binary_node lhs rhs = object(this)
    method private virtual do_op : float -> float -> float
    method eval () = this#do_op (lhs#eval ()) (rhs#eval ())
end

class plus lhs rhs = object
    inherit binary_node lhs rhs
    method private do_op = (+.)
end


let _ =
    let x = new plus (new constant 3.) (new constant 2.) in
    print_float (x#eval ())


Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
последнее выражение и есть возвращаемое, если я правильно понял...

Да, для любого оператора это так.

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
В сборке строк flatten_parts вижу Buffer.create 32, это случайно не ограниченный по размеру буффер?

Нет, это всего лишь начальный размер буфера, он растет по мере необходимости.
Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
И Hashtbl.create принимает аргумент число, это что, количество ковшей или максимальная длина ключа?

Это тоже начальное число ковшей, хинт для создания хэш-таблицы.

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
Вся прога это туева хуча closures, что правильно, это же функциональный язык. А в практическом плане, проц не любит прыжки по коду, как эффективно тогда исполняеться код?

Слышу ли я это от любителя скриптовых языков? ;-) Нативный кодогенератор OCaml сравним с компилятором Си средней руки, и иногда обгоняет GCC - несмотря на GC и кучу рантайм проверок. Мелкие closures он вполне может заинлайнить. (Хотя, надо признаться, избытком разума оптимизатор не страдает. Статический анализ явно проигрывает GHC, и если бы не ленивая по умолчанию семантика Haskell...)

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
Вся сила как я понял в match ... with конструкции, что очень загадочна, т.к. принимает строки, типы

Нет, при всей своей мощи pattern matching с типами, к сожалению, не работает smile Или ты имеешь в виду конструкторы вариантных типов (вроде type 'a option = None | Some of 'a)?

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
и даже... собсно

<scheme name=name> _+ as parts </>

что это? Не строка, видел что строки (по крайней мере один символ) в кавычках должны быть. Также не хороший это парсер если парой пробелов больше между <scheme и name и он не сможет найти. match принимает слева XML, видать какая то либа, что логику поиска и реализует, а match "перевызовет" эти функции из XML. А что тогда возвращаеться и вообще что это в языке <...>, какая то особая структура?

Вот! В этом-то вся фишка smile Я недаром говорил про CamlP4. Это архинавороченный препроцессор, фактически программируемый фронтэнд компилятора OCaml. Мы можем писать свои модули, которые с его помощью будут вклиниваться в процесс генерации AST. С помощью CamlP4 можно изменять синтаксис OCaml абсолютно произвольным образом, не затрачивая на это особых усилий - писать CamlP4 расширения в общем-то несложно. Что примечательно, механизм обработки ошибок будет работать по-прежнему, и сообщения об ошибках будут указывать точную позицию в коде до препроцессинга. Т.е. никакого геморроя, с которым обычно ассоциируются препроцессоры, нет в помине.
Но CamlP4 с таким же успехом можно использовать и для создания собственных пасеров, не привязанных к бэкэнду OCaml. Грамматика CamlP4 - это в конечном счете всего лишь функция, преобразующая поток лексем в значение любого типа. Чтобы работать, как синтаксическое расширение, она должна возвращать описанный в специальном модуле тип AST OCaml, но это совсем не обязательно. Впрочем, опять-таки лучше привести пару строк кода; итак, мини-калькулятор на CamlP4:
let grammar = Grammar.gcreate (Plexer.gmake ())
let expr_eoi = Grammar.Entry.create grammar "expr_eoi"

EXTEND
    GLOBAL: expr_eoi;
    expr_eoi:
    [ [ e = expr; EOI -> e ] ];
    expr:
    [ [ x = expr; "+"; y = expr -> x +. y
      | x = expr; "-"; y = expr -> x -. y ]
    | [ x = expr; "*"; y = expr -> x *. y
      | x = expr; "/"; y = expr -> x /. y ]
    | [ x = INT -> float_of_string x
      | x = FLOAT -> float_of_string x
      | "("; e = expr; ")" -> e ] ];
END

let eval s = Grammar.Entry.parse expr_eoi (Stream.of_string s)

let _ =
    while true do
        try
            Printf.printf "%g\n" (eval (read_line ()))
        with
              Stdpp.Exc_located _ -> print_endline "Syntax error"
            | End_of_file -> exit 0
    done

Теперь, думаю, понятно, почему Spirit вызывает у меня улыбку smile
CamlP4 в состоянии разбирать LL(1) грамматики, автоматически производить факторизацию правил, устранение леворекурсивности и заботиться о приоритетах и ассоциативности операторов.

Собственно, вернемся к XML smile OX состоит из двух частей: библиотеки, собственно обеспечивающей разбор XML, и расширения CamlP4, добавляющего синтаксические конструкции XML match и XML { ... }. (Да, XML в коде можно не только разбирать, но и создавать. Получается эдакий встроенный в язык XSLT.) И это расширение, правильно, транслирует XML pattern-matching в вызовы функций первой части. Кстати, внутри, насколько я понял из исходников, строится именно конечный автомат. Исходников там в общей сложности всего на 40 с лишним Кб. Сделать бы этот парсер валидирующим, да поток XML-токенов ленивым, чтобы уменьшить потребление памяти (если это возможно конечно, надо еще разбираться) - вообще вещь получится smile
Да, забыл сказать, лишние пробелы, естественно, не помеха, парсер отнюдь не берет конструкции из кода буквально.

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
конкретно возможности match и её возможные формы

В базовой форме (без расширений) match декомпозирует любые значения, кроме функций (ну это понятно) и объектов (наверное, чтобы не нарушать инкапсуляцию?).

Цитата (Sardar @  10.1.2006,  07:28 findReferencedText)
Особено добило правило именования, нафига сокращать имя хеш-таблицы и писать функции/замыкания через '_'... не привычно

Вот тут немного не понял smile Единственное (но обязательное) правило именования - это имена функций и типов с маленькой буквы, а конструкторов и модулей - с большой.

P. S.
Прошу прощения, только сейчас заметил, что код escaped_xml_string скопировал вместе с фатальной ошибкой: незавершенная &...; последовательность приводит к unhandled exception Not_found. Уже поправил. 
ava
Void | 14.01.2006, 00:40 #
 Guest
Послушайте, не стоит здесь разговаривать в таком тоне.
Цитата (Guest @  14.1.2006,  01:30 findReferencedText)
слабО за 10 минут разобраться с любым новым синтаксисо?

С любым? За 10 минут? Если честно, мне - слабо.
Хотя я считаю, что синтаксис - дело вторичное, и предпочитаю видеть его расширяемым. 
ava
sergejzr | 19.01.2006, 03:33 #
 [offtop] Ребят, а почему у нас не подсвeчивается OCalm? Если пишется столько кода, надо бы и подсвртку для него сообразить, не правда ли? smile может кто займётся определением ключ. слов и структур языка?[/offtop] 
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
advanced
Submit