本站小編為你精心準備了遞歸對形式文法教學的作用參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《福建電腦雜志》2014年第十二期

1文法的形式化描述

本節詳細給出文法的形式化定義，首先給出字母表∑的定義：定義1.1：字母表∑是一個非空符號的集合，集合中的符號是原子的，不可分。有限長度的符號序列稱為字符串。常見的字母表如二十六個字母及數字構成程序語言的基本字母表，{0，1}等。字符串w的長度為w中符號的個數，記為|w|，長度為0的字符串稱為空串，常用ε表示。令w1=a1a2…an，w2=b1b2…bm，則字符串w1、w2的連接運算記為w=w1w2=a1a2…anb1b2…bm，εw=wε，另外n個字符串w構成的字符串可簡記為wn。下面給出語言的定義。根據Chomsky文法分類模型，文法可分為0-型文法、1-型文法、2型文法和3型文法，各種文法的詳細討論，請參看相關文獻[4]。從0-型文法開始，文法復雜度遞增，表達能力遞增，但相應文法語言的分析越困難。綜合表達能力和分析困難程度，編譯原理重點在2-型文法和3-型文法的分析，根據兩種文法的特點，這兩種文法分別稱為上下文無關文法和線性文法。上下文無關文法產生式的左部為單個非終結符號。下文的方法圍繞上下文無關文法展開，由于3-型文法是2-型文法的子集，因此下文所討論的方法同樣適應于3-型文法。

2基于遞歸方法的文法分析

本節將在上節的基礎上，闡述遞歸分析方法在文法中的作用，包括兩方面的作用：如何利用遞歸方法計算形式化文法的語言；如何利用遞歸方法定義語言，并從遞歸定義的語言產生文法。在編譯原理的教學實踐中，對于文法所產生語言的描述主要基于集合論的基礎，特殊的情況，例如3-型文法的語言可以用正則式進行描述。但這些方法在實際使用中有著明顯的不足：基于集合的描述方法不是一種構造性和過程性的描述，復雜文法的語言集合描述需要復雜的數學對象的構造說明，不便于自動化，算法化處理；而正規式的表達能力則限制了它的使用。例如，下面的文法。該文法形式簡單，讀者很容易理解，馬上能得出該文法所產生的語言。該語言非形式的描述為：((L))L((L))或(((L)))L(((L)))，顯然，這種描述及其模糊不清，不能準確描述其所對應的語言。遞歸性是體現文法復雜性最重要的構造性特征，基于遞歸的描述方法是數學中用于定義復雜數學對象的常用方法。這種方法具有構造性及過程性的特點，且具有強大的描述能力，在離散數學課程中有所涉及。以上文法所表示的語言很容易用下面的方法描述，該方法表現為一規則序列，令L為該語言。其中，規則（1）為基礎規則，（2）和（3）為擴展規則，規則（4）確保語言L的最小性。這種基于規則的語言定義基于文法的遞歸結構。反之，引進非終結符號S，很容易構造出相應規則所定義語言的文法。但是，所產生的文法只具有遞歸性結構的語法特點，要體現其余的語法要素，則規則中需要相應的規則對應。對于復雜語言的描述，這種基于規則的方法自然、容易理解，又具有嚴謹性。下面講述如何從已知的文法采用遞歸的方法計算文法的語言，同樣以下面的表達式文法為例進行說明。對于文法任意一個產生式：A→αBβ，其中A和B是非終結符號。則根據產生式可得L(A)勐L(α)L(B)L(β)，其中L(A)和L(B)分別表示A和B作為開始符號相關文法的語言，L(α)和L(β)分別表示字符串α和β直接或間接推理出得句子的集合。當A→γ1｜γ2｜…｜γn包含某文法中所有左部為A的產生式，則L(A)=L(γ1)∪L(γ2)∪…∪L(γn)。下面基于以上的討論計算文法G2的語言。上式已經消去了所有的中間文法符號，是個復雜的可遞歸展開的式子，可采用類似的不動點的計算方法，但展開過程較為繁瑣，此處不進行詳細的展開。根據上式的結構，采用規則定義的方法給出語言的描述，這樣可以靈活地結合上面語言的遞歸計算及基于規則的語言遞歸定義方法。

3結論

針對編譯原理課程中形式文法教學過程中存在的問題，提出了基于遞歸方法的語言定義方法和語言計算方法。這種方法豐富了教學內容和教學方法，有利于培養學生抽象而嚴謹的思維能力，提高使用基礎數學知識解決實際問題的能力。

作者：陳冬火單位：蘇州大學計算機科學與技術學院