符號棧編譯原理

A. 這個在編譯原理中什麼意思啊

大學課程為什麼要開設編譯原理呢？這門課程關注的是編譯器方面的產生原理和技術問題，似乎和計算機的基礎領域不沾邊，可是編譯原理卻一直作為大學本科的必修課程，同時也成為了研究生入學考試的必考內容。編譯原理及技術從本質上來講就是一個演算法問題而已，當然由於這個問題十分復雜，其解決演算法也相對復雜。我們學的數據結構與演算法分析也是講演算法的，不過講的基礎演算法，換句話說講的是演算法導論，而編譯原理這門課程講的就是比較專註解決一種的演算法了。在20世紀50年代，編譯器的編寫一直被認為是十分困難的事情，第一Fortran的編譯器據說花了18年的時間才完成。在人們嘗試編寫編譯器的同時，誕生了許多跟編譯相關的理論和技術，而這些理論和技術比一個實際的編譯器本身價值更大。就猶如數學家們在解決著名的哥德巴赫猜想一樣，雖然沒有最終解決問題，但是其間誕生不少名著的相關數論。推薦參考書雖然編譯理論發展到今天，已經有了比較成熟的部分，但是作為一個大學生來說，要自己寫出一個像TurbocC,Java那樣的編譯器來說還是太難了。不僅寫編譯器困難，學習編譯原理這門課程也比較困難。第一本書的原名叫《CompilersPrinciples,Techniques,andTools》,另外一個響亮的名字就是龍書。原因是這本書的封面上有條紅色的龍，也因為獗臼樵詒嘁朐?砘?嘴域確實?忻?所以很多國外的學者都直接取名為龍書。最近機械工業出版社已經出版了此書的中文版，名字就叫《編譯原理》。該書出的比較早，大概是在85或86年編寫完成的，作者之一還是著名的貝爾實驗室的科學家。裡面講解的核心編譯原理至今都沒有變過，所以一直到今天，它的價值都非凡。這本書最大的特點就是一開始就通過一個實際的小例子，把編譯原理的大致內容羅列出來，讓很多編譯原理的初學者很快心裡有了個底,也知道為什麼會有這些理論，怎麼運用這些理論。而這一點是我感覺國內的教材缺乏的東西，所以國內的教材都不是寫給願意自學的讀者，總之讓人看了半天，卻不知道裡面的東西有什麼用。第二本書的原名叫《ModernCompilerDesign》,中文名字叫做《現代編譯程序設計》。該書由人民郵電出版社所出。此書比較關注的是編譯原理的實踐，書中給出了不少的實際程序代碼，還有很多實際的編譯技術問題等等。此書另外一個特點就是其現代而字。在傳統的編譯原理教材中，你是不可能看到如同Java中的垃圾回收等演算法的。因為Java這樣的解釋執行語言是在近幾年才流行起來的東西。如果你想深入學習編譯原理的理論知識，那麼你肯定得看前面那本龍書，如果你想自己動手做一個先進的編譯器，那麼你得看這本《現代編譯程序設計》。第三本書就是很多國內的編譯原理學者都推薦的那本《編譯原理及實踐》。或許是這本書引入國內比較早吧，我記得我是在高中就買了這本書，不過也是在前段時間才把整本書看完。此書作為入門教程也的確是個不錯的選擇。書中給出的編譯原理講解也相當細致，雖然不如前面的龍書那麼深入，但是很多地方都是點到為止，作為大學本科教學已經是十分深入了。該書的特點就是注重實踐，不過感覺還不如前面那本《現代編譯程序設計》的實踐味道更重。此書的重點還是在原理上的實踐，而非前面那本那樣的技術實踐。《編譯原理及實踐》在講解編譯原理的各個部分的同時，也在逐步實踐一個現代的編譯器TinyC.等你把整本書看完，差不多自己也可以寫一個TinyC了。作者還對Lex和Yacc這兩個常用的編譯相關的工具進行了很詳細的說明，這一點也是很難在國內的教材中看到的。推薦了這三本教材，都有英文版和中文版的。很多英文好的同學只喜歡看原版的書，不我的感覺是這三本書的翻譯都很不錯，沒有必要特別去買英文版的。理解理論的實質比理解表面的文字更為重要。編譯原理的實質幾乎每本編譯原理的教材都是分成詞法分析，語法分析（LL演算法，遞歸下降演算法，LR演算法），語義分析，運行時環境，中間代碼，代碼生成，代碼優化這些部分。其實現在很多編譯原理的教材都是按照85,86出版的那本龍書來安排教學內容的，所以那本龍書的內容格式幾乎成了現在編譯原理教材的定式，包括國內的教材也是如此。一般來說，大學裡面的本科教學是不可能把上面的所有部分都認真講完的，而是比較偏重於前面幾個部分。像代碼優化那部分東西，就像個無底洞一樣，如果要認真講，就是單獨開一個學期的課也不可能講得清楚。所以，一般對於本科生，對詞法分析和語法分析掌握要求就相對要高一點了。詞法分析相對來說比較簡單。可能是詞法分析程序本身實現起來很簡單吧，很多沒有學過編譯原理的人也同樣可以寫出各種各樣的詞法分析程序。不過編譯原理在講解詞法分析的時候，重點把正則表達式和自動機原理加了進來，然後以一種十分標準的方式來講解詞法分析程序的產生。這樣的做法道理很明顯，就是要讓詞法分析從程序上升到理論的地步。語法分析部分就比較麻煩一點了。現在一般有兩種語法分析演算法，LL自頂向下演算法和LR自底向上演算法。LL演算法還好說，到了LR演算法的時候，困難就來了。很多自學編譯原理的都是遇到LR演算法的理解成問題後就放棄了自學。其實這些東西都是只要大家理解就可以了，又不是像詞法分析那樣非得自己寫出來才算真正的會。像LR演算法的語法分析器，一般都是用工具Yacc來生成，實踐中完全沒有比較自己來實現。對於LL演算法中特殊的遞歸下降演算法，因為其實踐十分簡單，那麼就應該要求每個學生都能自己寫。當然，現在也有不少好的LL演算法的語法分析器，不過要是換在非C平台，比如Java,Delphi,你不能運用YACC工具了，那麼你就只有自己來寫語法分析器。等學到詞法分析和語法分析時候，你可能會出現這樣的疑問：詞法分析和語法分析到底有什麼？就從編譯器的角度來講，編譯器需要把程序員寫的源程序轉換成一種方便處理的數據結構（抽象語法樹或語法樹）,那麼這個轉換的過程就是通過詞法分析和語法分析的。其實詞法分析並非一開始就被列入編譯器的必備部分，只是我們為了簡化語法分析的過程，就把詞法分析這種繁瑣的工作單獨提取出來，就成了現在的詞法分析部分。除了編譯器部分，在其它地方，詞法分析和語法分析也是有用的。比如我們在DOS,Unix,Linux下輸入命令的時候，程序如何分析你輸入的命令形式，這也是簡單的應用。總之，這兩部分的工作就是把不規則的文本信息轉換成一種比較好分析好處理的數據結構。那麼為什麼編譯原理的教程都最終把要分析的源分析轉換成樹這種數據結構呢？數據結構中有Stack,Line,List這么多數據結構，各自都有各自的特點。但是Tree這種結構有很強的遞歸性，也就是說我們可以把Tree的任何結點Node提取出來後，它依舊是一顆完整的Tree。這一點符合我們現在編譯原理分析的形式語言，比如我們在函數裡面使用函樹，循環中使用循環，條件中使用條件等等，那麼就可以很直觀地表示在Tree這種數據結構上。同樣，我們在執行形式語言的程序的時候也是如此的遞歸性。在編譯原理後面的代碼生成的部分，就會介紹一種堆棧式的中間代碼，我們可以根據分析出來的抽象語法樹，很容易，很機械地運用遞歸遍歷抽象語法樹就可以生成這種指令代碼。而這種代碼其實也被廣泛運用在其它的解釋型語言中。像現在流行的Java,.NET，其底層的位元組碼bytecode,可以說就是這中基於堆棧的指令代碼的。關於語義分析，語法制導翻譯，類型檢查等等部分，其實都是一種完善前面得到的抽象語法樹的過程。比如說，我們寫C語言程序的時候，都知道，如果把一個浮點數直接賦值給一個整數，就會出現類型不匹配，那麼C語言的編譯器是怎麼知道的呢？就是通過這一步的類型檢查。像C++語言這中支持多態函數的語言，這部分要處理的問題就更復雜了。大部編譯原理的教材在這部分都是講解一些比較好的處理策略而已。因為新的問題總是在發生，舊的法不見得足夠解決。本來說，作為一個編譯器，起作用的部分就是用戶輸入的源程序到最終的代碼生成。但是在講解最終代碼生成的時候，又不得不講解機器運行環境等內容。因為如果你不知道機器是怎麼執行最終代碼的，那麼你當然無法知道如何生成合適的最終代碼。這部分內容我自我感覺其意義甚至超過了編譯原理本身。因為它會把一個計算機的程序的運行過程都通通排在你面前，你將來可能不會從事編譯器的開發工作，但是只要是和計算機軟體開發相關的領域,都會涉及到程序的執行過程。運行時環境的講解會讓你更清楚一個計算機程序是怎麼存儲，怎麼裝載，怎麼執行的。關於部分的內容，我強烈建議大家看看龍書上的講解，作者從最基本的存儲組織，存儲分配策略，非局部名字的訪問，參數傳遞，符號表到動態存儲分配(malloc,new)都作了十分詳細的說明。這些東西都是我們編寫平常程序的時候經常要做的事情，但是我們卻少去探求其內部是如何完成。關於中間代碼生成，代碼生成,代碼優化部分的內容就實在不好說了。國內很多教材到了這部分都會很簡單地走馬觀花講過去，學生聽了也只是作為了解，不知道如何運用。不過這部分內容的東西如果要認真講，單獨開一學期的課程都講不完。在《編譯原理及實踐》的書上，對於這部分的講解就恰到好處。作者主要講解的還是一種以堆棧為基礎的指令代碼，十分通俗易懂，讓人看了後，很容易模仿，自己下來後就可以寫自己的代碼生成。當然，對於其它代碼生成技術，代碼優化技術的講解就十分簡單了。如果要仔細研究代碼生成技術，其實另外還有本叫做《》,那本書現在由機械工業出版社引進的，十分厚重，而且是英文原版。不過這本書我沒有把它列為推薦書給大家，畢竟能把龍書的內容搞清楚，在中國已經就算很不錯的高手了，到那個時候再看這本《》也不遲。代碼優化部分在大學本科教學中還是一個不太重要的部分，就是算是實踐過程中，相信大家也不太運用得到。畢竟，自己做的編譯器能正確生成執行代碼已經很不錯了，還談什麼優化呢？編譯原理的課程畢竟還只是講解原理的課程，不是專門的編譯技術課程。這兩門課程是有很大的區別的。編譯技術更關注實際的編寫編譯器過程中運用到的技術，而原理的課

