編譯原理狀態轉化矩陣作用

① 通過運行狀態轉換圖識別正則文法的句子。

求解啊

② 【萬分緊急】這里想做一個優先矩陣（優先表）轉換成優先函數的C語言程序（若是解決得好定追加更多！）

就是讀取文件唄，你就按照一定的規則在文件中存儲矩陣，讀在按照規則讀出來放到數組中。

③ 優先函數是什麼編譯原理

構造算符優先分析表時使用的優先函數，其等價於矩陣表，但存儲量小。
定義兩個函數，其對應元素的值為優先值，通過循環比較各元素的兩個值，每次將優先順序大的值改為小的值+1，若相等則都賦為目前較大的值，循環直至結果沒有變化，構造OK

④ [高性能計算的三大研究領域]高性能計算領域的研究內容

科學計算、海量信息處理與檢索以及正在普及的多核個人計算機是高性能計算的主要研究領域，由於領域的不同，對於高性能計算各自都有不同的研究重點。 美國宇航局(NASA)是超級計算機最大的用戶之一

從起源來看，計算機系統的原始需求來自軍事，如第一台計算機ENIAC是美國軍隊為了計算彈道而投資研製的。在隨後的30年中，計大逗算機主要應用於與國家安全相關的領域，如核武器設計、密碼破譯等。到20世紀70年代末，高性能計算機開始應用於石油工業、汽車工業等資本密集型工業。隨後，高性能計算機開始廣泛進入各個行業，協助進行產品設計、用戶分析等等。如醫葯公司使用高性能計算機輔助進行葯物設計，可以大大節省新葯的研發開支; 超市使用高性能計算機分析用戶消費模式，以推出恰當促銷措施等等。在這些領域，更高的計算性能就意味著在產品和服務方面的競爭優勢。在科學研究領域，數值模擬方法成為現代科學方法的重要組成部分，這里更高的計算性能就意味著更快的科學發現速度。目前，高性能計算技術已成為促進科技創新和經濟發展的重要手段，是一個國家綜合國力的重要組成部分。本文將就高性能的幾個最重要的應用領域進行介紹。
用高性能計算機解決科學挑戰
許多重要的科學問題非常復雜，需要功能非常強大的計算機來進行數值模擬，這些問題被視作科學上的重大挑戰，可以分為如下幾類:
1. 量子化學、統計力學和相對論物理學;
搜純2. 宇宙學和天體物理學;
3. 計算流體力學和湍流;
4. 材料設計和超導;
5. 生物學、制葯研究、基因組序列分析、基因工程、蛋白質折疊、酶活動和細胞建模;
6. 葯物、人類骨骼和器官建模;
7. 全球天氣和環境建模。
這些重大世仿咐挑戰問題大多可以看作傳統的高性能計算應用的延伸，其特點是: 大部分是浮點密集型應用程序，並行演算法要求多個並行進程之間進行較為頻繁的通信和同步，而非簡單的多個計算用例之間的並行，因此無法使用多台規模較小的系統來替代一台大規模系統。
這些重大挑戰問題對計算能力的需求遠遠超出了現有的高性能計算機的性能。以量子化學計算為例，需要20T～100Tflops的持續計算能力才能夠對目前進行的實際實驗結果進行預測。在核聚變研究領域，需要20Tflops的持續計算能力才能夠進行全規模的系統模擬。蛋白質折疊的計算需要1Tflops的持續計算速度。另一方面，重大挑戰問題對數據的存儲也提出了更高的要求，以計算生物學為例，進行蛋白質分析時需要使用的一台質譜儀每天就可以產生100GB的數據，50台質譜儀1天就可以產生5TB的數據。
目前，世界上最快IBM BlueGene/L的處理器個數為131072個，Linpack速度為280.6TFlops，達到了其峰值速度的76.5%（2005年11月數據）。但一般並行演算法要比Linpack的通信更加頻繁，訪存局部性也沒有Linpack好，這使得其並行效率相當低，通常僅能達到系統峰值速度的10％，甚至更低。為了能夠有效地解決上述重大挑戰性的問題，需要研製千萬億次高性能計算機系統，這就需要攻克系統結構、軟體工具和並行演算法等多方面的難關:

1. 能耗控制
隨著現代處理器頻率的增加，其功率也大幅度增加，最新處理器的功耗已經超過100W。這使得高性能計算系統本身的耗電問題已經十分嚴重。同時由於系統散發的大量熱量，必須在機房中採用大功率的空調系統才能保持系統機房的正常溫度。這兩方面的因素造成系統的整體電能消耗非常巨大，維護成本很高。分析結果表明，未來系統主要的維護成本將來自系統的電能消耗。在研製千萬億次高性能計算機系統時，必須重視系統的能耗問題。
目前有幾種方法來處理系統能耗問題，一是給處理器設定較低的工作電壓，通過並行性來獲得高性能，例如BlueGene/L處理器的工作頻率僅有700Mhz，因此單個內核的處理能力遠遠低於其他高頻率的處理器。但BlueGene/L通過大量的處理器來彌補單個處理器能力的不足，達到了較高的整體系統性能，並獲得了優化的性能/能耗比。另一種方法是通過軟體和硬體感測器確定和預測需要使用的部件和不需要使用的部件，然後將不需要立即使用的部分通過某種措施，如降低頻率或完全關閉來減少其耗電量，從而達到降低整個系統功耗的目的。這方面的工作根據控制的粒度不同可分為晶元級、主板/BIOS級以及結點級。

2. 高性能計算軟體與演算法
大規模並行處理硬體系統僅僅為高性能計算提供了一個平台，真正的功能還要通過高性能計算軟體來完成。高性能計算軟體與演算法的主要工作可以分為3類:
（1） 提出具有較低理論復雜度或較好實際性能的串列演算法
盡管可以通過並行計算來加快運算的速度，但並行處理往往需要較大的軟體開發成本和硬體成本，因此在進行並行演算法的開發之前，必須考察是否存在可以解決問題的更好串列演算法。以整數排序問題為例，使用並行的冒泡排序演算法，其效果還不如使用串列的快速排序演算法。因此，高效的串列演算法研究是高性能演算法研究的重要課題。著名的演算法包括線性規劃問題的單純型法、FFT、快速排序、矩陣特徵值的QR演算法、快速多極演算法等。近年來在演算法方面的突破使印度學者在素數判定問題上提出了多項式復雜度演算法。
（2） 優化現有演算法
演算法只提供了理論上的性能，要在實際系統上獲得高性能，必須對演算法的實現進行優化。現代處理器大多使用多級Cache來隱藏訪存延遲，因此必須根據目標系統的Cache參數來優化演算法的訪存行為。此外，許多處理器還提供了SIMD指令，合理使用這些指令可以達到較高的性能。許多優化的數學庫，如ATLAS、Intel公司的MKL等已經為不同的體系結構，特別是Cache配置進行了特別優化，可以達到較高的執行效率，為優化演算法實現提供了很好的幫助。
(3) 並行演算法與並行應用的開發
並行演算法的研究與串列演算法有聯系也有區別。優秀的串列演算法並不一定適合並行化，某些時候在串列演算法中並非最優的演算法在並行實現時卻能體現出較大的優勢。對於千萬億次計算機而言，其處理器（核）個數在10萬以上，並行應用的並行度需要達到數萬個並行進程才能有效地利用千萬億次計算機。並行演算法的三個主要優化目標是: 通信優化、負載平衡以及最大化並行區。通信優化的目標是盡量減少通信次數和通信量，減少由於處理器之間通信帶寬限制引起的性能下降。在大規模並行程序中，負載平衡問題也非常突出，少數負載不平衡的任務會使得整體性能急劇下降。同樣的，根據Amdahl定律，應用加速比的上限是串列區所佔比例的倒數，即應用中1％的串列區域就會使得整個應用程序的加速比不可能超過100。因此，要在數萬個並行進程的情況下取得理想的加速比給並行演算法的開發提出了很大的挑戰。

3. 系統可靠性與可管理性
隨著系統內結點個數的增加，系統失效的可能性也隨著增大。並行程序的特點是只要有一個並行進程失敗，整個並行程序都執行不成功。對可靠性問題的處理方法之一是設法提高系統的穩定性，這包括硬體系統可靠性和軟體系統的可靠性。但目前公認的結論是: 大規模系統的故障是在設計時必須考慮的前提條件，而並非可以通過技術手段加以解決的問題。因此，必須考慮如何在系統結點出現故障的情況下仍然能夠保證系統服務質量不發生顯著下降。
故障監測技術和動態系統重構技術可以用來減少或消除系統失效對應用的影響，即盡快隔離出現問題的結點，使得用戶可以使用狀態正常的結點進行計算。與系統動態重構技術類似的技術還有系統動態劃分技術，主要用於向不同的用戶提供相互獨立的結點集，使得整個系統的管理和使用更加有效和安全。
但是上述技術僅能解決系統對新的應用的服務質量問題，無法保證已經執行的應用在某個計算結點出現問題後的處理。某些並行應用，如石油數據處理需要連續運行幾十天的時間，一旦某個結點出現錯誤，會使得前面的計算前功盡棄，需要從頭開始計算。並行檢查點技術主要提供應用級的容錯，即能夠自動地定期記錄並行程序的狀態（稱作檢查點），在計算過程中某個結點發生失效後，可以從所記錄的並行程序檢查點恢復執行，避免了重新執行整個程序。

高性能計算與海量信息處理

