计算句法学使用计算机进行自然语言的自动句法分析，揭示句子中单词与单词之间的句法关系以及词组与词组之间的句法关系。

计算句法学中的形式模型主要有基于短语结构语法的形式模型、基于合一运算的形式模型、基于依存和配价的形式模型、基于格语法的形式模型等。

把句子分割为成分层次的思想最早出现于实验心理学的奠基人W.冯特（W. Wundt，德国）的《大众心理学》（Völkerpsychologie，1900）一书中。冯特关于组成性的思想被L.布龙菲尔德（Leonard Bloomfield，美国，1887～1949）在其早期的著作《语言研究导论》（An Introduction to the Study of Language，1914）中引入了语言学。后来在他的著作《语言论》（Language，1933）发表的时候，“直接成分分析法”（immediate-constituent analysis）成为了美国语言学研究中的相当完善的方法。与此相反，从古典时期开始的传统的欧洲语法研究如何确定单词之间的关系，而不是研究如何确定成分之间的关系。欧洲的句法学家们在诸如依存语法（dependency grammar）等语法中，仍然强调以词为基础。

美国结构主义提出了关于直接成分的一些定义，把他们的研究说成是“发现程序”（discovery procedure）；这是描写语言句法的一种有方法论色彩的算法。这些研究都试图印证“直接成分的首要标准就是一个组合作为简单的单位起作用的程度”这样的直觉。其中最有名的定义是美国Z.S.哈里斯（Zellig Sabbettai Harris，美国，1909～1992）关于使用可替换性（substitutability）试验来检验单独的单位分布的相似性（distributional similarity）的思想。从实质上说，这种方法是把一个结构分解为若干个成分，把它替换为各个成分的简单结构。哈里斯的试验是把成分看成一种等价类（equivalence class）的这种直觉的开端。

这种层次成分思想的最早的形式化描述是A.N.乔姆斯基（Avram Noam Chomsky，美国，1928～ ）在1956年定义的短语结构语法（phrase structure grammar），又称上下文无关语法（context-free grammar，简称CFG）。此后，大多数的生成语法理论都建立在上下文无关语法的基础之上。例如，中心语驱动的短语结构语法（head-driven phrase structure grammar，简称HPSG）、词汇功能语法（lexical-functional grammar，简称LFG）、管辖与约束理论（Government and Binding Theory）、构式语法（construction grammar），等等。其中很多理论使用了叫作X阶标图式（X-bar schemata）的图式上下文无关模板，这种模板依赖于句法中心词的概念。

在这个时期研制了很多上下文无关语法的高效剖析算法，自然语言处理的大多数计算模型都是建立在上下文无关语法的基础之上的。

建立在上下文无关规则基础上的语法并不是无所不能的，它在处理长距离依存关系时显得无能为力。为了处理长距离依存关系的问题，对于上下文无关语法做了各种扩充。但是，有些处理长距离依存关系的语法都牵涉到语义，而没有牵涉到句法；表层句法并不表示长距离的链接。

除此之外还有其他的与此不同的语法，上下文无关语法形式化方法的一个扩充是A.尤喜于1985年提出的树邻接语法。树邻接语法的基本数据结构是树，而不是规则。有两种树：一种是初始树（initial trees），一种是附加树（auxiliary trees）。初始树表示简单的句子结构，附加树用于在树中增加递归。树通过两种运算结合起来：一种运算叫作替换（substitution），一种运算叫作邻接（adjunction）。邻接运算可以处理长距离依存关系。树邻接语法的一种扩充叫作词汇化树邻接语法。树邻接语法是柔性上下文有关语言（mildly context-sensitive language）家族的一个成员。

另外一种处理长距离依存关系的方法是建立在使用空范畴和相互索引的基础上的。宾州树库使用了这种模型，它是在宾州树库的各个语料库中，从扩充的标准理论（Extended Standard Theory）和最简单主义（Minimalism）抽取出来的。

另外一种语法理论不是建立在组成性的基础之上的，而是以单词之间的关系为基础的。这些语法理论中最著名的有I.A.梅尔丘克（I. A. Mel'čuk，加拿大）于1979年提出的依存语法、R.A.赫德森（Richard A. Hudson，英国）于1984年提出的词语法（word grammar）和F.卡尔森（F. Karlsson，美国）于1995年提出的约束语法（constraint grammar）。

