Цитата(svg @ 6.1.2006, 18:35 )

Есть и нерегулярные лексеры (в ANTLR, например), кодируются как LALR парсеры

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

Кстати, для Python есть интересная библиотека PyParsing, которая позволяет описывать грамматики непосредственно в коде. Какого именно рода, из описания не понятно, но скорее всего LL(1), потому что ничего, кроме recursive-descent parsing при таком подходе применять невозможно, а факторизацей там не пахнет.
(Подобная вещь есть и для C++ - Spirit. Но лично я после CamlP4 на эти попытки без улыбки смотреть не могу )

Цитата(svg @ 6.1.2006, 15:35 )

Google можно попытать на предмет "deterministic finite automata" и "nondeterministic finite automata".

Полученный автомат как направленный граф в скриптовом языке держать и использовать эффективно не получиться, всё равно окажуться реги быстрее

Цитата(svg @ 6.1.2006, 15:35 )

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

Цитата(Void @ 6.1.2006, 16:19 )

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

Это уже полноценные парсеры, не путаем с лексерами - генератор потока символов для синтаксического анализатора.

Цитата(Sardar @ 6.1.2006, 19:25 )

Это уже полноценные парсеры, не путаем с лексерами - генератор потока символов для синтаксического анализатора.

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

По поводу XML (да простит меня setq и все остальные, что я занимаюсь пропагандой в неподобающем разделе ): есть такое 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 в частности, тем больше убеждаюсь, что для задач парсинга пока ничего лучше не придумано

Цитата(Void @ 6.1.2006, 16:36 )

Чем больше я вожусь с 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модератор хорошо бы тему поделить

Цитата(Sardar @ 6.1.2006, 20:16 )

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

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

Цитата(Sardar @ 6.1.2006, 20:16 )

На счёт XML, задача не читать XML как поток элементов, а как поток событий твоей логики.

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

Цитата(Sardar @ 6.1.2006, 20:16 )

Вообщем offtop это всё

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

Цитата(Sardar @ 6.1.2006, 20:16 )

Xорошо бы увидеть пример такого на OCaml.

Попробую.

да. пожалуй пора делить.

вы где предпочетаете продолжить дискуссию: в Питоне или в Разном?

setq
По-моему, к Питону тема имеет минимальное отношение.

Sardar
Можно привести минимальный примерчик XML, который надо распарсить, и что по нему желательно сделать? SAX-парсеров для OCaml достаточно, как оберток над C-библиотеками (expat, libxml), так и нативных, но мне интересно, обязательна ли здесь event-driven модель?

Цитата(Void @ 6.1.2006, 17:28 )

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;     } }

Громоздко, но работает
Кстати почти всё у меня в текущем проекте лежит в XML, удобно очень для человека. В то же время читать это при каждом запросе не очень приятно, потому все прочитанные XML кешируються в нативный для PHP формат (функцией serialize). В результате компромис между удобством и эффективностью

Сам 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;     } }

Цитата(Void @ 6.1.2006, 17:28 )

(Why ML is good for writing compilers? - ППКС)

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

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

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

По словам автора ML (OCaml) это язык для работы со сложными структурами данных(списки, деревья и т.д.), при чём всё это реализованно в языке. Основной способ работы с данными в языке это рекурсивные функции. Вообще звучит очень не плохо, когда нужно реализовать сам компилер, но что будет когда встанут такие задачи как зачитать файл, удобная работа с бинарными файлами(считать смещения и генерить байты самим не есть удобно), работа по сети, вычисление в несколько потоков на нескольких процах (хотя это функциональный язык, тут by design распаралеллить выполнение можно), высокоуровневая работа с памятью (фантомные обьекты, сериализация, свопить по запросу и т.д.), да вообще много задачь встанет на пути построения компилера, помимо самой логики компилера...

Ага, вижу Постараюсь улучить минутку и показать реализацию подобной функциональности.

Цитата(Sardar @ 7.1.2006, 07:09 )

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

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

Цитата(Sardar @ 7.1.2006, 07:09 )

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

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

Цитата(Sardar @ 7.1.2006, 07:09 )

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

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

Цитата(Sardar @ 7.1.2006, 07:09 )

что будет когда встанут такие задачи как зачитать файл, удобная работа с бинарными файлами(считать смещения и генерить байты самим не есть удобно)

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

Цитата(Sardar @ 7.1.2006, 07:09 )

высокоуровневая работа с памятью (фантомные обьекты, сериализация, свопить по запросу и т.д.)

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


Я отнюдь не считаю, что OCaml - идеальный язык. О нет. В нем есть масса вещей, которые мне не нравятся и даже раздражают. Это касается и принципов языка, и особенностей единственной существующей реализации от INRIA. Но конкретно в области парсинга и создания DSL большинство из этих неудобств не проявляются.

Цитата(Void @ 7.1.2006, 15:26 )

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

Может F# понравится еще больше -- посмотри здесь. Разработан Microsoft. Интересно, что для "функционального" языка, а F# -- это от functional, был выбран фирмой именно OCalm, а не что-то из семейства LISP'а или Mirand'ы. Естественно, OCalm не только функциональный (декларативный, как я люблю употреблять), но и императивный и даже ООП-язык!

Cr@$h
Спасибо, F# я смотрел уже давно. Вещь интересная, но до оригинального OCaml кое в чем не дотягивает, увы.
Добавлено @ 19:12

Цитата(Cr@$h @ 7.1.2006, 19:32 )

был выбран фирмой именно OCalm, а не что-то из семейства LISP'а или Mirand'ы.

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

Но OCaml действительно наиболее практичный из ныне существующих декларативных языков, не считая Erlang, занимающего свою особую нишу.

Итак, как и обещал, разбор XML на OCaml.

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

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

Код

(* 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")]);;

Это сообщение отредактировал(а) Void - 10.1.2006, 13:41