人類所產生的信息量以指數速度增長，如何存儲、檢索和利用這些信息為信息技術提出了重要挑戰。從20世紀90年代開始，互聯網的飛速發展給信息的傳播與服務提供了新的機遇。傳統的信息服務系統以資料庫為中心，典型應用是OLTP（事務聯機處理）。而以Google為代表的海量信息檢索與處理服務是另一類重要應用，以Google集群系統為代表的系統體現了高性能計算系統的另一個發展方向。
信息檢索與處理服務系統的特點與科學計算非常不同，對處理系統也提出了不同的要求:
1. 信息處理與服務應用需要頻繁訪問動態的數據結構，包含很多不可預測的分支，使得現有超標量處理器中的許多技術，如分支預測、數據預取、亂序和推測執行等功能無法很好地發揮作用，應用的指令級並行性較差。
2. 大部分信息處理與服務應用具有較好的數據並行性，可以很容易地在分布式系統上執行。以信息檢索為例，一個信息檢索請求可以被分配到多個伺服器上進行並行檢索，最後再將搜索結果統一處理返回給用戶。這個過程中大多數的訪問是只讀的數據，並行任務之間的通信非常少，並行效率比較高。
3. 系統的性能指標一般不以單個服務請求的響應時間為量度，而更關注系統整體的吞吐率。以搜索引擎為例，信息服務系統更重視在1分鍾內能夠完成的用戶搜索次數，而對單次搜索在0.5秒內完成還是1秒內完成並不特別敏感。
4. 系統需要很高的可靠性和可維護性。可靠性是對服務而言的，即組成的系統必須能夠近乎不間斷地為用戶提供服務。可維護性是指系統的更換與維修可以簡單快捷地完成，新更換的結點可以快捷地加入到系統中。
5. 低成本。這包括系統構建成本和總擁有成本兩部分。海量信息處理和服務所需的系統規模極為龐大，Google Cluster在2003年就達到了15000台計算機的規模。如此巨大規模的系統，需要盡可能地降低成本。
為了能夠有效滿足上述信息處理與服務系統的要求，人們對於如何高效地構建相應的服務系統也展開了研究與實踐:
1. 使用副本技術通過軟體提供可靠性
在大規模系統中，單個系統結點的失效是不可避免的。現有的通過冗餘底層硬體提高系統可靠性的方式，比如冗餘電源、RAID技術等，成本較高，性價比較差。相反，在信息服務系統中可以廣泛使用軟體提供服務級別的可靠性。主要的方法是採用副本，即將服務和數據復制到多個系統結點上，即使單個系統結點的可靠性不是很高，多個副本提供了服務所需的可靠性。另一個使用副本技術的優點在於其提高系統可靠性的同時也提高了系統的性能，即保存副本的多個系統結點可以同時向用戶提供服務。
2. 注重系統的性能/價格比
由於信息服務系統應用容易並行的特點，採用大量低端系統組合的方法比使用少量高端系統在性能價格比方面更具有優勢（此處所指的低端系統是指1～2個CPU的PC機或入門伺服器，高端系統是指大規模處理器伺服器，如HP 的Superdom伺服器、IBM的P690伺服器等）。此外，信息服務系統與用於科學計算的高性能系統面臨同樣的挑戰: 能耗問題。在大規模信息處理與服務系統中，電費成本（包括系統本身耗電和空調系統耗電）將佔有總擁有成本的很大一部分。因此，在選用系統時，應選擇性能/能耗比較高的系統也是一個重要的原則。
(3) 使用多內核處理器
由於信息服務程序的特點，它更適合使用多個簡單內核構成的處理器，這些簡單內核僅需要按序執行，並使用較短的流水線。由於信息服務應用的指令級並行度較差，按序執行不會造成太多的性能下降，但可以節省復雜的亂序執行單元電路，從而可以降低功耗。另一方面，較短的流水線可以降低分支預測失效的開銷。
並行計算與個人計算機
隨著半導體工藝的發展，單個晶元上能夠集成的元件個數還將在5～10年內遵循摩爾定律繼續以指數級增長。但是當前的晶元散熱技術已無法支持晶元頻率的進一步提高，而通過提高發射寬度、提高分支預測效率以及數據預取等進一步在體系結構上提高單線程執行速度的方法也逐漸失去了有效性。多內核晶元通過在一個晶元內集成多個處理器內核，採用線程級並行提高處理器性能，已成為微處理器的主要發展趨勢。IBM公司在幾年前就推出了雙內核Power晶元，Intel公司和AMD在2005年推出的雙內核晶元更是標志著多內核技術進入了普及階段。支持更多核心的處理器晶元也正在快速涌現，如Sun公司已經推出了8核的Nigeria晶元，用於面向提高吞吐率的伺服器應用; IBM則聯合索尼和東芝推出了面向娛樂應用的9內核Cell晶元。Intel公司甚至已經在計劃100內核以上的處理器。
多核處理器的出現給計算機的使用帶來了新的挑戰。隨著多內核處理器的普及，成千上萬的桌面電腦將成為並行計算機。目前在桌面機上執行的應用程序大多數是單線程程序，無法有效利用多內核處理器提供的能力。如何有效地在個人電腦上利用多個處理器內核成為高性能計算領域一個重要的研究課題，從目前的趨勢來看主要有以下幾個方向:
1.使用多任務帶來的並發性
Intel的 雙核ViiV家用電腦是這方面的典型例子。ViiV電腦的典型使用模式是一個人在客廳使用ViiV電腦看電影，另一個在自己的房間里使用同一台電腦玩游戲，兩個人使用同一台電腦中的不同處理器內核，從而達到了有效發揮雙核能力的目的。但這種依靠多個用戶同時使用一台電腦的模式具有很大局限性，因為家庭成員的個數是有限的，對於4內核以上的多內核處理器，這種模式無法提供有效的支持。
2.聚合多內核的能力，加速串列程序的執行速度
計算機科學家們正在研究一種稱作推測多線程（TLS: Thread-Level Speculation）的技術，該技術可以自動分析串列程序，推測其中能夠並行執行的部分，在多個內核上並行執行。但一旦發現並行執行的部分有沖突，就撤銷其中一個沖突線程的執行，執行補償操作並重新執行該線程。推測多線程技術的優點在於無需用戶干預就可以在多內核系統上加速現有單線程程序，其缺點在於對於性能提高的幅度有限,大約在4內核系統上僅能比在單個內核上提高性能30％，而且再增加內核數，其加速比也不會顯著增加。因此，這種方式也無法支持更多內核的處理器。
另一種有前途的技術是自動並行化技術。自動並行化技術可以在編譯時識別程序中的並行性，並將其轉化為多線程並行程序。過去的自動並行化技術主要是面向SMP系統的，但不是很成功，原因是對真實應用程序，自動並行化無法得到滿意的加速比。一個程序通過自動並行化在4 CPU的SMP系統上得到20%的加速比是不能令人滿意的，因為4 CPU的系統通常價格是單CPU價格的10倍以上，自動並行化無法提供性能價格比上的優勢。但是對於多內核系統，如果能夠在四內核系統上通過自動並行化得到20％的加速比，應該是比較令人滿意的結果，因為這些內核是「免費」提供給用戶的，即用戶無法用四內核處理器1/4的價格購買一個單內核處理器。因此，多內核處理器在家用電腦上的普及，將大大降低人們對自動並行化效果的期望，使得自動並行化技術重新被接受和應用。
3. 並行化現有的桌面應用
既然採用多內核處理器加速串列應用無法充分利用多內核處理器的能力，那麼並行化現有的桌面應用就成為了一個重要選擇。這方面的研究主要是分析現有的桌面應用，對有代表性的應用進行手工並行化，這些研究試圖回答下面的問題: 哪些桌面應用能夠被有效並行化，哪些不能？並行化本身的難度有多大？應如何改進現有的編程模型、編程工具以及系統軟體來更好地支持應用的並行化？
研究表明，桌面系統上的大部分應用，如圖像處理、3D圖形運算、多媒體數據編碼與解碼、數據與文本挖掘、文本與媒體搜索、游戲與博弈等都可以有效地被並行化，並在多內核系統上得到有效的執行。但是，手工程序並行化的開銷仍然很大，並行程序員需要了解並行計算的有關知識，並對計算機體系結構、操作系統、編譯原理等有一定了解才能寫出有效率的並行程序。並行編程模型與並行編程工具還需要提供更好的支持，以幫助並行程序員開發、調試並行程序。
今天，高性能計算技術已成為整個計算機領域的引領技術。多內核處理器的出現，使得並行計算技術將很快普及到我們的每台計算機，滲入到我們生活的方方面面，這是計算機產業發展史上的一個重大變革，對我國而言是一次難得的機會。在「十一五」期間，我國將進一步加強對高性能計算技術研究的支持，注重引導企業應用高性能計算技術促進產業升級和科技創新，同時更加特別重視高性能計算技術的教育培訓工作，在高校的理工專業廣泛開設並行程序設計課程，培養更多了解和使用高性能計算技術的人才，在此次變革中實現跨越性的發展。

