GCC와 클랭 파서는 정말 손으로 쓴 건가요?

GCC와 클랭 파서는 정말 손으로 쓴 건가요?

GCC와 LLVM-Clang은 기계 생성되지 않은 Bison-Flex 기반의 상향식 파싱이 아닌 손으로 쓴 재귀 하강 파서를 사용하고 있는 것 같습니다.

여기 계신 분께서 확인 부탁드립니다.그렇다면 왜 메인스트림 컴파일러 프레임워크는 손으로 쓴 파서를 사용하는가?

업데이트: 이 주제에 대한 흥미로운 블로그는 이쪽

C는 해석하기 어렵고 C++는 기본적으로 불가능하다는 민속 이론이 있습니다.

사실이 아니에요.

사실 C와 C++는 파싱 머신을 해킹하거나 심볼 테이블 데이터에 얽히지 않고 LALR(1) 파서를 사용하여 파싱하는 것이 매우 어렵습니다.사실 GCC는 YACC와 이와 같은 추가 해킹을 사용하여 그것들을 해석하곤 했습니다. 그리고 그것은 추악했습니다.현재 GCC는 손으로 쓴 파서를 사용하지만 여전히 기호 테이블 해킹을 사용합니다. Clang 사람들은 자동 파서 생성기를 사용하려 하지 않았습니다. Clang 파서 AFIK는 항상 손으로 코드화된 재귀적 하강입니다.

사실 C와 C++는 GLR 파서 등 자동으로 생성되는 보다 강력한 파서로 해석하기 쉽고 해킹이 필요하지 않습니다.Elsa C++ 파서가 그 예입니다.C++의 프론트 엔드는 다른 것입니다('컴파일러'의 프론트 엔드와 마찬가지로 GLR은 매우 뛰어난 해석 기술입니다).

C++ 프론트 엔드는 GCC만큼 빠르지도 않고 Elsa보다 느리기도 합니다.다른 긴급한 문제가 있기 때문에 신중하게 튜닝하는 데 거의 힘을 들이지 않았습니다(그렇지만 수백만 줄의 C++ 코드에 사용되고 있습니다).엘사는 GCC보다 더 일반적이기 때문에 GCC보다 느릴 수 있습니다.현재의 프로세서 속도를 고려하면, 이러한 차이는 실제로는 그다지 중요하지 않을 수 있습니다.

그러나 오늘날 널리 보급되어 있는 "진짜 컴파일러"는 10년, 20년 이상 전의 컴파일러에 뿌리를 두고 있습니다.비효율성은 훨씬 더 중요했고 아무도 GLR 파서에 대해 들어본 적이 없었기 때문에 사람들은 그들이 할 수 있는 일을 했습니다.클랭은 확실히 더 최근의 것이지만, 민속 이론들은 오랫동안 그들의 "지속성"을 유지한다.

더 이상 그런 식으로 할 필요 없어요.컴파일러의 유지보수성을 향상시키면서 GLR 및 기타 파서를 프런트 엔드로 매우 합리적으로 사용할 수 있습니다.

사실 당신의 친절한 이웃 컴파일러의 행동에 맞는 문법을 얻는 것은 어렵습니다.거의 모든 C++ 컴파일러가 원래 표준의 (대부분)를 실장하고 있습니다만, MS 컴파일러의 DLL 사양 등, 많은 다크 코너 확장자를 가지는 경향이 있습니다.강력한 구문 분석 엔진이 있는 경우 파서 생성기의 제한에 맞춰 문법을 구부리는 것이 아니라 현실에 맞는 최종 문법을 얻으려고 시간을 할애할 수 있습니다.

2012년 11월 편집: 이 답변을 작성한 이후 C++ 프런트 엔드는 ANSI, GNU, MS 변종 사투리를 포함한 완전한 C++11에 대응하도록 개선되었습니다.추가 정보는 많지만 구문 분석 엔진을 변경할 필요는 없습니다.문법 규칙만 개정했습니다.의미 분석을 변경해야 했습니다.C++11은 의미론적으로 매우 복잡하기 때문에 이 작업은 파서를 실행하기 위한 노력을 낭비하고 있습니다.

