第2章高级语言及其语法描述

第2章高级语言及其语法描述内容摘要：

主语 ::=冠词 形容词 名词 冠词 ::=the 形容词 ::=big 名词 ::=elephant | peanut 谓语 ::=动词 宾语 动词 ::=ate 宾语 ::=冠词 名词 上述推导可写成 句子 = the big elephant ate the peanut + 说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为 最左推导 ，类似的有 最右推导 （一般推 导）。 (2) 从一组产生式可推出不同的句子，如以上产生式还可推 出“大象吃象”、“大花生吃象”、“大花生吃花生”等句子， 它们 在语法上都正确，但在语义上都不正确。 所谓 文法 是在 形式上 对句子结构的定义与描述，而未 涉及 语义 问题。 ：我们用语法树来描述一个句子的语法结构。 句子 主语 谓语 冠词 形容词 名词 动词 宾语 冠词 名词 The big elephant ate the peanut 语法成分（在形式 语言中又称“非终 结符”） 单词符号（在形 式语言中又称 “终结符号” ) 文法和语言的形式定义 定义 1: 文法 G=（ VN， VT， P， Z） VN ：非终结符号集 VT ：终结符号集 P：产生式或规则的集合 Z：开始符号（识别符号） Z∈ VN V＝ VN∪ VT 称为文法的字汇表 产生式： U :: x U ∈ VN, x∈ V* 其中 : ： 产生式是一个有序对 (U, x), 通常写为 : U :: x 或 U  x； | U| = 1 |x|  0 ： 出现在产生式的左部 ,且能推出符号或符号串的 那些符号。 其全体构成非终结符号集，记为 VN。 ： 不出现在产生式的左部 ,且不能推出符号或符号串 的那些符号。 其全体构成终结符号集，记为 VT。 P = {无符号整数 → 数字串 ； 数字串 → 数字串 数字 ； 数字串 → 数字 ； 数字 →0 ； 数字 →1 ； ………… 数字 →9 ； } Z = 无符号整数 ； 例：无符号整数的文法： G[无符号整数 ]=（ VN， VT， P， E） VN＝ {无符号整数 ,数字串 , 数字 } VT = {0,1,2,3,……9} 几点说明 ： 产生式左边符号构成集合 VN，且 Z ∈ VN 有些产生式具有相同的左部，可以合在一起 例、 无符号整数 → 数字串 ； 数字串 → 数字串 数字 | 数字 ； 数字 →0 | 1 | 2 | 3 | …… | 9 文法的 BNF表示 给定一个 文法，实际只需给出产生式集合，并指定识别符号 例、 G[无符号整数 ] 无符号整数 → 数字串 ； 数字串 → 数字串 数字 | 数字 ； 数字 →0 | 1 | 2 | 3 | …… | 9 推导与归约 定义 2： 直接推导：文法 G： v＝ x Uy， w＝ xuy, 其中 x、 y ∈ V* ， U∈ VN, u ∈ V*, 若 U :: u∈ P，则 v w。 若 x＝ y＝ ε，有 U :: u，则 U  u 换句话说， x和 y是符号串，若使用一次产生式可以从 x变换出 y，则称 x直接推导出 y(或者说 y是 x的直接推导），记为 x y。 当符号串已没有非终结符号时，推导就必须终止。 因为 终结符不可能出现在产生式左部，所以将在产生式左部出现的 符号称为非终结符号。 例如： G[N]： N → ND | D D → 0| 1| 2| 3| 4| 5| 6| 7| 8| 9 N ND NDD ND9 N09 D09 109 (6) == == (1) == (3) (4) == == (2) (5) == ＋ N==109 定义 3： +推导： x和 y是符号串，若使用若干次产生式可以从 x变换出 y，则称 x推导出 y(或者说 y是 x的推导），记为 x y。 ＋ N ND NDD ND9 N09 D09 109 (6) == == (1) == (3) (4) == == (2) (5) == 例： 则： 定义 4： *推导： x和 y是符号串，若使用 0次或若干次产生式可以从 x变换出 y，则称 x*推导出 y(或者说 y是 x的 *推导），记为 x y。 * * N==109 则： * N==N 或者说 ：若有直接推导序列：x=U0==U1==U2==……==U n=y,则 x==y。 + 直观意义：规范推导＝最右推导 定义 5： 最 右 推导：若符号串 α 中有两个以上的非终结符时，对推导的每一步坚持把 α 中的最右 非终结符进行替换，称为最 右 推导。 最 左 推导：若符号串 α 中有两个以上的非终结符时，对推导的每一步坚持把 α 中的最左 非终结符进行替换，称为最 左 推导。 定义 6： 推导的逆过程称之为归约。 例： x ==y,可称为 x直接推导出 y，也可称为 y直接归约出 x。 ＋ x ==y ,可称为 x推导出 y，也可称为 y归约出 x。 语言的形式定义。