1. 編譯原理 正則語言 二義文法 急~
這個沒有一個好老師，自己咬文嚼字看懂是很累的
二義性文法
【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。
二義性文法會引起歧義，應盡量避免之！
G(E)：E -> E+E | E*E | (E) | i
這兩種展開
E E
E + E E * E
i E * E E + E i
i i i i
都可以表示i+i*i
所以;文法具有二義性。
2. 學習「編譯原理」有什麼作用
編譯原理內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。主要是講怎麼做程序的編譯器。需要數學基礎和很強的邏輯思維。編譯原理里的字元閉包是指有限循環。關於閉包這些名詞解釋，你們的課程應該有離散數學吧？會有對這些概念的解釋。編譯原理這書啊。得花老大精力去看了。每一行都會是至關重要的。如果你漏看了哪一節，或許接下來看到的新字母就不知道是什麼意思了。所以要反復看，反復用邏輯思維推敲。做習題，習題類型也就幾種，做熟了就很簡單
3. 編譯原理、離散數學中閉包是什麼意思
數學中是閉的集合,也就是集合和它的邊界的並。集合e的全體聚點並上e稱為e的閉包。關系的閉包運算時關繫上的一元運算，它把給出的關系R擴充成一新關系R』，使R』具有一定的性質，且所進行的擴充又是最「節約」的。
比如自反閉包，相當於把關系R對角線上的元素全改成1，其他元素不變，這樣得到的R』是自反的，且是改動次數最少的，即是最「節約」的。
4. NFA轉DFA的子集構造(subset construction)演算法
之前 學習編譯原理的時候老師有講過 子集構造法 ，當時我以為自己聽懂了，信心滿滿。可是這兩天我做了一些題目，發現自己實際上還是太嫩了，學習浮於表面。之後又重新看了龍書和虎書，對子集構造法有了更深層次的了解。特此發出一篇文章分享我的經驗。
概念是我們學習編譯原理的重中之重，雖然他很晦澀難懂，但我有必要將其放在最開始。
虎書的概念更偏向於理論化，我當時看的時候一頭霧水，但是不要擔心， 之後會一點一點解釋的 。
首先 ，我們形式化定義 閉包如下：
現在 ，假設我們位於由 NFA 狀態 組成的集合 中。從 中的狀態出發，輸入符號 ，將到達 NFA 新的狀態集；我們稱這個狀態集為 ：
利用 能更形式化地寫出 NFA 模擬演算法。如果初態是 ，輸入字元串是 ，則演算法為：
有了 和 演算法，就能構造出 DFA ， DFA 的狀態 就是 。抽象而言，如果 則存在一條從 到 的標記為 的邊。令 是字母表：
個人認為龍書的概念更加通俗易懂，但是由於沒有數學公式的歸納，導致理論基礎不扎實，有點慌。所以推薦兩本書一起看。
首先，是概念：
接著，是演算法：
很簡單 ，如果開始於 的機器接收字元串 ，始於 的和始於與 接收的串相同 ， 並到達相同狀態 ，且兩個狀態集 同為終態或者非終態 ，那麼 是等價的。我們可以把指向 的連線全部指向 ，並刪除 ，反之亦然。
NFA 轉 DFA 知識總結就到這里，有什麼問題請留言，有錯誤請批評指正，非常感謝您的閱讀。
5. 編譯原理學習ing（1）詞法分析——符號和文法
學習編譯原理，首先要理解詞法分析的基礎概念。它涉及字母表中的符號，如字元、字元串和字元運算（如空串、連接、冪運算、乘積以及閉包）。文法是核心，它由兩個非交集的集合——終結符集和非終結符集——以及消配則映射規則組成，規則通過開始符號（來自非終結符集）生成字元串。
文法通常用G(Vn, Vt, P, S)表示，其中Vn和Vt分別代表非終結符集和終結符集，P是產生式集，S是開始符號。例如，一個簡單的文法可以表示為A-≥a，這意味著A可以推導為字元a。在文法G的作用下，通過規則推導形成句型，最終得到終結符串——句子，即語言L(G)。文法的等價性意味著不同的文法可能產生相同的語言。
對於文法的分類，上下文無關文法（2型文法）和語法樹是關鍵概念。語法樹通過標記和規則描述推導過程，但可能存在二義性，即同一種文法可以產生不同語法樹。短語、直接短語和句柄的概念在句型分析中至關重要，用於確認句子是否符合文法。
在詞法分析中，通過正則表達式或正規式（正規賣或集）分析輸入，將字元轉化為tokens，這是程序識別和處理語言的第一步。確定有限自動機（DFA）和非確定有限自動機（NFA）是自動化識別過程的基礎，它們以不同的規則描述輸入字元的接受方式。NFA與DFA雖然有區別，但它們在識別能力上是等價的，拿棚任何NFA都可以轉換為等價的DFA。
6. 編譯原理有有符號un-1.u=un嗎
編譯程序把源程序翻譯為目標程序。根據源程序的語言種類，翻譯程序可以分為匯編程序與編譯程序。與之相對，解釋程序是對源程序進行解釋執行的程序。相應的可以將高級語言分為
編譯型 C/C++, Swift, etc.
解釋型 Python, javascript, etc.
混合型 Java, etc.
本文重點放在編譯程序的設計上。典型的編譯程序具有 7 77 個邏輯部分
對源程序掃描一次被稱為一遍 (pass)。典型的一遍掃描編譯程序有如下形式
通常將中間代碼生成前的分析部分稱為編譯器的前端，其後的綜合部分則被稱為後端。這樣就把一個編譯程序分為了與源語言相關和與目標機有關的兩個獨立的部分，降低了程序的耦合。假設 llvm 編譯器 支持 M MM 種源語言到 N NN 種目標語言的編譯
傳統的編譯器如 gcc 可能需要開發 M × N M \times NM×N 個不同的子模塊。而 llvm 使用統一的中間語言 llvm Intermediate Representation 只需要 M MM 個前端與 N NN 個後端，大大降低了開發成本。
文法
設非空有窮集合 Σ \SigmaΣ 為一字母表，則其上的符號串為 ∀ s ∈ Σ ∗ \forall s \in \Sigma^*∀s∈Σ
∗
，其中 ∗ *∗ 表示集合的閉包。特別的記 Σ 0 = ε \Sigma^0 = {\varepsilon}Σ
0
=ε 為空串組成的集合。規則通常寫作
U : : = x or U → x , ∣ U ∣ = 1 , ∣ x ∣ ≥ 0 U ::= x\text{ or }U\rightarrow x,\quad |U| = 1, |x| \ge 0U::=x or U→x,∣U∣=1,∣x∣≥0
其中左部 U UU 是符號，右部 x xx 是有窮符號串。規則的集合 P PP 即可確定一個文法 G GG
<程序> ::= <常量說明><變數說明><函數說明>
<常量說明> ::= {const<常量定義>;}
<常量定義> ::= int<標識符>=<整數>{,<標識符>=<整數>}|char<標識符>=<字元>{,<標識符>=<字元>}
<變數說明> ::= {<類型標識符><變數定義>;}
<變數定義> ::= <標識符>[<下標>]{,<標識符>[<下標>]}
<下標> ::= '['<無符號整數>']' // <無符號整數>表示數組元素的個數，其值需大於0
<函數說明> ::= {(<類型標識符>|void)<函數定義>}void<主函數>
<函數定義> ::= <標識符>'('<參數表>')'<復合語句>
<參數表> ::= [<類型標識符><標識符>{,<類型標識符><標識符>}]
<主函數> ::= main'('')'<復合語句>
<復合語句> ::= '{'<常量說明><變數說明>{<語句>}'}'
<語句> ::= <條件語句>|'{'{<語句>}'}'|<函數調用語句>;|<賦值語句>;|<讀語句>;|<寫語句>;|<返回語句>;|;
<條件語句> ::= <if語句>|<while語句>|<do語句>|<for語句>
<if語句> ::= if'('<條件>')'<語句>[else<語句>]
<while語句> ::= while'('<條件>')'<語句>
<do語句> ::= do<語句>while'('<條件>')'
<for語句> ::= for'('<標識符>=<表達式>;<條件>;<標識符>=<標識符><加法運算符><無符號整數>')'<語句>
<條件> ::= <表達式>[<關系運算符><表達式>] // 表達式為0條件為假，否則為真
<函數調用語句> ::= <標識符>'('[<表達式>{,<表達式>}]')'
<賦值語句> ::= <標識符>['['<表達式>']']=<表達式>
<讀語句> ::= scanf'('<標識符>{,<標識符>}')'
<寫語句> ::= printf'('<字元串>[,<表達式>]')'|printf'('<表達式>')'
<返回語句> ::= return['('<表達式>')']
<表達式> ::= [<加法運算符>]<項>{<加法運算符><項>} // [+|-]只作用於第一個<項>
<項> ::= <因子>{<乘法運算符><因子>}
<因子> ::= <標識符>['['<表達式>']']|'('<表達式>')'|<整數>|<字元>|<函數調用語句>
<整數> ::= [<加法運算符>]<無符號整數>
<標識符> ::= <字母>{<字母>|<數字>}
<無符號整數> ::= <非零數字>{<數字>}|0
<數字> ::= 0|<非零數字>
<非零數字> ::= 1|...|9
<字元> ::= '<加法運算符>'|'<乘法運算符>'|'<字母>'|'<數字>'
<字元串> ::= "{十進制編碼為32,33,35-126的ASCII字元}"
<類型標識符> ::= int|char
<加法運算符> ::= +|-
<乘法運算符> ::= *|/
<關系運算符> ::= <|<=|>|>=|!=|==
<字母> ::= _|a|...|z|A|...|Z
復制
上述文法使用擴充的 BNF 表示法進行描述
符號 定義 說明
∣ \vert∣ 或 作用域由括弧限定
{ t } n m \{t\}^m_n{t}
n
m
將 t tt 重復連接 n ∼ m n \sim mn∼m 次 預設時 m = ∞ , n = 0 m = \infin,\ n = 0m=∞, n=0
[ t ] [t][t] 符號串 t tt 可有可無 等價於 { t } 1 \{t\}^1{t}
1
( t ) (t)(t) 局部作用域 主要用於限定 ∣ \vert∣ 范圍
相關概念有
概念 符號 定義 示例
識別符號 Z ZZ 文法中第一條規則的左部符號 <程序>
字匯表 V VV 文法中出現的全部符號 { <程序>, <常量說明>, …, 0, 1, … }
非終結符號集 V n V_nV
n
全部規則的左部組成的集合 { <程序>, <常量說明>, <變數說明>, … }
終結符號集 V t V_tV
t
V − V n V - V_nV−V
n
{ 0, 1, …, _, a, b, … }
設 U : : = u ∈ P U ::= u \in PU::=u∈P 則對於 ∀ x , y ∈ V ∗ \forall x, y \in V^*∀x,y∈V
∗
有直接推導 x U y ⇒ x u y xUy \Rightarrow xuyxUy⇒xuy 。如果 y ∈ V t ∗ y \in V_t^*y∈V
t
∗
則 x U y ⤃ x u y xUy\ ⤃\ xuyxUy ⤃ xuy 稱為規范推導。直接推導序列 u 0 ⇒ u 1 ⇒ ⋯ ⇒ u n u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_nu
0
⇒u
1
⇒⋯⇒u
n
可簡記為
{ u 0 ⇒ + u n n > 0 u 0 ⇒ ∗ u n n ≥ 0 \begin{cases} u_0 \mathop\Rightarrow\limits^+ u_n & n > 0\\ u_0 \mathop\Rightarrow\limits^* u_n & n \ge 0\\ \end{cases}{
u
0
⇒
+
u
n
u
0
⇒
∗
u
n
n
>
0
n
≥
0
進一步定義
句型 V ∗ ∋ x ⇐ ∗ Z V^* \ni x \mathop\Leftarrow\limits^* ZV
∗
∋x
⇐
∗
Z
句子 V t ∗ ∋ x ⇐ + Z V_t^* \ni x \mathop\Leftarrow\limits^+ ZV
t
∗
∋x
⇐
+
Z
語言 L ( G ) = { x ∣ x is sentence } L(G) = \{ x| x\text{ is sentence} \}L(G)={x∣x is sentence}
如果文法 G GG 和 G ′ G'G
′
有 L ( G ) = L ( G ′ ) L(G) = L(G')L(G)=L(G
′
) ，則稱這兩個文法等價。設 w = x u y w=xuyw=xuy 為一句型，稱 u uu 為一個相對於 U ∈ V n U \in V_nU∈V
n
的
w ww 的短語 如果 Z ⇒ ∗ x U y ∧ U ⇒ + u Z \mathop\Rightarrow\limits^* xUy \land U \mathop\Rightarrow\limits^+ uZ
⇒
∗
xUy∧U
⇒
+
u
w ww 的簡單短語 如果 u uu 是短語且 U ⇒ u U \mathop\Rightarrow\limits uU⇒u
句型的最左簡單短語稱為句柄。
二義性
文法 G GG 是二義性的，如果 ∃ x ∈ L ( G ) \exist x \in L(G)∃x∈L(G) 使下列條件之一成立
x xx 可以對應兩顆不同的語法樹
x xx 有兩個不同的規范推導
7. 編譯原理的正閉包與星閉包是什麼意思
仔細分析你的文法
f->f*|a|b也就是說，寫成正則表達式的話
f就是[ab]*
同樣的t也是[ab]*
你的整個文法就是[ab]+
[ab\+]*第一個+是+closure，第二個+是符號+，所以用了\符號
個人感覺這個文法是有問題的，因為根本不需要用上下文無關文法表達，只需要正則表達式就可以了。
8. 編譯原理的正閉包與星閉包是什麼意思
正閉包除去空字元串，星閉包包含空字元串。