Создаём парсер для ini-файлов. Теория

[Silentium]

А еще можно построить автомат для этой грамматики.

[avsmal]

Какой автомат?

[redchrom]

Конечный же.

[avsmal]

Ага, можно. Но надо понимать, что это можно сделать далеко не для всех КС-грамматик =)

[dosbear]

Не конечный, а автомат с магазинной памятью. (конечный автомат он вроде для регулярных грамматик). Далее строить ДСР и обходить его.

[Silentium]

По-моему, тут можно построить и конечный детерминированный.

[dosbear]

Согласен, только состояний в нем будем немало + надо выделить в них заключительные.
А еще для приведенной грамматики можно построить граф переходов.

[avsmal]

Я просто не очень понял, что вы имеете ввиду… Может вы просто хотели сказать, что данная грамматика автоматная?

[avsmal]

«грамматика автоматная» = «задаёт автоматный язык»

[Silentium]

Я имею в виду, что не очень понимаю зачем все это надо.

[avsmal]

Это надо для того, чтобы на основе этой грамматики написать парсер (как и показано в соответствующих статьях).

[EgAr]

Действительно автомат в данном случае будет эффективнее и проще, поскольку рекурсивный нисходящий парсер используется для разбора составных выражений, которые в ini файлах просто не предусмотрены.

Автомат справится с задачей в 1 проход.

[avsmal]

Конечные автоматы по определению «справляются» за один проход =)
Я согласен, что автомат тут справится, но, ИМХО, описание грамматикой намного естественнее и проще. К тому же для таких описаний есть готовые инструменты (будь это yacc или parsec).

[dosbear]

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

[avsmal]

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

[jtootf]

логика непонятна :) если Вы пишете BNF, то логичней было бы сравнивать lex/yacc с alex/happy. зачем описывать BNF для реализации с помощью комбинаторных парсеров?

хотя сама идея серии подобных статей интересна, да

[jtootf]

ага, сорри, не прошёл по ссылке. занятно, да :)

[Bobos]

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

[gaki]

en.wikipedia.org/wiki/Bubble_sort

[kalyaka]

С формой БНФ сталкивался лет пять назад, но вот это:

ident = identChar, {identChar}.
identChar = letter | digit…


насторожило.

Если не ошибаюсь, идентификатор в данном случае может начинаться с любого знака, а не только с буквы?

[avsmal]

Да, я не ограничиваю идентификатор. Я встречал названия секций вроде .default или #config.

[mrShadow]

Можете посоветовать какой-нибудь материал по грамматикам, для ознакомления?

[avsmal]

Есть классическая книжка Введение в теорию автоматов, языков и вычислений (Хопкрофт, Мотвани, Ульман). Дальше, если заинтересуетесь разбором грамматик, почитайте книжку с драконом.

[alexnd]

ням :)
еще бы могли дальше развить эту тему — сериализатор ini-файлов

[avsmal]

Сериализация немного другая тема — там важна поддержка параметров разных типов. Если же ограничиться строчными параметрами, то на C++ это бы выглядело так:

void serialize( std::ostream & os, IniData const & data )
{
  for ( IniData::const_iterator it = data.begin(); it != data.end(); ++it )
  {
   os << '[' << it->first << "]\n";
   for ( Entries::const_iterator p = it->second.begin(); p != it->second.end(); ++p )
    os << p->first << '=' << p->second << '\n';
 }
}


На Haskell (правда тут на стандартный вывод, но можно и на файл переделать)
printIni sl = mapM_ printSection sl
 where
  printSection (n, el) = putStrLn ( "[" ++ n ++ "]" ) >> mapM_ printEntry el
  printEntry (k, v) = putStr k >> putStr "=" >> putStrLn v