在计算机科学和语言学中，语法分析（英语：syntactic analysis，也叫 parsing）是根据某种给定的形式文法对由单词序列（如英语单词序列）构成的输入文本进行分析并确定其语法结构的一种过程。
语法分析器（parser）通常是作为编译器或解释器的组件出现的，它的作用是进行语法检查、并构建由输入的单词组成的数据结构（一般是语法分析树、抽象语法树等层次化的数据结构）。语法分析器通常使用一个独立的词法分析器从输入字符流中分离出一个个的“单词”，并将单词流作为其输入。实际开发中，语法分析器可以手工编写，也可以使用工具（半）自动生成.
句法分析(Parsing)就是指对句子中的词语语法功能进行分析，比如“我来晚了”，这里“我”是主语，“来”是谓语，“晚了”是补语。
句法分析是自然语言处理技术中的关键技术之一，其基本任务是确定句子的句法结构或句子中词汇之间的依存关系。 句法分析分为句法结构分析和依存关系分析。 句法结构分析又称成分结构分析或短语结构分析，其又分为两种。以获取整个句子的句法结构为目的分析称为完全句法分析或完全短语结构分析。以获得局部成分（如基本名词短语）为目的的分析称为局部分析或浅层分析。
依存关系分析又称为依存句法分析或依存结构分析。
语法分析器分类
语法分析器的任务主要是确定是否可以以及如何从语法的起始符号推导出输入符号串（输入文本），主要可以通过两种方式完成：
- 自顶向下 (top-down) 分析：根据形式语法规则，在语法分析树的自顶向下展开中搜索输入符号串可能的最左推导。单词按从左到右的顺序依次使用。
- 自底向上 (bottom-up) 分析：语法分析器从现有的输入符号串开始，尝试将其根据给定的形式语法规则进行改写，最终改写为语法的起始符号。
应用
句法分析现在主要的应用在于中文信息处理中，如机器翻译等。它是语块分析（chunking）思想的一个直接实现，语块分析通过识别出高层次的结构单元来简化句子的描述。从不同的句子中找到语块规律的一条途径是学习一种语法，这种语法能够解释我们所找到的分块结构。这属于语法归纳的范畴。
迄今为止，在句法分析领域中存在很多争议，也许你会发现恰巧有人提出了与你正在努力研究的语法归纳程序偶然产生的相似的句法结构，而且这些也可能已经被当成了句法结构模型的证据。但是，这些找到的结构依赖于学习程序中隐含的归纳偏置。这也指明了另外一个方向，我们需要事先知道模型能够找到什么样的结构，同时应该首先确定我们对句子进行句法分析的目的。这里有各种可能的目的：使用句法结构作为语义解释的第一步；识别短语语块，为信息检索系统的索引服务；构建一个概率句法分析器作为一个优于n元语法的语言模型。这些问题的共同目标是构建这样的一个系统：对于任意的句子都能够主产生证明有用的结构，也就是要构建一个句法分析器。
句法分析的三种不同的途径可以利用概率：
1、利用概率来确定句子：一种可能的做法是将句法分析器看成是一个词语网络上的语言模型，用来确定什么样的词序列经过网络的时候会获得最大概率。
2、利用概率来加速语法分析： 第二个目标是利用概率对句法分析器的搜索空间进行排序或剪枝。这使得句法分析器能够在不影响结果质量的情况下尽快找到最优的分析途径。
3、利用概率选择句法分析结果： 句法分析器可以从输入句子的众多分析结果中选择可能性最大的。
[来源: wiki ， URL:https://zh.wikipedia.org/wiki/%E8%AF%8D%E5%B9%B2%E6%8F%90%E5%8F%96]
对于Probabilistic context-free grammar算法
a probabilistic context-free grammar G 可以被定义为:
这里
- N非终结符号的集合
- Σ是终端符号的集合
- R 这是生成规则
- S 开始的标志
例如：
这里:S=sentence, VP=verb phrase, NP=noun phrase, PP=prepositional phrase, DT=determiner, Vi=intransitive verb, Vt=transitive verb, NN=noun, IN=preposition.
S 为 “sentence”, NP 是 “noun phrase”, VP是 “verb phrase”等. Σ 包含了所有单词词汇. 开始的符号是S, 这里将S设为根节点。最后，我们有context-free rules， 如：
那么一个语法分析树就是：
举例：
【https://www.inf.ed.ac.uk/teaching/courses/inf2a/slides/2015_inf2a_L20_slides.pdf, pp. 7-15】
发展历史
最早的自然语言理解方面的研究工作是机器翻译。1949年，美国人威弗首先提出了机器翻译设计方案。20世纪60年代，国外对机器翻译曾有大规模的研究工作，耗费了巨额费用，但人们当时显然是低估了自然语言的复杂性，语言处理的理论和技术均不成热，所以进展不大。主要的做法是存储两种语言的单词、短语对应译法的大辞典，翻译时一一对应，技术上只是调整语言的同条顺序。但日常生活中语言的翻译远不是如此简单，很多时候还要参考某句话前后的意思。
大约90年代开始，自然语言处理领域发生了巨大的变化。这种变化的两个明显的特征是：
（1）对系统输入，要求研制的自然语言处理系统能处理大规模的真实文本，而不是如以前的研究性系统那样，只能处理很少的词条和典型句子。只有这样，研制的系统才有真正的实用价值。
（2）对系统的输出，鉴于真实地理解自然语言是十分困难的，对系统并不要求能对自然语言文本进行深层的理解，但要能从中抽取有用的信息。例如，对自然语言文本进行自动地提取索引词，过滤，检索，自动提取重要信息，进行自动摘要等等。
语法分析主要分为三种Probabilistic context-free grammar；Dependency parsing; Combined structure.
Probabilistic context-free grammar ，扩展了context-free grammars，类似于隐藏的马尔科夫模型扩展正则语法。每个product都production分配一个概率。(Chomsky, Noam,1956;Chomsky, Noam, 1956;Chomsky, Noam,1956). 21世纪90年代开始，概率的方法普及于NLP。如1987年，Tomita, M.提高了传统parsing 算法的效率。
Dependency parsing这块主要是了解句法依存分析的基本概念. 用词与词之间的关系来描述语言结构的框架称为依存语法,又称从属关系语法. 在依存语法理论中,"依存"是词与词之间支配与被支配的关系,这种关系不是对等的,而是有方向的.处于支配的称为支配者,被支配的称从属者.最早研究该课题之一的是（Hudson, 1984)。还有：Eisner (1996), Collins et al. (1999), Yamada 和Matsumoto (2003), Nivre 和 Scholz (2004), 和 McDonald et al. (2005).Marcus等的工作都是关于Dependency parsing的, 1993使用映射树来解决parsing问题。
【出处：wiki， URL：https://zh.wikipedia.org/wiki/%E8%AF%8D%E5%B9%B2%E6%8F%90%E5%8F%96]
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1970 | Earley, J.将parsing 算法的复杂度n^3降低到n^2 | Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 13(2), 94-102. |
| 1978 | Frazier, L., & Fodor, J. D.设计一个两步骤的parsing算法 | Frazier, L., & Fodor, J. D. (1978). The sausage machine: A new two-stage parsing model. Cognition, 6(4), 291-325. |
| 2003 | Klein, D., & Manning, C. D提出非局部的PCFG算法更有效 | Klein, D., & Manning, C. D. (2003). Accurate unlexicalized parsing. In Proceedings of the 41st annual meeting of the association for computational linguistics. |
| 2005 | McDonald, R., Pereira, F., Ribarov, K., & Hajič, J.使用spanning tree algorithms设计了Non-projective dependency parsing的算法 | McDonald, R., Pereira, F., Ribarov, K., & Hajič, J. (2005, October). Non-projective dependency parsing using spanning tree algorithms. In Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing (pp. 523-530). Association for Computational Linguistics. |
| 2014 | Kong, L., Schneider, N., Swayamdipta, S.等人提出tweet的依赖解析器 | Kong, L., Schneider, N., Swayamdipta, S., Bhatia, A., Dyer, C., & Smith, N. A. (2014). A dependency parser for tweets. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) (pp. 1001-1012). |
发展分析
瓶颈
自然语言处理研究逐渐从词汇语义成分的语义转移，进一步的，叙事的理解。然而人类水平的自然语言处理，是一个人工智能问题，相当于希望计算机能够和人一样具备语言理解和表达的能力。自然语言处理的未来一般也因此密切结合人工智能发展。
在PCFG中，词的选择具有很强的独立性假设，词的选择完全依赖于当前的词性(POS)，而条件独立于与其他所有句法树上的结构(More formally, the choice of each word in the string is conditionally independent of the entire tree,once we have conditioned on the POS directly above the word)，而这正是很多歧义问题的原因。如，‘IBM’的选择仅仅与‘NP’有关，而与其他树上的结构完全无关。
对结构偏好（structure preference）不敏感
对于存在歧义的两个句子，具有完全相同的树形结构，但是由于缺乏词汇的信息，进而缺少结构依赖的信息，使得最终不同树形结构计算的概率完全相同。
如下例中：同一句话，两个完全不同的句法分析结构，由于采用了相同的rules，因此概率计算最终也会相同。
Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n^3 ) time
g Chu-Liu-Edmonds (Chu and Liu, 1965; Edmonds, 1967) MST algorithm, yielding an O(n^2 ) parsing algorithm.
未来发展方向
虽然上述新趋势给自然语言处理领域带来了成果，但从理论方法的角度看，由于采集、整理、表示和有效应用大量知识的困难，这些系统更依赖于统计学的方法和其他“简单”的方法或技巧。而这些统计学的方法和其他“简单”的方法似乎也快达到它们的极限。因此，就现在而言，在自然语言处理界广泛争论的一个问题便是：要取得更大的进展，是需要理论上的重要突破？还是能在已有方法的基础上通过完善和优化来实现呢？目前还无法给出确切答案。大致上，更多的语言学家倾向于前一种意见，而更多的工程师则倾向于后一种意见。答案或许在“中间”，即应将基于知识和推理的深层方法与基于统计等“浅层”方法结合起来。自然语言处理上，还有地域性地差异，不同语言的特异性使得这个工作的难度加大。
Contributor: Ruiying Cai