1
Я наткнулся на множество различных алгоритмов (CYK и Earley), чтобы проверить, является ли строка частью CFL, CFG которой предоставляется. Я ищу что-то простое для понимания и реализации. Мне нужно знать, есть ли строка в CFG или нет. CFG дается обычно в формепростой анализатор CFG с переходом epsilon
S->S1 S2
S1->S1 a | a
S2->S2 b | b
раствор должен принимать эпсилон переходы, а также, например, S1-> а | e
любые идеи?
Итак, вы нашли много разных алгоритмов. Почему бы вам не попытаться реализовать один из них? –
Я считаю, что они сложнее и требуют определенного типа ввода, они также не поддерживают переходы epsilon. – Iordanis
1) Они не так уж сложны. 2) «требует определенного типа ввода»; какой особый вклад они требуют (вы не можете жаловаться на такие вещи, не предоставляя доказательств). 3) Я думал, что алгоритм Эрли не возражал против правил эпсилона. Википедия http://en.wikipedia.org/wiki/Earley_parser, по-видимому, заявляет («альфа-бета-гамма ... [может быть] пустая строка»), что алгоритм Эрли допускает правила с переходами epsilon. Менее щедрый человек может подумать, что вы не сделали домашнее задание. –