Существует ли какие-нибудь методологии, подходы, рекомендации как лучше парсить текстовые файлы.
Хотелось бы ознакомится с мнением знатоков в этом деле.

Здравствуйте, Аноним, Вы писали:

А>Существует ли какие-нибудь методологии, подходы, рекомендации как лучше парсить текстовые файлы.
А>Хотелось бы ознакомится с мнением знатоков в этом деле.

ага, обычно для этого юзают готовую либу,
типа boost::spirit, boost::regex и т.п

Аноним 922 пишет:

> Существует ли какие-нибудь методологии, подходы, рекомендации как лучше
> парсить текстовые файлы.

Методологий думаю нет (кроме теории грамматик и парсеров для компиляторов)
А парсить надо с помощью регулярных выражений (PCRE например) и
генераторов парсеров (yacc, bizon, ANTLR).

Здравствуйте, Аноним, Вы писали:

А>Существует ли какие-нибудь методологии, подходы, рекомендации как лучше парсить текстовые файлы.
А>Хотелось бы ознакомится с мнением знатоков в этом деле.

Не совсем понятно, что вы имеете в виду под словом «парсить». Уж слишком ёмкое слово, и в него вкладывают смысла больше, чем оно того заслуживает.

Рассмотрим обработку текстовых файлов на примере фронт энда какого-нибудь компилятора. Пусть входной файл содержит строку «x * (9 + y1)».

Первый этап — лексический анализ, задача — разбить на токены (лексемы). Ту штуку (класс), которая осущствляет лексический анализ, называют лексером или сканнером. Ему на вход подаются правила. Они могут быть заданы в виде регулярных выражений, реже необходима контекстно-свободная грамматика. Как писать этот сканер? Есть несколько вариантов. В простейшем можно обойтись библиотеками Boost.Tokenizer и Boost.Regex. Но лучше использовать какой-нибудь генератор сканеров. Я работал с GNU Flex (это потомок древней никсовой утилиты LEX). На вход Flex'у подаётся описание лексики в его собственном формате, который выглядит как список рег. выражений и соответствующих ему действий. Третий вариант — GOLD Parser Generator, его входной файл представляет собой описание лексики в виде к.-с. грамматики в (расширенной) нормальной форме Бэкуса (БНФ). Удобно, но чаще всего к.-с. грамматика в описании лексики — overkill, достаточно регулярной грамматики (а для её описания достаточно языка регулярных выражений).

Итак, ещё раз, для случая Flex. Вы даёте ему на вход описание вашей лексики в виде списка рег. выражений, он генерирует вам исходник сканнера на Си (можно на C++). Затем вы уже используете этот класс в своём коде.

Итак, сканнер сможет разбить вашу строчку на токены: «x», «*», «(», «9», «+», «y1», «)». Вы в lex-файле указываете действия (прямо в виде кода на C++), которые могут сразу преобразовывать токены в лексемы, например: LxmId(«x»), LxmOpMult(), LxmLeftBrace(), LxmInt(«9»), LxmOpPlus(), LxmId(«y1»), LxmRightBrace().

Второй этап — это синтаксический анализ, задача — проверить последовательность лексем на соответствие синтаксису (соответствие семантике проверяется позже) и построить дерево разбора (т. н. конкретное синтаксическое дерево). Позже можно выбросить из этого дерева лишние узлы вроде скобок, получим абстрактное синтаксическое дерево. Тот класс, который осуществляет этот этап, называют синтаксическим анализатором или парсером. Ему на вход подаётся грамматика, часто записанная в виде БНФ. Как писать парсер? Можно воспользоваться библиотекой Boost.Spirit (если уверены в крепости своей психики). Но лучше использовать какой-нибудь традиционный генератор парсеров. Я работал с GNU Bison (потомок древней никсовой утилиты YACC). На вход Bison'у подаётся описание грамматики в его собственном формате, представляющем собой список правил вывода (редукций), и соответствующих им действий. В действиях пишут код на C++, формирующий узлы дерева разбора (GoF-паттерн Composite). Третий вариант — GOLD Parser Generator, его входной файл представляет собой описание синтаксиса в виде к.-с. грамматики в БНФ.

