Почему сгенерированный парсер настолько медленный?

Question

Я играл на PEG.js, пытаясь создать парсер, способный взять строку и создать объект.

Для примера возьмем строку «а & б» и создать:

{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

Я предполагаю, что это что-то делать со всеми вашими sep* с. Если вы посмотрите на примеры в оригинальной бумаге 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]*