上一節介紹的回聲機器人將使用者輸入的文字作為一個整體進行處理。對於英語和其他語言，存在著用於標記和分析句子的自然語言處理 (NLP) 工具，但 iBot 應用程式讓我們免除了在伺服器上使用這些工具，因為它在使用者的裝置上執行此任務並將結果傳送到伺服器。這是一個有用的功能，僅僅因為你不需要在伺服器上載入額外的程式碼。

iBot 應用程式將標記列表（在 tokens 屬性中）傳遞給伺服器。例如，句子 I don't like vegetables 被標記為 [I,do,n't,like,vegetables]。更重要的是，chart 屬性中提供了完整的形態分析。人類語言是模稜兩可的，也就是說，一個詞可能有多種含義。例如，單詞 book 可以是名詞或動詞，分別如在 I bought a book 和 I want to book a hotel 中。形態分析器以表格（稱為圖表）的形式提供所有可能含義的列表給解析器，解析器的任務是對文字進行句法分析。句法分析的副產品之一是對文字進行形態消歧。

接下來，我們將實現一個圖表解析器，旨在構建句子的句法結構。圖表解析是由 Alain Colmerauer 發明的，後來由 Martin Kay 等人改進。它是一種利用動態規劃的演算法，因此（上下文無關）解析的時間複雜度僅為 $O(n^{3})$ .

為了構建句法結構，我們將使用上下文無關規則和特徵結構。規則的左側是一個符號（稱為非終結符），它代表一個短語。右側是一個符號列表，代表構成較大短語的短語。特徵結構是包含詞語和短語的形態和句法屬性的屬性-值矩陣 (AVM)。例如，以下規則表示一個動詞短語 (VP)，其中可選的名詞短語 (NP) 作為其直接賓語

${\begin{array}{llcc}\mathrm {VP} &\rightarrow &\mathrm {V} &(\mathrm {NP} )\\&&{\mathfrak {M}}={\mathfrak {D}}&{\mathfrak {M}}({\mathsf {dobj}})={\mathfrak {D}}\\\end{array}}$

右側符號下方的方程用於構建短語的特徵結構。 ${\mathfrak {M}}$ 代表母節點的特徵結構，而 ${\mathfrak {D}}$ 代表子節點的特徵結構。在上面的規則中， ${\mathfrak {M}}={\mathfrak {D}}$ 表示 V 的特徵結構與 VP 的特徵結構統一，而 ${\mathfrak {M}}({\mathsf {dobj}})={\mathfrak {D}}$ 表示 NP 的特徵結構與母節點特徵結構的 dobj（直接賓語）屬性統一。例如，對於動詞短語 reading books，其語法樹為 $[_{\textrm {VP}}[_{\textrm {V}}{\textrm {reading}}][_{\textrm {NP}}{\textrm {books}}]]$ ，我們將得到以下特徵結構

$\left[{\begin{array}{ll}{\textrm {FUNC}}&{\textrm {'read'}}\\{\textrm {VFORM}}&{\textrm {ger}}\\{\textrm {DOBJ}}&\left[{\begin{array}{ll}\mathrm {FUNC} &{\textrm {'book'}}\\\mathrm {NUMBER} &{\textrm {pl}}\\\end{array}}\right]\\\end{array}}\right]$

詞典提供詞彙語義資訊（FUNC）和各個詞語的附加屬性。

一個示例語法

您可以使用可下載的解析器（適用於 OS X 和 Linux）來實現語法點選此處。以下是一個簡單的語法

// the girl reads a book

0 Det ^det=1 .
1 N	^func=girl ^person?3.
2 V	^func=read ^vform=fin ^tense=pres.
3 Det ^det=0 .
4 N	^func=book ^person?3 .

NP -> Det? A* N .
	^=. ; ^adj+. ; ^=. ;
VP -> V NP? .
	^=. ^voice=act ; ^obj=. ;
S -> NP VP .
	^subj=. ; ^=. ^vform=fin ;

請注意，您需要提供初始圖表，也就是說，沒有內建的形態分析器。以數字開頭的行定義了初始圖表（輸入句子的分析詞語）。其他行定義了帶有註釋的上下文無關規則，其中 ^ 表示 ${\mathfrak {M}}$ ，而 . 表示 ${\mathfrak {D}}$ 。運算子 = 表示相等（統一），運算子 ? 表示預設值，而 + 表示集合成員關係 ( $\in$ )。將程式碼儲存到 grammar.txt 後，使用 ./parser grammar.txt 執行解析器。