Если вам хочется реализовывать сканер с нуля, то надо погуглить на тему детерминированных конечных автоматов, стандартный теоретический формализм для анализа рег. выражений.

Если вам хочется реализовывать парсер с нуля, то надо погуглить на тему алгоритмов синтаксического анализа, наприрмер LALR(1).

В общем, надо точно определиться, что для вас значит «Задача парсинга тесктовых файлов», скорее всего вам регулярных выражений будет вполне достаточно.

Спасибо большое за развернутый ответ.
Меня интересует более простой вариант. Есть некий входной тествый файл, в котром содержится информация типа: ключ-значение, разделители, блок данных и проч.
Это все надо обработать и сложить в соответствующий класс.
На мой взгляд, тут наиболее подходит конечный автомат. Интересно было почитать какие существуют подходы, если таковые вообще имеются.

Здравствуйте, Qbit86, Вы писали:

Q>Здравствуйте, Аноним, Вы писали:

А>>Существует ли какие-нибудь методологии, подходы, рекомендации как лучше парсить текстовые файлы.
А>>Хотелось бы ознакомится с мнением знатоков в этом деле.

Q>Не совсем понятно, что вы имеете в виду под словом «парсить». Уж слишком ёмкое слово, и в него вкладывают смысла больше, чем оно того заслуживает.

Q>Рассмотрим обработку текстовых файлов на примере фронт энда какого-нибудь компилятора. Пусть входной файл содержит строку «x * (9 + y1)».

Q>Первый этап — лексический анализ, задача — разбить на токены (лексемы). Ту штуку (класс), которая осущствляет лексический анализ, называют лексером или сканнером. Ему на вход подаются правила. Они могут быть заданы в виде регулярных выражений, реже необходима контекстно-свободная грамматика. Как писать этот сканер? Есть несколько вариантов. В простейшем можно обойтись библиотеками Boost.Tokenizer и Boost.Regex. Но лучше использовать какой-нибудь генератор сканеров. Я работал с GNU Flex (это потомок древней никсовой утилиты LEX). На вход Flex'у подаётся описание лексики в его собственном формате, который выглядит как список рег. выражений и соответствующих ему действий. Третий вариант — GOLD Parser Generator, его входной файл представляет собой описание лексики в виде к.-с. грамматики в (расширенной) нормальной форме Бэкуса (БНФ). Удобно, но чаще всего к.-с. грамматика в описании лексики — overkill, достаточно регулярной грамматики (а для её описания достаточно языка регулярных выражений).

Q>Итак, ещё раз, для случая Flex. Вы даёте ему на вход описание вашей лексики в виде списка рег. выражений, он генерирует вам исходник сканнера на Си (можно на C++). Затем вы уже используете этот класс в своём коде.

Q>Итак, сканнер сможет разбить вашу строчку на токены: «x», «*», «(», «9», «+», «y1», «)». Вы в lex-файле указываете действия (прямо в виде кода на C++), которые могут сразу преобразовывать токены в лексемы, например: LxmId(«x»), LxmOpMult(), LxmLeftBrace(), LxmInt(«9»), LxmOpPlus(), LxmId(«y1»), LxmRightBrace().

Q>Второй этап — это синтаксический анализ, задача — проверить последовательность лексем на соответствие синтаксису (соответствие семантике проверяется позже) и построить дерево разбора (т. н. конкретное синтаксическое дерево). Позже можно выбросить из этого дерева лишние узлы вроде скобок, получим абстрактное синтаксическое дерево. Тот класс, который осуществляет этот этап, называют синтаксическим анализатором или парсером. Ему на вход подаётся грамматика, часто записанная в виде БНФ. Как писать парсер? Можно воспользоваться библиотекой Boost.Spirit (если уверены в крепости своей психики). Но лучше использовать какой-нибудь традиционный генератор парсеров. Я работал с GNU Bison (потомок древней никсовой утилиты YACC). На вход Bison'у подаётся описание грамматики в его собственном формате, представляющем собой список правил вывода (редукций), и соответствующих им действий. В действиях пишут код на C++, формирующий узлы дерева разбора (GoF-паттерн Composite). Третий вариант — GOLD Parser Generator, его входной файл представляет собой описание синтаксиса в виде к.-с. грамматики в БНФ.

