Лучший способ для комбинаторов парсеров в C?

Я пытаюсь загрузить исходный код (подмножество) C с нуля, не используя дополнительные зависимости (генераторы-синтаксические анализаторы, библиотеки и т.д.). Также я хочу использовать идею комбинаторов парсеров, что является фантастической техникой в ​​функциональном программировании. Я хотел бы заимствовать эту идею от функционального мира до процедурного С на сжатом и практическом пути.

Я попытался реализовать некоторые необходимые компараторы парсеров для следующей игрушечной грамматики, которая также является примером из книги "Реализация функциональных языков - учебник Саймона Пейтона Джонса".

greeting -> hg person "!"
hg -> "hello"
 | "goodbye"

где person - любой токен, начинающийся с буквы. Например, список токенов

["goodbye", "James", "!"]

анализируется на

[(("goodbye", "James"), ["!"])]

(В книге используется Haskell, и трудно сделать ее языковой агностикой, но вы получаете идею: -)

Я реализовал это на C, и вы можете просмотреть код здесь: https://gist.github.com/4451478

Эта реализация стоит 200+ строк кода C, что намного больше, чем 20 строк Haskell, как написано в книге. Поэтому я не уверен, что я нахожусь на правильном пути создания комбинаторов синтаксиса в C, и если есть какие-то возможные улучшения. Любые предложения приветствуются. Спасибо заранее.

5 ответов

Попробуйте Cesium3, который представляет собой реализацию комбинаторов парсеров для C. (LLVM.)


Я сам изучаю этот вопрос, и я слежу за работой Daniel Holden, автора mpc, очень хорошо написанная библиотека синтаксического анализатора для C, которая позволяет, среди прочего, вставлять **** и Regex внутри кода C:

mpc_parser_t *Expr = mpc_new("expression");
 mpc_parser_t *Prod = mpc_new("product");
 mpc_parser_t *Value = mpc_new("value");
 mpc_parser_t *Maths = mpc_new("maths");
 mpca_lang(MPCA_LANG_PREDICTIVE,
 " expression : <product> (('+' | '-') <product>)*; "
 " product : <value> (('*' | '/') <value>)*; "
 " value : /[0-9]+/ | '(' <expression> ')'; "
 " maths : /^/ <expression> /$/; "
 Expr, Prod, Value, Maths, NULL);
</expression></expression></value></value></product></product>

Даниэль Холден также написал онлайн-книгу где он продемонстрировал, как легко писать новый язык, используя свою библиотеку. Книга озаглавлена ​​ "Создайте свой собственный Lisp" . Я думаю, вы найдете это действительно полезным для своего проекта. И последнее, но не менее важное: в примерах библиотеки есть готовая программа, которая генерирует парсер для подмножества C. ; -)


Реализация комбинатора парсеров в C - это тема, которая меня тоже интересует, и недавно я написал комбинатор парсеров в C: https://github.com/petercommand/cparc

Ниже приведен тестовый пример из моего кода, который пытается разобрать числа, разделенные запятыми, в список чисел. Я использую список парсеров (и генерирую синтаксический анализатор из "списка парсера", вызывая parser_chain в коде), чтобы имитировать "сделать нотацию" в Haskell, хотя и не так элегантно.

parser_dp_return test_parser7_rest_dp(dynamic_parser_closure* ctx, input_t input) {
 parser_dp_return dp_ret;
 dp_ret.obj = ctx->objs[1]->obj;
 dp_ret.status = PARSER_NORMAL;
 dp_ret.i = input;
 dp_ret.discard_obj_callback = NULL;
 return dp_ret;
}
parser_dp_return test_parser7_full_dp(dynamic_parser_closure* ctx, input_t input) {
 parser_dp_return dp_ret;
 list* result = list_new();
 list_push_back(result, ctx->objs[0]->obj);//num
 if(ctx->objs[1] && ctx->objs[1]->obj) {
 list_append(result, ctx->objs[1]->obj);
 }
 dp_ret.status = PARSER_NORMAL;
 dp_ret.i = input;
 dp_ret.discard_obj_callback = (void (*)(void *))&list_delete;
 dp_ret.obj = result;
 return dp_ret;
}
bool test_parser7() {//comma separated values
 parser* number = num();
 parser* comma = symbol(',');
 parser* rest_parser = parser_chain_final(test_parser7_rest_dp);
 list* parser_chain_list = list_new();
 list_push_back(parser_chain_list, comma);//ctx 0
 list_push_back(parser_chain_list, number);//ctx 1
 list_push_back(parser_chain_list, rest_parser);
 parser* rest = parser_chain(parser_chain_list);
 list_delete(parser_chain_list);
 parser* many_rest = many(rest);
 list* parser_chain_full = list_new();
 list_push_back(parser_chain_full, number);//ctx 0
 list_push_back(parser_chain_full, many_rest);//ctx 1
 parser* full_parser = parser_chain_final(test_parser7_full_dp);
 list_push_back(parser_chain_full, full_parser);
 parser* final = parser_chain(parser_chain_full);
 const char* input = "1,20,300,4000,50000";
 input_t i;
 input_init(&i, input);
 parser_dp_return dp_ret = parse(final, i);
 parser_delete(number);
 parser_delete(comma);
 parser_delete(rest_parser);
 parser_delete(rest);
 parser_delete(many_rest);
 parser_delete(full_parser);
 parser_delete(final);
 bool result = true;
 test_true(&result, dp_ret.status == PARSER_NORMAL);
 list* l = dp_ret.obj;
 list_item* li = l->head;
 test_true(&result, ptr_to_int(li->item) == 1);
 li = li->next;
 test_true(&result, ptr_to_int(li->item) == 20);
 li = li->next;
 test_true(&result, ptr_to_int(li->item) == 300);
 li = li->next;
 test_true(&result, ptr_to_int(li->item) == 4000);
 li = li->next;
 test_true(&result, ptr_to_int(li->item) == 50000);
 return result;
}


Я думаю, что ваш C-код достаточно компактен для того, что вы делаете. Haskell просто более компактен для такого рода вещей. Начните с закрытия. Для этого вам нужны функции, закрытые по окружающему пространству, и ваш код имитирует их частично. Haskell имеет компактную нотацию для списков и правильно используется, они довольно хороши для деревьев, таких как AST, а C требует, чтобы вы создали свою собственную библиотеку AST и работали с "- > слева" и "-" справа ", или попытайтесь обернуть их в сжатые макросы.

Даже в реализациях на языке C, которые я видел, и в неопубликованной реализации С++, которую я написал сам, я думаю, что комбинаторы парсеров являются удовлетворительной альтернативой рекурсивному коду спуска, который был моим методом анализа в прошлом.


Интересно, почему бы не использовать что-то вроде Yacc или Bison?

У меня есть некоторый опыт работы с грамматикой LALR в Erlang и выглядит весьма полезным для меня. Гораздо меньше строк кода.

Приветствие...

http://www.erlang.org/doc/man/yecc.html

licensed under cc by-sa 3.0 with attribution.