天天看點

c++編譯器裡的字型_一文了解 Yacc、Lex、JavaCC、ANTLR 等編譯器相關概念

c++編譯器裡的字型_一文了解 Yacc、Lex、JavaCC、ANTLR 等編譯器相關概念

Compiler

定義一種“上下文無關文法”(context-free grammar,CFG),然後寫一個 C 程式來解釋這種 CFG,那麼這個 C 程式就叫做“編譯器”(compiler)。隻不過這個編譯器隻能編譯特定的 CFG,就像 g++ 隻能編譯 C++,javac 隻能編譯 Java 代碼,這些都是編譯器。

CC

CC 即 compiler-compiler,意思是“編譯器的編譯器”,另外還可以叫做 compiler generator。

對于任意給定的 CFG,如果可以寫出一個 C 程式,生成另一段 C 程式代碼,這段 C 程式代碼是給定 CFG 的編譯器。那麼,這個 C 程式就叫做 CC。

Yacc、Bison

c++編譯器裡的字型_一文了解 Yacc、Lex、JavaCC、ANTLR 等編譯器相關概念

Yacc 即 Yet Another Compiler-Compiler,是經典的生成文法分析器的工具,将任何一種程式設計語言的所有文法翻譯成針對此種語言的 Yacc 文法解析器。

Yacc 采用自下而上(LALR)文法分析方法,輸入是巴科斯範式(Backus-Naur Form,BNF)表達的文法規則以及文法規約的處理代碼,輸出的是基于表驅動的編譯器,包括輸入的文法規約的處理代碼部分。

Yacc 最初由 AT&T 的 Steven C. Johnson 為 Unix 作業系統開發,後來一些相容程式如 Berkeley Yacc(byacc)、GNU Bison 相續出現。它們在原先基礎上做了一些改進或者擴充,但基本概念是相通的。

GNU Bison 是 Yacc 的 GNU 自由軟體版本,基本相容 Yacc,并做了一些改進。在新近版本中,除了與 Yacc 相同的 LALR 文法分析,Bison 還增加了對 GLR(Generalized LR) 文法分析的支援。

Lex、Flex

c++編譯器裡的字型_一文了解 Yacc、Lex、JavaCC、ANTLR 等編譯器相關概念

Lex 是 LEXical compiler 的縮寫,是一個詞法分析器(scanner)的生成工具,它使用正規表達式(regular expression)來描述各個詞法單元的模式,由此給出一個詞法分析器的規約,并生成相應的實作代碼。 Lex 程式的輸入方法稱為 Lex 語言,而 Lex 程式本身被稱為 Lex 編譯器。

Yacc 生成的編譯器主要是用 C 語言寫成的文法解析器(Parser),需要與詞法分析器一起使用(一般為 Lex),再把兩部分産生的 C 程式代碼一起編譯。描述詞法分析器的檔案 *.l,經過 Lex 編譯後,生成一個 lex.yy.c 的檔案,然後由 C 編譯器編譯生成一個詞法分析器。詞法分析器,簡單來說,其任務就是将輸入的各種符号,轉化成相應的辨別符(token),轉化後的辨別符很容易被後續階段處理。

Flex 是 Lex 的開源版本,是 Lex 編譯器的一種替代實作。

JavaCC

JavaCC 即 Java Compiler Compiler,是開源、輕量的文法分析器生成器和詞法分析器生成器,采用純 Java 編寫,可生成 Java、C++ 和 C# 代碼。ANTLR 根據輸入的文法生成由 Java 語言編寫的分析器,相當于 Java 界的 Yacc + Lex 或 Bison + Flex。

和 YACC 類似,JavaCC 由(Extended Backus-Naur Form,EBNF) 格式的形式文法生成文法分析器。不同的是,JavaCC 生成的是自頂向下 LL 文法分析器對 CFG 進行解析。同時,JavaCC 生成詞法分析器的方式也和 Lex 很像。JavaCC 還提供 JJTree 幫助使用者建構文法樹,JJDoc 工具為源檔案生成 BNF 範式文檔。

JavaCC 源自著名的 Sun 公司。1996 年,Sun 推出了一個名為 Jack 的文法解析器生成器。後來,負責“Jack”的開發者創辦了自己的公司 Metamata,并将 Jack 改名為 JavaCC。Metamata 最後成為了WebGain 的一部分,後 WebGain 關閉。目前 JavaCC 代碼以 BSD 許可證托管在 GitHub。

很多著名開源項目用到了 JavaCC,包括:

  • Apache ActiveMQ
  • Apache Zookeeper
  • Apache Lucene
  • Apache Tomcat
  • Apache Avro
  • Apache Camel
  • Apache Calcite

ANTLR

c++編譯器裡的字型_一文了解 Yacc、Lex、JavaCC、ANTLR 等編譯器相關概念

ANTLR 即 ANother Tool for Language Recognition,是基于自頂向下的遞歸下降 LL 算法實作的文法解析器生成器(parser generator),采用純 Java 語言編寫。ANTLR 能夠自動生成解析器,并将使用者編寫的 ANTLR 文法規則直接生成目智語言的解析器。所生成的解析器用戶端将輸入的文本生成抽象文法樹,并提供周遊樹的接口,以通路文本的各個部分。

ANTLR 是 Terence Parr 在普渡大學攻讀碩士學位時的創作,在著名編譯器領域大師 Hank Dietz 教授的指導下,開始研究構造自動化的分析器。1993年,Parr 取得博士學位,并于同年釋出 ANTLR 1.10 版。最早的 ANTLR 隻支援 Java, 直到 ANTLR 3 以後開始支援 Ada95、C、C#、JavaScript、Objective-C、Perl、Python、Ruby、C++ 和 Standard ML。

ANTLR 生成的代碼與使用遞歸下降法(構造手工分析器的主要方法)産生的代碼非常相似,便于程式員閱讀和了解,與 Yacc 産生的晦澀代碼相比進步了很多。與 JavaCC 相比,ANTLR 功能更加全面,開箱即用,另外支援語言更豐富,不止局限于 Java 語言。

使用 ANTLR 的著名項目包括:

GroovyJythonHibernateApache CassandraWebLogic Server