上一节介绍的回声机器人将用户输入的文本作为一个整体进行处理。对于英语和其他语言，存在着用于标记和分析句子的自然语言处理 (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 运行解析器。