V.英格维（V.Yingve，美国）于1955年提出了一种广度优先、自底向上的算法，并把这种算法作为机器翻译过程的一个部分来描述。用于剖析和翻译的自顶向下方法最早是由A.葛莱尼（A. Glennie，美国）于1960年提出的。

以CKY算法为核心的动态规划剖析最早是由J.柯克（John Cocke，美国）于1960年实现的。后来又对这个算法做了进一步扩充和形式化，并且研究了它的时间复杂性。

有关良构子串表（well-formed substring table, 简称WFST）的概念是由美籍日裔学者久野暲于1965年独立地提出的，他把良构子串表作为一种数据结构来存储在剖析过程中前面的计算结果。基于对柯克工作的进一步泛化，美国M.凯伊在1967年和1973年的论文独立地描述了类似的数据结构。把动态规划应用于自顶向下的剖析是J.伊尔利（J. Earley，美国）于1968年在他的博士论文中提出的，叫作伊尔利算法（Earley algorithm）。美国B.A.舍尔（B. A. Sheil，美国）于1976年证明了良构子串表和伊尔利算法的等价性。P.诺维奇（P. Norvig，美国）于1991年证明，在任何语言中，所有这些动态规划算法都可以使用备忘（memoization）功能来实现，即给简单的自顶向下剖析增加一个备忘操作。

在句法剖析的早期历史上，曾经普遍使用层叠式的有限状态自动机，后来，研究的重点很快就转移到完全上下文无关语法剖析方面去了。K.W.邱奇（Kenneth Ward Church，美国）于1980年提出，应该回过头去使用有限状态语法作为自然语言理解的处理模型。

S.阿布尼（Steven Abney，美国）于1991年强调，浅层剖析（shallow parsing）在实际应用方面有重要的作用。在关于浅层剖析的许多工作中，应用机器学习的方法来研究模式学习问题。

概率上下文无关语法的很多形式特性是在1969年首先由T.L.布斯（T. L. Booth，美国）和A.沙乐马（A. Salomma，美国）揭示出来的。J.K.贝克（J. K. Baker，美国）于1979年F.杰利内克（Frederick Jelinek，美国）和J.D.拉斐尔提（J. D. Lafferty，美国）于1991年扩充了CKY算法，用这种算法来计算前缀的概率。A.斯托尔克（A. Stolcke，美国）于1995年改进了这两种算法，使伊尔利算法能够用于概率上下文无关语法。

在20世纪90年代初期，很多研究人员开始探索给概率上下文无关语法增加词汇依存关系的约束，以便使概率上下文无关语法的概率对于周围的句法结构具有更大的敏感性。

这些早期的词汇概率研究首先导致学者们来解决一些特定的剖析问题，例如，使用基于转换的学习方法、最大熵方法、基于记忆的学习方法、对数线性模型、决策树方法以及递进自举（boosting）的方法来解决英语句子中介词短语附着问题。

除了概率上下文无关语法之外，扩充词汇概率剖析方法的形式化算法还有：概率树邻接语法、概率LR剖析、概率链语法。

一种叫作超级标注（supertagging）的概率剖析方法把词类标注扩展到使用非常复杂标记的剖析，这样的标记在实际上就是基于词汇化树邻接语法的词汇化剖析树的片段。超级标注也应用于组合式范畴语法剖析和中心语驱动的短语结构语法剖析。

剖析的分辨方法可以广义地分为两类：动态程序设计方法和分辨再排序方法，分辨再排序方法要求N个最佳的剖析结果。基于A*搜索的剖析器可以容易地加以修改从而生成N-最佳表，这只要在得到第一个最佳的剖析结果之后，继续进行搜索就行了。

在动态程序设计方法中，不用先输出然后再重新排序，最后得到一个N-最佳表，而是把剖析结果凝练地在线图（chart）中表示出来，对数-线性方法以及其他方法都可以从线图直接地用来解码。

还有一种再排序方法，即通过改变最优化标准来进行再排序。

