8 비트 임베디드 시스템에서 사용할 수있는 flex / bison에 대한 대안이 있습니까?

8 비트 임베디드 시스템에서 사용할 수있는 flex / bison에 대한 대안이 있습니까?

---

avr-gcc 툴체인을 사용하여 C의 AVR 마이크로 컨트롤러에 대한 연습으로 언어와 같은 간단한 BASIC에 대한 작은 인터프리터를 작성하고 있습니다. 그러나 렉서와 파서를 작성하는 데 도움이 될 수있는 오픈 소스 도구가 있는지 궁금합니다.

내 Linux 상자에서 실행되도록 작성하려면 flex / bison을 사용할 수 있습니다. 이제 8 비트 플랫폼으로 제한 했으므로 모든 작업을 수작업으로해야합니까?

---

ATmega328p를 대상으로하는 간단한 명령 언어에 대한 파서를 구현했습니다 . 이 칩에는 32k ROM과 2k RAM 만 있습니다. RAM은 확실히 더 중요한 제한 사항입니다. 아직 특정 칩에 묶여 있지 않은 경우 가능한 한 많은 RAM이있는 하나를 선택하십시오. 이것은 당신의 삶을 훨씬 더 쉽게 만들 것입니다.

처음에는 flex / bison 사용을 고려했습니다. 나는 두 가지 주요 이유로이 옵션에 반대하기로 결정했습니다.

• 기본적으로 Flex & Bison은 사용할 수 없거나 avr-libc에서 동일하게 작동하지 않는 일부 표준 라이브러리 기능 (특히 I / O 용)에 의존합니다. 지원되는 해결 방법이 있다고 확신하지만 이것은 고려해야 할 추가 노력입니다.
• AVR에는 하버드 아키텍처가 있습니다. C는이를 설명하도록 설계되지 않았으므로 상수 변수도 기본적으로 RAM에로드됩니다 . 플래시 및 EEPROM에 데이터를 저장하고 액세스하려면 특수 매크로 / 기능을 사용해야합니다 . Flex & Bison은 상대적으로 큰 룩업 테이블을 생성 하며이 테이블은 RAM을 매우 빠르게 소모합니다. 내가 착각하지 않는 한 (가능한) 특별한 플래시 및 EEPROM 인터페이스를 활용하기 위해 출력 소스를 편집해야합니다.

Flex & Bison을 거부 한 후 다른 생성기 도구를 찾았습니다. 제가 고려한 몇 가지 사항은 다음과 같습니다.

• 레몬
• Ragel
• re2c

Wikipedia의 비교를 살펴볼 수도 있습니다 .

궁극적으로 나는 어휘 분석기와 파서를 모두 직접 코딩했습니다.

파싱을 위해 재귀 하강 파서를 사용했습니다. 내 생각 아이라 박스터는 이미이 주제를 다루는의 적절한 일을하고 있으며, 튜토리얼의 많은 온라인이 있습니다.

내 어휘 분석기를 위해 모든 터미널에 대한 정규식을 작성하고 동등한 상태 머신을 다이어그램으로 작성하고 상태 goto간 점프를 위해 's를 사용하여 하나의 거대한 함수로 구현했습니다 . 이것은 지루했지만 결과는 훌륭했습니다. 여담으로, goto상태 머신을 구현하기위한 훌륭한 도구입니다 - 당신의 모든 상태가 바로 옆에 관련 코드에 대한 명확한 라벨을 가질 수 있습니다, 거기에 어떤 함수 호출 또는 상태 변수의 오버 헤드가 없으며, 그것에 대해 최대한 빨리 얻을 수 있습니다. C는 실제로 정적 상태 머신을 구축하기위한 더 나은 구조를 가지고 있지 않습니다.

생각할 것 : 어휘 분석기는 파서의 전문 화일뿐입니다. 가장 큰 차이점은 일반적인 문법은 어휘 분석에 일반적으로 충분하지만 대부분의 프로그래밍 언어에는 (대부분) 문맥없는 문법이 있다는 것입니다. 따라서 렉서를 재귀 하강 파서로 구현하거나 파서 생성기를 사용하여 렉서를 작성하는 것을 막을 수는 없습니다. 일반적으로 더 전문화 된 도구를 사용하는 것만 큼 편리하지 않습니다.

---

파서를 코딩하는 쉬운 방법을 원하거나 공간이 부족한 경우 재귀 하강 파서를 직접 코딩해야합니다. 이들은 본질적으로 LL (1) 파서입니다. 이것은 Basic처럼 "단순"한 언어에 특히 효과적입니다. (나는 70 년대에이 중 몇 가지를했다!). 좋은 소식은 라이브러리 코드가 포함되어 있지 않다는 것입니다. 당신이 쓰는 그대로.

