编译器构造/描述编程语言
多年来，人们发现使用自然语言（例如英语）来描述编程语言是不令人满意的，因为可能存在遗漏、矛盾、歧义和模糊性。一个重要的里程碑是 Algol 60 报告的出版，该报告使用形式语法（BNF）来描述语言的语法。语义（含义）使用英语仔细描述。扩展 BNF（EBNF）的变体将用于本书，如本节后面所述。
已经进行了几次尝试来形式化语义，包括用于定义 Algol 68 的语法生成器，以及维也纳定义语言，该语言曾在某一阶段用于定义 PL/1 的含义。虽然理论上足够，但这些尝试非常复杂，以至于证明对实际应用几乎没有用处。
1956 年，乔姆斯基（一位语言学家）开发了一个形式语法层次结构（类型 0 到 3）用于研究英语和其他自然语言。类型 0 能力最强，类型 3 能力最弱。事实证明，类型 3 正则语法正是描述词法分析要求所需的，而类型 2 上下文无关语法正是描述许多编程语言的语法所需的。但即使是类型 0 语法也无法充分描述英语。
已经开发了可以接受语法描述作为输入，并生成使用该语法进行分析的代码的编程工具。请注意，可能存在几种不同的语法可以用来描述特定的编程语言，并且并非所有这些语法都能被这些工具使用。
使用正则语法进行词法分析的代码可以由诸如 lex、flex 和 JavaCC 之类的工具生成。
使用上下文无关语法进行语法分析的代码可以由诸如 yacc、bison 和 JavaCC 之类的工具生成。
即使你有一个合适的语法，这些工具也只能自动化编写编译器或解释器工作的相对较小的一部分。实际上，简单的词法和语法分析代码可以用手工编写，而不会造成过多的努力。我们将在后面的章节中看到一些例子。良好的手工编写代码可能比工具生成的代码更快。
用斜体（例如WholeNumber）中的词语来命名语法概念。选择这些概念的名称，这些名称在语义上对人类读者有意义，可以使内容更容易阅读和理解。Algol 60 报告使用菱形括号 '<' 和 '>' 而不是斜体来标记语法概念。
垂直线 | 用于分隔备选方案。
单引号用于指示按原样使用的字符。
复合符号 ::= 用于表示“定义为”，分号 ; 用于结束定义。
方括号 [ ] 用于指示选项和/或重复。
[ xxx ] xxx is optional. [ yyy ]* yyy may be repeated zero or more times. [ zzz ]+ zzz may be repeated one or more times.
我们将从一些满足正则语法规则的简单示例开始。
以下定义了一个十进制Digit，它可以是 '0' 到 '9' 之间的任何一个字符。
Digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ;
理解为
Digit is defined as: '0' OR '1' OR '2' OR '3' OR '4' OR '5' OR '6' OR '7' OR '8' OR '9'.
可以为Letter给出类似（有点繁琐）的定义，以涵盖 'a' 到 'z' 和 'A' 到 'Z'。
一个WholeNumber 是一个或多个十进制数字的序列，可以用以下两种方式之一表示
第一种方式
WholeNumber ::= [ Digit ]+ ;
理解为
WholeNumber is defined as: Digit may be repeated one or more times
第二种方式
WholeNumber ::= Digit [ Digit ]* ;
理解为
WholeNumber is defined as: Digit AND Digit repeated zero or more times.
这些定义允许诸如 007 之类的整数。有些人不喜欢允许整数有前导零。我们可以通过使用以下定义来处理这种看法，但我们必须将数字零（仅为 0）作为特殊情况包含在内。
NonZeroDigit ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' ; Digit ::= '0' | NonZeroDigit ; WholeNumber ::= '0' | NonZeroDigit [ Digit ]* ;
理解为
NonZeroDigit is defined as: '1' OR '2' OR '3' OR '4' OR '5' OR '6' OR '7' OR '8' OR '9'.
Digit is defined as: 0 OR NonZeroDigit.
WholeNumber is defined as: 0 OR as NonZeroDigit AND Digit repeated zero or more times.
最后一个定义是正式地说，一个整数要么是 0，要么以一个非零数字开头，并且这个非零数字后面可以跟着任意数量的数字（包括没有）。
在大多数编程语言中，一个Identifier 是任何以字母开头的字母和数字的序列。一些编程语言可能还允许一些特殊字符（例如下划线 _ 或井号 #）。Identifier 的长度也可能有一些限制，但这些限制通常被指定为以自然语言（如英语）表达的语义约束，而不是作为形式语法的一部分（例如，直到 Fortran 77，Fortran 中的Identifier 限制为最多 6 个字符）。
我们现在来看一些示例，这些示例结合在一起满足上下文无关语法的规则。
考虑一个算术表达式，如 3 + 4 * 5。通常的约定是乘法和除法先于加法和减法，因此 3 + 4 * 5 的值为 23。如果我们希望在本例中加法先进行，则会使用括号，以便 (3 + 4) * 5 的值为 35。
我们可以用以下方式表达这些关于括号和运算符优先级的约定。这些定义还指定具有相同优先级的运算符是从左到右应用的。
AddSub ::= '+' | '-' ;
MulDiv ::= '*' | '/' ;
Expression ::= Secondary [ AddSub Secondary ]* ;
Secondary ::= Primary [ MulDiv Primary ]* ;
Primary ::= '(' Expression ')' | Secondary | WholeNumber | Identifier ;
有一些非常简单的表达式没有被上述语法覆盖。你能在阅读下面第三段之前找出它们可能是什么吗？
请注意，这是一个相对简单的例子，运算符只有两个优先级级别。像 C/C++/Java 这样的语言有十多个优先级级别。
使它成为上下文无关而不是正则的特定方面是Expression 可以是Secondary 的方式，Secondary 可以是Primary，Primary 可以是带括号的Expression，即Expression 可以部分地用它自己来定义；这就是所谓的递归定义。
未被覆盖的表达式包括 -5 或 +4 之类的东西。为了处理这些，我们需要更改一个定义
Expression ::= [AddSub] Secondary [ AddSub Secondary ]* ;
此语法规则允许 -(+(-4))，但不允许 -+-4。