当前的研究中还有一个重要的领域——依存剖析。依存剖析算法有双词汇算法、使用联机学习的最大跨度树方法、给剖析器行为建立分类器的方法等。

通常还要区分投射性依存（projective dependencies）和非投射性依存（non-projective dependencies）。非投射性依存是依存线出现交叉的依存；这种依存在英语中不常见，但是在很多词序自由的语言中很常见。

语法归纳（grammar induction）的领域与统计剖析密切相关，剖析器常常可以当作语法归纳算法的一个部分来使用。语法归纳中最早的统计研究是J.J.霍宁（J. J. Horning，美国）于1969年进行的，他证明了不使用反面证据也可以归纳出概率上下文无关语法。

从源头上说，在语言学理论中使用“特征”（feature）起源于音系学。R.雅各布森于1939年首先把特征（叫作区别特征）作为他的理论中的一种知识本体类型（ontological type）来使用，在他之前曾经有N.S.特鲁别茨科伊（Nikolai Sergeevich Trubetskoi，俄罗斯，1890～1938）在1939年使用过特征这个术语。此后不久开始在语义学中使用特征。句法中的特征是20世纪50年代建立起来的。

语言学中的合一运算是分别由美国凯伊和A.科尔迈洛埃（A. Colmerauer，加拿大）独立地发展起来的。凯伊提出了特征结构的合一运算，科尔迈洛埃提出了“合一”（unification）这个术语。他们两人都从事机器翻译研究，都试图探索一种形式化方法把语言信息结合起来，并且要求这种结合是可逆的。科尔迈洛埃原来的Q系统是一个自底向上剖析器，它是建立在包含逻辑变量的一系列重写规则基础上的，使用Q系统，科尔迈洛埃设计了一个英语到法语的机器翻译系统。这样的重写规则是可逆的，既可以用于剖析，也可以用于生成。科尔迈洛埃和他的同事们还设计了Prolog语言，Prolog语言的基础是完全合一的、扩充的Q系统，在Prolog语言的基础上，他们在1996年还实现了一个法语分析器。在自然语言中使用Prolog与合一，提出了定子句语法，定子句语法的基础是科尔迈洛埃的变形语法（metamorphosis grammar），而定子句语法本身是由F.佩瑞拉（Fernando Pereira，美国）和美国D.沃伦（D. Warren，美国）于1980年研制和命名的。

与此同时，美国凯伊和R.卡普兰研制了扩充转移网络（Augmented Transition Netwirk，简称ATN）语法。ATN是经过改进的递归转移网络（Recursive Transition Network，简称RTN），其中的结点用特征寄存器来加以扩充。在用ATN分析英语被动式句子时，第一个NP首先被指派到主语寄存器中，然后，当遇到被动式动词时，它的值就被移动到宾语寄存器中。为了使这个过程成为可逆的，他们对寄存器的指派进行限制，使得某些寄存器只能填写一次，因此，在写了一次之后，就不能再重新写了。他们还研究了“逻辑变量”（logical variables）的概念，但是没有实现这个概念。凯伊原来的合一算法是针对特征结构来设计的，而不是针对项目来设计的。

在KL-ONE知识表示系统的背景下，R.J.博布洛（Robert J. Bobrow，美国）和B.L.韦伯（Bonnie Lynn Webber，美国）于1980年首先提出了语言知识的继承（inheritance）和适切性条件（appropriateness conditions）。一些学者提出了没有适切性条件的简单的继承关系，早期使用这种继承关系的是P.S.雅克布（Paul S. Jacobs，美国）。

基于合一的语法理论有J.布列斯南于1982年提出的词汇功能语法、冯志伟于1981年提出的多叉多标记树模型、C.珀拉德（Carl Pollard，美国）和I.A.萨格（Ivan A. Sag，美国）于1987年提出的中心语驱动的短语结构语法、凯伊和C.J.菲尔墨于1999年提出的构式语法、H.乌慈克拉伊特（Hans Uszkoreit，德国）于1986年提出的合一范畴语法（unificationcategorial grammar，简称UCG）。关于合一语法的许多新近的工作主要集中在研究如何使用概率方法来提升排歧效果的问题。