Да, вы можете использовать любой обобщенный алгоритм синтаксического анализа, например GLR (Tomita) parser, Earley parser или даже a CYK parser; все они могут производить разбор «лес» (т. е. орграф всех возможных парсеров) в O (N) времени и пространства. (Создание дерева синтаксического анализа немного сложнее, чем «разбор» (т. Е. Распознавание), но существуют известные алгоритмы, на которые ссылаются в статье википедии.
Поскольку обобщенные алгоритмы синтаксического анализа находят все возможные анализы, вы можете будьте уверены, что если для строки найдено ровно один синтаксис, то строка не является двусмысленной.
Я бы держался подальше от анализа CYK для этого алгоритма, потому что он требует преобразования грамматики в нормальную форму Хомского, что делает восстановление оригинальное дерево синтаксического анализа более сложное.
Bison будет генерировать GLR parser, если потребуется, поэтому вы можете просто использовать этот инструмент. что он не оптимизирует хранение дерева синтаксического анализа, поскольку он ожидает, что будет создан только один синтаксический анализ, и поэтому вы можете получить экспоненциальные размеры данных (которые затем требуют экспоненциального времени для построения). Это, как правило, только проблема с патологическими грамматиками.