2015년 2월 편집: ...이제 완전한 C++14를 처리합니다.(간단한 코드의 GLR 구문 분석 및 C++의 악명 높은 "가장 성가신 구문 분석"에 대해서는 c++ 코드에서 사람이 판독할 수 있는 AST를 가져오기를 참조하십시오.

2017년 4월 편집 : C++17을 취급하게 되었습니다.

네:

• GCC는 옛날에 yacc(bison) 파서를 사용했지만 3.x 시리즈의 어느 시점에서는 손으로 쓴 재귀 하강 파서로 대체되었습니다.관련 패치 송신에 대한 링크는 http://gcc.gnu.org/wiki/New_C_Parser을 참조하십시오.

• Clang은 또한 손으로 쓴 재귀적 하강 파서를 사용합니다.http://clang.llvm.org/features.html의 마지막 부분에 있는 "A single unified parser for C, Objective C, C++ and Objective C++" 섹션을 참조하십시오.

Clang의 파서는 다른 오픈 소스 및 상용 C 및 C++ 프런트 엔드와 마찬가지로 손으로 쓴 재귀적 파서입니다.

Clang은 다음과 같은 몇 가지 이유로 재귀적 감소 파서를 사용합니다.

• 퍼포먼스: 손으로 쓴 파서를 사용하면 고속 파서를 쓸 수 있어 필요에 따라 핫 패스를 최적화할 수 있습니다.또, 그 퍼포먼스를 항상 관리할 수 있습니다.고속 파서를 사용함으로써 Clang은 구문 강조 표시 및 IDE 코드 완성 등 "실제" 파서가 일반적으로 사용되지 않는 다른 개발 도구에서 사용할 수 있게 되었습니다.
• 진단 및 오류 복구: 손으로 쓴 재귀 수정 파서를 통해 완전한 제어가 가능하므로 일반적인 문제를 검출하고 뛰어난 진단 및 오류 복구를 제공하는 특수한 사례를 쉽게 추가할 수 있습니다(예: http://clang.llvm.org/features.html#expressivediags) 참조).자동으로 생성된 파서를 사용하면 생성기의 기능으로 제한됩니다.
• 단순성: 재귀파서는 쓰기, 이해 및 디버깅이 용이합니다.파서를 확장/개선하기 위해 파싱 전문가가 되거나 새로운 도구를 배울 필요는 없습니다(오픈 소스 프로젝트에서 특히 중요). 하지만 여전히 훌륭한 결과를 얻을 수 있습니다.

전체적으로 C++ 컴파일러의 경우 그다지 중요하지 않습니다.C++의 해석 부분은 간단하지 않지만 여전히 쉬운 부분 중 하나이기 때문에 단순하게 유지하는 것이 좋습니다.의미 분석(특히 이름 검색, 초기화, 오버로드 해결 및 템플릿 인스턴스화)은 구문 분석보다 훨씬 복잡합니다.증명하려면 Clang의 "Sema" 컴포넌트(시맨틱 분석용)와 "Parse" 컴포넌트(파싱용)의 코드 및 커밋 분포를 확인하십시오.

이상한 대답이야!

C/C++ 문법은 문맥이 자유롭지 않습니다.Foo * 바, 모호성 때문에 문맥에 민감합니다.Foo가 타입인지 아닌지를 알기 위해 typedefs 목록을 작성해야 합니다.

Ira Baxter:난 네 GLR이 무슨 의미가 있는지 모르겠어.왜 애매모호하게 구성된 해석 트리를 만드나요?구문 분석이란 애매한 부분을 해결하고 구문 트리를 구축하는 것을 의미합니다.이 애매모호함을 두 번째 경로로 해결하면, 이것은 덜 추악하지 않습니다.나한텐 그게 훨씬 더 못생겼어...

Yacc는 LR(1) 파서 제너레이터(또는 LALR(1))이지만 상황에 따라 쉽게 변경할 수 있습니다.그리고 그 안에는 추악한 것이 없다.Yacc/Bison은 C 언어 해석을 지원하기 위해 작성되었기 때문에 C 파서를 생성하는 가장 추악한 도구는 아닐 것입니다.

GCC 3.x까지 C 파서는 yacc/bison에 의해 생성되어 해석 중에 typedefs 테이블이 구축됩니다."in parse" typedefs 테이블을 구축하면 C 문법은 로컬 컨텍스트에서 자유로워지고 더 나아가 "localally LR(1)"가 됩니다.

Gcc 4.x에서는 재귀 하강 파서입니다.이는 Gcc 3.x의 파서와 완전히 동일하며 여전히 LR(1)이며 문법 규칙도 동일합니다.차이점은 yacc 파서는 손으로 고쳐졌고, 시프트/스택은 콜스택에 숨겨져 있습니다.gcc 3.x yacc 파서에서와 같이 (nextsym == '(') goto state398'은 존재하지 않기 때문에 패치 적용, 오류 처리 및 보다 나은 메시지 인쇄가 용이하며, 다음 단계의 일부 컴파일 작업을 수행할 수 있습니다.gcc noob을 위한 훨씬 적은 "읽기 쉬운" 코드 가격.

왜 그들은 yacc에서 재귀 강하로 전환했을까요?C++를 해석하기 위해서는 yacc를 피하는 것이 매우 필요하며, GCC는 다중 언어 컴파일러, 즉 컴파일할 수 있는 다른 언어 간에 최대 코드 공유를 꿈꾸기 때문입니다.따라서 C++와 C 파서는 같은 방법으로 기술됩니다.

C++는 C로서 「로컬」LR(1)이 아니고, LR(k)도 아니기 때문에, C보다 해석하기 어렵습니다.보다func<4 > 2>이것은 4 > 2로 인스턴스화된 템플릿 함수입니다.func<4 > 2>라고 읽어야 한다func<1>이것은 LR(1)이 아닙니다.자, 생각해 보세요.func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>여기서 재귀적 강하로 애매함을 쉽게 해결할 수 있습니다(parse_template_parameter는 애매한 파서 함수입니다).parse_template_parameter(17tokens)에 실패한 경우 parse_template_parameter(15tokens)와 parse_template_parameter(13tokens)를 다시 시도합니다.동작할 때까지).

왜 yacc/bison 재귀 서브그램에 추가할 수 없는지 모르겠습니다만, 이것이 gcc/GNU 파서 개발의 다음 단계가 되지 않을까요?

GCC와 LLVM-Clang은 기계 생성되지 않은 Bison-Flex 기반의 상향식 파싱이 아닌 손으로 쓴 재귀 하강 파서를 사용하고 있는 것 같습니다.

특히 바이슨은 애매하게 해석하고 나중에 두 번째 패스를 하지 않으면 문법을 다룰 수 없다고 생각합니다.

Haskell's Happy는 C 구문을 사용하여 특정 문제를 해결할 수 있는 모노딕(상태 의존) 파서를 허용하지만 사용자가 제공한 상태 모나드를 허용하는 C 파서 생성기는 없습니다.

In theory, error recovery would be a point in favor of a handwritten parser, but my experience with GCC/Clang has been that the error messages are not particularly good.

As for performance - some of the claims seem unsubstantiated. Generating a big state machine using a parser generator should result in something that's O(n) and I doubt parsing is the bottleneck in much tooling.

gcc's parser is handwritten.. I suspect the same for clang. This is probably for a few reasons:

• Performance: something that you've hand-optimized for your particular task will almost always perform better than a general solution. Abstraction usually has a performance hit
• Timing: at least in the case of GCC, GCC predates a lot of free developer tools (came out in 1987). There was no free version of yacc, etc. at the time, which I'd imagine would've been a priority to the people at the FSF.

This is probably not a case of "not invented here" syndrome, but more along the lines of "there was nothing optimized specifically for what we needed, so we wrote our own".

ReferenceURL : https://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten