Context Free Grammars(CFG)
上下文无关文法
属于Syntactic Analysis，即分析words怎么组成一个sentence
应用：对文本进行结构化的建模，基于语言的实际语法
CFG
Definition: a set of recursive rewriting rules (or productions) used to generate patterns of strings.
主要通过
- Constituency 选区：把一个句子分区
- ordering：words和分区之间如何排序的规则
Constituents 区
phrases
判断是不是一个unit：
- units 是不是可以重新排序
- John talked [to the children] [about drugs].
- John talked [about drugs] [to the children].
- But not: John talked drugs to the children about (random reorder) (反例）
- units 是不是可以被拓展或者取代
- I sat [on the box / right on top of the box / there]
CFG 组成部分
- Terminals symbols： words
- car, man, house
- Non-terminal symbols：句法标签
- NP, VP, etc. representing the constituents or categories of phrases
- Rules/ productions： 是由一个 “→” 连接的表达式，解释了怎么插入words的规则
值得注意的是，如果一个句子的句法结构不是很清楚，可能可以产生多种cfg
示意图如下：
常见 phrases in English
陈述句、祈使句、yes-no疑问句、wh疑问句
代词、专有名词、限定词、名目
动词+名词、动词加从句
重复的adj、adv
重复累加的介词名词结构
CFG局限性
有三点分别是agreement、subcategorization、movement
1.Agreement
人称和单复数，解决办法就是增加rules或者加一层features在grammar上面
2.Subcategorization
简单的说就是，很多单词有对应的搭配。比如你不能吃书，看米饭。
3.Movement
也就是说一个单词，句法的变化会导致单词位置的变化，这对于cfg来说识别比较困难
book the flight 但是book和flight隔了2个动词，want和have
小结一下，cfg就是得出句子的基本结构，更精细的结构需要更好的算法。
Dependency Grammars
依存句法
和cfg的区别是，cfg直接以句子中的words来得到分割树（上下文无关），而依存句法用单词之间的依存关系来得到句法结构（上下文有关）。
具体分类很细致，不在这里展开
Parsing algorithms 解析算法
如何运用rules来解析句法
Top-down Parser
Goal-driven，以一个non-terminal sybol开始从上到下，从左到右。 可能有多种方式
Bottom-up Parser
Data-driven，先给单词都列好词性，从下到上。 保留原来路径，也可能有多种方式
算法复杂度高，也可能给出完全no sense的树结构
1. Chart Parsers
CKY (Cocke-Kasami-Younger) algorithm， **Bottom-up **，要求grammar符合Chomsky Normal Form， 而且最后成一个图表，或者一个解析三角形。
- CNF: only allow two types of right-hand sides:
- Two non-terminal symbols: NP -> DT NN
- One terminal symbol: VP -> look
对于所有可能的字符串，判定否属于一个上下文无关文法的rule
2.Treebanks
Semi-automatically generated sets of parse trees for the sentences in some corpus (manually corrected by human annotators). 也就是说一种数据库，根据数据库，我们在parse的时候可以得到相关的统计概率解析，以更好的判断。
产生最高概率的树即为结果（pcfg）
可以cky作为骨干，结合tree bank来得到pcfg。但是这个算法同样有准确度不能保证的问题， 因为现实生活中的句法可能会和数据库不太一样。这个问题通过 lexicalization词汇化来解决。
3.Lexicalized Statistical Parsing
Add lexical dependencies to the scheme of probabilities. Integrate the preferences of particular words into the probabilities in the derivation
整合语义学的知识，使得解析更好。（比如限定phrase的开头词汇等）
结合了上述技术，真实的句法结构很有可能在前几个高概率结构树中，排序选择即可
Evaluation
根据gold standard， 算precision，recall，f-measure等。
当今较好的算法如下图：
http://nlp.stanford.edu:8080/parser/
小结
主要就是句法分析，上下文无关文法， 简单讲了依存句法，详细讲了如何进行解析，解决了一些什么问题。具体代码还是在nltk包中，简单用法如下
