Разбор контекстно-свободных языков в потоке токенов

Question

проблема

Учитывая контекстно-свободную грамматику с произвольными правилами и потоком токенов, как эффективно идентифицировать потоки, соответствующие грамматике?

Пример:

Грамматика

S -> ASB | AB
A -> a 
B -> b

(по существу, число a с, за которым следует равное число b с)

Поток:

aabaaabbc...

Ожидаемый результат:

1. Матч начинается с позиции 1: ab
2. Матч, начинающийся в позиции 4: aabb

Конечно, ключ "эффективно". без проверки слишком много безнадежных кандидатов слишком долго. Единственное, что я знаю о своих данных, это то, что хотя грамматика произвольна, на практике совпадающие последовательности будут относительно короткими (<20 терминалов), тогда как сам поток будет довольно длинным (> 10000 терминалов).

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

С чего мне начать? Какой тип синтаксического анализатора может быть адаптирован к этому типу работы?

Answer 1

«Произвольная грамматика» заставляет меня предложить вам посмотреть комментарий wberry.

Насколько сложны эти грамматики? Есть ли шаг ручного вмешательства?

Я сделаю попытку. Если бы я изменил ваш пример грамматики из:

S -> ASB | AB
A -> a 
B -> b

для включения:

S' -> S | GS' | S'GS' | S'G
G -> sigma*

Так что G = мусор и S '- это много S-фрагментов с мусором между ними (возможно, я был небрежен с моими правилами производства. Вы поняли), я думаю, мы можем решить вашу проблему. Вам просто нужен анализатор, который будет соответствовать другим правилам до G. Возможно, вам придется изменить эти производственные правила на основе синтаксического анализатора. Я почти гарантирую, что будут изменения порядка правил в зависимости от парсера. Поскольку большинство библиотек синтаксического анализатора отделяют лексизм от синтаксического анализа, вам, вероятно, понадобится универсальная лексема с последующей модификацией G для включения всех возможных лексем. В зависимости от вашей специфики, это может быть не лучше (с точки зрения эффективности), чем просто начинать каждую попытку в каждой точке потока.

Но ... Предполагая, что мои производственные правила фиксированы (как для корректности, так и для конкретного вида синтаксического анализатора), это должно не только сопоставлять фрагменты в потоке, но и давать вам дерево разбора для всего потока. Вы заинтересованы только в поддеревьях с корнями в узлах типа S.