PHP preg_match_all을 사용하여 간단한 CFG 파서를 어떻게 구현할 수 있습니까?

Question

저는 preg_match_all을 사용하여 간단한 파서를 만듭니다. 단 몇 문장 만 파싱하므로 성능은 중요하지 않습니다. 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' 

여기서 내가 해결할 수없는 문제는 루프입니다.

예를 들어, PP -> NP -> PP가 될 수있는 곳의 루프를 볼 수 있습니까?

이 문제를 해결할 수있는 푸시 다운 오토 마타처럼 작동하는 PHP가 있습니까?

예시 입력 '고양이 개 쫓아'

예제 출력 :

(S (NP 제 (N 고양이)) (VP (V 쫓아) (NP 제 (N 개))))

예 입력 :

출력 예 (들) :

(S (NP 제 (N 고양이)) "고양이는 깔 개 쫓아 ' (VP (S (NP 제 (N 고양이가)) 이 (VP (V가 쫓아

))() NP 제 (N 개) (PP (에 P) (NP 제 (N 양탄자를))) (V 추격)) (NP the (N 개)) (NP (N 개))))

Answer 1

일반적인 방법은 예측 파서를 작성하는 것입니다. 이것은 정규 표현식을 사용하여 명사, 동사 또는 조건자를 일치시킨 다음 사용할 저작물을 결정하는 것을 의미 할 수 있습니다. 문법을 파싱하는 것이 푸시 다운 오토 마톤 (즉, 정규 표현식 만이 달성 할 수있는 것 이상)의 계산 능력을 필요로한다는 것이 맞습니다. 푸시 다운 오토 마톤을 시뮬레이션하는 것이 한 가지 방법이며 yacc/bison과 같은 파서 생성기가 자주 수행하는 것입니다. 그런 작은 문법을 위해서 암묵적으로 호출 스택을 사용할 수 있습니다.