---
title: 'NLP技術之文字表示法 - 句法分析'
tags: NLP
---

NLP技術之文字表示法 - 句法分析
===

## Table of Contents

[TOC]

## 學習目標
* 之前講過：
* 如何處理斷詞、詞性標註、Stemming？
* 如何表達語言的表示法？3種
* 假設做自然語言處理時，使用的表示法是==向量表示法 (Bag of Words, BOW)==
* BOW表示法：將句子拆成一個個的`字`或`詞`，以便接下來利用Syntactic Parsing (句法分析)來理解。
* 下一步驟，如何利用Syntactic Parsing (句法分析)，知道`Input Sentence`要拆解成什麼樣子？

---

==4. Syntactic Parsing (句法分析)==
---

* 目標：
* 利用文法結構，產生正確的句法結構樹 (Syntactic Parsing Tree)
* 句法結構不一樣！

### Context Free Grammars (CFG)

* Context Free Grammars ==與內文、功能無關==。
* 透過簡單的對應(Grammar)，得知句子該如何拆解。
* 兩種symbols：
1. non-terminal symbol
* 代表Parsing尚未結束，需要一直被分解，直到最小單位為terminal symbol。
* 遞迴(Recursive)演算法
2. terminal symbol

> [NLP技術之概論](/%2FSlVAWTARRKGI4tuEpp09DQ)

:::info
#### 1. $N$ a set of non-terminal symbols

#### 2. $\sum_{}$ a set of terminal symbols (disjoint from $N$)

#### 3. $R$ a set of **_rules_** of the form $A \to \beta$, where $A \in N$ and $\beta$ is a string of symbols from $(\sum_{} \cup N)^*$
* 透過 **_rules_** ，一層一層地遞迴(Recursive)往下拆解，將non-terminal symbol ($A$) 轉為 terminal symbol ($\beta$)，直至Parsing結束。

#### 4. $S$, a designated non-terminal called the `start symbol`
* 一個一個的`句子(start symbol)`，方便往下拆解。
:::

### Simple CFG for English

* 在做Syntactic Parsing (句法分析)時，需要以下兩項：
1. Grammar (文法)
* 透過簡單的對應(Grammar)，得知 $S$ `句子(start symbol)` 該如何拆解其結構。
2. Lexicon (詞彙)
* 將`字(Ex: the, book, ...)`歸類為哪一種詞性？
* 將`字`與`詞性`的對應，建立成一個字典。
* 接著，把字典裡東西 Input 到 Syntactic Parsing 裡面。透過Grammar Tree，最後會建出Syntactic Parsing Tree。


### Sentence Generation
* Sentences are generated by recursively rewriting the start symbol using the rules until only terminals symbols remain
* Ex: `I ate the pizza with meatballs.`

### Parsing

* 最終結果：==輸入 == 產出==
* Ex:

* Parsing分為兩種方式，用來建立`句法結構樹 (Syntactic Parsing Tree)`：
1. Top-Down Parsing (由上往下)：從start symbol開始。
* 容易操作。


2. Bottom-up Parsing (由下往上)：從the terminal symbols開始。
* 過程中，需要一直做拆解、替換。
* 費時。


* 如何讓Parsing建立地更有效率？
* 演算法：==動態規劃（Dynamic programming，簡稱DP）==
* 目的：讓尋找過程的computation complexity(計算複雜性)降低。

* 可使用實驗室已寫好的Library。

---
* ##### tags: `NLP技術之文字表示法 - 句法分析`
* [Introduction to Dynamic Programming (動態規劃)](http://mirlab.org/jang/books/dcpr/dp.asp?title=8-1%20Introduction%20to%20Dynamic%20Programming%20(%B0%CA%BAA%B3W%B9%BA)&language=chinese)
* [動態規劃(Dynamic Programming)](https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/dong-tai-gui-hua-dynamic-programming)