B. 尋求pascal計算四則混合運算的原理

在編譯原理里有講,利用堆棧.
我來簡單的說下.
程序中有2個棧,一個放數值,一個放操作符

A 程序開始後,第一次的操作符和數值先入棧
B 獲取下一個操作符NextOP
C 把NextOP和棧頂操作符進行優先順序比較

情況1.NextOP優先順序比棧頂操作符要高的話,把NextOP壓入操作符棧.繼續步驟B
情況2.NextOP優先順序比棧頂操作符要低的話,用棧頂運行符,數值棧拿頂的2個值做運算,運算結果壓入數值棧.重復步驟C 如果操作符棧為空,運算結束,步驟D

D 運算結果在數值棧
回答者： cpplyy - 千總 四級 10-8 09:12
1.分治搜索法 每次找到最後運算的符號,對其左右分別深搜到出結果為止
2.堆棧處理法 分數棧與符號棧 先定義常量數組(判斷運算\入棧\錯誤),然後從左到右依次運算 數進數棧 符號與符號棧內比較運算\入棧\錯誤操作 運算從數棧里拿數與後面的計算 然後結果入數棧 最後結果在數棧里
回答者： LXYXYNT - 舉人 四級 10-8 12:50
堆棧就行了
回答者： sd542927172 - 見習魔法師 二級 10-9 20:09
堆棧

