yacclex編譯器

A. linux 下怎樣安裝使用 Yacc 和 Lex

在Linux系統中，Lex和Yacc是用於詞法分析和語法分析的工具，能夠幫助開發者創建自定義編譯器或重製已有編程語言的解析器。它們生成的程序源碼限定為C或C++語言。盡管如此，現今已有如JavaCC這樣的工具，能夠生成Java源碼，這在某些場景下會更為便利。

Lex和Yacc不僅在Unix和Linux系統中得到廣泛應用，也已被移植至Windows平台。現今，一些常用的工具如Parser Generator成為Windows下的選擇。本文專注於介紹Linux環境下Lex和Yacc的具體使用方法。

Lex工具通過定義格式來生成C語言源碼文件，然後通過編譯該源碼文件，可以實現.lex或.l文件定義的編譯器功能。這些文件通常分為三部分：

1. 全局變數聲明部分，例如：

2. 詞法規則部分，例如：

3. 函數定義部分，例如：

以一個簡單的例子來說明：

在這個例子中，我們定義了幾個簡單的規則，例如識別單詞、文件名、引號等，並在規則部分通過%%符號進行分隔。函數定義部分則負責文件的打開、讀取、解析和關閉操作。通過這樣的定義，可以實現基本的詞法分析功能。

總而言之，Lex和Yacc是強大的工具，能夠幫助開發者構建復雜編譯器或解析器。盡管現今有了更多選擇，但對於特定需求，它們仍然是值得學習和掌握的。

B. 「編譯」與「編譯器」是什麼意思

編譯是動詞
編譯器是名詞
編譯(compilation , compile)
1、利用編譯程序從源語言編寫的源程序產生目標程序的過程。
2、用編譯程序產生目標程序的動作。

編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。
編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；中間代碼生成；代碼優化；目標代碼生成。主要是進行詞法分析和語法分析，又稱為源程序分析，分析過程中發現有語法錯誤，給出提示信息。
（1） 詞法分析
詞法分析的任務是對由字元組成的單詞進行處理，從左至右逐個字元地對源程序進行掃描，產生一個個的單詞符號，把作為字元串的源程序改造成為單詞符號串的中間程序。執行詞法分析的程序稱為詞法分析程序或掃描器。
源程序中的單詞符號經掃描器分析，一般產生二元式：單詞種別；單詞自身的值。單詞種別通常用整數編碼，如果一個種別只含一個單詞符號，那麼對這個單詞符號，種別編碼就完全代表它自身的值了。若一個種別含有許多個單詞符號，那麼，對於它的每個單詞符號，除了給出種別編碼以外，還應給出自身的值。
詞法分析器一般來說有兩種方法構造：手工構造和自動生成。手工構造可使用狀態圖進行工作，自動生成使用確定的有限自動機來實現。
（2） 語法分析
編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。編譯程序的語法規則可用上下文無關文法來刻畫。
語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。
（3） 中間代碼生成
中間代碼是源程序的一種內部表示，或稱中間語言。中間代碼的作用是可使編譯程序的結構在邏輯上更為簡單明確，特別是可使目標代碼的優化比較容易實現。中間代碼即為中間語言程序，中間語言的復雜性介於源程序語言和機器語言之間。中間語言有多種形式，常見的有逆波蘭記號、四元式、三元式和樹。
（4） 代碼優化
代碼優化是指對程序進行多種等價變換，使得從變換後的程序出發，能生成更有效的目標代碼。所謂等價，是指不改變程序的運行結果。所謂有效，主要指目標代碼運行時間較短，以及佔用的存儲空間較小。這種變換稱為優化。
有兩類優化：一類是對語法分析後的中間代碼進行優化，它不依賴於具體的計算機；另一類是在生成目標代碼時進行的，它在很大程度上依賴於具體的計算機。對於前一類優化，根據它所涉及的程序范圍可分為局部優化、循環優化和全局優化三個不同的級別。
（5） 目標代碼生成
目標代碼生成是編譯的最後一個階段。目標代碼生成器把語法分析後或優化後的中間代碼變換成目標代碼。目標代碼有三種形式：
① 可以立即執行的機器語言代碼，所有地址都重定位；
② 待裝配的機器語言模塊，當需要執行時，由連接裝入程序把它們和某些運行程序連接起來，轉換成能執行的機器語言代碼；
③ 匯編語言代碼，須經過匯編程序匯編後，成為可執行的機器語言代碼。
目標代碼生成階段應考慮直接影響到目標代碼速度的三個問題：一是如何生成較短的目標代碼；二是如何充分利用計算機中的寄存器，減少目標代碼訪問存儲單元的次數；三是如何充分利用計算機指令系統的特點，以提高目標代碼的質量。
編譯器，是將便於人編寫，閱讀，維護的高級計算機語言翻譯為計算機能解讀、運行的低階機器語言的程序。編譯器將原始程序（Source program）作為輸入，翻譯產生使用目標語言（Target language）的等價程序。源代碼一般為高階語言 (High-level language), 如 Pascal、C++、Java 等，而目標語言則是匯編語言或目標機器的目標代碼（Object code），有時也稱作機器代碼（Machine code）。
一個現代編譯器的主要工作流程如下：
源代碼 (source code) → 預處理器 (preprocessor) → 編譯器 (compiler) → 匯編程序 (assembler) → 目標代碼 (object code) → 連接器 (Linker) → 可執行程序 (executables)

