avsmal 3 фев 2009 в 20:23

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

3 мин

29K

Веб-разработка*

+29

Комментарии 25

Silentium 4 фев 2009 в 00:47

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

avsmal 4 фев 2009 в 00:57

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

redchrom 4 фев 2009 в 01:03

Конечный же.

avsmal 4 фев 2009 в 01:06

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

dosbear 4 фев 2009 в 02:58

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

Silentium 4 фев 2009 в 09:31

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

dosbear 4 фев 2009 в 10:52

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

avsmal 4 фев 2009 в 01:04

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

avsmal 4 фев 2009 в 01:05

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

Silentium 4 фев 2009 в 09:36

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

avsmal 4 фев 2009 в 12:51

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

EgAr 4 фев 2009 в 02:44

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

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

avsmal 4 фев 2009 в 02:54

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

-1

dosbear 4 фев 2009 в 03:08

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

avsmal 4 фев 2009 в 03:39

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

jtootf 4 фев 2009 в 01:37

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

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

jtootf 4 фев 2009 в 01:40

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

Bobos 4 фев 2009 в 03:45

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

-7

gaki 4 фев 2009 в 04:46

en.wikipedia.org/wiki/Bubble_sort

-3

kalyaka 4 фев 2009 в 13:13

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

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

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

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

avsmal 4 фев 2009 в 17:44

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

mrShadow 4 фев 2009 в 14:23

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

avsmal 4 фев 2009 в 14:37

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

alexnd 4 фев 2009 в 15:39

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

avsmal 4 фев 2009 в 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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Показать лучшие за всё время

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

Комментарии 25

Публикации

Истории