表達式的計算應用相當廣泛，比如電力調度系統中的計算遙測、車站票務系統中的票價類型計算公式等。
本文講述中置表達式轉換為後置表達式和後置表達式的求值演算法，並給出實現的C++源代碼，同時給出一個相當簡潔的堆棧C++模板類。

中綴表達式到後綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用後綴表示法表示的等價表達式，必須了解操作符的優先順序和結合性。優先順序或者說操作符的強度決定求值順序；優先順序高的操作符比優先順序低的操作符先求值。 如果所有操作符優先順序一樣，那麼求值順序就取決於它們的結合性。操作符的結合性定義了相同優先順序操作符組合的順序（從右至左或從左至右）。
轉換過程包括用下面的演算法讀入中綴表達式的操作數、操作符和括弧：
1. 初始化一個空堆棧，將結果字元串變數置空。
2. 從左到右讀入中綴表達式，每次一個字元。
3. 如果字元是操作數，將它添加到結果字元串。
4. 如果字元是個操作符，彈出（pop）操作符，直至遇見開括弧（opening parenthesis）、優先順序較低的操作符或者同一優先順序的右結合符號。把這個操作符壓入（push）堆棧。
5. 如果字元是個開括弧，把它壓入堆棧。
6. 如果字元是個閉括弧（closing parenthesis），在遇見開括弧前，彈出所有操作符，然後把它們添加到結果字元串。
7. 如果到達輸入字元串的末尾，彈出所有操作符並添加到結果字元串。

