【编译原理】第二章：语言和文法
上述文法 表示，该文法由终结符集合 ，非终结符集合 ，产生式集合 ，以及开始符号 构成。
而产生式 表示，一个表达式（Expression） ，可以由一个标识符（Identifier） 、或者两个表达式由加号 或乘号 连接、或者另一个表达式用括号包裹（ ）构成。
约定 ：在不引起歧义的情况下，可以只写产生式。如以上文法可以简写为：
产生式
可以简写为：
如上例中，
可以简写为：
给定文法 ，如果有 ，那么可以将符号串 重写 为 ，记作 ，这个过程称为 推导 。
如上例中， 可以推导出 或 或 等等。
如果 ，
可以记作 ，则称为 经过n步推导出 ，记作 。
推导的反过程称为 归约 。
如果 ，则称 是 的一个 句型（sentential form ）。
由文法 的开始符号 推导出的所有句子构成的集合称为 文法G生成的语言 ，记作 。
即：
例
文法
表示什么呢？
代表小写字母；
代表数字；
表示若干个字母和数字构成的字符串；
说明 是一个字母、或者是字母开头的字符串。
那么这个文法表示的即是，以字母开头的、非空的字符串，即标识符的构成方式。
并、连接、幂、克林闭包、正闭包。
如上例表示为：
中必须包含一个 非终结符 。
产生式一般形式：
即上式中只有当上下文满足 与 时，才能进行从 到 的推导。
上下文有关文法不包含空产生式（ ）。
产生式的一般形式：
即产生式左边都是非终结符。
右线性文法 ：
左线性文法 ：
以上都成为正则文法。
即产生式的右侧只能有一个终结符，且所有终结符只能在同一侧。
例：（右线性文法）
以上文法满足右线性文法。
以上文法生成一个以字母开头的字母数字串（标识符）。
以上文法等价于 上下文无关文法 ：
正则文法能描述程序设计语言中的多数单词。
正则文法能描述程序设计语言中的多数单词，但不能表示句子构造，所以用到最多的是CFG。
根节点 表示文法开始符号S；
内部节点 表示对产生式 的应用；该节点的标号是产生式左部，子节点从左到右表示了产生式的右部；
叶节点 （又称边缘）既可以是非终结符也可以是终结符。
给定一个句型，其分析树的每一棵子树的边缘称为该句型的一个 短语 。
如果子树高度为2，那么这棵子树的边缘称为该句型的一个 直接短语 。
直接短语一定是某产生式的右部，但反之不一定。
如果一个文法可以为某个句子生成 多棵分析树 ，则称这个文法是 二义性的 。
二义性原因：多个if只有一个else；
消岐规则：每个else只与最近的if匹配。
