Pull to refresh

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

Website development *
Эта статья задумывалась как наглядное сравнение двух схожих библиотек для создания парсеров: Boost Spirit для C++ и Parsec для Haskell. Потом я решил, что лучше разбить статью на 3 части. В первой части я расскажу как написать контекстно-свободную грамматику для описания содержимого ini-файла.

ini файлы


Файлы с расширением ini широко распространены не только в мире Windows, но и в других системах (к примеру, php.ini). Формат ini-файла очень прост: файл разделён на секции, в каждой секции может находится произвольное число записей вида «параметр=значение». Имена параметров в разных секциях могут совпадать.
[секция_1]
параметр1=значение1
параметр2=значение2

[секция_2]
параметр1=значение1
параметр2=значение2

Каждый параметр может быть адресован через имя секции и имя параметра: что-нибудь вроде 'секция_1'.'параметр2'.

В ini-файлах предусмотрены комментарии — строки начинающиеся с ";".

Строим грамматику


Давайте попробуем описать этот формат виде контекстно свободной грамматики в расширенной нотации Бэкуса-Наура (надеюсь, что будет понятно даже тем, кто не знаком с ней).

Опишем что из себя представляет ini файл. Для этого опишем все конструкции от самых сложных (собственно сам ini-файл) к самым простым (что такое идентификатор). Каждой такой конструкции сопоставляется специальное обозначение (нетерминал), которое определяется через другие нетерминалы и обычные символы (терминалы), которые я буду
задавать в кавычках.
  • Данные ini-файла (inidata) содержат несколько секций (фигурные скобки означают повторение любое количество раз).
    inidata = {section} .

  • Секция состоит из названия секции, заключённого в квадратные скобки, за которым со следующей строки идет несколько записей (параметров).
    section = "[", ident, "]", "\n", {entry} .

  • Запись состоит из имени параметра, знака "=", значения параметра и заканчивается концом строки.
    entry = ident, "=", value, "\n" .

  • Определим что такое идентификатор: всё что состоит из букв, цифр или знаков "_.,:(){}-#@&*|" (в действительности могут встречаться и другие символы).
    ident = {letter | digit | "_" | "." | "," | ":" | "(" | ")" | "{" | "}" | "-" | "#" | "@" | "&" |"*" | "|"} .

    Это определение не совсем верно, т.к. идентификатор должен состоять хотя бы из одного символа. Переделаем так:
    ident = identChar, {identChar} .
    identChar = letter | digit | "_" | "." | "," | ":" | "(" | ")" | "{" | "}" | "-" | "#" | "@" | "&" |"*" | "|" .

  • Теперь определим что является значением: всё кроме конца строки (для краткости пришлось расширить нотацию обозначение not)
    value = {not "\n"} .

Осталось учесть, что некоторые парсеры/люди любят ставить дополнительные пробелы и пустые строки.
Для этого нам потребуется ввести ещё два нетерминала: пробельные символы используемые в строке и просто пробельные символы.
stringSpaces = {" " | "\t"} .
spaces = {" " | "\t" | "\n" | "\r"} .

Пробелы могут быть почти где угодно. Поэтому немножко подкорректируем грамматику:
inidata = spaces, {section} .
section = "[", ident, "]", stringSpaces, "\n", {entry} .
entry = ident, stringSpaces, "=", stringSpaces, value, "\n", spaces .
ident = identChar, {identChar} .
identChar = letter | digit | "_" | "." | "," | ":" | "(" | ")" | "{" | "}" | "-" | "#" | "@" | "&" |"*" | "|" .
value = {not "\n"} .
stringSpaces = {" " | "\t"} .
spaces = {" " | "\t" | "\n" | "\r"} .


Вот в общем-то и всё, что касается грамматики =).

Кто-то, наверное, заметил, что я ничего не сказал про комментарии. Я не забыл — просто их проще «ручками» вырезать =) (в качестве упражнения можете подправить грамматику так, чтобы она комментарии учитывала).

Важно: я немного схитрил и построил грамматику так, чтобы в ней не было левой рекурсии. Обе рассматриваемые мною библиотеки строят рекурсивный нисходящий парсер, который уязвим к левой рекурсии. Перед тем, как использовать эти библиотеки в реальных проектах, убедитесь, что вы понимаете что это такое и как с этим бороться =).

Теперь вы можете сравнить использование этой грамматики для построения парсера на C++ и на Haskell.

PS. Спасибо maxshopen за идею поместить эту статью в блог «Разработка».
Tags:
Hubs:
Total votes 43: ↑36 and ↓7 +29
Views 28K
Comments 25
Comments Comments 25

Posts