引用博客https://blog.csdn.net/continueoo/article/details/72851724
什么是语法解析在自然语言中，句子可以分为主谓宾等表示。人们说话的方式（即使是在酒后的胡言乱语）也存在一些结构和规则。语言学中的语法分析的目标就是努力分离出这些语法结构。词语之间绝非是简单的顺序关系，它必须是描述词语如何相联系的。语法解析中有两个主要的问题： 1.句子语法在计算机中的表达与储存方式。 2.语法解析算法。
对于第一个问题，最近50年间，最主要的方法就是为每个句子构造一个树结构。举例如下，S表示句子；NP、VP、PP是名词、动词、介词短语（短语级别）；N、V、P分别是名词、动词、介词。
实际存储的时候上述的树可以表示为(S (NP (N Boeing)) (VP (V is) (VP (V located) (PP (P in) (NP (N Seattle))))))。互联网上已经有成熟的、手工标注的语料数据集，例如The Penn Treebank Project （Penn Treebank II Constituent Tags）。 以上名词短语的中心就是velocity而不是waves，这是顺序关系中得不到的结论。最简单的表达地嵌入概念的概率模型是PCFG，概率上下文无关文法就是一个为规则添加了概率的简单CFG，下面我们来看一下处理算法
上下文无关语法（Context-Free Grammer）为了生成句子的语法树，我们可以定义如下的一套上下文无关语法。 1）N表示一组非叶子节点的标注，例如{S、NP、VP、N…} 2）Σ表示一组叶子结点的标注，例如{boeing、is…} 3）R表示一组规则，每条规则可以表示为X->Y1Y2…Yn，X∈N，Yi∈(N∪Σ) 4）S表示语法树开始的标注
举例来说，语法的一个语法子集可以表示为下图所示。当给定一个句子时，我们便可以按照从左到右的顺序来解析语法。例如，句子the man sleeps就可以表示为(S (NP (DT the) (NN man)) (VP sleeps))。
这种上下文无关的语法可以很容易的推导出一个句子的语法结构，但是缺点是推导出的结构可能存在二义性。例如下面两张图中的语法树都可以表示同一个句子。常见的二义性问题有：1）单词的不同词性，如can一般表示“可以”这个情态动词，有时表示罐子；2）介词短语的作用范围，如VP PP PP这样的结构，第二个介词短语可能形容VP，也可能形容第一个PP；3）连续的名字，如NN NN NN。
概率分布的上下文无关语法（Probabilistic Context-Free Grammar）由于语法的解析存在二义性，我们就需要找到一种方法从多种可能的语法树种找出最可能的一棵树。一种常见的方法既是PCFG （Probabilistic Context-Free Grammar）。除了常规的语法规则以外，我们还对每一条规则赋予了一个概率。对于每一棵生成的语法树，我们将其中所以规则的概率的乘积作为语法树的出现概率。 《统计自然语言处理》中，对PCFG的描述如下：
概率表示如下：
综上所述，当我们或得多颗语法树时，我们可以分别计算每颗语法树的概率p(t)，出现概率最大的那颗语法树就是我们希望得到的结果，即arg max p(t)。 但是该模型存在一些假设条件：
利用这些假设条件，我们可以证明一棵树的概率可以通过与所用规则的概率相乘来计算得到。
训练算法我们已经定义了语法解析的算法，而这个算法依赖于CFG中对于N、Σ、R、S的定义以及PCFG中的p(x)。上文中我们提到了Penn Treebank通过手工的方法已经提供了一个非常大的语料数据集，我们的任务就是从语料库中训练出PCFG所需要的参数。 1）统计出语料库中所有的N与Σ； 2）利用语料库中的所有规则作为R； 3）针对每个规则A -> B，从语料库中估算p(x) = p(A -> B) / p(A)；
在CFG的定义的基础上，我们重新定义一种叫Chomsky的语法格式。这种格式要求每条规则只能是X -> Y1 Y2或者X -> Y的格式。实际上Chomsky语法格式保证生产的语法树总是二叉树的格式，同时任意一棵语法树总是能够转化成Chomsky语法格式。
语法树预测算法 假设我们已经有一个PCFG的模型，包含N、Σ、R、S、p(x)等参数，并且语法树总数Chomsky语法格式。当输入一个句子x1, x2, … , xn时，我们要如何计算句子对应的语法树呢？ 第一种方法是暴力遍历的方法，每个单词x可能有m = len(N)种取值，句子长度是n，每种情况至少存在n个规则，所以在时间复杂度O(m*n*n)的情况下，我们可以判断出所有可能的语法树并计算出最佳的那个。 第二种方法当然是动态规划，我们定义w[i, j, X]是第i个单词至第j个单词由标注X来表示的最大概率。直观来讲，例如xi, xi+1, … , xj，当X=PP时，子树可能是多种解释方式，如(P NP)或者(PP PP)，但是w[i, j, PP]代表的是继续往上一层递归时，我们只选择当前概率最大的组合方式。特殊情况下，w[i, i, X] = p(X -> xi)。因此，动态规划的方程可以表示为w[i, j, X] = max (p(X -> Y Z) * w(i, s, Y) * w(s+1, j, Z))。关于动态规划方法，leetcode里有不少案例可以说明。