作者簡介
陳文光
清華大學計算機博士，清華大學計算機系副教授，863高性能計算機評測中心副主任。曾任Opportunity International Inc.總工程師。主要研究領域為並行計算的編程模型、並行化編譯和並行應用分析。

鏈接:高性能計算發展趨勢
隨著應用的需求與計算機技術本身的發展，近年來高性能計算的發展體現出一些新的特點，可以用「大，寬，小」來代表這三個特點:
「大」是指高性能計算系統向更大規模發展，處理器個數可達10萬個以上，主要用於解決超大規模的數值模擬問題。
「寬」是指在傳統的數值計算之外，高性能計算系統正越來越廣泛地應用於信息處理和服務領域，為海量信息的存儲與檢索以及網路服務提供有效的保證。
「小」是指多內核CPU的出現和普及，將使得今後的每台個人計算機都成為並行計算機，如何有效地利用個人計算機的多個內核是對高性能計算技術提出的新挑戰。

⑤ 編譯原理NFA轉DFA ，請問DFA的初始狀態如何確定

NFA確定化的時候，包含NFA初態的那個DFA狀態就是確定後的DFA的初態。

DFA的終態就是所有包含了NFA終態的DFA的狀態。

對於DFA來說，他的初態就是包含了NFA唯一初態1的那個狀態，就是左邊的1，2右邊的1了。

脫氧核糖-磷酸鏈在螺旋結構的外面，鹼基朝向裡面。兩條多脫氧核苷酸鏈反向互補，通過鹼基間的氫鍵形成的鹼基配對相連，形成相當穩定的組合。

(5)編譯原理狀態轉化矩陣作用擴展閱讀：

將DNA或RNA序列以三個核苷酸為一組的密碼子轉譯為蛋白質的氨基酸序列，以用於蛋白質合成。密碼子由mRNA上的三個核苷酸（例如ACU，CAG，UUU）的序列組成，每三個核苷酸與特定氨基酸相關。

例如，三個重復的胸腺嘧啶（UUU）編碼苯丙氨酸。使用三個字母，可以擁有多達64種不同的組合。由於有64種可能的三聯體和僅20種氨基酸，因此認為遺傳密碼是多餘的（或簡並的）：一些氨基酸確實可以由幾種不同的三聯體編碼。

但每個三聯體將對應於單個氨基酸。最後，有三個三聯體不編碼任何氨基酸，它們代錶停止（或無意義）密碼子，分別是UAA，UGA和UAG 。

⑥ 軟考中級軟體設計師要學會哪種程序設計語言（我只學過C，C++，匯編）

