Правило в BNF состоит из названия нетерминального символа, стрелки, и (возможно пустого) перечня символов (как терминальных, так и нетерминальных).
Пометим сначала все нетерминальные символы с пустыми перечнями символов после стрелки, как те, что могут породить пустые строки.
Затем рассмотрим остальные правила вывода. Если все символы в правой части могут породить пустые строки, то нетерминальный символ этого правила тоже надо пометить (а непомеченные правила проверить снова).
Повторяем процесс разметки до тех пор, пока не проверим все правила вывода. Если при очередной проверке не удалось пометить ни один новый  нетерминальный символ - процесс завершен.
Если делать так, то сложность алгоритма разметки будет квадратичная от количества правил в грамматике.

Если правые части правил состоят только из двух символов (грамматика в форме 2NF), то сложность этого алгоритма можно сделать линейной.

см. также
[html]<a href="https://stackoverflow.com/questions/41448121/nullable-nonterminals">SO 41448121</a>[/html]

Отредактировано Лис (2017-11-06 07:29:26)