Простой парсер CFG с эпсилон-переходом

Question

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

S->S1 S2
S1->S1 a | a
S2->S2 b | b

Предполагается, что решение принимает эпсилон-переходы, например, S1-> a | е

есть идеи?

Answer 1

Я нашел действительно прямой подход к этому проекту

https://code.google.com/p/cykparser/downloads/list

В отличие от других парсеров CYK, которые проходят ненужную проверку грамматики. Этот парсер является действительно хорошим доказательством концепции, которая просто реализует алгоритм CYK с базовой грамматикой.

Код в Python.