工作原理
[編輯本段]

編譯是從源代碼（通常為高階語言）到能直接被計算機或虛擬機執行的目標代碼（通常為低階語言或機器語言）的翻譯過程。然而，也存在從低階語言到高階語言的編譯器，這類編譯器中用來從由高階語言生成的低階語言代碼重新生成高階語言代碼的又被叫做反編譯器。也有從一種高階語言生成另一種高階語言的編譯器，或者生成一種需要進一步處理的的中間代碼的編譯器（又叫級聯）。
典型的編譯器輸出是由包含入口點的名字和地址, 以及外部調用（到不在這個目標文件中的函數調用）的機器代碼所組成的目標文件。一組目標文件，不必是同一編譯器產生，但使用的編譯器必需採用同樣的輸出格式，可以鏈接在一起並生成可以由用戶直接執行的可執行程序。

編譯器種類
[編輯本段]

編譯器可以生成用來在與編譯器本身所在的計算機和操作系統（平台）相同的環境下運行的目標代碼，這種編譯器又叫做「本地」編譯器。另外，編譯器也可以生成用來在其它平台上運行的目標代碼，這種編譯器又叫做交叉編譯器。交叉編譯器在生成新的硬體平台時非常有用。「源碼到源碼編譯器」是指用一種高階語言作為輸入，輸出也是高階語言的編譯器。例如: 自動並行化編譯器經常採用一種高階語言作為輸入，轉換其中的代碼，並用並行代碼注釋對它進行注釋（如OpenMP）或者用語言構造進行注釋（如FORTRAN的DOALL指令）。

預處理器（preprocessor）

作用是通過代入預定義等程序段將源程序補充完整。

編譯器前端（frontend）

前端主要負責解析（parse）輸入的源代碼，由語法分析器和語意分析器協同工作。語法分析器負責把源代碼中的『單詞』（Token）找出來,語意分析器把這些分散的單詞按預先定義好的語法組裝成有意義的表達式，語句 ，函數等等。 例如「a = b + c;」前端語法分析器看到的是「a, =, b , +, c;」，語意分析器按定義的語法，先把他們組裝成表達式「b + c」，再組裝成「a = b + c」的語句。 前端還負責語義（semantic checking）的檢查，例如檢測參與運算的變數是否是同一類型的，簡單的錯誤處理。最終的結果常常是一個抽象的語法樹（abstract syntax tree，或 AST），這樣後端可以在此基礎上進一步優化，處理。

