2012-01-08 3 views
12

제목은 그것을 요약합니다. 아마도 소스 코드 생성 파서 생성기 (본질적으로 프로그램에 문법을 하드 코딩하는)로 수행 할 수있는 모든 작업은 구성 가능한 파서를 사용하여 수행 할 수 있습니다 (문법을 유지할 수있는 구문 분석기 데이터 구조로 소프트 코딩 된 -parsed).단지 구성 가능한 파서 대신 파서 생성기를 사용하는 이유는 무엇입니까?

하드 코드 된 코드 생성 구문 분석기는 간접 참조 수준이 한 단계 낮 으면 성능 보너스가되지만 컴파일 및 실행 (또는 동적 언어로는 exec())이 복잡하고 전반적인 clunkiness 코드 생성은 상당히 큰 단점이 있습니다. 파서의 코드 생성과 관련하여 내가 알지 못하는 다른 이점이 있습니까?

내가 사용한 코드 생성의 대부분은 언어 (예 : 웹 프레임 워크, AOP, 데이터베이스와의 인터페이스)의 메타 프로그래밍 기능의 한계를 해결하는 것이지만, 전체 lex-parse 작업은 매우 간단하고 코드 생성에서 얻을 수있는 추가적인 메타 프로그래밍 역 동성을 필요로하지 않습니다. 뭐라 구요? 성능상의 이점이 큽니다?

+0

@BartKiers : 파서 ​​- 제네레이터에 의해 생성 된 파서가 제너레이터 자체보다 더 복잡하거나 더 일반적인 것은 아니지만? 파서 생성기가 뭔가를 구문 분석 할만큼 복잡한 코드를 생성 할 수 있다면 왜 코드를 생성하고 컴파일하고 메모리에서 코드를 실행하여 즉시 구문 분석 할 수 없습니까? 그냥 파싱하는 것과 똑같은가? (아마도 파서 생성기가 있기 때문에 그 이유가 모르겠다.) –

+0

죄송합니다, 이해가되지 않습니다. 더 이상 설명하려고하지 마십시오. 나는이 질문이 SO에 잘 맞지 않는다고 생각합니다. 따라서 나는 그 질문을 따르지 않을 것입니다. –

+0

약간의 노력으로 lex와 yacc (flex와 bison)에 의해 생성 된 테이블을 얻고 비표준 스켈레톤에서 사용할 수 있습니다. 가장 큰 문제점은 사용자 공급 조치를 연결하는 것입니다. – wildplasser

답변

11

원하는 경우 문법 규칙을 전달하여 구성 할 수있는 파서 만 있으면됩니다. 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에 의해 계산 된 코드/테이블.

질문에 대한 의견에는 왜 런타임에 파서 생성기를 실행하지 않는지에 대한 관심이있는 것으로 보입니다. 간단한 대답은 런타임에 제거하려는 오버 헤드 비용의 상당 부분을 지불한다는 것입니다.

+1

감사합니다. 매우 유익합니다! 코드 생성 파서는 파싱하는 문법이 일반적으로 런타임에 변경되지 않고 프로그램에 하드 코딩 될 수 있기 때문에 수행 할 수있는 최적화라고 말할 수 있습니까? 런타임에 파서의 AST를 동적으로 작성할 수있는 LISP와 같은 언어에도 이러한 종류의 사항이 여전히 적용됩니까? (필자는 렉서/구문 분석이나 형식 언어 이론에 대한 교육을받지 못했습니다. 일반적인 방법을 배제하기 위해 노력하고 있습니다. 코드 생성은 흔히 볼 수있는 단계가 아닙니다.) –

+0

@LiHaoyi : 대부분 최적화는 그것들의 뒤의 상황에 대한 가정을 가지고있다. 부분적인 평가의 전체 점은 PE가 한 번 실행하는 데 비싸지 만 F '(y)는 일반적으로 F (x, y)보다 훨씬 저렴하며 x [문법]이 일정하게 유지되는 한 안전하게 사용할 수 있다는 것입니다 F '(y). 이것은 심지어 리스프에 대해서도 마찬가지입니다 : 그것은 S-expressions이라고 불리는 "일정한"문법을 가지고 있습니다. –

+1

에필로그로서 다소, 나는 스칼라가 제공 한 파서 결합 자 라이브러리를 사용하는 방법을 최근에 배웠다. 필자가 생각하기에 PyParsing, (F) Parsec과 같은 비슷한 라이브러리를 코드 생성없이 모두 사용할 수있게 해주는 유사한 라이브러리가 다른 언어에 존재합니다. 이것들이 당신의 대답에 어떻게 들어 맞습니까? 그들은 런타임에 초기화 작업으로 전처리 단계를 수행합니까, 아니면 전처리 작업을하지 않아도 성능상의 불이익을 겪고 있습니까? –