朋友，我考過，別聽他們胡說
軟體設計師考試分上午和下午
上午的考試是選擇題目，范圍很廣
C和C++都有，但題目難度不大，匯編語言不考，建議多看看軟體工程的理論知識，考得很多，特別在下午。還有操作系統，編譯原理等跟計算機專業相關的理論
下面給出大綱：
軟體設計師考試大綱
一、考試說明
1．考試要求：
(1) 掌握數據表示、算術和邏輯運算；
(2) 掌握相關的應用數學、離散數學的基礎知識；
(3) 掌握計算機體系結構以及各主要部件的性能和基本工作原理；
(4) 掌握操作系統、程序設計語言的基礎知識，了解編譯程序的基本知識；
(5) 熟練掌握常用數據結構和常用演算法；
(6) 熟悉資料庫、網路和多媒體的基礎知識；
(7) 掌握C程序設計語言，以及C++、Java、Visual、Basic、Visual C++中的一種程序設計語言；
(8) 熟悉軟體工程、軟體過程改進和軟體開發項目管理的基礎知識；
(9) 熟悉掌握軟體設計的方法和技術；
(10) 掌握常用信息技術標准、安全性，以及有關法律、法規的基本知識；
(11) 了解信息化、計算機應用的基礎知識；
(12) 正確閱讀和理解計算機領域的英文資料。
2．通過本考試的合格人員能根據軟體開發項目管理和軟體工程的要求，按照系統總體設計規格說明書進行軟體設計，編寫程序設計規格說明書等相應的文檔，組織和指導程序員編寫、調試程序，並對軟體進行優化和集成測試，開發出符合系統總體設計要求的高質量軟體；具有工程的實際工作能力和業務水平。
3．本考試設置的科目包括：
(1) 計算機與軟體工程知識，考試時間為150分鍾，筆試；
(2) 軟體設計，考試時間為150分鍾，筆試。
二、考試范圍
考試科目1：計算機與軟體工程知識
1． 計算機科學基礎
1.1 數制及其轉換
• 二進制、十進制和十六進制等常用制數制及其相互轉換
1.2 數據的表示
• 數的表示（原碼、反碼、補碼、移碼表示，整數和實數的機內表示，精度和溢出）
• 非數值表示（字元和漢字表示、聲音表示、圖像表示）
• 校驗方法和校驗碼（奇偶校驗碼、海明校驗碼、循環冗餘校驗碼）
1.3 算術運算和邏輯運算
• 計算機中的二進制數運算方法
• 邏輯代數的基本運算和邏輯表達式的化簡
1.4 數學基礎知識
• 命題邏輯、謂詞邏輯、形式邏輯的基礎知識
• 常用數值計算（誤差、矩陣和行列式、近似求解方程、插值、數值積分）
• 排列組合、概率論應用、應用統計（數據的統計分析）
• 運算基本方法（預測與決策、線性規劃、網路圖、模擬）
1.5 常用數據結構
• 數組（靜態數組、動態數組）、線性表、鏈表（單向鏈表、雙向鏈表、循環鏈表）、隊列、棧、樹（二叉樹、查找樹、平衡樹、線索樹、線索樹、堆）、圖等的定義、存儲和操作
• Hash（存儲地址計算，沖突處理）
1.6 常用演算法
• 排序演算法、查找演算法、數值計算方法、字元串處理方法、數據壓縮演算法、遞歸演算法、圖的相關演算法
• 演算法與數據結構的關系、演算法效率、演算法設計、演算法描述（流程圖、偽代碼、決策表）、演算法的復雜性
2． 計算機系統知識
2.1 硬體知識
2.1.1 計算機系統的組成、體系結構分類及特性
• CPU和存儲器的組成、性能和基本工作原理
• 常用I/O設備、通信設備的性能，以及基本工作原理
• I/O介面的功能、類型和特性
• I/O控制方式（中斷系統、DMA、I/O處理機方式）
• CISC/RISC，流水線操作，多處理機，並行處理
2.1.2 存儲系統
• 主存-Cache存儲系統的工作原理
• 虛擬存儲器基本工作原理，多級存儲體系的性能價格
• RAID類型和特性
2.1.3 安全性、可靠性與系統性能評測基礎知識
• 診斷與容錯
• 系統可靠性分析評價
• 計算機系統性能評測方式
2.2 軟體知識
2.2.1 操作系統知識
• 操作系統的內核（中斷控制）、進程、線程概念
• 處理機管理（狀態轉換、共享與互斥、分時輪轉、搶占、死鎖）
• 存儲管理（主存保護、動態連接分配、分段、分頁、虛存）
• 設備管理（I/O控制、假離線）
• 文件管理（文件目錄、文件組織、存取方法、存取控制、恢復處理）
• 作業管理（作業調度、作業控制語言（JCL）、多道程序設計）
• 漢字處理，多媒體處理，人機界面
• 網路操作系統和嵌入式操作系統基礎知識
• 操作系統的配置
2.2.2 程序設計語言和語言處理程序的知識
• 匯編、編譯、解釋系統的基礎知識和基本工作原理
• 程序設計語言的基本成分：數據、運算、控制和傳輸，過程（函數）調用
• 各類程序設計語言主要特點和適用情況
2.3 計算機網路知識
• 網路體系結構（網路拓撲、OSI/RM、基本的網路協議）
• 傳輸介質、傳輸技術、傳輸方法、傳輸控制
• 常用網路設備和各類通信設備
• Client/Server結構、Browser/Server結構
• LAN拓撲，存取控制，LAN的組網，LAN間連接，LAN-WAN連接
• 網際網路基礎知識以及應用
• 網路軟體
• 網路管理
• 網路性能分析
2.4 資料庫知識
• 資料庫管理系統的功能和特徵
• 資料庫模型（概念模式、外模式、內模式）
• 數據模型，ER圖，第一範式、第二範式、第三範式
• 數據操作（集合運算和關系運算）
• 資料庫語言（SQL）
• 資料庫的控制功能（並發控制、恢復、安全性、完整性）
• 數據倉庫和分布式資料庫基礎知識
2.5 多媒體知識
• 多媒體系統基礎知識，多媒體設備的性能特性，常用多媒體文件格式
• 簡單圖形的繪制，圖像文件的處理方法
• 音頻和視頻信息的應用
• 多媒體應用開發過程
2.6 系統性能知識
• 性能指標（響應時間、吞吐量、周轉時間）和性能設計
• 性能測試和性能評估
• 可靠性指標及計算、可靠性設計
• 可靠性測試和可靠性評估
2.7 計算機應用基礎知識
•信息管理、數據處理、輔助設計、自動控制、科學計算、人工智慧等基礎知識
• 遠程通信服務基礎知識
• 常用應用系統
3． 系統開發和運行知識
3.1 軟體工程、軟體過程改進和軟體開發項目管理知識
• 軟體工程知識
• 軟體開發生命周期各階段的目標和任務
• 軟體開發項目管理基礎知識（時間管理、成本管理、質量管理、人力資源管理、風險管理等）及其常用管理工具
• 主要的軟體開發方法（生命周期法、原型法、面向對象法、CASE）
• 軟體開發工具與環境知識
• 軟體過程改進知識
• 軟體質量管理知識
• 軟體開發過程評估、軟體能力成熟評估基礎知識
3.2 系統分析基礎知識
• 系統分析的目的和任務
•結構化分析方法（數據流圖（DFD）、數據字典（DD）、實體關系圖（ERD）、描述加工處理的結構化語言）
• 統一建模語言（UML）
• 系統規格說明書
3.3 系統設計知識
• 系統設計的目的和任務
• 結構化設計方法和工具（系統流程圖、HIPO圖、控制流程圖）
• 系統總體結構設計（總體布局、設計原則、模塊結構設計、數據存儲設計、系統配置方案）
• 系統詳細設計（代碼設計、資料庫設計、用戶界面設計、處理過程設計）
• 系統設計說明書
3.4 系統實施知識
• 系統實施的主要任務
• 結構化程序設計、面向對象程序設計、可視化程序設計
• 程序設計風格
• 程序設計語言的選擇
• 系統測試的目的、類型，系統測試方法（黑盒測試、白盒測試、灰盒測試）
• 測試設計和管理（錯誤曲線、錯誤排除、收斂、注入故障、測試用例設計、系統測試報告）
• 系統轉換基礎知識
3.5 系統運行和維護知識
• 系統運行管理基礎知識
• 系統維護基礎知識
• 系統評價基礎知識
3.6 面向對象開發方法
• 面向對象開發概念（類、對象、屬性、封裝性、繼承性、多態性、對象之間的引用）
• 面向對象開發方法的優越性以及有效領域
• 面向對象設計方法（體系結構、類的設計、用戶介面設計）
• 面向對象實現方法（選擇程序設計語言、類的實現、方法的實現、用戶介面的實現、准備測試數據）
• 面向對象程序設計語言（如C++、Java、Visual、Bsasic、Visual C++）的基本機制
• 面向對象資料庫、分布式對象的概念
4． 安全性知識
• 安全性基本概念
• 防治計算機病毒、防範計算機犯罪
• 存取控制、防闖入、安全管理措施
• 加密與解密機制
•風險分析、風險類型、抗風險措施和內部控制
5． 標准化知識
• 標准化意識、標准化的發展、標准制訂過程
• 國際標准、國家標准、行業標准、企業標准基本知識
• 代碼標准、文件格式標准、安全標准、軟體開發規范和文檔標准知識
• 標准化機構
6． 信息化基礎知識
• 信息化意識
• 全球信息化趨勢、國家信息化戰略、企業信息化戰略和策略
• 有關的法律、法規
• 遠程教育、電子商務、電子政務等基礎知識
• 企業信息資源管理基礎知識
7． 計算機專業英語
• 掌握計算機技術的基本詞彙
• 能正確閱讀和理解計算機領域的英文資料
考試科目2：軟體設計
1． 外部設計
1.1 理解系統需求說明
1.2 系統開發的准備
• 選擇開發方法、准備開發環境、制訂開發計劃
1.3 設計系統功能
• 選擇系統結構，設計各子系統的功能和介面，設計安全性策略、需求和實現方法，制訂詳細的工作流和數據流
1.4 設計數據模型
• 設計ER模型、數據模型
1.5 編寫外部設計文檔
• 系統配置圖、各子系統關系圖、系統流程圖、系統功能說明書、輸入輸出規格說明、數據規格說明、用戶手冊框架
• 設計系統測試要求
1.6 設計評審
2． 內部設計
2.1 設計軟體結構
•按構件分解，確定構件功能規格以及構件之間的介面
• 採用中間件和工具
2.2 設計輸入輸出
• 屏幕界面設計、設計輸入輸出檢查方法和檢查信息
2.3 設計物理數據
• 分析數據特性，確定邏輯數據組織方式、存儲介質，設計記錄格式和處理方式
• 將邏輯數據結構換成物理數據結構，計算容量，進行優化
2.4 構件的創建和重用
• 創建、重用構件的概念
• 使用子程序庫或類庫
2.5 編寫內部設計文檔
• 構件劃分圖、構件間的介面、構件處理說明、屏幕設計文檔、報表設計文檔、文件設計文檔、資料庫設計文檔
2.6 設計評審
3．程序設計
3.1 模塊劃分（原則、方法、標准）
3.2 編寫程序設計文檔
• 模塊規格說明書（功能和介面說明、程序處理邏輯的描述、輸入輸出數據格式的描述）
• 測試要求說明書（測試類型和目標、測試用例、測試方法）
3.3 程序設計評審
4．系統實施
4.1 配置計算機系統及其環境
4.2 選擇合適的程序設計語言
4.3 掌握C程序設計語言，以及C++、Java、Visual、Basic、Visual C++中任一種程序設計語言，以便能指導程序員進行編程和測試，並進行必要的優化
4.4 系統測試
• 指導程序員進行模塊測試，並進行驗收
• 准備系統集成測試環境和測試工具
• 准備測試數據
• 寫出測試報告
5．軟體工程
• 軟體生存期模型（瀑布模型、螺旋模型、噴泉模型）和軟體成本模型
• 定義軟體需求（系統化的目標、配置、功能、性能和約束）
• 描述軟體需求的方法（功能層次模型、數據流模型、控制流模型、面向數據的模型、面向對象的模型等）
• 定義軟體需求的方法（結構化分析方法、面向對象分析方法）
• 軟體設計（分析與集成、逐步求精、抽象、信息隱蔽）
• 軟體設計方法（結構化設計方法、Jackson方法、Warnier方法、面向對象設計方法）
• 程序設計（結構化程序設計、面向對象程序設計）
• 軟體測試的原則與方法
• 軟體質量（軟體質量特性、軟體質量控制）
• 軟體過程評估基本方法、軟體能力成熟度評估基本方法
• 軟體開發環境和開發工具（分析工具、設計工具、編程工具、測試工具、維護工具、CASE）
• 軟體工程發展趨勢（面向構件，統一建模語言（UML））
•軟體過程改進模型和方法

