让我们理解计算理论(TOC)中的语法概念。
字母 ∑ 上的语言是来自 ∑ 的一组字符串。
语法是一组用于定义语言的规则。简而言之，它是语言中字符串的结构。
要描述一种语言的语法，需要两个字母（符号）集合。这些解释如下 -
终结符是由语言中的所有字符串组成的那些符号——生成语言的“给定”字母表的符号。这些通常是小写字母。
非终结符是用于定义语法替换规则（在产生式规则中）的“临时”符号（与终结符不相交）。这些必须全部被终端替换，然后才能成功地生成有效的语言字符串。这些通常是大写字母。
此外，语言 L（在字母表∑上）的语法由以下形式的一组语法规则（产生式）组成 -
α → β，
其中 α, β 是取自终端 (∑) 和非终端集合的符号串。
语法规则 α → β 可以用下面提到的几种方式中的任何一种来阅读 -
“用 β 替换 α”，
“α产生β”，
“α 重写为 β” ,
“α 减少到 β”。
语法的正式定义
考虑下面给出的例子 -
如果 ∑ = {a, b} 且 S 是非终结符，则规则 S → aS, S → ∧ 是文法 L 的产生式示例。
现在我们准备好了语法的正式定义，如下所示 -
称为终端的符号字母 T。这些与生成的语言的字母表相同。
文法符号的字母 N 称为非终结符，用于产生式规则。
一个特定的非终结符称为开始符号。通常是S。
形式为 α → β 的有限产生式集合，其中 α 和 β 是字母表 N ∪ T 上的字符串。