後綴表達式求值
對後綴表達式求值比直接對中綴表達式求值簡單。在後綴表達式中，不需要括弧，而且操作符的優先順序也不再起作用了。您可以用如下演算法對後綴表達式求值：
1. 初始化一個空堆棧
2. 從左到右讀入後綴表達式
3. 如果字元是一個操作數，把它壓入堆棧。
4. 如果字元是個操作符，彈出兩個操作數，執行恰當操作，然後把結果壓入堆棧。如果您不能夠彈出兩個操作數，後綴表達式的語法就不正確。
5. 到後綴表達式末尾，從堆棧中彈出結果。若後綴表達式格式正確，那麼堆棧應該為空。

寫在這里不方便，講解的話+Q244957727
給分拉給分啦~
回答者： wind_teller - 魔法師 四級 10-10 21:57
表達式的計算應用相當廣泛，比如電力調度系統中的計算遙測、車站票務系統中的票價類型計算公式等。
本文講述中置表達式轉換為後置表達式和後置表達式的求值演算法，並給出實現的C++源代碼，同時給出一個相當簡潔的堆棧C++模板類。

中綴表達式到後綴表達式的轉換
要把表達式從中綴表達式的形式轉換成用後綴表示法表示的等價表達式，必須了解操作符的優先順序和結合性。優先順序或者說操作符的強度決定求值順序；優先順序高的操作符比優先順序低的操作符先求值。 如果所有操作符優先順序一樣，那麼求值順序就取決於它們的結合性。操作符的結合性定義了相同優先順序操作符組合的順序（從右至左或從左至右）。
轉換過程包括用下面的演算法讀入中綴表達式的操作數、操作符和括弧：
1. 初始化一個空堆棧，將結果字元串變數置空。
2. 從左到右讀入中綴表達式，每次一個字元。
3. 如果字元是操作數，將它添加到結果字元串。
4. 如果字元是個操作符，彈出（pop）操作符，直至遇見開括弧（opening parenthesis）、優先順序較低的操作符或者同一優先順序的右結合符號。把這個操作符壓入（push）堆棧。
5. 如果字元是個開括弧，把它壓入堆棧。
6. 如果字元是個閉括弧（closing parenthesis），在遇見開括弧前，彈出所有操作符，然後把它們添加到結果字元串。
7. 如果到達輸入字元串的末尾，彈出所有操作符並添加到結果字元串。

後綴表達式求值
對後綴表達式求值比直接對中綴表達式求值簡單。在後綴表達式中，不需要括弧，而且操作符的優先順序也不再起作用了。您可以用如下演算法對後綴表達式求值：
1. 初始化一個空堆棧
2. 從左到右讀入後綴表達式
3. 如果字元是一個操作數，把它壓入堆棧。
4. 如果字元是個操作符，彈出兩個操作數，執行恰當操作，然後把結果壓入堆棧。如果您不能夠彈出兩個操作數，後綴表達式的語法就不正確。
5. 到後綴表達式末尾，從堆棧中彈出結果。若後綴表達式格式正確，那麼堆棧應該為空
在編譯原理里有講,利用堆棧.
我來簡單的說下.
程序中有2個棧,一個放數值,一個放操作符

