Эта статья задумывалась как наглядное сравнение двух схожих библиотек для создания парсеров: Boost Spirit для C++ и Parsec для Haskell. Потом я решил, что лучше разбить статью на 3 части. В первой части я расскажу как написать контекстно-свободную грамматику для описания содержимого ini-файла.
Файлы с расширением ini широко распространены не только в мире Windows, но и в других системах (к примеру, php.ini). Формат ini-файла очень прост: файл разделён на секции, в каждой секции может находится произвольное число записей вида «параметр=значение». Имена параметров в разных секциях могут совпадать.
Каждый параметр может быть адресован через имя секции и имя параметра: что-нибудь вроде
В ini-файлах предусмотрены комментарии — строки начинающиеся с ";".
Давайте попробуем описать этот формат виде контекстно свободной грамматики в расширенной нотации Бэкуса-Наура (надеюсь, что будет понятно даже тем, кто не знаком с ней).
Опишем что из себя представляет ini файл. Для этого опишем все конструкции от самых сложных (собственно сам ini-файл) к самым простым (что такое идентификатор). Каждой такой конструкции сопоставляется специальное обозначение (нетерминал), которое определяется через другие нетерминалы и обычные символы (терминалы), которые я буду
задавать в кавычках.
Осталось учесть, что некоторые парсеры/люди любят ставить дополнительные пробелы и пустые строки.
Для этого нам потребуется ввести ещё два нетерминала: пробельные символы используемые в строке и просто пробельные символы.
Пробелы могут быть почти где угодно. Поэтому немножко подкорректируем грамматику:
Вот в общем-то и всё, что касается грамматики =).
Кто-то, наверное, заметил, что я ничего не сказал про комментарии. Я не забыл — просто их проще «ручками» вырезать =) (в качестве упражнения можете подправить грамматику так, чтобы она комментарии учитывала).
Важно: я немного схитрил и построил грамматику так, чтобы в ней не было левой рекурсии. Обе рассматриваемые мною библиотеки строят рекурсивный нисходящий парсер, который уязвим к левой рекурсии. Перед тем, как использовать эти библиотеки в реальных проектах, убедитесь, что вы понимаете что это такое и как с этим бороться =).
Теперь вы можете сравнить использование этой грамматики для построения парсера на C++ и на Haskell.
PS. Спасибо maxshopen за идею поместить эту статью в блог «Разработка».
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 за идею поместить эту статью в блог «Разработка».
