avsmal Feb 3 2009 at 20:23

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

3 min

28K

Website development *

+29

Comments 25

Silentium Feb 4 2009 at 00:47

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

avsmal Feb 4 2009 at 00:57

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

redchrom Feb 4 2009 at 01:03

Конечный же.

avsmal Feb 4 2009 at 01:06

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

dosbear Feb 4 2009 at 02:58

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

Silentium Feb 4 2009 at 09:31

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

dosbear Feb 4 2009 at 10:52

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

avsmal Feb 4 2009 at 01:04

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

avsmal Feb 4 2009 at 01:05

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

Silentium Feb 4 2009 at 09:36

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

avsmal Feb 4 2009 at 12:51

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

EgAr Feb 4 2009 at 02:44

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

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

avsmal Feb 4 2009 at 02:54

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

-1

dosbear Feb 4 2009 at 03:08

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

avsmal Feb 4 2009 at 03:39

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

jtootf Feb 4 2009 at 01:37

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

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

jtootf Feb 4 2009 at 01:40

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

Bobos Feb 4 2009 at 03:45

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

-7

gaki Feb 4 2009 at 04:46

en.wikipedia.org/wiki/Bubble_sort

-3

kalyaka Feb 4 2009 at 13:13

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

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

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

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

avsmal Feb 4 2009 at 17:44

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

mrShadow Feb 4 2009 at 14:23

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

avsmal Feb 4 2009 at 14:37

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

alexnd Feb 4 2009 at 15:39

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

avsmal Feb 4 2009 at 17:54

Сериализация немного другая тема — там важна поддержка параметров разных типов. Если же ограничиться строчными параметрами, то на 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

Only those users with full accounts are able to leave comments. Log in, please.