C에서 DSL을 파싱하기위한 lex/yacc보다 나은 솔루션?

Question

내 프로그램 중 하나는 런타임에 명령 (예 : kill foo)을 허용합니다. 도메인 별 언어로 생각하면됩니다. 다음은 몇 가지 예입니다 :

kill 
kill client 
exit 

뿐만 아니라, 체인 명령이 허용 공백 전과 명령 후 중요하지 않습니다있다, 그래서 다음 예는 유효합니다

kill ; say "that was fun" 
    kill ; kill  ; kill; 

나는 현재이 구현 렉스/yacc (플렉스/들소 특정)와 두통이 많이 발생합니다. 렉서는 문맥에 크게 의존합니다 (예를 들어, 공백 토큰은 일반적으로 kill 키워드 이후에 반환되지 않는 한 반환되지 않음). 그리고 여러 가지 상태가 있습니다. 문법은 충돌을 일으키기 때문에 필자는 ($ 1, $ 2, $ 3, ... 비 터미널에 대한 인수를 사용하는) 특히 지정해야하는 형식을 좋아하지 않습니다. 또한 bison이 제공하는 오류 메시지 (구문 분석시)는 정확하지만 때로는 정확하지 않은 경우가 종종 있습니다. (옵션 인수가있는 kill 명령은 kill client 대신에 의 경우 Unexpected $undefined, expected $end or ;과 같은 오류 메시지를 표시합니다). 마지막으로 yacc의 C API는 잔인합니다 (외부에서 정의 된 외부).

위의 질문을 모두 풀어 줄 것을 요구하지는 않습니다. lex/yacc 주위에 방법이 없으면 좀 더 구체적인 설명과 코드로 별도의 스레드를 열어 볼 것입니다. 대신 lex/yacc의 대안에 관심이 있습니다.

• 입력 문자열 (const를 숯불 *)이며, 거기에는 출력되지 않습니다 대신 몇 가지 코드가 각기 다른 키워드를 호출해야합니다 :

  내 기준은 다음과 같습니다.

• C (C99)와 함께 사용하고 싶습니다.
• 소프트웨어는 이미 주요 Linux 배포판에 포함되어 있거나 최소한 번들/패키지로 묶여 있어야합니다.
• 잘 문서화되어야합니다.
• 내 언어를 설명하는 구문은 쉽습니다.
• 구문 분석 오류시 의미있는 오류 메시지를 출력해야합니다.
• 성능은 그다지 중요하지 않습니다 (당연히 빠르지 만 일반적인 사용 사례는 대용량의 MB 명령을 처리하지 않는 대화식 사용입니다).

Answer 1

ANTLR은 프로덕션 시스템에서 두 번 사용했습니다.

버전 2에서는 버전 C에서 C++ 코드는 지원하지만 C는 지원하지 않지만 버전 3에서는 C 코드 생성을 지원하지만 C++은 지원하지 않습니다. 나는 C++을 좋아해 ANTLR v2를 여전히 사용하지만 아마도 v3를 즐기게 될 것입니다. 당신을 위해 훨씬 낫습니다.

많은 배포판에는 ANTLR v2 패키지가 있으며 일부 패키지에는 v3도 포함되어 있습니다. 상당히 잘 문서화되어 있습니다 (v2를 사용하는데, v3가이 점에있어 더 나쁘지 않기를 바랍니다).

ANTLR은 "out of the box"라는 훌륭한 구문 분석 오류 메시지를 생성하지 않습니다. 이것은 가장 일반적인 파서 시스템에 공통적 인 것으로 보이며 근본적으로 해결하기 쉬운 문제는 아닙니다. 그러나 ANTLR 기반 시스템에서 나오는 적절한 진단 출력을 보았습니다. (ANTLR은 여기에 많은 마법을 가지고 있지 않습니다.)

Answer 2

아주 간단하고 작은 문법은 손으로 렉서/파서를 작성하는 것이 좋습니다. 많은 경우 그다지 효과적이지 않습니다.

거의 모든 리눅스 배포판에는 lex/yacc의 변형이 포함되어 있습니다. 그 외에도 널리 사용되는 두 개의 파서 생성기는 lemon과 antlr입니다.

Answer 3

Lacc에 대한 흥미로운 대안 & Yacc는 Lemon 파서입니다. 꽤 많은 일들이 있었지만, 본격적으로 사용하지는 않았으므로 실제로 얼마나 잘 작동하는지 잘 모르겠습니다. 그것은 SQLite에 의해 사용됩니다.

Answer 4

어휘없는 구문 분석기 (예 : PEG 구현)가 필요합니다. C를 사용하고 yacc에 익숙하기 때문에 this 같은 것을 시도해 볼 가치가 있습니다.

문법이 아주 간단하다면, 임시 재귀 파서를 대신 구현할 수 있습니다.

Answer 5

언어가 매우 단순 해 보이므로 입력을 토큰 화하고 구문 분석하는 유한 상태 시스템을 구현하는 것이 좋습니다.

공백에서 토큰 화하면서 (인용 문자열에없는 경우) 입력을 한 번에 한 문자 씩 읽습니다. 각 "명령"은 명령 인수를 구문 분석하는 다른 상태에서 기계를 가져옵니다. ";" 또는 "\ n"기계를 시작 상태로 재설정합니다.

Answer 6

Ragel을 고려해 볼 수 있습니다. 나는 최근에 그것을 사용하기 시작했고, 일단 속도를 높이면 작업 할 수있는 즐거움을 발견했습니다. ragel <filename.rl>와 Ragel 통해

#include <stdio.h> 
#include <string.h> 

%%{ 
    machine my_cmd_lang; 

    action pk { printf("Killing %.*s\n", fpc-mark, mark); } 
    action mk { mark = fpc; } 

    k = 'kill'; # creates a machine that doesn't do anything 
    x = 'exit' @{ printf("Exiting\n"); }; 
    arg = alpha+ >mk; # arg to kill is built in machine 'alpha' 1 or more times 
    cmd = ((k space arg) @pk space* ';'?) | x; 
    main := cmd* ; 
}%% 

%% write data; 

int main(int argc, char* argv[]) { 
    int cs; 
    char* p = "kill client"; 
    char* pe = p + strlen(p); 
    char* mark; 

    %% write init; 
    %% write exec; 

    return 0; 
} 

실행을하며 <filename.c>을 뱉어 : (: 테스트하지! 주) 귀하의 예제에서, 당신은 뭔가를 할 수 있습니다.