A 程序開始後,第一次的操作符和數值先入棧
B 獲取下一個操作符NextOP
C 把NextOP和棧頂操作符進行優先順序比較

情況1.NextOP優先順序比棧頂操作符要高的話,把NextOP壓入操作符棧.繼續步驟B
情況2.NextOP優先順序比棧頂操作符要低的話,用棧頂運行符,數值棧拿頂的2個值做運算,運算結果壓入數值棧.重復步驟C 如果操作符棧為空,運算結束,步驟D

D 運算結果在數值棧
.分治搜索法 每次找到最後運算的符號,對其左右分別深搜到出結果為止
2.堆棧處理法 分數棧與符號棧 先定義常量數組(判斷運算\入棧\錯誤),然後從左到右依次運算 數進數棧 符號與符號棧內比較運算\入棧\錯誤操作 運算從數棧里拿數與後面的計算 然後結果入數棧 最後結果在數棧里

C. 棧的應用舉例：數制轉換，表達式求值

關於表達式的分析與求值是計算機軟體專業中「編譯原理」課程極其重要的部分，主要用於最初的詞法分析。其表示方式有：前綴、中綴、後綴表示法。其數據結構可以使用一個堆棧來表示。具體的實現代碼，我以前使用的書籍是《C語言大全》，那上面就有完整的、現成的代碼，可以供你參考運行。同時你還可以參考《編譯原理》相關的教材。
但是由於我已經很久沒有編寫編譯原理方面的程序了，況且編寫並親自調試通過該程序，難度還是比較大的。所以我也無法親自給你編寫一個完整表達式分析與求值的程序。只能夠給你提供一些思路和線索。
另外，關於不同數制之間的轉換問題，這個倒是不難解決，可以採用通常的演算法就是短除法，然後將每一次的余數採取「倒排」即可。例如：將十進制的 15 轉換為二進制。
2|15(1
--
2|7(1
-
2|3(1
-
2|1(1

-
0
則十進制的 15 為二進制的：1111。

D. 編譯原理什麼是素短語

編譯原理中，素短語是至少含義一個終結符，並且自身不包含任何更小素短語的一種短語。

素短語是一種特殊的短語，它是一個遞歸的定義，至少含有一個終結符，並且除它自身之外不再含任何更小的素短語，所謂最左素短語就是處於句型最左邊的素短語的短語。

一個算符優先文法G的任何句型的最左素短語是滿足以下條件的最左子串NaNb…NcNdN(N是非終結符，a,b,c,d是終結符)。例如：句型T+T*F+id，T*F是最左素短語，id是素短語。

(4)符號棧編譯原理擴展閱讀：

通過語法樹可以得知素短語：

1、每個句型對應一棵語法樹

2、每棵語法樹的葉子結點從左到右排列構成一個句型

3、每棵語法樹的子樹的葉子結點從左到右排列構成一個短語

4、每棵語法樹的簡單子樹（只有父子兩層結點）的葉子結點從左到右排列構成一個簡單(直接)短語。

5、素短語是至少包含一個終結符的短語，但它不能包含其它素短語。

E. 誰能夠解釋下編譯原理中什麼是FIRSTVT,和LASTVT，盡量淺顯易懂點謝謝

Firstvt和Lastvt是為了畫算符優先關系表的（就是表裡面填優先大於小於等於的那個）。
然後要注意他們可都是終結符的集合。
Firstvt
找Firstvt的三條規則：如果要找A的Firstvt，A的候選式中出現：
A->a.......，即以終結符開頭，該終結符入Firstvt
A->B.......，即以非終結符開頭，該非終結符的Firstvt入A的Firstvt
A->Ba.....，即先以非終結符開頭，緊跟終結符，則終結符入Firstvt

Lastvt
找Lastvt的三條規則：如果要找A的Lastvt，A的候選式中出現：
A->.......a，即以終結符結尾，該終結符入Lastvt
A->.......B，即以非終結符結尾，該非終結符的Lastvt入A的Lastvt
A->.....aB，即先以非終結符結尾，前面是終結符，則終結符入Firstvt

F. 編譯原理

編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。

編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成

(6)符號棧編譯原理擴展閱讀：

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。

編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。

而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。