編譯器後端（backend）

編譯器後端主要負責分析，優化中間代碼（Intermediate representation）以及生成機器代碼（Code Generation）。

一般說來所有的編譯器分析，優化，變型都可以分成兩大類： 函數內（intraproceral）還是函數之間（interproceral）進行。很明顯，函數間的分析，優化更准確，但需要更長的時間來完成。

編譯器分析（compiler analysis）的對象是前端生成並傳遞過來的中間代碼，現代的優化型編譯器（optimizing compiler）常常用好幾種層次的中間代碼來表示程序，高層的中間代碼（high level IR）接近輸入的源代碼的格式，與輸入語言相關（language dependent），包含更多的全局性的信息，和源代碼的結構；中層的中間代碼（middle level IR）與輸入語言無關，低層的中間代碼(Low level IR)與機器語言類似。 不同的分析，優化發生在最適合的那一層中間代碼上。

常見的編譯分析有函數調用樹（call tree），控制流程圖（Control flow graph），以及在此基礎上的 變數定義－使用，使用－定義鏈（define-use/use-define or u-d/d-u chain），變數別名分析（alias analysis），指針分析（pointer analysis），數據依賴分析（data dependence analysis）等等。

上述的程序分析結果是編譯器優化（compiler optimization）和程序變形（compiler transformation）的前提條件。常見的優化和變新有：函數內嵌（inlining），無用代碼刪除（Dead code elimination），標准化循環結構（loop normalization），循環體展開（loop unrolling），循環體合並，分裂（loop fusion，loop fission），數組填充（array padding），等等。 優化和變形的目標是減少代碼的長度，提高內存（memory），緩存（cache）的使用率，減少讀寫磁碟，訪問網路數據的頻率。更高級的優化甚至可以把序列化的代碼（serial code）變成並行運算，多線程的代碼（parallelized，multi-threaded code）。

機器代碼的生成是優化變型後的中間代碼轉換成機器指令的過程。現代編譯器主要採用生成匯編代碼（assembly code）的策略，而不直接生成二進制的目標代碼（binary object code）。即使在代碼生成階段，高級編譯器仍然要做很多分析，優化，變形的工作。例如如何分配寄存器（register allocatioin），如何選擇合適的機器指令（instruction selection），如何合並幾句代碼成一句等等。

編譯語言與直譯語言對比
[編輯本段]

許多人將高階程序語言分為兩類: 編譯型語言 和 直譯型語言 。然而，實際上，這些語言中的大多數既可用編譯型實現也可用直譯型實現，分類實際上反映的是那種語言常見的實現方式。（但是，某些直譯型語言，很難用編譯型實現。比如那些允許 在線代碼更改 的直譯型語言。）

歷史
[編輯本段]

上世紀50年代，IBM的John Backus帶領一個研究小組對FORTRAN語言及其編譯器進行開發。但由於當時人們對編譯理論了解不多，開發工作變得既復雜又艱苦。與此同時，Noam Chomsky開始了他對自然語言結構的研究。他的發現最終使得編譯器的結構異常簡單，甚至還帶有了一些自動化。Chomsky的研究導致了根據語言文法的難易程度以及識別它們所需要的演算法來對語言分類。正如現在所稱的Chomsky架構（Chomsky Hierarchy），它包括了文法的四個層次：0型文法、1型文法、2型文法和3型文法，且其中的每一個都是其前者的特殊情況。2型文法（或上下文無關文法）被證明是程序設計語言中最有用的，而且今天它已代表著程序設計語言結構的標准方式。分析問題（parsing problem，用於上下文無關文法識別的有效演算法）的研究是在60年代和70年代，它相當完善的解決了這個問題。現在它已是編譯原理中的一個標准部分。

有限狀態自動機（Finite Automaton）和正則表達式（Regular Expression）同上下文無關文法緊密相關，它們與Chomsky的3型文法相對應。對它們的研究與Chomsky的研究幾乎同時開始，並且引出了表示程序設計語言的單詞的符號方式。

人們接著又深化了生成有效目標代碼的方法，這就是最初的編譯器，它們被一直使用至今。人們通常將其稱為優化技術（Optimization Technique），但因其從未真正地得到過被優化了的目標代碼而僅僅改進了它的有效性，因此實際上應稱作代碼改進技術（Code Improvement Technique）。

當分析問題變得好懂起來時，人們就在開發程序上花費了很大的功夫來研究這一部分的編譯器自動構造。這些程序最初被稱為編譯器的編譯器（Compiler-compiler），但更確切地應稱為分析程序生成器（Parser Generator），這是因為它們僅僅能夠自動處理編譯的一部分。這些程序中最著名的是Yacc（Yet Another Compiler-compiler），它是由Steve Johnson在1975年為Unix系統編寫的。類似的，有限狀態自動機的研究也發展了一種稱為掃描程序生成器（Scanner Generator）的工具，Lex（與Yacc同時，由Mike Lesk為Unix系統開發）是這其中的佼佼者。

在70年代後期和80年代早期，大量的項目都貫注於編譯器其它部分的生成自動化，這其中就包括了代碼生成。這些嘗試並未取得多少成功，這大概是因為操作太復雜而人們又對其不甚了解。

編譯器設計最近的發展包括：首先，編譯器包括了更加復雜演算法的應用程序它用於推斷或簡化程序中的信息；這又與更為復雜的程序設計語言的發展結合在一起。其中典型的有用於函數語言編譯的Hindley-Milner類型檢查的統一演算法。其次，編譯器已越來越成為基於窗口的交互開發環境（Interactive Development Environment，IDE）的一部分，它包括了編輯器、連接程序、調試程序以及項目管理程序。這樣的IDE標准並沒有多少，但是對標準的窗口環境進行開發已成為方向。另一方面，盡管近年來在編譯原理領域進行了大量的研究，但是基本的編譯器設計原理在近20年中都沒有多大的改變，它現在正迅速地成為計算機科學課程中的中心環節。

在九十年代，作為GNU項目或其它開放源代碼項目標一部分，許多免費編譯器和編譯器開發工具被開發出來。這些工具可用來編譯所有的計算機程序語言。它們中的一些項目被認為是高質量的，而且對現代編譯理論感興趣的人可以很容易的得到它們的免費源代碼。

大約在1999年，SGI公布了他們的一個工業化的並行化優化編譯器Pro64的源代碼，後被全世界多個編譯器研究小組用來做研究平台，並命名為Open64。Open64的設計結構好，分析優化全面，是編譯器高級研究的理想平台。

C. Lex與YACC詳解

只要你在Unix環境中寫過程序，你必定會邂逅神秘的Lex&YACC，就如GNU/Linux用戶所熟知的Flex&Bison，這里的Flex就是由Vern Paxon實現的一個Lex，Bison則是GNU版本的YACC。這些程序實用性極廣，但如同你的C編譯器一樣，在其主頁上並沒有描述它們，也沒有關於怎樣使用的信息。然而，Lex和YACC可以讓你輕易的解析復雜的語言，當你需要讀取一個配置文件時，或者你需要編寫一個你自己使用的語言的編譯器時，這對於你來說是莫大的裨益。

Lex會生成一個叫做『詞法分析器』的程序。這是一個函數，它帶有一個字元流傳入參數，詞法分析器函數看到一組字元就會去匹配一個關鍵字(key)，採取相應措施。一個非常簡單的例子如下:

詞法分析器會等待輸入一些數據，每次輸入一些不匹配的命令(非』stop』和』start』)，它會將你輸入的字元再次輸出。你若輸入』stop』，它將輸出』Stop command received』。用一個EOF(^D)來結束程序。

Lex的常規表達式是一種使用元語言的模式描述。表達式由符號組成。符號一般是字元和數字，還有一些具有特殊含義的其他標記。例如，常規表達式可以匹配「[0123456789]+」或「[a-zA-Z][a-zA-Z0-9]*」。其中，後者匹配一個變數名，必須以字母開頭，可以在後續字元中用數字。

YACC可以解析輸入流中的標識符(token)，這就清楚的描述了YACC和LEX的關系。YACC並不知道『輸入流』為何物，它需要事先就將輸入流預加工成標識符，雖然你可以自己手工寫一個Tokenizer，但我們將這些工作留給LEX來做。YACC用來為編譯器解析輸入數據，即程序代碼。這些用編程語言寫成的程序代碼一點也不模稜兩可——它們只有一個意思。正因為如此，YACC才不會去對付那些有歧義的語法，並且會抱怨shift/rece或者rece/rece沖突。

Lex和YACC可以生成C++代碼的解析器。雖然LEX和YACC的歷史要早於C++，但是還是可以用它們來生成一個C++解析器。我們用LEX來生成C++的詞法分析器，YACC並不知道如何直接來處理這些，所以我們不打算這么做。比較好的做法是，要做一個C++解析器，就需要LEX生成一個C文件，並且讓YACC來生成C++代碼。然而，在這個過程中，你會遇到一些問題，因為C++代碼默認情況下並不能找到C的函數，除非你將那些函數定義為extern 「C」。為解決此問題，我們在YACC代碼中編寫一個C開頭。

在YACC文件中，你定義了你自己的main()函數，它在某個點上調用了yyparse()。YACC會創建你的yyparse()函數，並在y.tab.c中結束該函數。yyparse()函數讀取一個『標識符/值對』(token/value pairs)流，這些流需要事先就提供，這些流可以是你自己手寫的代碼提供的，也可以是LEX生成的。在我們的示例中，我們把這個工作丟給了LEX。LEX生成的yylex()函數從文件參數FILE *file中讀取字元(文件名為yyin)。

遞歸是YACC一個極其重要的特性。沒有遞歸的話，你就確定一個文件是由一系列獨立的命令組成還是由語句組成。由於YACC自身的特性，它只對第一個規則或那個你將其設計為『起始規則』的規則感興趣。起始規則用』%start』符號標記。YACC中的遞歸以兩種形式出現，左遞歸和右遞歸。左遞歸是你應該經常使用的，它們看起來如下：

在解析長的語句時，務必使用左遞歸，例如整個文件。但有時難以避免右遞歸，不過，如果你的語句並不太長，你就沒有必要越軌使用左遞歸。正確的做法是使用左遞歸。

為了匹配所有丟給它的東西，避免了將那些不匹配的輸入輸出到標准輸出的默認行為，我們可以通過字元作為速記法來作為標識符的數字ID，我們可以這樣來重寫我們的詞法分析器。

我們需要定義yylval的類型。但是這並不一直恰如其當。我們可能會多次這樣做，因為需要處理多種數據類型。例如，我們需要定義yylval為一個union，它可以存儲字元串，也可以存儲整數，但並不是同時存儲。我們可以定義YYSTYPE為一個union，YACC中有一種簡便的方法來實現，即%union語句。

我們不希望從標准輸入解析，而希望解析給定的字元串。實現方法是自定義實現YY_INPUT。

YACC中有許多調試反饋信息。這些調試信息的代價有點高，所以你需要提供一些開關來打開它。當你運行那個生成的二進制文件，它將輸出很多運行時信息。裡麵包含當前所運行的狀態機以及讀取到的一些標識符。你可以用Emacs中那個非常好的『pinfo』工具閱讀.info文件。

YACC解析器在內部運行的是一個『狀態機』，該狀態機可以有多種轉台。接著有多個規則來管制狀態間的相互轉化。任何內容都是從『root』規則開始。狀態機不斷遞減演化，直到它遇到某些它能理解的東西。