GCC 및 Clang 파서는 실제로 손으로 작성됩니까?

GCC 및 Clang 파서는 실제로 손으로 작성됩니까?

---

GCC와 LLVM-연타 사용하고있는 것으로 보인다 필기 재귀 하강 파서를 , 그리고 하지 생성, 들소 플렉스를 기반으로, 아래에서 위로 구문 분석 기계.

여기 누군가가 이것이 사실인지 확인해 주시겠습니까? 그렇다면 주류 컴파일러 프레임 워크는 왜 손으로 쓴 파서를 사용합니까?

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

---

예:

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

• Clang은 또한 손으로 작성한 재귀 하강 파서를 사용합니다 . http://clang.llvm.org/features.html 끝 부분에있는 "C, Objective C, C ++ 및 Objective C ++ 용 단일 통합 파서"섹션을 참조 하십시오 .

---

C는 구문 분석하기 어렵고 C ++는 본질적으로 불가능하다는 민중 정리가 있습니다.

사실이 아닙니다.

사실은 C와 C ++는 구문 분석 기계를 해킹하고 기호 테이블 데이터를 엉키지 않고 LALR (1) 구문 분석기를 사용하여 구문 분석하기가 매우 어렵다는 것입니다. 실제로 GCC는 YACC와 이와 같은 추가 해커를 사용하여 구문을 분석하는 데 사용되었으며, 그렇습니다. 이제 GCC는 손으로 쓴 파서를 사용하지만 여전히 기호 테이블 해커를 사용합니다. Clang 사람들은 자동화 된 파서 생성기를 사용하지 않았습니다. Clang 파서 AFAIK는 항상 수동으로 코딩 된 재귀 하강입니다.

사실은 C와 C ++는 GLR 파서 와 같은 강력한 자동 생성 파서로 비교적 쉽게 파싱 할 수 있으며 해킹이 필요하지 않다는 것입니다. 엘사 C ++ 파서는이 하나의 예이다. 우리의 C ++ 프런트 엔드 는 또 다른 것입니다 (모든 "컴파일러"프런트 엔드와 마찬가지로 GLR은 매우 훌륭한 구문 분석 기술입니다).

우리의 C ++ 프론트 엔드는 GCC만큼 빠르지 않고 확실히 Elsa보다 느립니다. 우리는 다른 더 긴급한 문제가 있기 때문에 신중하게 튜닝하는 데 약간의 에너지를 쏟았습니다 (그러나 수백만 줄의 C ++ 코드에서 사용되었습니다). Elsa는 더 일반적이기 때문에 GCC보다 느릴 수 있습니다. 요즘 프로세서 속도를 감안할 때 이러한 차이는 실제로별로 중요하지 않을 수 있습니다.

그러나 오늘날 널리 배포되는 "실제 컴파일러"는 10 년 또는 20 년 전 또는 그 이상의 컴파일러에 뿌리를두고 있습니다. 비 효율성은 훨씬 더 중요했고 아무도 GLR 파서에 대해 들어 본 적이 없었기 때문에 사람들은 자신이 할 줄 아는대로했습니다. Clang은 확실히 더 최근이지만 민속 정리는 오랫동안 "설득력"을 유지합니다.

더 이상 그렇게 할 필요가 없습니다. 컴파일러 유지 관리 기능이 향상되어 GLR 및 기타 파서를 프런트 엔드로 매우 합리적으로 사용할 수 있습니다.

무엇 이며 사실, 당신의 다정한 이웃 컴파일러의 동작에 알맞은 문법을 얻는 것은 어려운 것입니다. 거의 모든 C ++ 컴파일러는 원래 표준을 (대부분) 구현하지만 MS 컴파일러의 DLL 사양 등과 같은 많은 다크 코너 확장이있는 경향이 있습니다. 강력한 구문 분석 엔진이 있다면 시간을 들여 구문 분석기 생성기의 한계에 맞추기 위해 문법을 구부리려고하기보다는 현실과 일치하는 최종 문법입니다.

2012 년 11 월 편집 :이 답변을 작성한 이후로 ANSI, GNU 및 MS 변형 방언을 포함한 전체 C ++ 11을 처리하도록 C ++ 프런트 엔드를 개선했습니다. 많은 추가 사항이 있었지만 파싱 엔진을 변경할 필요가 없습니다. 방금 문법 규칙을 수정했습니다. 우리 는 의미 분석을 변경해야했습니다. C ++ 11은 의미 상 매우 복잡하며이 작업은 파서를 실행하기위한 노력을 엄청나게합니다.

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

2017 년 4 월 편집 : 이제 (초안) C ++ 17을 처리합니다.

---

Clang의 파서는 다른 여러 오픈 소스 및 상용 C 및 C ++ 프런트 엔드와 마찬가지로 손으로 작성한 재귀 하강 파서입니다.

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

