YACC/BYACC/Bison 및 Lex/Flex에 적절한 용도

StackOverflow https://stackoverflow.com/questions/2414303

  •  19-09-2019
  •  | 
  •  

문제

내가이 유틸리티와 관련하여 읽은 대부분의 게시물은 일반적으로 다른 방법을 사용하여 동일한 효과를 얻는 것이 좋습니다. 예를 들어, 이러한 도구를 평소에 언급하는 질문은 다음 중 일부를 포함하는 하나 이상의 답변이 있습니다.

  • 부스트 라이브러리를 사용하십시오 (여기에 적절한 부스트 라이브러리 삽입)
  • DSL 사용을 만들지 마십시오 (여기에 좋아하는 스크립팅 언어 삽입)
  • Antlr이 더 좋습니다

개발자를 가정 ...

  • ... C 언어에 편안합니다
  • ... 적어도 하나의 스크립팅 언어 (예 : Python, Perl 등)를 알고 있습니다.
  • ... 거의 모든 프로젝트에서 몇 가지 구문 분석 코드를 작성해야합니다.

그래서 내 질문은 다음과 같습니다.

  • 이 유틸리티에 적합한 적절한 상황은 무엇입니까?
  • YACC 및 LEX (또는 파생 상품)보다 문제에 대한 더 나은 대안이없는 (합리적인) 상황이 있습니까?
  • 실제 구문 분석 문제에서 얼마나 자주 최근 솔루션으로 더 잘 해결되는 YACC와 LEX의 짧은 연합에 빠질 것으로 기대할 수 있습니까?
  • 이러한 도구에 아직 익숙하지 않은 개발자에게는 구문/관용을 배우는 데 시간을 투자하는 것이 가치가 있습니까? 이것들은 다른 솔루션과 어떻게 비교됩니까?
도움이 되었습니까?

해결책

Lex/YACC와 파생물이 오늘날 유비쿼터스 인 것처럼 보이는 이유는 다른 도구보다 훨씬 오래 걸렸고 문헌에 훨씬 더 많은 범위를 가지고 있으며 전통적으로 유닉스 운영 체제와 함께 왔기 때문입니다. 다른 Lexer 및 Parser Generator 도구와 비교하는 방법과는 거의 관련이 없습니다.

어떤 도구를 선택하든 항상 중요한 학습 곡선이있을 것입니다. 따라서 주어진 도구를 몇 번 사용하고 사용이 비교적 편안 해지면 다른 도구를 배우는 추가 노력을 원할 것 같습니다. 그것은 자연스러운 일입니다.

또한 LEX/YACC가 만들어진 1960 년대 후반과 1970 년대 초반에 하드웨어 제한은 구문 분석에 심각한 도전을 제기했습니다. YACC가 사용하는 테이블 중심 LR 구문 분석 방법은 비교적 작은 일반 프로그램 논리를 사용하고 테이프 또는 디스크의 파일에 상태를 유지함으로써 작은 메모리 풋 프린트로 구현 될 수 있기 때문에 당시 가장 적합했습니다. LL과 같은 코드 중심 구문 분석 방법은 파서 프로그램의 코드 자체가 문법을 나타내므로 전체 RAM에 맞아야하고 RAM의 스택에 상태를 유지해야하기 때문에 최소 메모리 풋 프린트가 더 큽니다.

메모리가 더욱 풍부 해지면 LL 및 PEG와 같은 다른 구문 분석 방법과 이러한 방법을 사용하여 도구를 구축하는 방법에 대한 연구가 훨씬 더 많았습니다. 이는 LEX/YACC 패밀리 이후에 만들어진 대체 도구가 다른 유형의 문법을 사용한다는 것을 의미합니다. 그러나 문법 유형을 전환하면 상당한 학습 곡선이 발생합니다. LR 또는 LALR 문법과 같은 한 가지 유형의 문법에 익숙해지면 LL 문법과 같은 다른 유형의 문법을 사용하는 도구로 전환 할 가능성이 적습니다.

전반적으로, LEX/YACC 도구 제품군은 일반적으로 문법과 문법 충돌을 그래픽으로 시각화하거나 자동 리팩토링을 통해 갈등을 해결하기 위해 종종 정교한 사용자 인터페이스를 갖는 최신 도착보다 더 기초적입니다.

따라서 파서 도구에 대한 사전 경험이 없다면 어쨌든 새로운 도구를 배워야한다면 문법 및 갈등의 그래픽 시각화, 자동 반박, 좋은 문서의 가용성, 언어와 같은 다른 요소를 살펴 봐야합니다. 생성 된 Lexers/Parsers는 출력 등이 될 수 있습니다. 단순히 "다른 사람들이 사용하는 것 같습니다".

다음은 Lex/YACC 또는 Flex/Bison을 사용하는 데 생각할 수있는 몇 가지 이유입니다.

  • 개발자는 이미 LEX/YACC 또는 Flex/Bison에 익숙합니다.
  • 개발자는 LR/LALR 문법에 가장 친숙하고 편안합니다.
  • 개발자는 Lex/YACC를 다루는 많은 책을 가지고 있지만 다른 책을 다루는 책은 없습니다.
  • 개발자는 예비 구인 제안이 다가오고 있으며 Lex/YACC 기술이 고용 될 기회를 증가시킬 것이라고 들었습니다.
  • 개발자는 다른 도구를 사용하기 위해 프로젝트 회원/이해 관계자로부터 구매를받을 수 없습니다.
  • 환경에는 LEX/YACC가 설치되어 있으며 어떤 이유로 다른 도구를 설치할 수 없습니다.

