2009-04-21 3 views
7

큰 상용 응용 프로그램에서 사용자 지정 텍스트 파일 형식을 읽을 때 사용할 수있는 훌륭한 파서 생성기를 찾고 있습니다. 현재이 특정 파일 형식은 수작업 재귀 파서로 읽혀 지지만 그 형식이 성장하고 복잡해지면서 그 접근법은 관리하기 어려워졌습니다.제한된 메모리가있는 C++ 응용 프로그램에 가장 적합한 ANTLR 파서 생성기입니까?

궁극적 인 해결책은이 형식에 맞는 적절한 문법을 ​​작성한 다음 yacc과 같은 실제 파서 생성기를 사용하여 읽는 것일 수 있지만 사용하려고하는 생성기를 결정하는 데 문제가 있습니다. 문제의 가치가있는 것입니다. 저는 ANTLR과 Spirit을 살펴 봤습니다. 그러나 우리 프로젝트는 earlier answers 이상의 특수한 제약 조건을 가지고있어서 우리에게 적절한지 궁금합니다. 특히, 나는 다음을 필요로한다 :

  • MSVC로 C 코드 또는 C++ 코드를 생성하는 파서. ANTLR 3은 C++을 지원하지 않습니다. 그것은 똑바로 C를 생성한다고 주장하지만, 실제로 작동하도록하기위한 문서는 혼란 스럽습니다.
  • 심각하게 제한된 메모리 사용. 메모리는 우리 앱에서 엄청난 프리미엄을 받고 있으며 심지어 작은 누출도 치명적입니다. 나는 우리의 커스텀 malloc()을 사용하기 위해 파서의 메모리 할당자를 오버라이드 할 수 있어야한다. 또는 적어도 모든 메모리를 가져 오는 인접한 풀을 제공해야한다. (그리고 이후에 일괄 블록을 할당 취소 할 수있다.) 나는 파서 실행 파일 자체에 대해 약 200kb를 남겨 둘 수 있지만 파싱에 할당 된 동적 힙은 이후에 해제되어야한다.
  • 성능이 좋습니다. 이것은 덜 비판적이지만 3ghz 프로세서에서 1 초 내에 100kb의 텍스트를 파싱 할 수 있어야합니다.
  • GPL이 필요합니다. 우리는 GNU 코드를 사용할 수 없습니다.

나는 ANTLRworks의 IDE 및 디버깅 도구를 좋아하지만, C 타겟을 실제로 응용 프로그램과 함께 사용하는 것이 큰 사업이 될 것으로 보인다. 내가 그 palaver에 착수하기 전에 ANTLR이이 일에 적합한 도구입니까?

는 문제의 텍스트 형식과 같이 보입니다 :

attribute "FluxCapacitance" real constant 

asset DeLorean 
{ 
    //comment foo bar baz 
    model "delorean.mdl" 
    animation "gullwing.anm" 
    references "Marty" 
    loadonce 
} 

template TimeMachine 
{ 
    attribute FluxCapacitance 10  
    asset DeLorean 
} 

답변

4

ANTLR 3은 C++를 지원하지 않습니다. 그것은 가 C를 생성한다고 주장하지만 실제로 작동하려면 에있는 문서는 입니다.

C를 생성하고 Visual Studio 및 C++에서도 작동합니다. 이전에 해본 적이 있고 stdcall과 함께 작동하도록 패치를 제출했기 때문에 이것을 알 수 있습니다.

메모리는 우리 앱의 큰 프리미엄이며 이며 작은 누출도 치명적입니다. 나는 모든 메모리를 그립니다 (그리고 에서 그것을 연속 풀을 제공하기 위해 나는 필요 최소한 우리의 사용자에게 의 malloc(), 또는를 사용하도록 파서의 메모리 할당을 재정의 할 수 이 필요한 내가 할 수있는 블록 할당 해제 후 ). 파서 실행 파일 자체에 대해 약 120kb의 을 예비 할 수 있지만 파싱에서 할당하는 동적 힙이 모두 해제 된 후에 이 해제되어야합니다.

마지막으로 확인한 antlr3c 런타임은 메모리 누수가 없으며 사용자가 설명하는 메모리 풀 패러다임을 사용합니다. 그러나 저자가 변경을 거부 한 API에는 단점이 하나 있습니다. 즉, 노드의 문자열을 요청하면 매번 파서를 해제 할 때까지 매번 새로운 사본이 생성됩니다.

사용자 정의 malloc 사용의 용이성에 대해서는 언급하지 않았지만 전체 프로젝트에서 사용할 malloc 기능을 정의하는 매크로가 있습니다.

실행 파일의 크기는 작은 인터프리터를 포함하여 약 100KB입니다.

내 제안은 ANTLR을 계속 학습하는 것입니다. ANTLR은 여전히 ​​요구 사항에 맞고 일하기 전에 약간의 시간을 희생해야하기 때문입니다.

+1

ANTL3은 C++을 지원합니다. https://theantlrguy.atlassian.net/wiki/pages/viewpage.action?pageId=2687097이 대답을 업데이트해야합니다. –

0

ANTLR 파서를, 실제로 뭔가 LALR 등으로 내장 파서는 큰 경향이있다. 당신은 이것에 대한 실제 문법을 가지고 있습니까? 처럼 보이지만 손으로 ​​쓰는 재귀 적 파서로 가장 쉽게 파싱 될 수 있지만 샘플은별로 없습니다.

죄송합니다. ANTLR이 실수로 재귀 - 강하를 생성합니다. 여전히 ANTLR에서 큰 파서를 생성하는 데 문제가 있습니다.

+0

그것은 단지 작은 샘플입니다 - 우리는 현재 형식의 손으로 쓴 파서를 할 수 있지만, 유지 보수 및 추가 새로운 기능이 비참한 악몽 너무 복잡되고있다. ANTLR로 파싱하는 것이 더 쉬울 지, 아니면 더 힘들지는 않은지 궁금합니다. ANTLRworks에서 우리 형식에 대한 LR 문법을 만들었지 만 문법 검사는 괜찮은 것처럼 보이지만 다음 단계는 실제로 C 작업을 연결하여 프로그램에 연결하는 것입니다. – Crashworks

+0

생성 된 파서의 크기는 얼마나됩니까? 추한 부분은 일반적으로 파서 구조 자체입니다. –

+0

알다시피, 당신은 내가 ANTLR book을 read to stack으로 옮길 것을 확신했습니다. ANTLR v3은 내가 2005-2006 년에보고 있던 몇 가지 문제를 해결할 수 있습니다. –

4

우리는 Boost Spirit을 성공적으로 사용합니다. Boost license은 매우 자유로운 제품이므로 상용 응용 프로그램에서 문제없이 사용할 수 있습니다.

Quote from the documentation:

성령

는 객체 지향 재귀 하강 파서 생성기 프레임 워크는 템플릿 메타 프로그래밍 기법을 사용하여 구현됩니다. Expression 템플릿을 사용하면 C++에서 EBNF (Extended Backus-Normal Form) 구문을 완전히 근사 할 수 있습니다. Spirit 프레임 워크를 사용하면 대상 문법을 독점적으로 C++로 작성할 수 있습니다.인라인 EBNF 문법 스펙은 다른 C++ 코드와 자유롭게 혼합 할 수 있으며 C++ 템플릿의 생성력 덕분에 즉시 실행 가능합니다. 되돌아 보면 기존 컴파일러 컴파일러 또는 파서 생성기는 소스 EBNF 코드에서 C 또는 C++ 코드로 추가 변환 단계를 수행해야합니다.

1

그럼 flex/yacc을 사용하지 않으시겠습니까? 그것은 MSVC에서 실행될 수있는 C 코드를 생성하고, 효율성을 염두에두고 개발되었으며, malloc (yymalloc 용 google)을 재정의 할 수 있습니다. 이들은 GPL이지만 결과 코드 (프로젝트에서 사용하는 코드)는 AFAIK가 아닙니다.

또는 손으로 만든 파서를 사용하십시오.

0

실제적으로 문법이 비교적 작고 모호성이나 구문 분석 복잡성이 많지 않은 경우 재귀 적 파생 파서 또는 시프트 - 감소 파서를 사용하면 문제가되지 않습니다.

필자는 ANTLR과 Spirit을 살펴보고 Flex와 Bison을 살펴 보겠습니다. Coco/R (C++을 비롯한 많은 언어의 생성자 포함)과 같이 잘 알려지지 않은 파서도 있습니다.

+0

들소는 좋지 않습니다. 우리는 GPL이 없어야합니다. – Crashworks

2

직접 코딩 된 재귀 적 파서는 실제로 매우 빠르며 은 매우 콤팩트 할 수 있습니다. 유일한 단점은 본질적으로 LL (1) 문법을 코드화 할 때주의해야한다는 것입니다 ( ).[ANTLR을 사용하는 경우 과 비슷한 제한 사항이 있으므로 큰 거래는 아닙니다.]

일반 재귀 C 코드와 같은 파서 코드를 사용할 수 있습니다. 당신이 공간에 정말 꽉 경우

, 당신은 구문 분석 가상 머신을 정의 할 수 있습니다, 그것을 실행하는 작은 C 인터프리터를 구축 : ( Is there an alternative for flex/bison that is usable on 8-bit embedded systems?이 완료 자세한 내용은이 답변을 참조). 저는 70 년대 초반에이 방식으로 기본 통역사를 만들었습니다.

이 파서가 실제로 작동하게하는 매우 간단한 규칙을 고수하면 구문 분석 기계로 인한 메모리 누수가 발생하지 않습니다. 이 보장됩니다. (물론, 당신은 관심있는 아이템 인 을 인식하는 파서에 임의의 액션을 첨부 할 수 있으며, 그러한 액션이 누출되는지 여부는 파서가 아닌 일반 프로그래밍의 입니다.

아이디어는 metacompilers에 관한 1964 년의 논문에서 나온 것입니다. Val Schorre는 10 페이지에 완전한 컴파일러를 만드는 방법을 보여줍니다. Shorre의 작은 파서 생성기는 꽤 좋은 반복적 인 하강 파서를 생성합니다. 어떻게 같은 파서를 구축하는 방법을 정확하게 보여주는이 논문과 을 설명하는 사이트는 내가 손으로 코딩 복잡한 문법 질린 후, 70 년대 후반에 을 기본 컴파일러를 구축하는 Schorre의 방법을 사용 http://www.bayfronttechnologies.com/metaii.html

에서 찾을 수 있습니다.

관련 문제