• 성능 : 손으로 쓴 파서를 사용하면 빠른 파서를 작성하여 필요에 따라 핫 경로를 최적화 할 수 있으며 항상 해당 성능을 제어 할 수 있습니다. 빠른 구문 분석기를 사용하면 "실제"구문 분석기가 일반적으로 사용되지 않는 다른 개발 도구 (예 : IDE의 구문 강조 표시 및 코드 완성)에서 Clang을 사용할 수 있습니다.
• 진단 및 오류 복구 : 손으로 작성한 재귀 하강 파서로 모든 권한을 가지고 있기 때문에 일반적인 문제를 감지하고 훌륭한 진단 및 오류 복구를 제공하는 특수 사례를 쉽게 추가 할 수 있습니다 (예 : http : //clang.llvm 참조) . .org / features.html # expressivediags ) 자동으로 생성 된 파서를 사용하면 생성기의 기능으로 제한됩니다.
• 단순성 : 재귀 하강 파서는 작성, 이해 및 디버그가 쉽습니다. 파싱 ​​전문가가되거나 파서를 확장 / 개선하기위한 새로운 도구 (오픈 소스 프로젝트에 특히 중요)를 배울 필요는 없지만 여전히 훌륭한 결과를 얻을 수 있습니다.

전반적으로 C ++ 컴파일러의 경우 그다지 중요하지 않습니다. C ++의 구문 분석 부분은 사소하지 않지만 여전히 쉬운 부분 중 하나이므로 단순하게 유지하는 것이 좋습니다. 시맨틱 분석 (특히 이름 조회, 초기화, 과부하 해결 및 템플릿 인스턴스화)은 구문 분석보다 훨씬 더 복잡합니다. 증명을 원한다면 Clang의 "Sema"구성 요소 (의미 분석 용)와 "Parse"구성 요소 (파싱 용)의 코드 배포 및 커밋을 확인하십시오.

---

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".

---

Weird answers there!

C/C++ grammars aren't context free. They are context sensitive because of the Foo * bar; ambiguity. We have to build a list of typedefs to know if Foo is a type or not.

Ira Baxter: I don't see the point with your GLR thing. Why build a parse tree which comprises ambiguities. Parsing means solving ambiguities, building the syntax tree. You resolve these ambiguities in a second pass, so this isn't less ugly. For me it is far more ugly ...

Yacc is a LR(1) parser generator (or LALR(1)), but it can be easily modified to be context sensitive. And there is nothing ugly in it. Yacc/Bison has been created to help in parsing C language, so probably it isn't the ugliest tool to generate a C parser ...

Until GCC 3.x the C parser is generated by yacc/bison, with typedefs table built during parsing. With "in parse" typedefs table building, C grammar becomes locally context free and furthermore "locally LR(1)".

Now, in Gcc 4.x, it is a recursive descent parser. It is exactly the same parser as in Gcc 3.x, it is still LR(1), and has the same grammar rules. The difference is that the yacc parser has been hand rewritten, the shift/reduce are now hidden in the call stack, and there is no "state454 : if (nextsym == '(') goto state398" as in gcc 3.x yacc's parser, so it is easier to patch, handle errors and print nicer messages, and to perform some of the next compiling steps during parsing. At the price of much less "easy to read" code for a gcc noob.

Why did they switched from yacc to recursive descent? Because it is quite necessary to avoid yacc to parse C++, and because GCC dreams to be multi language compiler, i.e. sharing maximum of code between the different languages it can compile. This is why the C++ and the C parser are written in the same way.

C++ is harder to parse than C because it isn't "locally" LR(1) as C, it is not even LR(k). Look at func<4 > 2> which is a template function instantiated with 4 > 2, i.e. func<4 > 2> has to be read as func<1>. This is definitely not LR(1). Now consider, func<4 > 2 > 1 > 3 > 3 > 8 > 9 > 8 > 7 > 8>. This is where a recursive descent can easily solve ambiguity, at the price of a few more function calls (parse_template_parameter is the ambiguous parser function. If parse_template_parameter(17tokens) failed, try again parse_template_parameter(15tokens), parse_template_parameter(13tokens) ... until it works).

I don't know why it wouldn't be possible to add into yacc/bison recursive sub grammars, maybe this will be the next step in gcc/GNU parser development?

---

It seems that GCC and LLVM-Clang are using handwritten recursive descent parsers, and not machine generated, Bison-Flex based, bottom up parsing.

Bison in particular I don't think can handle the grammar without parsing some things ambiguously and doing a second pass later.

I know Haskell's Happy allows for monadic (i.e. state-dependent) parsers that can resolve the particular issue with C syntax, but I know of no C parser generators that allow a user-supplied state monad.

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.

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