首先我們回顧一下上篇的內容，上篇講述了四種類型的文法，0型1型2型3型，他們要求的規則越來越嚴格。 **開始教程**： 本篇著重講解上下文無關文法及其語法樹，因為對于計算機程序來講，上下文無關文法表達能力足夠強，來表達大多數程序語言的語法。 描述一種上下文無關的推導工具：**句型的推導和語法樹（推導樹）** 給定文法G（VN,VT,P ,S）,對于G的任何句型都能構造與之關聯的語法樹。**這棵樹滿足下面四個條件**： ①?每個結點都有一個標記，此標記是V的?一個符號。（說的是節點一定是終結符或非終結符） ②?根的標記是S。（說的是樹根的標記是開始符號S） ③?若一結點標記A,至少有一個從它出發的分枝，則A肯定在VN中（說的是如果一個節點有分支的話，這個節點一定是非終結符） ④?如果標記為A，有n個從它出發的分枝，并且這些分枝的結點的標記（從左到右）為B1,?B2，…，Bn，那么A→B1B2，…，Bn一定是P中的一個產生式。（說的是從A出發的葉子節點從左到右排列，一定是P中規則的一個產生式） 例1: 文法G[S]: S→aAS A→SbA A→SS S→a A→ba 寫出aabbaa句型的推導過程： （１）Ｓ＝＞aAS=>aAa=>aSbAa=>aSbbaa=>aabbaa(最右推導）（最右推（２）Ｓ＝＞aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa(最左推導）（最左推導，就是從最左側的非終結符開始） 例2： G[E]：??????? E→E+T|T ???????????????????? T→T*F|F ???????????????????? F→(E)|a ?????????????????? ? 判斷a+a*a???????? 是否是合法的句子,采用最左推導和最右推導 　　　　Ｅ＝＞Ｅ＋Ｔ＝＞Ｔ＋Ｔ＝＞Ｆ＋Ｔ＝＞a＋Ｔ＝＞a+Ｔ*Ｆ ??????????? ??? ＝＞a＋Ｆ＊Ｆ＝＞a＋a＊Ｆ=>a＋a*a(最左推導） 　　　　Ｅ＝＞Ｅ+Ｔ＝＞Ｅ＋Ｔ＊Ｆ＝＞Ｅ＋Ｔ＊a＝＞Ｅ＋Ｆ＊a ??????????????? =>Ｅ＋a*a＝＞Ｔ＋a*a＝＞Ｆ＋a*a＝＞a+a*a(最右推導） 書上規定，**最右推導又稱為規范推導，規范推導推導出的句型又稱為規范句型**。 **構造上述句型的語法樹：** 畫出a+a*a句型的語法樹???????????? ???????????????? E→E+T|T? ?????????????????T→T*F|F ?????????????????F→(E)|a  注:上面的例子來自網絡。 而一個語法樹可以表示可能的不同推導過程，包括最右推導和最左推導。但是一個句型是否對應唯一的一顆語法樹呢？一個句型是否只有唯一的一個最左推導（最右推導）？答案是否定的，下面我們講述二義文法。 看看下面的文法推導樹：  **二義文法的定義**： 若一個文法存在某個句子對應兩棵不同的語法樹，則稱這個文法是二義的，或一個文法有兩個不同的最左推導，則稱這個文法是二義的。 當然我們不希望程序的某些文法是二義的，希望對程序的每個句子的分析是唯一的。 本篇到此結束，下篇講述句型的簡單分析。 愿開心閱讀，一起掌握知識(*^__^*) 。 ?? ?????????????? ???????