Q>Если вам хочется реализовывать сканер с нуля, то надо погуглить на тему детерминированных конечных автоматов, стандартный теоретический формализм для анализа рег. выражений.

Q>Если вам хочется реализовывать парсер с нуля, то надо погуглить на тему алгоритмов синтаксического анализа, наприрмер LALR(1).

Q>В общем, надо точно определиться, что для вас значит «Задача парсинга тесктовых файлов», скорее всего вам регулярных выражений будет вполне достаточно.

Здравствуйте, Аноним, Вы писали:

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

Вполне может быть, что для вашей задачи подойдёт конечный автомат. Тогда давайте чуть подробнее о конечных автоматах. (Уж извините, если буду продолжать в занудном лекторском тоне :) Просто тема, имхо, интересная.)

Под словосочетанием «конечный автомат» понимают два понятия.

1) Конечный автомат в теории формальных грамматик — математический формализм для описания регулярных грамматик, тип 3 по Хомскому. Это самая слабая машинка в его иерархии :) Куда слабее той же машини Тьюринга. У «теоретического» конечного автомата даже нет памяти, поэтому с помощью него много не напрограммируешь.

2) Конечный автомат в «программистком быту» — гораздо более мощная штука. Чтобы не путать с первым пунктом, такой автомат часто называют машиной состояний (FSM — Finite State Machine). В FSM программисты не стесняются хранить контекст, выполнять побочные действия при переходах и т. д.

Как его реализовать. Самый тонкий момент заключается в том, что будут чесаться руки впихнуть в машину состояний большой switch, а это некузяво. Так что надо использовать поиск функций по таблице за константное время. А если скилл ООП развит хорошо, то не придётся использовать самопальных массивов указателей на функции, т. к. их вполне заменят предоставляемые языком таблицы функций — vtable, если правильным образом извратиться.

Зарисовки охретектуры: у вас будет класс StateMachine, у него метод ProcessEvent(), получающий интерфейс Event. На каждый тип события будет свой класс ConcreteEvent. Внутри машины будет указатель на текущее состояние (почти паттерн State, но не совсем), и несколько ConcreteStat'ов. В обработчиках React<Event>() будут вызываться функции Transit(), осуществляющие переход в новое состояние.

Собственно, создание машины свелось к задаче двойной диспетчеризации — по состоянию, и по пришедшему событию. Как это сделать — см. например в книжке Александреску, глава про мультиметоды. Но можно сделать и по другому, как в GoF-варианте паттерна Visitor, там ведь тоже диспетчеризация по двум классам — сам объект и класс, определяющий действие.

После того, как реализуете свою машину состояний, смело можете о ней забыть, так как в Boost'е есть обобщённая реализация машин состояний — Boost.Statechart :) Почему-то эта часть Boost'а довольно малоизвестна (появилась в версии 1.34.0), но тем не менее сделана довольно хорошо, мне понравилась.

Здравствуйте, Аноним, Вы писали:

А>Есть некий входной тествый файл, в котром содержится информация типа: ключ-значение, разделители, блок данных и проч.

Это INI-файл что ли? Или что-то более сложное?
Откуда этот файл берется-то? Формат стандартный/документированый?

Здравствуйте, bnk, Вы писали:

bnk>Это INI-файл что ли? Или что-то более сложное?
bnk>Откуда этот файл берется-то? Формат стандартный/документированый?

А если это ini-файл, то, быть может, удастся обойтись библиотекой Boost.ProgramOptions.

Здравствуйте, Qbit86, Вы писали:

Q>Здравствуйте, bnk, Вы писали:

bnk>>Это INI-файл что ли? Или что-то более сложное?
bnk>>Откуда этот файл берется-то? Формат стандартный/документированый?

Q>А если это ini-файл, то, быть может, удастся обойтись библиотекой Boost.ProgramOptions.

...кубит86 никому не оставил шанса на ответ, все посты его.