peg.js에서 어떻게 역 추적이 가능합니까 (예를 들어)?

Question

나는 다음과 같은 최소한의 Peg.js 문법 정의했습니다 :

start = "A1"/"A123" 

당신이 in the sandbox을 시도 할 수 있습니다.

"A1"과 "A123"이 일치 할 것으로 예상됩니다 (백 트랙킹 작동 방식에 대한 나의 견해에 따르면). 그러나 이것은 사실이 아닙니다 : 문법은 "A1"을 인식하지만 "A123"을 인식하지 못합니다.

참고 : 관련 질문 How to transform a simple grammar into something which works in PEG.js (expected "a" but "a" found)에서와 같이 "용어의 순서를 역으로"하는 조언을 찾고있는 것이 아닙니다. 오히려, 나는 내가 보는 행동을 이해하려고하며, 왜 Peg.js의 역 추적이이 경우에 적용되지 않는지 이해하려고합니다. 내 용어의 순서를 뒤집어도 도움이되지 않는 이유에 대한 설명은 아래의 좀 더 현실적인 예를 참조하십시오.

---

보다 현실적인 예를 보려면 단위 분석을 고려하십시오. 문법은 "mm", "mmol"과 같은 접두어 및 "yr", "week"또는 "mo"와 같은 비표준 단위를 사용하여 미터법 단위 (예 : "m", "mol")를 인식해야합니다.

다음과 같은 Peg.js 문법은 "mo"를 소모하여 다시 되돌아 가지 않으므로 "mol"을 인식하지 못합니다.

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/"m"/"g" 
nonmetric = "yr"/"mo"/"week"/"day"/"hour" 
prefix = "m"/"k"/"c" 

나는 ANTLR에서와 똑같이 일을 할 수 있습니다 ("몰"또는 "밀리몰"의 비용으로 인식되도록, 또는 오히려 "모"것입니다 용어의 순서는 도움이되지 않습니다 변경.) 좋은 성공 :

grammar units; 
start : nonmetric | metric | prefix metric; 
metric : 'mol' | 'l' | 'm' | 'g'; 
nonmetric : 'yr' | 'mo' | 'week' | 'day' | 'hour'; 
prefix : 'm' | 'k' | 'c'; 

Answer 1

문제는 의 개념을 되돌아와있다. PEG 파서는 다른 재귀 적 파생 파서 나 Prolog처럼 되돌릴 수 없습니다. 오히려 선택 사항에 직면 할 때 PEG 파서는 성공할 때까지 모든 옵션을 시도합니다. 성공하면 규칙이 어떻게 호출되는지에 관계없이 커밋합니다. Wikipedia article에서

: 문맥 자유 문법과 정규 표현식 달리

그러나 이러한 연산자는 항상 가능 결코 되돌아없는만큼 입력을 소비하는, 탐욕 동작합니다.

복잡한 경우에 대해 묻는 질문은 this question과 같습니다. 지금까지의 대답은 예입니다. PEG 문법의 규칙을 조정하여 결과가 다소 어색한 문법 인 경우에도 가장 긴 옵션이 항상 먼저 일치하는지 확인해야합니다. 이것은 의도적으로 설계된 동작

start = nonmetric/metric/prefix metric 
metric = "mol"/"l"/!"mo" "m"/"g" 
nonmetric = "yr"/!"mol" "mo"/"week"/"day"/"hour" 
prefix = !("mol"/"mo") "m"/"k"/"c" 

Answer 2

입니다 : PEG 문법을 조정할

한 가지 방법은 (즉 lookaheads이 PEG에 등장하는 주요 이유 중 하나) lookaheads을 사용하는 것입니다. 주문 또는 일치하는 데 사용할 규칙을 지정하는 것은 귀하에게 달려 있습니다.

원래 white paper에서 인용 :

는 이러한 도구는 물론, 언어 구문 디자인을 쉽게하지 않는다. CFG에서 두 가지 가능한 대안이 모호한 지 여부를 결정해야하는 장소에서 PEG는 언어 설계자에게 언어에 영향을주지 않고 '/'표현식 의 두 가지 대안을 재정렬 할 수 있는지 여부를 결정하는 것과 유사한 방식으로 나타냅니다. 이 질문은 종종 분명하지만, 때로는 아니며 일반적으로 결정할 수 없습니다. 그러나 CFG에서 모호성을 발견하는 것과 마찬가지로 우리는 주문 민감도를 식별하는 자동 알고리즘을 찾거나 일반적인 상황에서 보수적으로 민감하지 않게 을 찾길 바랍니다.

이 간단한 경우 PEG.js는 조금 더 똑똑하고 지정한 규칙이 모호하다는 것을 인식 할 수 있습니다. 아마도 ask의 가치가있을 것입니다.