PEG와 CFG의 차이점은 무엇입니까? 이 <a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar#Semantics">wikipedia</a> 페이지에서

Question

:

문맥 자유 문법과 구문 분석 표현 문법 사이의 근본적인 차이는 PEG의 선택 운영자가 주문되어 있다는 점이다. 첫 번째 대안이 성공하면 두 번째 대안은 무시됩니다. 따라서 을 선택하면 교환 할 수 없습니다. 문맥 자유 문법 및 문법과 마찬가지로 순서가 없습니다. 주문 선택은 소프트 절단 연산자를 일부 로직 프로그래밍 언어와 유사하게 사용할 수 있습니다.

왜 PEG의 선택 연산자가 일치를 단락하나요? 메모 사용으로 인한 메모리 사용을 최소화했기 때문입니까?

선택 연산자가 정규 표현식에 무엇인지 확실하지 않지만 다음과 같이 가정 해 봅시다 : /[aeiou]/ 모음과 일치시킵니다. 그래서이 정규식은 교환 가능합니다. 왜냐하면 제가 5 중 하나에 그것을 쓸 수 있었기 때문입니다! 모음 문자의 (5 계승) 순열? 즉 /[aeiou]/은 /[eiaou]/과 동일하게 동작합니다. 교환 할 수있는 이점은 무엇입니까? (로 페놀 PEG의 비 교환 법칙)은

결과는 CFG는 PEG에 직접 자역 경우, 이전의 모든 모호성이 는 결정 론적으로 가능한 구문 분석에서 하나 개의 구문 분석을 트리를 선택하여 해결 될 것입니다. 문법 대안이 지정되어있는 순서를 신중하게 선택하면 프로그래머는 이라는 구문 트리를 선택하는 데있어 큰 제어 권한을 갖게됩니다.

이것은 PEG의 문법이 CFG보다 우수하다는 말입니까?

Answer 1

CFG 문법은 비 결정적입니다. 즉, 일부 입력으로 인해 두 개 이상의 가능한 파스 트리가 발생할 수 있습니다. 대부분의 CFG 기반 파서 생성기는 문법의 결정 가능성에 제한을가집니다. 둘 이상의 선택 사항이있는 경우 경고 또는 오류가 표시됩니다.

PEG 문법은 결정적입니다. 즉, 모든 입력을 한 방향으로 만 구문 분석 할 수 있음을 의미합니다.

고전적인 예를 들어보세요. 문법

if_statement := "if" "(" expr ")" statement "else" statement 
       | "if" "(" expr ")" statement; 

입력에인가

if (x1) if (x2) y1 else y2 

어느

if_statement(x1, if_statement(x2, y1, y2)) 

또는

로서 해석 될 수

if_statement(x1, if_statement(x2, y1), y2) 

CFG 파서 시프트를 생성 할 것이다/축소 - 내가 결정할 수 없기 때문에 충돌한다. "else"키워드에 도달 할 때 이동 (다른 토큰 읽기)하거나 줄이기 (노드 완료)해야합니다. 물론이 문제를 해결할 수있는 방법이 있습니다.

PEG 파서는 항상 첫 번째 선택 사항을 선택합니다.

어느 것이 더 좋은지는 사용자가 결정하는 것입니다. 저의 객관적인 견해는 종종 PEG 문법은 작성하기 쉽고 CFG 문법은 분석하기 쉽다는 것입니다.

Answer 2

저는 CFG와 LR을 혼동스럽게 생각하고 모호한 것으로 생각합니다. 문법은 파서가 될 수도 있지만 결정적/비 결정적이지 않습니다. 모호한 문법은 정의를 준수하는 경우 여전히 CFG이며, PEG가 수행하는 작업에 대해 결정적 파서를 작성할 수 있습니다.