BUAACT-Chap02-文法和语言的概念和表示
第二章 文法和语言的概念和表示
2.1 形式语言基础
2.1.1 字母表和字符串
字母表：符号的非空有限集，例：\(\Sigma=\{a, b, c\}\)
符号：字母表中的元素，例：\(a, b, c\)
符号串：符号中的有穷序列，例：\(a, aa, ac, abc, ...\)
空符号串：无任何意义的符号串\((\varepsilon)\)
符号串集合：由符号串构成的集合
2.1.2 符号串和符号串集合的运算
- 符号串相等
- 符号串的长度
- 符号串的联接
- 符号串集合中的乘积运算：
令 \(A, B\) 为符号串集合，定义乘积 \(AB\)： \[AB = \{xy|x\in A, y\in B\}\]
- 符号串集合中的幂运算
- 符号串集合的闭包运算：
设 \(A\) 是符号串的集合，定义： \[A^+=A\cup A^2\cup ... A^n\cup ...\] 称为集合 \(A\) 的正闭包。 \[A^*=A^0\cup A^+ = \{\varepsilon\}\cup A^+\] 称为集合 \(A\) 的闭包。
2.2 文法和语言的形式定义
2.2.1 文法的定义
文法 \(G=(V_n, V_t, P, Z)\)
- \(V_n\)：非终结符号集
- \(V_t\)：终结符号集
- \(V\)：文法的字汇表，\(V=V_n\cup V_t\)
- \(P\)：产生式或规则的集合，规则 \(U::=x, U\in V_n, x\in V^*\)
- \(Z\)：开始符号（识别符号），\(Z\in V_n\)
几点说明：
- 产生式左边符号构成集合 \(V_n\)，且 \(X\in V_n\)
- 有些产生式具有相同的左部，可以合在一起（文法的 BNF 表示）
- <数字串> \(\to\) <数字串><数字>|<数字>
- <数字> \(\to\) 0|1|2|3|...|9
- 给定一个文法，实际只需给出产生式的集合，并指定符号。（识别符号一般约定为第一条规则的左部符号）
2.2.2 推导的形式定义
直观意义：规范推导=最右推导
最右推导：若符号串中有两个以上的非终结符时，先推右边的。
最左推导：若符号串中有两个以上的非终结符时，先推左边的。
2.2.3 语言的形式定义
- 已知文法，求语言，通过推导；
- 已知语言，构造文法，无形式化方法，更多是凭经验。
定义：\(G\) 和 \(G'\) 是两个不同的文法，若 \(L(G)=L(G')\)，则 \(G\) 和 \(G'\) 是等价文法。
编译感兴趣的问题是：给定 \(x, G\)，求 \(x\in L(G)\)？
2.2.4 递归文法
递归规则：规则右部有与左部相同的符号，对于 \(U::= xUy\)
若 \(x=\varepsilon\)，即 \(U::= Uy\)，左递归；
若 \(y=\varepsilon\)，即 \(U::= xU\)，右递归。
左递归文法的缺点：不能用自顶向下的方法来进行语法分析（可能会造成死循环）；
递归文法的优点：可用又穷条规则，定义无穷语言。
2.2.5 句型的短语、简单短语和句柄
直观理解：短语是前面句型中的某个非终结符所能推出的符号串。
任何句型本身一定是相对于识别符号 \(Z\) 的短语。
定义：任一句型的最左简单短语称为该句型的句柄。
2.3 语法树与二义性文法
2.3.1 推导与语法树
语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。
结点：符号
- 根节点：识别符号
- 中间结点：非终结符
- 叶节点：终结符或非终结符
有向边：表示节点间的派生关系。
语法树是自顶向下生成的，给定 G[Z]，句型 w，可建立语法树，以 Z 为树根节点，每步推导生成语法树的一枝，最终可生成句型的语法树。
子树：语法树中的某个结点（子树的根）连同它向下派生的部分所组成。
定理：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。
只需画出句型的语法树，然后根据子树找短语→简单短语→句柄。
句型推导过程\(\iff\)句型语法树的生长过程。
对句型中最左简单短语（句柄）进行的规约称为规范规约。
通过规范推导或规范规约所得到的句型称为规范句型。
2.3.2 文法的二义性
若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。
换而言之，无二义性文法的句子只有一棵语法树，尽管推导过程可以不同。
若一个文法的某句子存在两个不同的规范推导，则该文法是二义性的，否则是无二义性的。
若一个文法的某规范句型的句柄不唯一，则该文法是二义性的，否则是无二义性的。
2.4 有关文法的实用限制
若文法中有如 \(U::=U\) 的规则，则这就是有害规则，它会引起二义性。
多余规则： 1. 在推导文法的所有句子中，始终用不到的规则。即该规则的左部非终结符不出现在任何句型中。 1. 在推导句子的过程中，一旦使用了该规则，将推不出任何终结符号串。即该规则中含有推不出任何终结符号串的非终结符。
若某文法中无有害规则或多余规则，则称该文法是压缩过的。
2.6 文法的其它表示法
2.6.1 扩充的 BNF 表示（Backus Normal Form）
- BNF的元符号：<, >, ::=, |
- 扩充的BNF的元符号： <, >, ::=, |, {, }, [, ], (, )
2.6.2 语法图
