--- title: 自動機 ch.5 --- # Automata Theory and Formal Languages NTNU 自動機理論與正規語言 ##### [Back to Note Overview](https://hackmd.io/@NTNUCSIE112/NTNUNote) ##### [Back to Automata Theory and Formal Languages](https://hackmd.io/@NTNUCSIE112/AT110-1) {%hackmd @sophie8909/pink_theme %} ###### tags: `AutomataTheoryandFormalLanguages` `110-1` `選修` `CSIE` `NTNU` <!-- https://hackmd.io/@NTNUCSIE112/AT110-1_X --> ## Ch.05 Context-Free Languages Parsing - Parsing 是描述句子結構的一種方式 - 每當我們需要理解句子的含意時很重要 - 在電腦科學中，他與直譯器、編譯器等翻譯程序相關 ### 5.1 Context-Free Grammars #### Context-free grammar - 正規文法中的產生式受到兩種方式的限制 - LHS 必須為單一的變數 - RHS 有一個特殊的格式 LHS/RHS 產生式的左/右邊 - 為創造更強大的文法，我們必須放寬一些限制 - 保留左側的限制，允許右側的所有東西，得到上下文無關文法 #### Definition 5.1 - 若文法 $G=(V, T, S, P)$ 中的 $P$ 都是 $A\rightarrow x$ , $A\in V$ and $x\in(V\cup T)^*$ - 語言 $L$ 被稱為上下文無關 i.f.f. 有一個上下文無關文法使得 $L=L(G)$ - 所有正規語言都是上下文無關的，所以一個正規語言也是上下文無關的 備註：linear grammer RHS中只有一個變數 #### Leftmost and Rightmost derivation #### Definition 5.2 一個 derivation 中每個 step 都是由最左／右邊的變數做替換的 稱該 derivation leftmost/rightmost #### Derivation Tree 右邊的東西為左邊東西的child ![](https://i.imgur.com/Xy3dHOI.png) #### Definition 5.3 設 $G=(V, T, S, P)$ 為一個 cfg，一個 ordered tree 為一個 derivation tree i.f.f. 1. root 為 $S$ 2. 每個 leaf 都是從 $T\cup\{\lambda\}$ 來的 3. 每個 interior vertex（不是 leaf 的 vertex），都是 $V$ 中的 label 4. 如果一個 vertex 有一個 label $A\in V$，且其 children 從左到右為 $a_1, a_2,..., a_n$ ，則 $P$ 必包含一個 production $A\rightarrow a_1a_2...a_n$ 5. label 為 $\lambda$ 的 leaf 不會有 sibiling #### Patrial derivation tree 1. 每個 leaf 都是從 $T\cup U\cup\{\lambda\}$ 來的 2. 每個 interior vertex（不是 leaf 的 vertex），都是 $V$ 中的 label 3. 如果一個 vertex 有一個 label $A\in V$，且其 children 從左到右為 $a_1, a_2,..., a_n$ ，則 $P$ 必包含一個 production $A\rightarrow a_1a_2...a_n$ 4. label 為 $\lambda$ 的 leaf 不會有 sibiling 從左到右看 tree 的 leaf，忽略 $\lambda$ 的符號串稱為 tree 的 yield #### Theorem 5.1 - 設 $G=(V, T, S, P)$ 為一個 cfg， 則 $\forall w\in L(G)$，存在一個 $G$ 的 derivation tree 其 yield 為 $w$ - 任何 derivation tree 中的 yield 都在 $L(G)$ 中 - 如果 $t_G$ 為 $G$ 中的任一個 partial derivation tree 且其 root 為 $S$，則 $t_G$ 的 yield 為 $G$ 的 sentential form ### 5.2 Parsing and Ambiguity #### Parsing - 找出一個 production 的序列，透過他可以導出 $w\in L(G)$ - 窮舉搜尋 parsing（一種 top-down parsing） - 給一個字串 $w$，我們系統性的建構所有的可能（e.g. leftmost）derivation 去看他們是否 match $w$ - 缺點： - 單調、低效率 - ### 5.3 Context-Free Grammars and Programming Languages