首先我們回顧一下上篇的內容,上篇講述了四種類型的文法,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句型的推導過程:
(1)S=>aAS=>aAa=>aSbAa=>aSbbaa=>aabbaa(最右推導)(最右推(2)S=>aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa(最左推導)(最左推導,就是從最左側的非終結符開始)
例2: G[E]:??????? E→E+T|T
???????????????????? T→T*F|F
???????????????????? F→(E)|a
?????????????????? ? 判斷a+a*a???????? 是否是合法的句子,采用最左推導和最右推導
E=>E+T=>T+T=>F+T=>a+T=>a+T*F
??????????? ??? =>a+F*F=>a+a*F=>a+a*a(最左推導)
E=>E+T=>E+T*F=>E+T*a=>E+F*a
??????????????? =>E+a*a=>T+a*a=>F+a*a=>a+a*a(最右推導)
書上規定,**最右推導又稱為規范推導,規范推導推導出的句型又稱為規范句型**。
**構造上述句型的語法樹:**
畫出a+a*a句型的語法樹????????????
???????????????? E→E+T|T?
?????????????????T→T*F|F
?????????????????F→(E)|a

注:上面的例子來自網絡。
而一個語法樹可以表示可能的不同推導過程,包括最右推導和最左推導。但是一個句型是否對應唯一的一顆語法樹呢?一個句型是否只有唯一的一個最左推導(最右推導)?答案是否定的,下面我們講述二義文法。
看看下面的文法推導樹:

**二義文法的定義**:
若一個文法存在某個句子對應兩棵不同的語法樹,則稱這個文法是二義的,或一個文法有兩個不同的最左推導,則稱這個文法是二義的。
當然我們不希望程序的某些文法是二義的,希望對程序的每個句子的分析是唯一的。
本篇到此結束,下篇講述句型的簡單分析。
愿開心閱讀,一起掌握知識(*^__^*) 。
??
??????????????
???????