【Compiler】 Ch2. Languages and Their Representations

Alphabets and Languages

• 如何定義一個"語言"？這邊先定義語言的"字母集"。
• 字母集(alphabet)是任何有限符號的集合，例如：
  • 英文alphabet {A, B, C…, Z}
  • 希臘alphabet {α, β, γ…, ω}
  • 二元alphabet {0, 1}
• 而sentence就是從alphabet的符號中組合出的有限string(這邊的sentence不是句子是單字!)
  • 空的sentence習慣用 є 表示。
• 如果
  $V$是一個alphabet，則
  • $V^{\ast }$為在
    $V$裡面的所有sentence。
  • $V^{+}=V^{\ast }-\{ϵ\}$(不包含空字串的意思)

---

• 有了上述的定義，我們到底如何定義一個Language？
  • 我們必須用有限的東西去定義一個無限的語言
• 兩種方法：
  • 給一個演算法，丟入sentence時可以回傳它在該語言內或不是。
  • 給予一個語法，能產生所有該語言內的sentence。

Grammars

• 先給個語法範例：
• 看不懂沒關係，下面帶你來了解Grammar

Formal Notation of a Grammar

• Grammar有4個元素：
  • Nonterminals
    • 不在alphabet中的符號，衍生符號，如範例中的<sentence> <adjective>等
  • Terminals
    • 與Nonterminals，最原始的符號，如範例中的The little boy等
  • Productions
    • 符號(Terminals和Nonterminals)的轉換關係，如範例中的<sentence> -> <noun phrase><verb phrase>等
  • Start Symbol
    • 開始符號，如果輸入的terminal最後可以透過Productions轉換為Start Symbol，表示該輸入屬於該語言。例如範例中的<sentence>(在Productions或parse tree的最上面)

---

• 使用數學的方式來表達：
  • $G=(V_N,V_T,P,S)$
  • $V_N$: nonterminals
  • $V_T$: terminals (
    $V_N\bigcap V_T=\varphi ,V_N\bigcup V_T=V$)
  • $P$: productions,
    $\alpha \to \beta \in P$
  • $S$: start symbol
• 習慣上nonterminals會用大寫字母表示，而
  $V_T$是小寫。

Derivation

• Derivation(推導)指將productions左側符號變為右側符號的動作。
  • 例如：
    $\alpha \to \beta \in P$ 且
    $\gamma ,\delta \in V$，則
    $\gamma \alpha \delta \Rightarrow \gamma \beta \delta$。
  • 其中我們可以說
    $\gamma \alpha \delta$ derives
    $\gamma \beta \delta$。
• 如果有一段連續的Derivation，可以用*表示：
  • 如果
    ${\alpha }_1\Rightarrow {\alpha }_2\Rightarrow ...\Rightarrow {\alpha }_m$ 則可寫為
    ${\alpha }_1\stackrel{\ast }{\Rightarrow }{\alpha }_m$
• $L(G)=\{w|w\in V_T^{\ast }\wedge S\stackrel{\ast }{\Rightarrow }w\}$
  • 表示使用語法G的語言L
• 如果兩個語法
  $G_1$
  $G_2$是相等的，則
  $L(G_1)=L(G_2)$

---

範例問題

$G=(V_N,V_T,P,S)$

$V_N=\{S\},V_T=\{0,1\},P=\{S\to 0S1,S\to 01\}$
根據以上語法，請描述L(G)為何？

答案
L(G) =

$\{0^n{1}^n\}$

Types of Grammars

• 在這邊將介紹四種不同等級的Grammar，先大致上有個印象就可以了。
  • 越下面的限制越高。
• 給予語法
  $G=(V_N,V_T,P,S)$
  1. Type 0 grammar
     • 沒有任何限制。
  2. Type 1 grammar (context-sensitive grammar)
     • 必須符合
       $\alpha \to \beta \in P,|\alpha |\le |\beta |$
     • 也就是說，Derivation不會讓句子變短。
  3. Type 2 grammar (context-free grammar)
     • 必須符合
       $\alpha \to \beta \in P,|\alpha |=1,\beta \ne ϵ$
     • 也就是說，production的左側只能有一個符號。
  4. Type 3 grammar (regular grammar)
     • 所有production都只能是
       1. $A\to aB$
       2. $A\to a$

tags: compiler note