为什么生成的解析器这么慢？

Question

我在使用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]

Answer 1

如果你看看Bryan Ford的原始sep*论文中的例子，你会发现以空格开头的唯一规则是第一。然后，他从逻辑上分解语法，使词法部分(令牌规则)位于底部，每个令牌定义后面跟着空格。我认为它将解决您的问题，但即使它不能，它也会使它更具可读性(并且可能更容易修复)。

例如：

    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]*