【文章內容簡介】 然不符合規(guī)則的符號串不能稱為語言。 構成語言的三個要點： 1．字母表 也即字符集，它規(guī)定了語言中所允許的字符或基本符號 2．目標 這是一個語言最終要達到或處理的目標 3．規(guī)則 規(guī)則指如何從字母表中的字符或基本符號構成目標 文法提供了三個要點。 1．在語言的設計和編譯器的編寫方面，文法都提供了極大的優(yōu)點： 2．文法給出了精確的，也于理解的語言語法說明 設計得漂亮的文法，把結構加于程序設計語言，這些結構對把源程序翻譯成真正的目標代碼和錯誤診斷都是有用的。 3．語言也是逐步完善的，需要補充新的結構和完成附加任務。如果存在以語法為基礎的語言的實現(xiàn)，這些新結構的加入就更方便了。 語言的特征： 1．一種語言需借助于另一種語言來描述 2．語法是以有窮的方式來描述潛在無窮句子集合的手段 3．語法上的正確不能保證語義上的正確 推導與遞歸 定義 如果每次推導最左非終結符稱最左推導，記為 α=l=β 定義 如果每次推導最右非終結符稱最右推導，最右推導又稱為規(guī)范推導，記為 α=r=β，由最右推導得出的句型稱為右句型又稱規(guī)范句型 遞歸規(guī)則與遞歸文法 由于語言通常是無窮的而文法是有限的，用有限的文法定義無窮的語就必須使用遞歸定義。 遞歸規(guī)則 若文法中存在規(guī)則 A→ αAβ 這種左部和右部具有相同的非終結符號的規(guī)則稱為直接遞歸規(guī)則或稱遞歸規(guī)則。這種遞歸稱為規(guī)則遞歸。 若 A→ Aα，即為左遞歸規(guī)則； 若 A→ αA，即為右遞歸規(guī)則； 若 A→ αAβ(α、 β≠ε），即為自嵌套規(guī)則。 遞歸文法 有時文法中不含有直接的遞歸規(guī)則，但通過若干推導仍能得到遞歸，這種遞歸稱為間接遞歸或文法遞歸，含有遞歸的文法被稱為遞歸文法。 如： A→ Bα B→ Aβ 則 A=Bα= Aβα 文法的分類 形式語言自 1956年喬姆斯基（ Chomsky）進行描述以來，得到了很大的發(fā)展。喬姆斯基從理論上討論了語言和文法，按照文法規(guī)則的不同定義形式進行分類，并且為每一語言構造象自動機一樣的識別器。形式語言的理論形成和發(fā)展對計算機科學有著深刻的影響，特別是對程序設計語言的設計技術、編譯實現(xiàn)都有重大影響。 喬姆斯基把文法分成四種類型，即 0型、 1型、 2型和 3型文法。 設 G=（ Vn,Vt， P， S）如果它的每個產(chǎn)生式 α→ β是這樣一種結構： α∈ （ Vn∪ Vt ） *且至少含有一個非終結符，而 β∈（ Vn∪ Vt V） *，則 G是個 0型文法。 0型文法也稱短語文法。一個非常重要的理論結果是， 0型文法的能力相當于圖靈機 （ Turing）?；蛘哒f；任何 0型語言都是遞歸可枚舉的；反之，遞舊可枚舉集必定是一個 0型語言。 設 G=（ Vn,Vt， P， S）為一文法，若 P中的每一個產(chǎn)生式α→ β除 S→ ε外均滿足 |β|≥|α|，則文法 G是 1型或上下文有關文法。 可以證明滿足 |β|≥|α|的文法都存在規(guī)則均形如 αAβ→ αγβ的等價的文法， α、 β不都空，意為非終結符 A在 α、 β這樣的上下文條件下，允許替換為 γ 設 G= （ Vn,Vt， P， S） ，若 P中的每一個產(chǎn)生式 α→ β滿足：α是一非終結符，即： α∈ Vn， β∈ （ Vn∪ Vt ） * 則此文法稱為 2型的或上下文無關文法。 設 G= （ Vn,Vt， P， S） ，若 P中的每一個產(chǎn)生式的形式都是A→ aB或 A→ a，其中 A和 B都是非終結符． a是終結符，則 G是 3型文法或正規(guī)文法。三型文法又分左線性和右線性的。如每一個產(chǎn)生式的形式都是 A→ aB或 A→ a 稱為右線性的；如每一個產(chǎn)生式的形式都是 A→ Ba或 A→ a 稱為左線性的。 0型文法、 1型文法、 2型文法、 3型文法對應的自動機分別為圖靈機、線性界限自動機、下推自動機、有限自動機 顯然， 3型文法即 2型文法、 1型文法、 0型文法 2型文法即 1型文法、 0型文法 1型文法即 0型文法 例 1：寫出語言 L={aibjck|i,j,k≥1}的文法 S→ aS|aB B→ bB|bC C→ cC|c 例 2：寫出語言 L={aibick|i,k≥1}的文法 S→ AC A→ aAb|ab C→ cC|c 例 3：寫出語言 L={aibici|i≥1}的文法 S→ aSBC|aBC CB→ BC aB→ ab bB→ bb bC→ bc cC→ cc 注意： 雖然 3型文法是 0型文法的特例 ,但 0型文法描述的語言不一定比3型文法描述的語言豐富 句型分析 所謂句型分析是指給定一個字符串判定是否是文法上定義的句子。在日常生活中語言（無論中文、英文）都是上下文有關。實際上程序設計語言也是上下文有關的。如： GOTO 標號 → GOTO無符號整數(shù) 。標識符的前說明后使用問題，但程序設計語言中的大部分規(guī)則是可以寫成上下文無關文法，上下文無關文法有足夠的能力描述現(xiàn)今程序設計語言的語法結構，比如描述算術表達式，描述各種語句等等。 由于上下文無關文法不必考慮這所處的上下文，計算機實現(xiàn)比較方便，因而在程序設計語言的識別中較多地采用下文無關文法，今后如不特別指出的文法均為上下文無關的文法。 語法樹 如果把推導的過程用一種直觀的圖形表示就形成了一棵樹，即語法樹．也稱推導樹或分析樹。 例：設 G[S]： S→ A