爲什麼生成的解析器如此緩慢？

我在PEG.js上試圖創建一個能夠接受一個字符串並創建一個對象的解析器。爲什麼生成的解析器如此緩慢？

例如，以字符串「a & b」和創建：

{type:"operator",value:operator, children:[a, b]}

然而，我已經達到，其中如果存在兩個或多個座返回結果可需要10秒以上的階段。

我一直在使用該測試的說法是：

(All a (All a (All a b)))

語法不會返回正確的答案，但需要的時間太長了。我的問題是，是什麼原因導致了這種簡單解析的時間延遲？

是可能的嘗試，並在PEG.js

我的語法在線編輯語法是：

start = sep* All:All sep* {return All} 

All = sep* operator:"All" sep* xValue: Ex sep* pValue: Ex{return {type:"operator",value:operator, children:[xValue, pValue]}} /Ex 

Ex = sep* operator:"Ex" sep* xValue: AND sep* pValue: AND {return {type:"operator",value:operator, children:[xValue, pValue]}} /AND 

AND= left: Plus sep* operator:"&" sep* right:AND {return {type:"operator", value:operator, children:[left,right]}}/Plus 

Plus = left: Equals sep* operator:"+" sep* right:Plus{return {type:"operator", value:operator, children:[left,right]}}/ Equals 

Equals = left:GEQ sep* operator:"=" sep* right:Equals{return {type:"operator", value:operator, children:[left,right]}}/GEQ 

GEQ = left:implication sep* operator:">=" sep* right:GEQ{return {type:"operator", value:operator, children:[left,right]}}/implication 

implication = left:OR sep* operator:"->" sep* right:implication{return {type:"operator", value:operator, children:[left,right]}}/OR 

OR = left:Not sep* operator:"|" sep* right:OR{return {type:"operator", value:operator, children:[left,right]}}/Not 

Not = sep* operator:"¬" sep* right:Suc{return {type:"operator", value:operator, children:[right]}}/Suc 

Suc = sep* operator:"suc" sep* right:primary{return {type:"operator", value:operator, children:[right]}}/primary 

primary = letter:letter{return {type:"variable", value:letter}}/ "{" sep* All:All sep* "}" {return All}/"(" sep* All:All sep* ")" {return All} 

sep = spaces:[' ',\\t] 

letter = "false"/"0"/letters:[A-Za-z]

來源

2014-12-30 Budgy

PEG是回溯解析器;它會嘗試多種替代方案來尋找可行的方案。你可能回溯到死亡。 –

我猜它是與所有sep* S的。如果你看看Bryan Ford最初的PEG論文中的例子，以空白開頭的唯一規則是第一個。然後，他邏輯地打破語法，使詞彙部分（標記規則）位於底部，每個標記定義後跟空格。我認爲它會解決你的問題，但即使沒有，它也會使它更具可讀性（並且可能更容易修復）。

例如：

start = SPACING All:All 
    All = operator:All_op xValue:Ex pValue: Ex 
     /Ex 
    Ex = operator:Ex_op xValue:AND pValue:AND 
    /* etc. */ 


    /* Lexical Portion */ 
    All_op = 'All' SPACING 
    Ex_op = 'Ex' SPACING 

    SPACING = [ \t]*

來源

2015-01-16 22:11:58 bekroogle

爲什麼生成的解析器如此緩慢？

回答

相關問題