⑦ 編譯原理試題·

Lex和Yacc應用方法(一).初識Lex
草木瓜 20070301
Lex(Lexical Analyzar 詞法分析生成器)，Yacc(Yet Another Compiler Compiler
編譯器代碼生成器)是Unix下十分重要的詞法分析，語法分析的工具。經常用於語言分
析，公式編譯等廣泛領域。遺憾的是網上中文資料介紹不是過於簡單，就是跳躍太大，
入門參考意義並不大。本文通過循序漸進的例子，從0開始了解掌握Lex和Yacc的用法。

一.Lex(Lexical Analyzar) 初步示例
先看簡單的例子(註：本文所有實例皆在RetHat linux下完成):
一個簡單的Lex文件 exfirst.l 內容：
%{
#include "stdio.h"
%}
%%
[\n] ;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在命令行下執行命令flex解析，會自動生成lex.yy.c文件：
[root@localhost liweitest]flex exfirst.l
進行編譯生成parser可執行程序：
[root@localhost liweitest]cc -o parser lex.yy.c -ll
[注意：如果不加-ll鏈結選項，cc編譯時會出現以下錯誤，後面會進一步說明。]
/usr/lib/gcc-lib/i386-redhat-linux/3.2.2/../../../crt1.o(.text+0x18): In function `_start':
../sysdeps/i386/elf/start.S:77: undefined reference to `main'
/tmp/cciACkbX.o(.text+0x37b): In function `yylex':
: undefined reference to `yywrap'
/tmp/cciACkbX.o(.text+0xabd): In function `input':
: undefined reference to `yywrap'
collect2: ld returned 1 exit status