이미 문법이 있다면 코딩하기가 매우 쉽습니다. 먼저 왼쪽 재귀 규칙을 제거해야합니다 (예 : X = XY). 이것은 일반적으로 매우 쉽기 때문에 연습으로 남겨 둡니다. (목록 형성 규칙에는이 작업을 수행 할 필요가 없습니다. 아래 설명 참조).

다음 형식의 BNF 규칙이있는 경우 :

 X = A B C ;

규칙 (X, A, B, C)의 각 항목에 대해 "I saw the 해당 구문 구조를 보았다"라는 부울을 반환하는 서브 루틴을 만듭니다. X의 경우 코드 :

subroutine X()
     if ~(A()) return false;
     if ~(B()) { error(); return false; }
     if ~(C()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end X;

A, B, C도 마찬가지입니다.

토큰이 터미널 인 경우 터미널을 구성하는 문자열의 입력 스트림을 확인하는 코드를 작성하십시오. 예를 들어 숫자의 경우 입력 스트림에 숫자가 포함되어 있는지 확인하고 입력 스트림 커서를 숫자를지나 앞으로 이동합니다. 버퍼 스캔 포인터를 전진 시키거나 전진시키지 않음으로써 버퍼에서 파싱하는 경우 특히 쉽습니다 (BASIC의 경우 한 번에 한 줄씩 가져 오는 경향이 있음). 이 코드는 본질적으로 파서의 렉서 부분입니다.

BNF 규칙이 재귀 적이라면 ... 걱정하지 마십시오. 재귀 호출을 코딩하기 만하면됩니다. 이것은 다음과 같은 문법 규칙을 처리합니다.

T  =  '('  T  ')' ;

다음과 같이 코딩 할 수 있습니다.

subroutine T()
     if ~(left_paren()) return false;
     if ~(T()) { error(); return false; }
     if ~(right_paren()) { error(); return false; }
     // insert semantic action here: generate code, do the work, ....
     return true;
end T;

대안이있는 BNF 규칙이있는 경우 :

 P = Q | R ;

그런 다음 대체 선택 사항으로 P를 코딩합니다.

subroutine P()
    if ~(Q())
        {if ~(R()) return false;
         return true;
        }
    return true;
end P;

Sometimes you'll encounter list forming rules. These tend to be left recursive, and this case is easily handled. The basic idea is to use iteration rather than recursion, and that avoids the infinite recursion you would get doing this the "obvious" way. Example:

L  =  A |  L A ;

You can code this using iteration as:

subroutine L()
    if ~(A()) then return false;
    while (A()) do { /* loop */ }
    return true;
end L;

You can code several hundred grammar rules in a day or two this way. There's more details to fill in, but the basics here should be more than enough.

If you are really tight on space, you can build a virtual machine that implements these ideas. That's what I did back in 70s, when 8K 16 bit words was what you could get.

---

If you don't want to code this by hand, you can automate it with a metacompiler (Meta II) that produces essentially the same thing. These are mind-blowing technical fun and really takes all the work out of doing this, even for big grammars.

August 2014:

I get a lot of requests for "how to build an AST with a parser". For details on this, which essentially elaborates this answer, see my other SO answer https://stackoverflow.com/a/25106688/120163

July 2015:

There are lots of folks what want to write a simple expression evaluator. You can do this by doing the same kinds of things that the "AST builder" link above suggests; just do arithmetic instead of building tree nodes. Here's an expression evaluator done this way.

---

You can use flex/bison on Linux with its native gcc to generate the code that you will then cross-compile with your AVR gcc for the embedded target.

---

GCC can cross-compile to a variety of platforms, but you run flex and bison on the platform you're running the compiler on. They just spit out C code that the compiler then builds. Test it to see how big the resulting executable really is. Note that they have run time libraries (libfl.a etc.) that you will also have to cross compile to your target.

---

Try Boost::Spirit. It's a header-only library which you can drop in and build a very fast, clean parser completely in C++. Overloaded operators in C++ are used instead of a special grammar file.

---

바퀴를 다시 발명하는 대신 LUA : www.lua.org를 살펴 보십시오 . 다른 소프트웨어에 내장되고 내장 시스템과 같은 소규모 시스템에서 사용되는 해석 언어입니다. 내장 된 절차 적 구문 구문 분석 트리, 제어 로직, 수학 및 변수 지원-수천 명의 다른 사람들이 이미 디버깅하고 사용했던 것을 재발 명 할 필요가 없습니다. 그리고 확장 가능합니다. 즉, 자체 C 함수를 추가하여 문법에 추가 할 수 있습니다.

참고 URL : https://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems