c語言編譯器用的文法

㈠ 編譯器龍書虎書鯨書基本抽象概念

在編譯原理的世界裡，三本堪稱經典的著作猶如璀璨明珠：龍書（Aho, Sethi, Ullman合著的《編譯原理技術和工具》）、虎書（Appel和Palsberg合作的《現代編譯器實現：C語言版》），以及被稱為「鯨書」的神秘巨著（未提及具體書名）。龍書是編譯器領域的基石，涵蓋了詞法分析、語法分析等核心內容，雖早期版本存在一些過時技術，但後期修訂版不斷擴展新知識。虎書則緊跟時代步伐，融合了數據流分析等現代元素，特別適合教學，不僅有C語言版本，還有Java和ML版本，詳細內容可通過參考鏈接獲取。

深入研究現代商業編譯器的關鍵問題，學生們通過學習基礎概念，為後續深入探索奠定基礎。推薦必讀的《現代編譯原理：C語言描述》由Steven S. Muchnick撰寫，是虎書的升級版。而「鯨書」則為進階學習者量身打造，探討高級編譯器設計與實現，涵蓋了抽象層次的深入轉換，如從高級語言到機器代碼的優化過程，分為基礎抽象、數據模型、編程語言語義和演算法效率等幾個核心領域。

基礎抽象如同Java介面，它不僅包含操作的名稱，還承載了預期的功能含義。這些抽象可以分為兩類：一類是常見的操作，如字典和堆棧，提供多種實現；另一類是廣泛應用於組件化的概念，如樹和圖。在計算思維中，抽象是靈魂，如圖抽象中的「查找相鄰節點」，它在圖靈完備的語言中嵌入，類似於面向對象的類方法，但底層實現則更為具體，涉及有限自動機、解析器等與機器模型緊密相連的技術。聲明性抽象，如正則表達式和關系代數，強調的是表達和描述而非實現，對優化性能有高要求；而計算抽象，如通用編程語言和理論模型，如RAM和並行計算模型，盡管可能非圖靈完備，但其重要性不言而喻。

舉例來說，當需要在聲明階段將標識符插入符號表S時，編譯器會根據標識符類型進行檢索。字典語言雖然不具備圖靈機的復雜性，但它關注的是進程的表示，而非演算法設計。字典操作的時間復雜性與集合大小相關，鏈表實現可能導致O(n)時間，而搜索樹如AVL或紅黑樹則可達到O(log n)。

哈希抽象的核心是全集、哈希函數和哈希桶，操作基於計算哈希值。盡管哈希操作存在最壞情況性能問題，但通常假設平均性能。哈希桶存儲結構可根據集合規模採用鏈表或優化存儲，如調整磁碟塊大小以適應主存容量。

從詞法分析到後端優化，現代編譯器分為前後端任務。前端涉及詞法分析、句法分析、語義分析和中間代碼生成，而共享符號表則用於收集源代碼信息。如Lex，通過正則表達式實現標記簡化，早期的磁帶檢索技術效率較低，但Aho-Corasick演算法通過一次遍歷查找多個關鍵字，提高了效率。句法分析器生成器基於正則表達式，產生確定性有限自動機，確保語法的有效性。

2.1.1 Lex的升級：Aho-Corasick演算法通過集成多個正則表達式集合，顯著提升了關鍵字檢索的效率。

2.1.2 Lex設計關注交互復雜性，區分標識符與控制流關鍵字，避免混淆。

2.1.3 懶惰評估的DFA（確定性有限自動機）技術，優化了正則表達式到DFA的轉換，為grep等工具的性能提升做出了貢獻。

繼續深入，語法分析構建了語言的結構，如表達式樹。上下文無關文法（CFG）描述編程語言的句法規則，LR(k)分析法通過一次左到右掃描，處理復雜語法結構。

編譯器研究涉及眾多抽象層次，從關系模型在編程語言中的應用，到SQL的抽象和優化，再到分布式計算和量子計算的前沿探索。隨著技術的演進，我們期待在編譯器領域的知識體系中，不斷發掘新的抽象理論，推動計算機科學的邊界不斷拓寬。

參考資料：[1] [2] [3]

㈡ ★C語言中字元： '\1' 是什麼意思

'1'為轉義字元，代表的意思是「標題開始」

在C語言中，所有的ASCII碼都可以用「」加數字（一般是8進制數字）來表示。

而C中定義了一些字母前加""來表示常見的那些不能顯示的ASCII字元，如, , 等，就稱為轉義字元，因為後面的字元，都不是它本來的ASCII字元意思了。

轉義字元是很多程序語言、數據格式和通信協議的形式文法的一部分。對於一個給定的字母表，一個轉義字元的目的是開始一個字元序列，使得轉義字元開頭的該字元序列具有不同於該字元序列單獨出現時的語義。因此轉義字元開頭的字元序列被叫做轉義序列。

轉義序列通常有兩種功能。第一個是編碼一個句法上的實體，如設備命令或者無法被字母表直接表示的特殊數據。

第二種功能，也叫字元引用，用於表示無法在當前上下文中被鍵盤錄入的字元（如字元串中的回車符），或者在當前上下文中會有不期望的含義的字元（如C語言字元串中的雙引號字元"，不能直接出現，必須用轉義序列表示）。

在後面那種情況，轉義序列是一種由轉義字元自身和一個被引用的字元組成的一個二合字母（digraph）情形。

參考資料來源：

網路-轉義字元

網路-ASCII

㈢ LL（1）文法-------編譯原理

我正在寫一個編譯器，源代碼在這里：
http://code.google.com/p/bellman/source/browse
其中詞法規則在lex.l文件中，語法規則在grammer.y中，分別用flex和bison的輸入文件的格式寫的。我實現了一個類似C/C++的語法

地址如下：
http://code.google.com/p/bellman/source/browse/trunk/lib/bellman/lex.l
http://code.google.com/p/bellman/source/browse/trunk/lib/bellman/grammer.y
具體有什麼問題可以發郵件[email protected]

㈣ 求C語言編譯原理語法分析程序

一繼承的詞法來自

http://blog.sina.com.cn/s/blog_67c9fc300100srad.html
二語法

用擴充的BNF表示如下：

⑴<程序>：：=begin<語句串>end

⑵<語句串>：：=<語句>{；<語句>}

⑶<語句>：：=<賦值語句>

⑷<賦值語句>：：=ID：=<表達式>

⑸<表達式>：：=<項>{+<項> | -<項>}