創建待解析的文件 file.txt：
title
i=1+3.9;
a3=909/6
bcd=4%9-333
通過已生成的可執行程序，進行文件解析。
[root@localhost liweitest]# ./parser < file.txt
Var : title
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
到此Lex用法會有個直觀的了解：
1.定義Lex描述文件
2.通過lex，flex工具解析成lex.yy.c文件
3.使用cc編譯lex.yy.c生成可執行程序

再來看一個比較完整的Lex描述文件 exsec.l ：

%{
#include "stdio.h"
int linenum;
%}
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}
進行解析編譯：
[root@localhost liweitest]flex exsec.l
[root@localhost liweitest]cc -o parser lex.yy.c
[root@localhost liweitest]./parser < file.txt
----- Lex Example -----
Var : i
Unknown : =
Int : 1
Op : +
Float : 3.9
Unknown : ;
Var : a3
Unknown : =
Int : 909
Op : /
Int : 6
Var : bcd
Unknown : =
Int : 4
Op : %
Int : 9
Op : -
Int : 333
Line Count: 4
這里就沒有加-ll選項，但是可以編譯通過。下面開始著重整理下Lex描述文件.l。

二.Lex(Lexical Analyzar) 描述文件的結構介紹
Lex工具是一種詞法分析程序生成器，它可以根據詞法規則說明書的要求來生成單詞識
別程序，由該程序識別出輸入文本中的各個單詞。一般可以分為<定義部分><規則部
分><用戶子程序部分>。其中規則部分是必須的，定義和用戶子程序部分是任選的。

