高级语言及其语法描述.ppt

第2章高级语言及其语法描述 2 1编译程序需要重点考虑的程序语言特性2 2符号和符号串2 3上下文无关文法2 4语法树和二义性2 5形式语言介绍 2 1编译程序需要重点考虑的程序语言特性 1 标识符与名字 标识符 字母打头的字母数字串 名字 用标识符表示的 带有类型 值域的程序语言对象 高级语言之间的差异也是在这里体现的 例 aa 标识符realaa 名字 实型变量 值域 运算确定 2 名字的定义 影响 目标程序的执行效率的高低 能否静态分配存储空间 能否作静态语义检查 例 intaaaa 12 3 类型错误 静态语义检查 全程变量 主程序中定义 局部变量 过程 函数 分程序 对象中定义 影响 3 变量的作用域 存储空间能否复用 变量重名时的实现方法 如 采用最小作用域原则 4 语义 同一语句 在不同的语言中的含义可能不同 例 数组A 1 3 1 4 访问 A 2 3 Pascal 按行分配 FORTRAN 按列分配 a23地址 a11地址 7 访问 a23地址 a11地址 6 5 支持的数据类型 类型中允许的运算 基本数据类型 整型 实型 布尔 字符 字符串 复杂数据类型 数组 记录 结构 指针 集合 类 6 支持的语句 分支 循环 过程 函数 7 存储空间分配方式 静态存储分配动态存储分配 函数 允许递归调用时 每一次调用需要一片数据区动态数组动态创建对象用户可动态申请 释放数据空间 2 2符号和符号串 字母表 元素的非空 有穷集合 符号 字母表中的元素 例1 V a b c 字母表 V符号 a b c例2 单词符号集 if then begin 标识符 字母表 单词符号集符号 if then begin 标识符 3 符号串 符号组成的任何有穷序列 不包括任何符号的符号串称为空串 空字 记为 注 符号串中符号的顺序是重要的 例1 V a b c 符号串 a b c ab ba cc aab 其中 ab ba例2 单词符号集 if then begin 标识符 程序 由上述符号构成的一个符号串但 任一符号串不一定是合法的程序 编译研究 什么样的符号串是合法的程序 4 串的长度 设 是字母表V中的符号串 的长度 中符号的个数 记为 5 串的联结 设 是字母表V中的符号串 联结 是指 将 放在 之后形成的符号串 记为 例 V a b c 且有 ab bca则 abbca bcaab 2 5特别 0 6 符号串集合 由符号串构成的集合 记为 A x x A 7 符号串集合的乘积 若A B是V上的符号串集合 A B的乘积定义为 AB A B 例 若 A ab ba B ca acb 则 AB abca abacb baca baacb A A A 8 符号串的方幂 对任意符号串 0 1 2 n n 1 n 0 例 ab则 0 1 ab 2 abab 3 ababab 例 V a b c V0 长度 0的符号串的集合V1 a b c 长度 1的符号串的集合V2 aa ab ac ba bb bc ca cb cc 长度 2的符号串的集合V3 aaa aab aac aba abb abc 长度 3的符号串的集合V100长度 100的符号串的集合Vn长度 n的符号串的集合 9 集合V的方幂 对任意集合V V0 V1 V V2 VV V3 VVV Vn VVn 1 n 0 10 集合的闭包 设V为集合 V V1 V2 V3 Vn 正闭包V V0 V1 V2 V3 Vn 闭包两种闭包之间的关系 V V0 V V VV V V 两个集合的乘积 2 3上下文无关文法 1 产生式 产生规则 简称规则 一个有序对 A 通常写作 A 或A A 符号 称为产生式左部 符号串 称为 产生式右部 或 产生式的候选式 产生式的书写方式称为 BNF范式若有产生式 A 1A 2 A n写成 A 1 2 n 候选式 2 文法G S 产生式的非空有穷集合 S是一个符号 它至少要在一条产生式中作为左部出现 称为识别符号或开始符号 出现在产生式左部和右部中的所有符号形成字母表V 例 G E E E T TT T F FF i E V E T F i 产生式 识别符号或开始符号 3 非终结符号 给定文法G 把作为产生式左部出现的那些符号称为非终结符号 或语法实体 所有非终结符号汇集成 非终结符号集 记为 VN 例 G E E E T TT T F FF i E V E T F i VN E T F 左部 4 终结符号 给定文法G 产生式中不属于VN的那些符号称为终结符号 所有终结符号汇集成 终结符号集 记为 VT 由定义知 V VN VT VN VT 例 G E E E T TT T F FF i E V E T F i VN E T F VT i 5 上下文无关文法的形式定义 上下文无关文法是一个四元组G S VN VT P S 其中 VN 非终结符号集合VT 终结符号集合P 产生式集合S 文法的识别符号 开始符号 6 直接推导 直接归约 令G为文法 为符号串 若 A 是一个产生式 称 A 直接推导出 或 直接归约为 A 记为 A 例 G E E E E E E E E E i推导 E E E E E E E E E i E E i i E i E E E i E i i E i 7 推导 归约 若存在一个直接推导序列 1 2 3 n称 1可以出推导 n 或 n可归约为 1记为 1 n 推导步骤 0步 读作 号推导出 或 即 例 G E E E E E E E E E i从E E到i i i的几种可能推导 E E E E E i E E i i E i i iE E E i E E i E i i i i iE E E E E E E i E i i i i iE E E E E E i E E i i i i i 8 最左推导 最右推导 推导中若每一步直接推导 替换的都是符号串的最左非终结符 称为最左推导 替换的都是符号串的最右非终结符 称为最右推导 说明 例 G E E E E E E E E E iE E E E E E i E E i i E i i i 只要符号串中有产生式的左部符号 就能从该符号串推导出新的符号串 即 推导过程未结束 非终结 所以左部符号称为非终结符号Non terminalsymbol符号串中没有产生式的左部符号了 那么推导过程就必须终结 所以不在产生式的左部出现的符号称为终结符号Terminalsymbol故 非终结符集 VN终结符集 VT 9 句型 句子 令G S 为一文法 如果符号串 是由文法的开始符号推导出来的 即 S 则称 是句型 若S 且 VT 则称 是句子 即 仅由终结符号构成的句型称为句子 例 G E E E E E E E E E iE E E E E E i E E i i E i i i句型 E E E E E E i E E i i E i i i句子 i i i 例 G1 E E E E E E E E E iL G1 E 带有 扩号等运算的算术表达式 说明 句型集 VN VT 即 句型集是符号串集的子集L G S VT 即 语言是终结符号串集的子集句子是由文法决定的 不同的文法可以产生相同的语言 即 G1 S G2 S 但L G1 S L G2 S 则称文法G1 S G2 S 等价 G1 E G2 E 但L G1 E L G2 E 称 文法G1 E G2 E 等价 即 不同的文法 可以产生相同的语言 例 G1 E E E E E E E E E iL G1 E 带有 扩号等运算的算术表达式 G2 E E E T E T TT T F FF E iL G2 E 带有 扩号等运算的算术表达式 例 G S S bAA aA a句子 S bA baS bA baA baaS bA baA baaA baaa S bA baA baaA baa aA baa a L G S ban n 1 例 G S S PQP aPb abQ Qc 句子 S PQ abQ abS PQ aPbQ aaPbbQ a ab bS PQ a ab bQc a ab bc c L G S anbncm n 1 m 0 2 4语法树和二义性 1 语法树 用图表示一个句型的推导过程 通常表示成一棵倒立的树 树根表示文法开始符号 S A a1a2a3 an 若有直接推导 A a1a2 an 则从结点A出发 划出n个分支 指向n个结点 a1 a2 an 语法树末端结点 再没有分支从中向下射出的结点 从左向右遍历语法树末端结点 形成该树表示的句型 例 G E E E T TT T F FF i E i i i推导过程 E E T T T T F T F F T i F T i i T i i F i i i末端结点 i i i语法树对应的句型 i i i 2 子树 由语法树的某个结点 子树根 连同从它向下射出的部分组成的 子树的末端结点形成一个短语 相对于子树根 子树 i1 F2 i1 T3 i2 F1 i1 i2 T2 i1 i2 E2 i3 F3 i3 T1 i1 i2 i3 E1 总结 例 G E E E T TT T F FF i E 句型 T F F推导1 E E T T T T T F T F F推导2 E E T E T F E F F T F F推导3 E E T E T F T T F T F F 对于每个语法树 至少存在一个推导 对于每个推导 都有一个对应的语法树 若不同的推导产生相同的语法树 称这些推导是等价的 3 二义性 句子的二义性 若文法G中 某一个句子有两棵不同的语法树 称该句子是二义的 例 G E E E E E E E E E i句子 i i i如 2 3 4 语法树1 2 3 4 20 2 3 4 14 语法树2 句子二义性的等价定义若文法G中 某一个句子存在两个不同的最左推导 称该句子是二义的 若文法G中 某一个句子存在两个不同的最右推导 称该句子是二义的 例 G E E E E E E E E E i句子 i i 最左推导 E E E i E i i最右推导 E E E E i i i 误解 有两个不同的推导 就是二义的句子 文法的二义性 如果一个文法包含有一个二义性的句子 称该文法是二义的 说明 文法的二义性是由句子决定的 不是由句型决定的 例 G E E T iT T T T T存在句型 T T T 对应两棵语法树 语法树1 但 该文法只有一个句子 i 文法是无二义的 语法树2 文法的二义问题 不可判定的 即 不存在一种算法 能在有限的步骤内判定文法二义 原因 句子是无限的 判定了N个句子无二义 可能第N 1个句子就是二义的 目前的做法 找一组充分条件 满足条件的文法就是无二义的 如 算符优先文法就是无二义文法 语言的二义性 一般不提判定标准 原因 一个语言可能由多个等价的文法定义 即 G1 S G2 S 但可能 L G1 S L G2 S 对一个语言 可能存在无二