Как я могу реализовать простой парсер CFG с помощью PHP preg_match_all?

Question

Я использую preg_match_all для создания простого парсера. Обратите внимание, что, поскольку он будет анализировать только несколько предложений, производительность не имеет значения. Можно ли создать синтаксический анализатор, который анализирует ниже контекстно-зависимую грамматику?

S -> NP VP
PP -> P NP
NP -> 'the' N | N PP | 'the' N PP
VP -> V NP | V PP | V NP PP
N -> 'cat'
N -> 'dog'
N -> 'rug'
V -> 'chased'
V -> 'sat'
P -> 'in'
P -> 'on'

Проблема, которую я не смог решить, была зациклена.

Например, вы видите цикл, в котором может быть PP -> NP -> PP и так далее?

Есть ли в PHP что-нибудь, что работает как автоматы Push-down, которые могут решить эту проблему?

Пример ввода: «кот погнался за собакой»

Пример вывода:

(S (NP the (N cat)) (VP (V погнался) (NP the (N dog))))

Пример ввода: «кошка преследовала собаку на ковре»

Пример выходных данных:

(S (NP the (N cat)) (VP (V погнался) (NP the (N dog) (PP (P on) (NP the (N rug))))))

(S (NP the (N cat)) (VP (V погнался) (NP the (N dog)) (PP (P on) (NP the (N rug)))))

Answer 1

Обычный подход здесь заключается в написании прогнозирующего синтаксического анализатора. Для вас это может означать использование регулярных выражений для сопоставления существительного, глагола или предиката, а затем решение, какую продукцию использовать. Вы правы в том, что синтаксический анализ грамматики требует вычислительных мощностей автоматов с понижением скорости (т. Е. Больше, чем может достигнуть только одно регулярное выражение). Имитация автомата нажатия - это один из подходов, который часто используют генераторы парсеров, такие как yacc / bison. Для такой небольшой грамматики вы можете неявно использовать стек вызовов.