(1)定義部分
定義部分起始於 %{ 符號，終止於 %} 符號，其間可以是包括include語句、聲明語句
在內的C語句。這部分跟普通C程序開頭沒什麼區別。
%{
#include "stdio.h"
int linenum;
%}
(2) 規則部分
規則部分起始於"%%"符號，終止於"%%"符號，其間則是詞法規則。詞法規則由模式和
動作兩部分組成。模式部分可以由任意的正則表達式組成，動作部分是由C語言語句組
成，這些語句用來對所匹配的模式進行相應處理。需要注意的是，lex將識別出來的單
詞存放在yytext[]字元數據中，因此該數組的內容就代表了所識別出來的單詞的內容。
類似yytext這些預定義的變數函數會隨著後面內容展開一一介紹。動作部分如果有多
行執行語句，也可以用{}括起來。
%%
title showtitle();
[\n] linenum++;
[0-9]+ printf("Int : %s\n",yytext);
[0-9]*\.[0-9]+ printf("Float : %s\n",yytext);
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
[\+\-\*\/\%] printf("Op : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
A.規則部分的正則表達式
規則部分是Lex描述文件中最為復雜的一部分，下面列出一些模式部分的正則表達式字
符含義：
A-Z, 0-9, a-z 構成模式部分的字元和數字。
- 指定范圍。例如：a-z 指從 a 到 z 之間的所有字元。
\ 轉義元字元。用來覆蓋字元在此表達式中定義的特殊意義，
只取字元的本身。

[] 表示一個字元集合。匹配括弧內的任意字元。如果第一個字
符是^那麼它表示否定模式。例如: [abC] 匹配 a, b, 和C
的任何一個。

^ 表示否定。
* 匹配0個或者多個上述模式。
+ 匹配1個或者多個上述模式。
? 匹配0個或1個上述模式。
$ 作為模式的最後一個字元時匹配一行的結尾。
{ } 表示一個模式可能出現的次數。 例如: A{1,3} 表示 A 可
能出現1次或3次。[a-z]{5} 表示長度為5的，由a-z組成的
字元。此外，還可以表示預定義的變數。

. 匹配任意字元，除了 \n。
( ) 將一系列常規表達式分組。如：{Letter}({Letter}|{Digit})*
| 表達式間的邏輯或。
"一些符號" 字元的字面含義。元字元具有。如："*" 相當於 [\*]。
/ 向前匹配。如果在匹配的模式中的"/"後跟有後續表達式，
只匹配模版中"/"前面的部分。如：模式為 ABC/D 輸入 ABCD，
時ABC會匹配ABC/D，而D會匹配相應的模式。輸入ABCE的話，
ABCE就不會去匹配ABC/D。

B.規則部分的優先順序

規則部分具有優先順序的概念，先舉個簡單的例子：

%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
%%
此時，如果輸入內容：
[root@localhost liweitest]# cat file1.txt
AAAAAAA
[root@localhost liweitest]# ./parser < file1.txt
THREE
TWO
ONE
Lex分析詞法時，是逐個字元進行讀取，自上而下進行規則匹配的，讀取到第一個A字元
時，遍歷後發現三個規則皆匹配成功，Lex會繼續分析下去，讀至第五個字元時，發現
"AAAA"只有一個規則可用，即按行為進行處理，以此類推。可見Lex會選擇最長的字元
匹配規則。
如果將規則
AAAA {printf("THREE\n");};
改為
AAAAA {printf("THREE\n");};
./parser < file1.txt 輸出結果為：
THREE
TWO

再來一個特殊的例子：
%%
title showtitle();
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
%%
並輸入title，Lex解析完後發現，仍然存在兩個規則，這時Lex只會選擇第一個規則，下面
的則被忽略的。這里就體現了Lex的順序優先順序。把這個例子稍微改一下：
%%
[a-zA-Z][a-zA-Z0-9]* printf("Var : %s\n",yytext);
title showtitle();
%%
Lex編譯時會提示：warning, rule cannot be matched.這時處理title字元時，匹配
到第一個規則後，第二個規則就無效了。
再把剛才第一個例子修改下，加深下印象！
%{
#include "stdio.h"
%}
%%
[\n] ;
A {printf("ONE\n");};
AA {printf("TWO\n");};
AAAA {printf("THREE\n");};
AAAA {printf("Cannot be executed!");};
./parser < file1.txt 顯示效果是一樣的，最後一項規則肯定是會忽略掉的。

C.規則部分的使用變數
且看下面示例：
%{
#include "stdio.h"
int linenum;
%}
int [0-9]+
float [0-9]*\.[0-9]+
%%
{int} printf("Int : %s\n",yytext);
{float} printf("Float : %s\n",yytext);
. printf("Unknown : %c\n",yytext[0]);
%%
在%}和%%之間，加入了一些類似變數的東西，注意是沒有;的，這表示int，float分
別代指特定的含義，在兩個%%之間，可以通過{int}{float}進行直接引用，簡化模
式定義。

(3) 用戶子程序部分
最後一個%%後面的內容是用戶子程序部分，可以包含用C語言編寫的子程序，而這些子
程序可以用在前面的動作中，這樣就可以達到簡化編程的目的。這里需要注意的是，
當編譯時不帶-ll選項時，是必須加入main函數和yywrap(yywrap將下後面說明)。如：
...
%%
showtitle()
{
printf("----- Lex Example -----\n");
}
int main()
{
linenum=0;
yylex(); /* 進行Lex分析 */
printf("\nLine Count: %d\n",linenum);
return 0;
}
int yywrap()
{
return 1;
}

三.Lex(Lexical Analyzar) 一些的內部變數和函數
內部預定義變數：
yytext char * 當前匹配的字元串
yyleng int 當前匹配的字元串長度
yyin FILE * lex當前的解析文件，默認為標准輸出
yyout FILE * lex解析後的輸出文件，默認為標准輸入
yylineno int 當前的行數信息
內部預定義宏：
ECHO #define ECHO fwrite(yytext, yyleng, 1, yyout) 也是未匹配字元的
默認動作

內部預定義的函數：
int yylex(void) 調用Lex進行詞法分析
int yywrap(void) 在文件(或輸入)的末尾調用。如果函數的返回值是1，就停止解
析。 因此它可以用來解析多個文件。代碼可以寫在第三段，這
樣可以解析多個文件。 方法是使用 yyin 文件指針指向不同的
文件，直到所有的文件都被解析。最後，yywrap() 可以返回1
來表示解析的結束。

lex和flex都是解析Lex文件的工具，用法相近，flex意為fast lexical analyzer generator。
可以看成lex的升級版本。

相關更多內容就需要參考flex的man手冊了，十分詳盡。

四.關於Lex的一些綜述
Lex其實就是詞法分析器，通過配置文件*.l，依據正則表達式逐字元去順序解析文件，
並動態更新內存的數據解析狀態。不過Lex只有狀態和狀態轉換能力。因為它沒有堆棧，
它不適合用於剖析外殼結構。而yacc增加了一個堆棧，並且能夠輕易處理像括弧這樣的
結構。Lex善長於模式匹配，如果有更多的運算要求就需要yacc了。

⑧ 對給定的正規式b(a|b)*aa,構造其NFA M，並將其確定化。

表示方法：五元組（S，Z，f，S0，z）

S：狀態集

Z：字母表

f：映射關系

s0：初態

z：終態

（2）確定有限自動機DFA：f為單值映射

（3）非確定有限自動機NFA：f為多值映射

（4）狀態轉換圖和狀態轉換矩陣

(8)編譯原理狀態轉化矩陣作用擴展閱讀

假定DFAMd＝（｛s0，s1，s2｝，｛a，b｝，f，s0，｛s2｝）：

f：

f（s0，a）＝s1f（s0，b）＝s2

f（s1，a）＝s1f（s1，b）＝s2

f（s2，a）＝s2f（s2，b）＝s1

試著給出Md的狀態轉換圖和狀態轉換矩陣。

狀態轉換矩陣如下

ab

s0s1s2

s1s1s2

s2s2s1