I am using preg_match_all to make a simple parser. Note that since it will parse only few sentences, the performance does not matter. Would it be possible to make a parser which parse through below Context free grammer?
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'
The problem here that I couldn't resolve was loop.
For example, do you see loop where there can be PP -> NP -> PP and so on?
Is there anything in PHP that works like Push-down automata that can solve this problem?
Example input: 'the cat chased the dog'
Example output:
(S (NP the (N cat)) (VP (V chased) (NP the (N dog))))
Example input: 'the cat chased the dog on the rug'
Example output(s):
(S (NP the (N cat)) (VP (V chased) (NP the (N dog) (PP (P on) (NP the (N rug))))))
(S (NP the (N cat)) (VP (V chased) (NP the (N dog)) (PP (P on) (NP the (N rug)))))