Цитата(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

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

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

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

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

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

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

Млин теперь вопросов море(конкретно возможности match и её возможные формы), а разбираться с OCaml нет времени/возможности, да и язык своим синтаксисом не приятен. Особено добило правило именования, нафига сокращать имя хеш-таблицы и писать функции/замыкания через '_'... не привычно

Цитата(Sardar @ 10.1.2006, 07:28 )

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

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

Цитата(Sardar @ 10.1.2006, 07:28 )

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

Слово "нет" можно без кавычек Объектов в моем коде действительно нет, не пригодились. Полиморфизм и инкапсуляцию здесь обеспечивают вариантные типы и модули.
Вообще, ООП в 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 )

последнее выражение и есть возвращаемое, если я правильно понял...

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

Цитата(Sardar @ 10.1.2006, 07:28 )

В сборке строк flatten_parts вижу Buffer.create 32, это случайно не ограниченный по размеру буффер?

Нет, это всего лишь начальный размер буфера, он растет по мере необходимости.

Цитата(Sardar @ 10.1.2006, 07:28 )

И Hashtbl.create принимает аргумент число, это что, количество ковшей или максимальная длина ключа?

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

Цитата(Sardar @ 10.1.2006, 07:28 )

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

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

Цитата(Sardar @ 10.1.2006, 07:28 )

Вся сила как я понял в match ... with конструкции, что очень загадочна, т.к. принимает строки, типы

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

Цитата(Sardar @ 10.1.2006, 07:28 )

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

Вот! В этом-то вся фишка Я недаром говорил про 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 вызывает у меня улыбку
CamlP4 в состоянии разбирать LL(1) грамматики, автоматически производить факторизацию правил, устранение леворекурсивности и заботиться о приоритетах и ассоциативности операторов.

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

Цитата(Sardar @ 10.1.2006, 07:28 )

конкретно возможности match и её возможные формы

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

Цитата(Sardar @ 10.1.2006, 07:28 )

Особено добило правило именования, нафига сокращать имя хеш-таблицы и писать функции/замыкания через '_'... не привычно

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

P. S.
Прошу прощения, только сейчас заметил, что код escaped_xml_string скопировал вместе с фатальной ошибкой: незавершенная &...; последовательность приводит к unhandled exception Not_found. Уже поправил.

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

Guest
Послушайте, не стоит здесь разговаривать в таком тоне.

Цитата(Guest @ 14.1.2006, 01:30 )

слабО за 10 минут разобраться с любым новым синтаксисо?

С любым? За 10 минут? Если честно, мне - слабо.
Хотя я считаю, что синтаксис - дело вторичное, и предпочитаю видеть его расширяемым.

[offtop] Ребят, а почему у нас не подсвeчивается OCalm? Если пишется столько кода, надо бы и подсвртку для него сообразить, не правда ли? может кто займётся определением ключ. слов и структур языка?[/offtop]