생성 된 구문 분석기의 속도가 느린 이유는 무엇입니까?

Question

문자열을 가져 와서 개체를 만들 수있는 파서를 만들기 위해 PEG.js에서 놀고있었습니다.

예를 들어, 문자열 "는 & 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

나는 당신의 sep*의 모두와 함께 할 수있는 뭔가가 추측에는 요. 브라이언 포드 (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]*