递归语法

在计算机科学中，如果一个语法包含的生成规则是递归的，也就是说，根据这些规则扩展一个非终端，最终可以得到一个再次包括同一非终端的字符串，那么该语法就被非正式地称为递归语法。否则它就被称为非递归语法。例如，如果存在一个非终端符号A，可以通过生产规则产生一个包含A（作为最左边的符号）的字符串，那么无语境语言的语法就是左递归的。乔姆斯基层次结构中的所有类型的语法都可以是递归的，正是递归允许产生无限的词集。

一个非递归语法只能产生一种有限的语言；而每一种有限的语言都可以由一个非递归语法产生。例如，一个直线型语法只产生一个词。一个不包含无用规则的递归上下文自由语法必然产生一种无限语言。这一特性构成了一种算法的基础，这种算法可以有效地测试无背景语法产生的是有限语言还是无限语言。