원하는 경우 문법 규칙을 전달하여 구성 할 수있는 파서 만 있으면됩니다. Earley 구문 분석기는 일련의 규칙 만 주어진 문맥없는 언어를 구문 분석합니다. 가격은 중요한 실행 시간 : O (N^3)입니다. 여기서 N은 입력의 길이입니다. N이 크면 (많은 분석 가능한 엔티티의 경우와 마찬가지로) 매우 느린 구문 분석으로 끝낼 수 있습니다.
그리고 이것이 파서 생성기 (PG)의 이유입니다. 많은 문서를 파싱하면 느린 파싱은 나쁜 소식입니다. 컴파일러는 사람이 많은 문서를 파싱하는 프로그램 중 하나이며 프로그래머 (또는 그의 관리자)는 프로그래머가 컴파일러를 기다리지 않기를 바랍니다. 파싱해야 할 다른 많은 것들이 있습니다 : SQL querys, JSON 문서 ...이 모든 것은 "아무도 기다릴 용의가 없습니다"속성을 가지고 있습니다.
PG가하는 일은 런타임에 (예 : Earley 파서의 경우) 발생해야하는 많은 결정을 내리고 파서 생성시 해당 결과를 미리 계산하는 것입니다. 따라서 LALR (1) PG (예 : Bison)는 O (N) 시간에 실행되는 파서를 생성 할 것이며 이는 실제 상황에서 훨씬 빠릅니다. (ANTLR은 LL (k) 파서와 비슷한 것을합니다). 대개 선형 구문 분석을 원하는 경우 GLR parsing이라는 LR 구문 분석 변형을 사용할 수 있습니다. 이 기능을 사용하면 "구성 가능한"(Earley) 파서의 편리함을 훨씬 더 향상시킬 수 있습니다.
이 사전 계산은 일반적으로 partial evaluation으로 알려져 있습니다. 즉 함수 F (x, y)가 주어지고 x가 항상 일정 상수 x_0이라는 지식이있는 경우 새 함수 F '(y) = F (x0, y)는 x의 값에만 의존하는 의사 결정과 계산이 사전 계산됩니다. F는 대개 F보다 훨씬 빠르게 실행됩니다. 우리의 경우 F는 일반 구문 분석 (예 : Earley 파서)과 같으며 x는 특정 문법 인 x0의 문법 인수이고 F '는 일부 구문 분석기 인프라 P이며 추가 F '= PG (x) + P가되도록 PG에 의해 계산 된 코드/테이블.
질문에 대한 의견에는 왜 런타임에 파서 생성기를 실행하지 않는지에 대한 관심이있는 것으로 보입니다. 간단한 대답은 런타임에 제거하려는 오버 헤드 비용의 상당 부분을 지불한다는 것입니다.
@BartKiers : 파서 - 제네레이터에 의해 생성 된 파서가 제너레이터 자체보다 더 복잡하거나 더 일반적인 것은 아니지만? 파서 생성기가 뭔가를 구문 분석 할만큼 복잡한 코드를 생성 할 수 있다면 왜 코드를 생성하고 컴파일하고 메모리에서 코드를 실행하여 즉시 구문 분석 할 수 없습니까? 그냥 파싱하는 것과 똑같은가? (아마도 파서 생성기가 있기 때문에 그 이유가 모르겠다.) –
죄송합니다, 이해가되지 않습니다. 더 이상 설명하려고하지 마십시오. 나는이 질문이 SO에 잘 맞지 않는다고 생각합니다. 따라서 나는 그 질문을 따르지 않을 것입니다. –
약간의 노력으로 lex와 yacc (flex와 bison)에 의해 생성 된 테이블을 얻고 비표준 스켈레톤에서 사용할 수 있습니다. 가장 큰 문제점은 사용자 공급 조치를 연결하는 것입니다. – wildplasser