編譯原理子樹是什麼

❶ 編譯原理-句型、句子、短語、直接短語、句柄、素短語、最左素短語

在進行語法分析的時候，有時候會對這些詞語的概念不清晰，這里我們就詳細歸納總結一下。

可以看出這個裡面，最需要理解的概念就是短語，其他大部分概念都是在短語基礎上延伸的，從概念上可以看出：

假設有一個文法

針對文法的一個特定句型 (Sd(T)db) , 其推導過程如下:

這個句型 (Sd(T)db) 對應的 CFG 分析樹如下：

那個這個句型 (Sd(T)db) 有多少個短語呢？

還記得短語的定義么， S ⇒* αβδ ， αβδ 代表句型就是這里的 (Sd(T)db) 。

因此這個句型 (Sd(T)db) :

演算法非常簡單，就是通過分析樹的後序遍歷，先將子樹的葉節點從左到右排合並成字元串(即一個短語)，然後用它代表子樹的根節點的值，再和與子樹根節點同一層節點值合並，得到新的短語。就這樣從分析樹的最底層，一路合並到分析樹的根節點，就能得到所有的短語了。

通過遞歸的方法，獲取短語列表 phraseList , 直接短語列表 directPhraseList 和 素短語列表 plainPhraseList 。

運行結果:

❷ 離散數學在具體領域的應用

你看看這個行不？【摘要】離散數學是計算機科學基礎理論的核心,本文介紹了離散數學在人工智慧、數據結構、資料庫等方面的應用,顯示了離散數學在計算機科學中的重要性。
【關鍵詞】人工智慧 二叉樹的遍歷 資料庫


1 引言
離散數學是計算機專業的核心基礎課,它在計算機科學中有著重要的應用。它是計算機專業課《數據結構》、《操作系統》、《編譯原理》、《資料庫系統原理》和《數字邏輯》等課的必備基礎,因此離散數學是掌握計算機科學理論基礎的重要數學工具。本文正是從這一角度出發,介紹離散數學在計算機科學中的重要應用。

2 離散數學在計算機學科中的應用
2.1 數理邏輯在人工智慧中的應用
人工智慧是計算機學科中一個非常重要的方向,離散數學在人工智慧中的應用主要是數理邏輯部分在人工智慧中的應用。數理邏輯包括命題邏輯和謂詞邏輯,命題邏輯就是研究以命題為單位進行前提與結論之間的推理,而謂詞邏輯就是研究句子內在的聯系。大家都知道,人工智慧共有兩個流派,連接主義流派和符號主義流派。其中在符號主義流派里,他們認為現實世界的各種事物可以用符號的形式表示出來,其中最主要的就是人類的自然語言可以用符號進行表示。語言的符號化就是數理邏輯研究的基本內容,計算機智能化的前提就是將人類的語言符號化成機器可以識別的符號,這樣計算機才能進行推理,才能具有智能。由此可見數理邏輯中重要的思想、方法及內容貫穿到人工智慧的整個學科。
2.2 圖論在數據結構中的應用
離散數學在數據結構中的應用主要是圖論部分在數據結構中的應用,樹在圖論中占著重要的地位。樹是一種非線性數據結構,在現實生活中可以用樹來表示某一家族的家譜或某公司的組織結構,也可以用它來表示計算機中文件的組織結構,樹中二叉樹在計算機科學中有著重要的應用。二叉樹共有三種遍歷方法:前序遍歷法、中序遍歷法和後序遍歷法。
2.2.1 前序遍歷法:如果二叉樹為空,則返回。否則(1)訪問根節點(2)前序遍歷左子樹(3)前序遍歷右子樹,得到前序序列。
2.2.2 中序遍歷法:如果二叉樹為空,則返回。否則(1)中序遍歷左子樹(2)訪問根節點(3)中序遍歷右子樹,得到中序序列。
2.2.3 後序遍歷法:如果二叉樹為空,則返回。否則(1)後序遍歷左子樹(2)後序遍歷右子樹(3)訪問根節點,得到後序序列。
通過訪問不同的遍歷序列,可以得到不同的節點序列,通常在計算機中利用不同的遍歷方法讀出代數表達式,以便在計算機中對代數表達式進行操作。
2.3 集合論在資料庫系統理論中的應用
集合論是離散數學中極其重要的一部分,它在資料庫中有著廣泛的應用。我們可以利用關系理論使資料庫從網路型、層次型轉變成關系型,這樣使資料庫中的數據容易表示,並且易於存儲和處理,使邏輯結構簡單、數據獨立性強、數據共享、數據冗餘可控和操作簡單。當資料庫中記錄較多時,集合中的笛卡兒積方便了記錄的查詢、插入、刪除和修改。
2.4 代數畝搜系統在通信方面的應用
代數系統在計算機中的應用廣泛,例如有限機,開關線路的計數等方面。但最常用的是在糾錯碼方面的應用。在計算機和數據通信中,經常需要將二進制數字信號進行傳遞,這種傳遞常常距離很遠,所以難免會出現錯誤。通常採用糾錯碼來避免這種錯誤的發生,而設計的這種糾錯碼的數學基礎就是代數系統。糾錯碼中的一致校驗矩陣就是根據代數系統中的群概念來進行設計的,另外在群碼的校正中,也用到了代數系統中的陪集。
2.5 離散數學在生物信息學中的應用
生物信息學是現代計算搏橡機科學中一個嶄新的分支,它是計算機科學與生物學相結合的產物。目前,在美國有一個國家實驗室Sandia國家實驗室,主要進行組合編碼理論和密碼學的研究,該機構在美國和國際學術界有很高的地位。另外,由於DNA是離散數學中的序列結構,美國科學院院士,近代離散數學的奠基人Rota教授預言,生物學中的組合問題將成為離散數學的一個前沿領域。而且,IBM公司也將成立一個生物信息學研究中心。在1994年美迅銀歷國計算機科學家阿德勒曼公布了DNA計算機的理論,並成功地運用DNA計算機解決了一個有向哈密爾頓路徑問題,這一成果迅速在國際產生了巨大的反響,同時也引起了國內學者的關注。DNA計算機的基本思想是:以DNA鹼基序列作為信息編碼的載體,利用現代分子生物學技術,在試管內控制酶作用下的DNA序列反應,作為實現運算的過程;這樣,以反應前DNA序列作為輸入的數據,反應後的DNA序列作為運算的結果,DNA計算機幾乎能夠解決所有的NP完全問題。

3 結論
現在我國每一所大學的計算機專業都開設離散數學課程,正因為離散數學在計算機科學中的重要應用,可以說沒有離散數學就沒有計算機理論,也就沒有計算機科學。所以,應努力學習離散數學,推動離散數學的研究,使它在計算機中有著更為廣泛的應用。

參考文獻
[1] 耿素雲,屈婉玲,離散數學[M].北京:高等教育出版社<1998.
[2] 左孝凌,李永監,劉永才編著.離散數學[M].上海:上海科學技術文獻出版社,2004.
[3] 朱一清.離散數學[M].北京:電子工業出版社,2004

❸ 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

直接短語一定是某產生式的右部，但反之不一定。

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

❹ 編譯原理中的句柄是什麼意思舉個簡單的例子

語法樹的最左子樹

❺ 編譯原理習題，下圖為什麼a為句柄, 而不是最左面的b為句柄怎樣理解句柄定義中的最左簡單子樹中的簡

baSb的最右推導為：S->AB->ASb->bBSb->baSb

根據句柄定義：

所以a為baSb的句柄。

只有單層分支的子樹稱為簡單子樹。最左簡單子樹末端結點組成的符號串為句柄。