다른 팁

이러한 도구를 배울 가치가 있는지 여부에 관계없이 크게 의존 할 것입니다 (거의 전적으로 귀하가 작성하는 코드의 양 또는 일반 순서에 대해 더 많은 코드를 작성하는 데 관심이있는 관심에 관심이 있습니다. .

당신이 사용하는 도구는 많은 사람들이 믿는 것만 큼 큰 차이를 만들지 않습니다. 내가 다루어야 할 입력의 약 95%에 대해, 최선의 선택은 단순히 내가 가장 친숙하고 편안한 선택이라는 것이 충분한 차이는 없습니다.

물론 Lex와 YACC는 C (또는 C ++)에 동작을 작성해야합니다 (또는 C ++). 당신이 그들에게 편안하지 않다면, 당신이 선호하는 언어를 사용하고 생산하는 도구 (예 : Python 또는 Java)는 의심 할 여지없이 훨씬 더 나은 선택이 될 것입니다. 나는 당신이 익숙하지 않거나 불편한 언어로 이와 같은 도구를 사용하는 것을 조언하지 않을 것입니다. 특히 컴파일러 오류를 생성하는 작업에 코드를 작성하면 문제를 추적하는 데있어 평소보다 컴파일러로부터 도움이 덜 도움이되므로 문제를 인식 할 수있는 언어에 익숙해야합니다. 컴파일러가 무언가 잘못되었는지에 대한 최소한의 힌트만으로.

이전 프로젝트에서는 비교적 비 기술적 인 사람이 사용할 수있는 쉬운 방식으로 임의의 데이터에 대한 쿼리를 생성 할 수있는 방법이 필요했습니다. 데이터는 CRM 유형의 물건 (따라서 이름, 성, 이메일 주소 등) 이었지만 다양한 데이터베이스에 대해 다른 스키마를 사용하는 것이 었습니다.

그래서 나는 쿼리를 지정하기 위해 작은 DSL을 개발했습니다 (예 : [FirstName] = 'joe'및 [lastName] = 'bloggs'는 "Joe Bloggs"라는 모든 사람을 선택합니다). 예를 들어 특정 매체 (이메일, SMS 등)에서 메시지 수신을 선택한 모든 사람들을 선택하는 "Optedout (medium)"구문이 예를 들어 더 복잡한 옵션이있었습니다. 특정 그룹의 모든 사람을 선택하는 "Ingroup (XYZ)"이있었습니다.

기본적으로 "Ingroup ( 'groupa') 및 Ingroup ( 'groupb')과 같은 쿼리를 지정할 수있게 해주었다.

SELECT
    *
FROM
    Users
WHERE
    Users.UserID IN (SELECT UserID FROM GroupMemberships WHERE GroupID=2) AND
    Users.UserID NOT IN (SELECT UserID GroupMemberships WHERE GroupID=3)

(보시다시피, 쿼리는 가능한 한 효과적이지 않지만 그것이 기계 생성으로 얻는 것입니다).

나는 그것을 위해 Flex/Bison을 사용하지 않았지만, 파서 생성기를 사용했습니다 (그 이름은 지금 나를 탈출했습니다 ...)

도메인 특정 언어를 지원하기 위해 새로운 언어를 만드는 것이 꽤 좋은 조언이라고 생각합니다. 기존 언어를 사용하여 도메인 기능으로 확장하는 데 시간을 더 잘 사용할 것입니다.

다른 이유, 아마도 언어 설계에 대한 연구를 위해 새로운 언어를 만들려고한다면 이러한 도구는 약간 구식입니다. ANTLR과 같은 새로운 발전기 또는 ML과 같은 최신 구현 언어는 언어 디자인을 훨씬 쉽게 수행합니다.

이러한 도구를 사용해야할만한 충분한 이유가 있다면 아마도 유산 때문일 것입니다. 당신은 이미 이러한 도구 중 하나에서 이미 구현 된 강화 해야하는 언어의 골격을 가지고있을 수 있습니다. 또한이 오래된 도구에 대해 쓰여진 엄청난 양의 튜토리얼 정보로부터 혜택을 볼 수 있습니다.이 도구는 언어를 구현하는 새롭고 매끄러운 방법을 위해 쓰여진 코퍼스가 없습니다.

우리는 내 사무실에 전체 프로그래밍 언어를 구현했습니다. 우리는 그것을 위해 그것을 사용합니다. 나는 그것이 통역사를 쓰는 빠르고 쉬운 방법이라고 생각합니다. 당신은 아마도 거의 모든 종류의 텍스트 파서를 사용하여 쓸 수 있지만, 많은 a) a) 직접 작성하기가 더 쉽거나 b) 그들이 제공하는 것보다 더 많은 유연성이 필요합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top