如何使用PHP preg_match_all實現簡單的CFG解析器？

我正在使用preg_match_all來製作一個簡單的解析器。請注意，因爲它只能解析幾句話，所以表現並不重要。是否有可能通過下面的上下文自由語法來解析解析器？如何使用PHP preg_match_all實現簡單的CFG解析器？

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 （V追趕）（NP追蹤（NP追蹤）（NP追蹤）（NP追蹤追蹤追蹤）（P追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤追蹤）（NP（N dog））（PP（P on）（NP the（N rug）））））

來源

2011-03-08 user482594

你需要輸出什麼？只是句子在語法中是否有效或是否必須返回某種數據結構纔是真假？ – 2011-03-08 01:29:25

我需要數據結構返回.. – user482594 2011-03-08 01:31:14

你能給出一個給定輸入的期望輸出的例子嗎？ – 2011-03-08 01:34:52

這裏常用的方法是編寫一個預測解析器。對你而言，這可能意味着使用正則表達式來匹配名詞，動詞或謂詞，然後決定使用哪種生產。你解釋一個語法需要計算下推自動機的能力是正確的（即不僅僅是一個正則表達式可以實現的）。模擬一個下推式自動機是一種方法，是像yacc/bison這樣的解析器生成器經常做的事情。對於這樣的小語法，您可以隱式使用調用堆棧。

來源

2011-03-08 01:51:59 Samsdram

有沒有任何示例代碼，我可以看看？只有Google搜索後發現的代碼纔是正則表達式......也許PHP對此太有限了。 – user482594 2011-03-08 02:29:15

@ user482594我不知道PHP，因此我無法使用該語言的示例代碼。這是一個用Java編寫的預測解析器的鏈接http://www.cs.arizona.edu/~collberg/Teaching/453/2009/Handouts/Handout-8.pdf。 – Samsdram 2011-03-08 15:21:36

如何使用PHP preg_match_all實現簡單的CFG解析器？

回答

相關問題