Objective Caml - Пятница, 17 сентября 2010

Objective Caml

ocaml@conference.jabber.ru

Пятница, 17 сентября 2010< ^ >

Конфигурация комнаты

Участники комнаты

GMT+4
[00:31:09] ermine вышел(а) из комнаты
[00:38:59] komar вошёл(а) в комнату
[00:47:12] zert вышел(а) из комнаты
[02:53:49] komar вышел(а) из комнаты: Replaced by new connection
[02:53:58] komar вошёл(а) в комнату
[04:22:18] Typhon вышел(а) из комнаты
[05:49:06] komar вышел(а) из комнаты: Replaced by new connection
[05:49:17] komar вошёл(а) в комнату
[08:44:22] iNode вошёл(а) в комнату
[09:03:31] gds вошёл(а) в комнату
[10:01:51] Typhon вошёл(а) в комнату
[10:21:59] arhibot вышел(а) из комнаты
[11:12:37] komar вышел(а) из комнаты
[11:14:49] Kakadu вошёл(а) в комнату
[11:25:08] gds вышел(а) из комнаты
[11:26:23] gds вошёл(а) в комнату
[11:36:51] <Kakadu> Я тут поговорил с человеком, который у нас писал диплом про синтаксический разбор на F#. Он говорит, что утверждения о том, что lex тормозит  не лишены смысла. И lex не строит никакие конечные автоматы и если есть списочек ключевых слов keywords, то в автомате языка будет переход из состояния 23 в состояние 44 по этому списку keywords. когда будет проверяться возможность осуществления такого перехода, то автомат честно пройдет бинарным поискои по этому списку и проверит можно ли переходить
[11:37:29] <Kakadu> Вообще надо взять lex скомпилировать его и посмотреть на код который получится на выходе. Только так можно разобраться что происходит.
[11:46:56] <Kakadu> Сейчас меня посетила такая мысль, после прочтения http://plus.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/chap-usage-tips.html
[11:48:21] <Kakadu> если количество ключевых слов ограничено (в данном случае 65535), то наверное каждое ключевое слово представляет вершину конечного автомата. Следовательно никакое преобразование регулярных выражений в конечный автомат, где вершинами являются просто символы не происходит
[11:49:50] <f[x]> все вменяемые лексеры строят автомат переходов
[11:50:42] arhibot вошёл(а) в комнату
[11:51:46] <f[x]> lex/lexgen.ml
[11:52:38] <f[x]> каждый символ - это лукап в массив индексированный символом
[12:03:41] <gds> госспади исусе!  Это же куча таблиц!  Кеш-миссы!  Обращения к памяти!  (а также к уму, чести и совести!)  И вообще, в этом lex не продумана архитектура, сразу видно, писали лохи.
[12:06:21] ermine вошёл(а) в комнату
[12:21:08] ʇsʎɯ вошёл(а) в комнату
[12:21:45] <ʇsʎɯ> gds, не баись, таблицы транспонированы
[12:21:54] <ʇsʎɯ> не так уж много там кэшмисов
[12:22:08] <ʇsʎɯ> зато FSM очень быстрый
[12:25:38] komar вошёл(а) в комнату
[12:29:53] <Kakadu> Ну посмотрев что на lexer.ml я понял что он как-то строит NFA и там ссылается на dragon book
[12:30:40] <Kakadu> Я думаю что производительность стандартного lex не такой уж простой вопрос как В.Сафонов описывает в своей книге
[12:31:03] <Kakadu> сейчас надо бы пойти писать письмо "турецкому султану")
[12:35:52] <Kakadu> у нас в компании нашелся человек, который только на камле и пишет
[12:35:58] <Kakadu> http://oops.tepkom.ru/projects.html его проекты
[12:38:52] <gds> а, Д.Булычёв, знаем такого.  Ключевое слово -- "ostap", по нему решил подтвердить догадку.
[13:06:14] Kakadu про догадку не понял
[13:23:24] <Kakadu> Всё-таки, вот эти парсер комбинаторы из ostap, те ленивые парсер-комбинаторы из какого-то номера fprog. это всё действительно полезно бывает?
[13:23:49] <komar> Очень.
[13:24:07] <komar> Впрочем, в окамле с ними очень хреново.
[13:24:18] <Kakadu> надо бы мне написать чтонить эдакое чтобы осмыслить их значимость
[13:24:22] <Kakadu> а где не хреново?
[13:24:45] <komar> Там, где нас нет.
[13:26:18] <gds> а почему хреново?
[13:26:51] <Kakadu> и где именно нас (меня) нет? :-)
[13:26:59] <komar> В хаскелле.
[13:27:40] <komar> gds: ткни меня мордой в хорошую комбинаторную библиотеку, скажу спасибо.
[13:28:54] <Typhon> Kakadu: если нужно что-то распарсить, и у тебя нет граматики этого чего-то, то удобнее пользовать парсер-комбинаторы, нежели рожать граммаитку, а потом засовывать её в lex/yacc
[13:29:53] <gds> komar: судя по http://oops.tepkom.ru/projects/ostap/browser/trunk/src/combinators.mli , остапа можно брать в дело.
[13:30:11] <komar> Я в последний раз ниасилил его собрать, надо поглядеть.
[13:30:44] <ʇsʎɯ> lex/yacc лучше
[13:30:51] <ʇsʎɯ> do one thing and to it right
[13:31:01] <komar> Лучше, только оно ниасиливает хуиту вроде текстайла.
[13:31:07] <ʇsʎɯ> а костыли эти комбинаторные... вы ещё boost предложите
[13:31:16] <komar> Сам ты костыль.
[13:31:22] <ʇsʎɯ> я не костыль
[13:31:25] <komar> Что это тебе, регэкспы?
[13:31:49] <ʇsʎɯ> причём тут регэкспы?
[13:31:59] <komar> А почему ты комбинаторные парсеры костылями называешь?
[13:32:30] <ʇsʎɯ> потому что это так
[13:32:56] <komar> Вот и поговорили.
[13:34:11] <ʇsʎɯ> ты ещё скажи, что писать RNG на монадах - это не костыли?
[13:34:28] <ʇsʎɯ> я понимаю, что по-другому никак, но всё-таки...
[13:34:45] <komar> RNЧЕ?
[13:35:12] <Kakadu> random number generation?
[13:36:18] <ʇsʎɯ> ну есессна
[13:36:29] <komar> А RNG тут каким боком записался?
[13:36:40] <ʇsʎɯ> к вопросу о костылях
[13:37:35] <komar> Ага, давай я еще про XSLT расскажу.
[13:37:42] <komar> Тоже костыли!
[13:37:42] <ʇsʎɯ> не стоит этого делать
[13:37:46] <ʇsʎɯ> конечно же костыли
[13:37:51] <ʇsʎɯ> как и сам XML
[13:38:41] Kakadu будет сдавать спецкурс про xslt зимой. Надо разобраться как малой кровью проводить преобразования
[13:39:04] komar пишет xmlfuzzer.
[13:40:35] <ʇsʎɯ> пойми меня правильно, я не против xml как универсального языка разметки текста
[13:40:42] <komar> О хоспади.
[13:40:45] <ʇsʎɯ> я против xml как формата представления данных
[13:40:49] <komar> Давай не будем, а?
[13:40:52] <ʇsʎɯ> давай
[13:54:37] <f[x]> казалось бы при чём тут lex..
[14:42:19] Typhon вышел(а) из комнаты
[17:30:57] gds вышел(а) из комнаты
[18:04:35] iNode вышел(а) из комнаты
[18:18:36] <Kakadu> я написал В.Сафонову насчет лексера
[18:18:58] <Kakadu> Я вовсе не говорю, что не нужно строить конечный автомат для лексического
анализа.
Какой бы метод ни применялсядля этого, все равно в итоге получится какой-то
аналог конечного автомата.
Но весь вопрос в том, насколько он будет эффективно работать.
Вы сами пишете, что по регулярным выражениям будет строиться NFA,
т.е. недетерминированный автомат.
Но есть методы оптимизации конечных автоматов, которые позволяют
сделать полученный автомат более эффективным.
Мы в шаних компиляторах делали это вручную.
Но я вполне допускаю, что будут реализованы
(или уже реализованы) инструменты автоматической генерации
лексических анализаторов, в которых эти методы оптимизации автоматов
будут применяться в общем виде.
Я видел выход работы lex, и мне очень не понравился полученный им
лексический анализатор.
Но наверняка есть системы, которые делают это дучше, чем lex.
[18:19:10] <Kakadu> это ответ
[18:22:35] gds вошёл(а) в комнату
[18:29:40] <f[x]> ясно, ок. lex'у-то сто лет в обед, может там всё плохо. для сишников ещё есть flex
[18:32:06] <gds> Kakadu: интересен ответ человека на письмо.  Процитируешь/перескажешь, если будет приемлемо?
[18:32:46] <Kakadu> gds: я не понял ...
[18:32:50] <Kakadu> это и есть ответ
[18:35:06] <gds> тьфуты, йалохе.  Очень похоже было на вопрос.
[18:36:06] <Kakadu> gds: да я тоже хорош. Надо было полностью цитировать
[18:36:15] <Kakadu> gds: )
[19:00:54] ʇsʎɯ вышел(а) из комнаты
[19:06:31] f[x] вышел(а) из комнаты: Logged out
[19:06:37] f[x] вошёл(а) в комнату
[19:08:04] arhibot вышел(а) из комнаты
[19:22:39] Kakadu вышел(а) из комнаты
[19:31:08] f[x] вышел(а) из комнаты
[20:12:38] gds вышел(а) из комнаты
[20:16:16] gds вошёл(а) в комнату
[20:34:08] Kakadu вошёл(а) в комнату
[21:14:46] Typhon вошёл(а) в комнату
[21:26:37] arhibot вошёл(а) в комнату
[21:46:42] komar вышел(а) из комнаты
[22:02:23] Kakadu вышел(а) из комнаты
[23:40:07] iNode вошёл(а) в комнату
[23:53:24] Kakadu вошёл(а) в комнату