2.1 指定语法：正则表达式和上下文无关语法
语法的形式规范需要一组规则。语法复杂性（表现力）取决于我们使用的规则。可以证明，我们直觉认为 tokens 可以通过三种规则来从单个字符集中构建：concatenation, alternation（在有限方案中选择）, 和被称为 "Kleene closure"（重复任意次数）。指定剩余的语法还需要一个额外的规则： recursion（通过相同结构构造简单实例）。前三种规则定义的字符串集合被称为 regular set，或者 regular language。Regular set 可以由正则表达式生成，并由 scanner 识别。然后给字符串集合加上递归被称为 context-free grammars(CFGs)，并且由 parser 识别。（这里的术语可能会比较困惑。“语言”这个单词的意义要放在上下文中考虑。formal 语言只是字符串集合，没有被赋予语义）。
2.1.1 Tokens 和 Regular Expressions
Tokens 是组成程序的基本块--具有含义的最短字符串。
2.1.2 Context-Free Grammars
Regular expressions 用来定义 tokens 很好。但是不能确定嵌套结构，这才是编程语言的核心。考虑一个数学表达式的结构例子：
expr -> id | number | - expr | (expr)
| expr op expr
op -> + | - | * | /
根据结构本身定义结构的能力至关重要。除了其他事项外，也能使我们确保左右括号匹配，有些不能仅通过 regular expressions 完成的事情。箭头符号（->）表示“可以具有形式”。
在 Context-free grammar 的每个规则被看作产品。作词符号是variables或者non-terminals。可能存在任意数量。构成从语法衍生出的符号称为 terminals。不能出现在左侧。编程语言中，上下文无关的 terminals 是语言的 tokens。nonterminal 的其中之一，在左侧的第一个出现被称为 start symbol。命名了语法定义的结构。
上下文无关语法符号被称为 Backus-Naur Form(BNF)，为了纪念 John Backus 和 Peter Naur,他们发明了 Algol-60 语言。严格来说*和元级别的括号不在 BNF 范围，但是它们不改变符号的表达能力，然后为了方便就看作一样的。有时还包括 +，表示前面符合的一个或者多个重复。当通过额外的操作扩展时，符号被称作 extended BNF(EBNF)。这个结构:
id_list -> id (, id)*
展开后
id_list -> id
id_list -> id_list, id
+是类似的。注意这里的括号时元符号。
就像*和括号，|貌似也比较多余。结构同样可以展开为不需要竖线的表示：
op -> + | - | * | /
# shorthand
op -> +
op -> -
op -> *
op -> /
# 或者
op -> +
-> -
-> *
-> /
很多 tokens，比如上面的 id 和 number，有很多可能的拼写（即很多可能的字符串表示）。parser 不关心这个。语义分析才会区分它们，scanner 必须保存每个这样“有趣”的拼写 tokens 以供后面使用。