⑹<項>：：=<因子>{*<因子> | /<因子>

⑺<因子>：：=ID | NUM | （<表達式>）

三要求

輸入單詞串，以「#」結束，如果是文法正確的句子，則輸出成功信息，列印「success」，否則輸出「error」。

例如：

輸入 begin a:=9; x:=2*3; b:=a+x end #

輸出 success！

輸入 x:=a+b*c end #

輸出 error!

㈤ 編譯原理

C語言編譯過程詳解
C語言的編譯鏈接過程是要把我們編寫的一個C程序(源代碼)轉換成可以在硬體上運行的程序(可執行代碼)，需要進行編譯和鏈接。編譯就是把文本形式源代碼翻譯為機器語言形式的目標文件的過程。鏈接是把目標文件、操作系統的啟動代碼和用到的庫文件進行組織形成最終生成可執行代碼的過程。過程圖解如下：

從圖上可以看到，整個代碼的編譯過程分為編譯和鏈接兩個過程，編譯對應圖中的大括弧括起的部分，其餘則為鏈接過程。
一、編譯過程
編譯過程又可以分成兩個階段：編譯和匯編。
1、編譯
編譯是讀取源程序(字元流)，對之進行詞法和語法的分析，將高級語言指令轉換為功能等效的匯編代碼，源文件的編譯過程包含兩個主要階段：
第一個階段是預處理階段，在正式的編譯階段之前進行。預處理階段將根據已放置在文件中的預處理指令來修改源文件的內容。如#include指令就是一個預處理指令，它把頭文件的內容添加到.cpp文件中。這個在編譯之前修改源文件的方式提供了很大的靈活性，以適應不同的計算機和操作系統環境的限制。一個環境需要的代碼跟另一個環境所需的代碼可能有所不同，因為可用的硬體或操作系統是不同的。在許多情況下，可以把用於不同環境的代碼放在同一個文件中，再在預處理階段修改代碼，使之適應當前的環境。
主要是以下幾方面的處理：
(1)宏定義指令，如 #define a b。
對於這種偽指令，預編譯所要做的是將程序中的所有a用b替換，但作為字元串常量的 a則不被替換。還有 #undef，則將取消對某個宏的定義，使以後該串的出現不再被替換。
(2)條件編譯指令，如#ifdef，#ifndef，#else，#elif，#endif等。
這些偽指令的引入使得程序員可以通過定義不同的宏來決定編譯程序對哪些代碼進行處理。預編譯程序將根據有關的文件，將那些不必要的代碼過濾掉
(3) 頭文件包含指令，如#include "FileName"或者#include <FileName>等。
在頭文件中一般用偽指令#define定義了大量的宏(最常見的是字元常量)，同時包含有各種外部符號的聲明。採用頭文件的目的主要是為了使某些定義可以供多個不同的C源程序使用。因為在需要用到這些定義的C源程序中，只需加上一條#include語句即可，而不必再在此文件中將這些定義重復一遍。預編譯程序將把頭文件中的定義統統都加入到它所產生的輸出文件中，以供編譯程序對之進行處理。包含到C源程序中的頭文件可以是系統提供的，這些頭文件一般被放在/usr/include目錄下。在程序中#include它們要使用尖括弧(<>)。另外開發人員也可以定義自己的頭文件，這些文件一般與C源程序放在同一目錄下，此時在#include中要用雙引號("")。
(4)特殊符號，預編譯程序可以識別一些特殊的符號。
例如在源程序中出現的LINE標識將被解釋為當前行號(十進制數)，FILE則被解釋為當前被編譯的C源程序的名稱。預編譯程序對於在源程序中出現的這些串將用合適的值進行替換。
預編譯程序所完成的基本上是對源程序的「替代」工作。經過此種替代，生成一個沒有宏定義、沒有條件編譯指令、沒有特殊符號的輸出文件。這個文件的含義同沒有經過預處理的源文件是相同的，但內容有所不同。下一步，此輸出文件將作為編譯程序的輸出而被翻譯成為機器指令。
第二個階段編譯、優化階段。經過預編譯得到的輸出文件中，只有常量；如數字、字元串、變數的定義，以及C語言的關鍵字，如main,if,else,for,while,{,}, +,-,*,\等等。
編譯程序所要作得工作就是通過詞法分析和語法分析，在確認所有的指令都符合語法規則之後，將其翻譯成等價的中間代碼表示或匯編代碼。
優化處理是編譯系統中一項比較艱深的技術。它涉及到的問題不僅同編譯技術本身有關，而且同機器的硬體環境也有很大的關系。優化一部分是對中間代碼的優化。這種優化不依賴於具體的計算機。另一種優化則主要針對目標代碼的生成而進行的。
對於前一種優化，主要的工作是刪除公共表達式、循環優化(代碼外提、強度削弱、變換循環控制條件、已知量的合並等)、復寫傳播，以及無用賦值的刪除，等等。
後一種類型的優化同機器的硬體結構密切相關，最主要的是考慮是如何充分利用機器的各個硬體寄存器存放的有關變數的值，以減少對於內存的訪問次數。另外，如何根據機器硬體執行指令的特點(如流水線、RISC、CISC、VLIW等)而對指令進行一些調整使目標代碼比較短，執行的效率比較高，也是一個重要的研究課題。
2、匯編
匯編實際上指把匯編語言代碼翻譯成目標機器指令的過程。對於被翻譯系統處理的每一個C語言源程序，都將最終經過這一處理而得到相應的目標文件。目標文件中所存放的也就是與源程序等效的目標的機器語言代碼。目標文件由段組成。通常一個目標文件中至少有兩個段：
代碼段：該段中所包含的主要是程序的指令。該段一般是可讀和可執行的，但一般卻不可寫。
數據段：主要存放程序中要用到的各種全局變數或靜態的數據。一般數據段都是可讀，可寫，可執行的。
UNIX環境下主要有三種類型的目標文件：
(1)可重定位文件
其中包含有適合於其它目標文件鏈接來創建一個可執行的或者共享的目標文件的代碼和數據。
(2)共享的目標文件
這種文件存放了適合於在兩種上下文里鏈接的代碼和數據。
第一種是鏈接程序可把它與其它可重定位文件及共享的目標文件一起處理來創建另一個 目標文件；
第二種是動態鏈接程序將它與另一個可執行文件及其它的共享目標文件結合到一起，創建一個進程映象。
(3)可執行文件
它包含了一個可以被操作系統創建一個進程來執行之的文件。匯編程序生成的實際上是第一種類型的目標文件。對於後兩種還需要其他的一些處理方能得到，這個就是鏈接程序的工作了。
二、鏈接過程
由匯編程序生成的目標文件並不能立即就被執行，其中可能還有許多沒有解決的問題。
例如，某個源文件中的函數可能引用了另一個源文件中定義的某個符號(如變數或者函數調用等)；在程序中可能調用了某個庫文件中的函數，等等。所有的這些問題，都需要經鏈接程序的處理方能得以解決。
鏈接程序的主要工作就是將有關的目標文件彼此相連接，也即將在一個文件中引用的符號同該符號在另外一個文件中的定義連接起來，使得所有的這些目標文件成為一個能夠被操作系統裝入執行的統一整體。
根據開發人員指定的同庫函數的鏈接方式的不同，鏈接處理可分為兩種：
(1)靜態鏈接
在這種鏈接方式下，函數的代碼將從其所在地靜態鏈接庫中被拷貝到最終的可執行程序中。這樣該程序在被執行時這些代碼將被裝入到該進程的虛擬地址空間中。靜態鏈接庫實際上是一個目標文件的集合，其中的每個文件含有庫中的一個或者一組相關函數的代碼。
(2) 動態鏈接
在此種方式下，函數的代碼被放到稱作是動態鏈接庫或共享對象的某個目標文件中。鏈接程序此時所作的只是在最終的可執行程序中記錄下共享對象的名字以及其它少量的登記信息。在此可執行文件被執行時，動態鏈接庫的全部內容將被映射到運行時相應進程的虛地址空間。動態鏈接程序將根據可執行程序中記錄的信息找到相應的函數代碼。
對於可執行文件中的函數調用，可分別採用動態鏈接或靜態鏈接的方法。使用動態鏈接能夠使最終的可執行文件比較短小，並且當共享對象被多個進程使用時能節約一些內存，因為在內存中只需要保存一份此共享對象的代碼。但並不是使用動態鏈接就一定比使用靜態鏈接要優越。在某些情況下動態鏈接可能帶來一些性能上損害。
我們在linux使用的gcc編譯器便是把以上的幾個過程進行捆綁，使用戶只使用一次命令就把編譯工作完成，這的確方便了編譯工作，但對於初學者了解編譯過程就很不利了，下圖便是gcc代理的編譯過程：

從上圖可以看到：
預編譯
將.c 文件轉化成 .i文件
使用的gcc命令是：gcc –E
對應於預處理命令cpp
編譯
將.c/.h文件轉換成.s文件
使用的gcc命令是：gcc –S
對應於編譯命令 cc –S
匯編
將.s 文件轉化成 .o文件
使用的gcc 命令是：gcc –c
對應於匯編命令是 as
鏈接
將.o文件轉化成可執行程序
使用的gcc 命令是： gcc
對應於鏈接命令是 ld
總結起來編譯過程就上面的四個過程：預編譯、編譯、匯編、鏈接。了解這四個過程中所做的工作，對我們理解頭文件、庫等的工作過程是有幫助的，而且清楚的了解編譯鏈接過程還對我們在編程時定位錯誤，以及編程時盡量調動編譯器的檢測錯誤會有很大的幫助的。

㈥ C語言實現NFA轉DFA

ε只能出現在NFA中，當然不是為了方便直觀，而是連通NFA和DFA的橋梁。編譯原理講授的不是如何繪制NFA或者DFA，二是告訴讀者怎樣能夠自動實現NFA或DFA的構造。在實際應用中ε可以幫助計算機轉換NFA為DFA，而在屬性文法和語法制導階段，它也是溝通綜合屬性與繼承屬性、執行語義動作不可或缺的一部分。另外ε的使用可以大大簡化文法產生式的構造難度。我記得最初使用ε是為了使得文法體系（字母表）更加完善，但是在實際應用中卻變得應用廣泛(此觀點不一定正確)。
最後想說的是，在編譯中，ε也帶來了不小的麻煩，否則也就不會有諸如「去空產生式」這樣的演算法了:)