编译原理 - 文法和语言 ## 文法和语言 ### 字母表和符号串 #### 字母表 元素非空的又穷集合，包含了语言中允许出现的全部符号 #### 字母表上的符号串 有字母表Σ中的符号所组成的任何有穷序列。无任何符号的符号产称为空符号串，记作ε #### 符号串的长度 符号串中符号的个数。字符串"110011"的长度 = |110011| = 6 ,空串ε的长度为 0 #### 符号串的字串 设 w 是一个符号串，把从 w 的尾部删除 0 个或若干个符号后剩余之后的部分称为 w 的前缀。同理后缀 从一个符号串总删去他的一个前缀和一个后缀之后剩余的部分称为该符号串的字符号串或字串 #### 符号串的方幂 设 w 是某字母表上的符号串，把 w 自身连接 n 次得到的符号串即 v = www...ww(n 个 w)，称 v 是 w 的 n 次幂 w^0 = ε #### 集合的闭包 设 A 是一个集合，A 的正闭包记作 A^+ 定义为： > A^+ = A^1 ∪ A^2 ∪...∪ A^n∪... A^* 定义为 A 的自反闭包，显然有： > A^* = A^0 ∪A^1 ∪ A^2 ∪...∪ A^n∪... ### 文法和语言的形式化定义 #### 文法 一部文法 G 是一个四元组 > G = (V_N,V_T,S,P) > > V_N:非空有限的非终结符集合 > > V_T:非空有限的终结符集合 > > S:文法的开始符号，S 属于 V_N > > P:产生式集合。产生式是按一定格式书写的定义原发范畴的文法规则 A、B、C 等大写字母表示非终结符 a,b,c 等小写字母表示终结符 α，β，γ等希腊字母表示文法符号串。文法符号串是由终结符和非终结符组成的符号串 #### 直接推导 文法 G=(V_N,V_T,S,P)。ζ，γ∈(V_N∪V_T)^* ,若 S=*>ζαγ，且存在 a->β，则称ζαγ直接推导出ζβγ，记作ζαγ=>ζβγ，与之相应，称ζβγ直接规约到ζαγ。 #### 直接推导序列 设有文法 G=(V_N,V_T,S,P)，若存在ω = α0=>α1=>...αn-1=>αn = υ #### 句型 如果 S⇒* α，α∈(VT∪VN)*，则称α是 G 的一个句型 (sentential form)。 一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。 #### 句子 如果 S⇒* w，w ∈VT*，则称 w 是 G 的一个句子 (sentence)。 句子是不包含非终结符的句型。 ##### 最左 (右) 推导 在每一步推导过程中，总是对字符串中最左 (右) 边的非终结符进行替换 ### 语法分析树和文法二义性 #### 语法分析树 语法分析树来表示经推导而产生的句子结构，有助于理解句子的语法结构层次。 1. 根由开始符号所标记； 2. 每个叶子由一个终结符、非终结符或 ε 标记； 3. 每个内部节点都是非终结符； 4. 若 A 是某节点的内部标记，且 X1、X2...Xn 是该节点从左到右的所有孩子的标记。则：A→X1X2...Xn 是一个产生式。若 A→ε，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。若 A→ε，则标记为 A 的节点可以仅有一个标记为 ε 的孩子。 #### 二义文法 一个句子可能对应多于一棵语法树。 这种问题由"句子产生过程中的某些推导有多于一种选择"引起。