LL (*)에서 PEG에 대한 잘 정의되고 잘 설명 된 변환이 있습니까?

Question

저는 PEG (Parsing Expression Grammar) 파서를 조사하는 중입니다. 제가 짚어보고있는 주제 중 하나는 다른 파싱 기술과 동등한 것입니다.

From Regular Expressions to Parsing Expression Grammars에서 regexes를 동등한 PEG로 변형하는 것에 대한 좋은 논문을 찾았습니다.

나는 LL(*) 파서에 대해 비슷한 치료법을 찾고 있지만 아직까지는 공손한 것으로 나타났습니다. 1에 설명 된 기술 중 많은 부분이 LL(*) 변환 문제에도 적용될 수 있지만 내 자신의 분석에 확신을 갖기에는 형식주의에 충분히 익숙하지 않은 것으로 보입니다.

귀하의 집단적 도움을 많이 주시면 감사하겠습니다.

Answer 1

PEG에 대해서는 Wikipedia article에 모두 나와 있다고 생각합니다. PEG는 명확성을 위해 절 순서를 사용하여 재귀 적으로 수행합니다. 이론적으로 재귀 적으로 파싱 할 수있는 언어 계열은 LL 패밀리이지만 PEG는 무제한의 선견지명과 모호성이 없으므로 패밀리는 더 큰 것, 아마도 완전한 CFG 여야합니다.

모든 LL (k) 문법은 k 미리보기 헤드를 가진 재귀 - 하강 파서로 구현할 수 있으므로 가장 긴 표정을 필요로하는 규칙을 나열하여 규칙을 순서화하여 모든 LL (k) 문법을 PEG 문법으로 변환 할 수 있습니다 먼저.

이

은 LL (k)는 문법입니다 :

params = expr 
params = expr ',' params 

이 같은 언어에 대한 PEG 문법하려면 규칙을 다시 정렬해야합니다

params = expr ',' params 
params = expr