• /  44
  • 下载费用: 14.90积分  

高级语言及其语法描述21

'高级语言及其语法描述21'
第2章 高级语言及其语法描述2.1 编译程序需要重点考虑的程序语言特性2.2 符号和符号串2.3 上下文无关文法2.4 语法树和二义性2.5 形式语言介绍§2.1 编译程序需要重点考虑的程序语言特性 高级语言之间的差异也是在这里体现的。 1. 标识符与名字 ? 标识符:字母打头的字母数字串。 ? 名字:用标识符表示的,带有类型、值域的 程序语言对象。 例: aa —— 标识符 real aa —— 名字,实型变量, 值域、运算确定。 2. 名字的定义 类型 名字定义方式 典型语言显式定义 名字的类型必须定义 C, Pascal 名字的类型可以定义或者不定义,未定 FORTRAN隐式定义 义的名字的类型按照缺省定义处理。 (I-N规则) 名字的类型不必定义。根据运行时名 早期的BASIC, 不定义 字的取值动态确定。 VFP 影响 -- 目标程序的执行效率的高低。 ⑴ 能否静态分配存储空间; ⑵ 能否作静态语义检查 例: int aa aa=12.3; 类型错误(静态语义检查) 3.变量的作用域? 全程变量:主程序中定义。? 局部变量:过程/函数/分程序/对象 中定义。影响: Ø 存储空间能否复用。 Ø 变量重名时的实现方法。 如:采用最小作用域原则。 4.语义 同一语句,在不同的语言中的含义可能不同。例:数组 A[1..3,1..4],访问: A[2,3] Pascal:按行分配 FORTRAN:按列分配 a11 a12 a13 a14 1 a11 a12 a13 a14 a21 a22 a23 a24 2 a21 a22 a23 a24 a31 a32 a33 a34 a31 a32 a33 a34 3 1 2 3 4 访问: a23地址=a11地址+6 a23地址=a11地址+75.支持的数据类型,类型中允许的运算 ? 基本数据类型: 整型,实型,布尔,字符,字符串 … ? 复杂数据类型: 数组,记录,结构,指针,集合,类 …6.支持的语句 分支、循环、过程、函数…7. 存储空间分配方式? 静态存储分配? 动态存储分配 Ø 函数:允许递归调用时,每一次调用 需要一片数据区 Ø 动态数组 Ø 动态创建对象 Ø 用户可动态申请/释放数据空间 §2.2 符号和符号串 1.字母表: 元素的非空、有穷集合。 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{ε} = A8.符号串的方幂: 对任意符号串α, α0 =ε α1 =α α2 =αα … αn =ααn-1 (n>0) 例: α=ab 0 1 则:α =ε, α =ab , 2 3 α = abab , α = ababab9. 集合V的方幂:对任意集合V, 0 1 2 3 V ={ε} , V = V , V = V V , V = V V V n n-1 … V = V V (n>0) 例: V={a,b,c} 0V ={ε} 长度=0 的符号串的集合 1V ={a,b,c} 长度=1 的符号串的集合 2V ={aa,ab,ac,ba,bb,bc,ca,cb,cc}长度=2 的符号串的集合 3V ={aaa,aab,aac,aba,abb,abc…}长度=3 的符号串的集合 100V 长度=100 的符号串的集合 nV 长度=n 的符号串的集合10. 集合的闭包: 设V为集合, V+ = V1 ∪ V2 ∪ V3 …∪ Vn ∪… 正闭包 V* = V0 ∪ V1 ∪ V2 ∪ V3 … ∪ Vn ∪ … 闭包 两种闭包之间的关系: V* = V0 ∪ V+ V+ = V V* = V* V —— 两个集合的乘积§2.3 上下文无关文法 1.产生式(产生规则,简称规则): 一个有序对(A,α),通常写作: A∷=α  或 A→α A:符号,称为产生式左部; α:符号串,称为:产生式右部, 或:产生式的候选式产生式的书写方式称为:BNF范式 若有产生式: A→α1 A→α2 … A→αn 写成:A→α1|α2| … |αn 元符号 → :定义为 候选式 | :或2. 文法G[S]: 产生式的非空有穷集合,S是一个符号,它 至少要在一条产生式中作为左部出现,称为 识别符号或开始符号,出现在产生式左部 和右部中的所有符号形成字母表 V。 例: G[E] 识别符号或开始符号 E → E + T | T T → T * F | F 产生式 F → i | (E) V ={ E , + , T, *, F, i, ( , ) }3. 非终结符号:给定文法G,把作为产生式左部出现的那些符号称为非终结符号,或语法实体,所有非终结符号汇集成:非终结符号集,记为:VN 。 例: G[E] E → E + T | T 左 部 T → T * F | F F → 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 | T T → T * F | F F → 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步,读作:+号推导出) α β,表示推导步骤≥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 + i8. 最左推导、最右推导:推导中若每一步直接推导, 替换的都是符号串的最左非终结符,称为最左推导; 替换的都是符号串的最右非终结符,称为最右推导。说明:例: G[E]: E → E + E | E – E | E * E | (E) | i E =〉E + E =〉E * E + E =〉i * E + E =〉i * i + E =〉i * i + iØ 只要符号串中有产生式的左部符号,就能从该符号串 推导出新的符号串,即:推导过程未结束(非终结), 所以左部符号称为非终结符号 Non-terminal symbolØ 符号串中没有产生式的左部符号了,那么推导过程就 必须终结。所以不在产生式的左部出现的符号称为 终结符号 Terminal symbol 故:非终结符集 —— VN 终结符集 —— VT 9. 句型、句子: Ø 令G[S]为一文法,如果符号串α是由文法的开始 符号推导出来的,即:S α,则称α是句型。 * Ø 若 S α,且 α∈VT , 则称α是句子。 (即:仅由终结符号构成的句型称为句子)例: G[E]: E → E + E | E–E | E * E |(E)| i E => 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 + i10. 语言: 令G[S]为一文法,G 所产生的句子的全体是 一个语言。记为:L(G), * L(G[S]) ={α| S α ,且α∈VT }例: G1[E]: E → E + E | E – E | E * E | (E) | i L(G1[E]) = {带有+、-、*、扩号等运算的 算术表达式 }说明: * Ø 句型集 (VN∪VT) , ∩ 即:句型集是符号串集的子集 *Ø L(G[S]) VT , ∩ 即:语言是终结符号串集的子集Ø 句子是由文法决定的。Ø 不同的文法可以产生相同的语言, 即:G1[S]≠G2[S] ,但 L(G1[S])=L(G2[S]) 则称文法 G1[S]、G2[S] 等价。例: G1[E]: E → E + E | E – E | E * E | (E) | i L(G1[E])={带有+、-、*、扩号等运算的算术表达式 } G2[E]: E → E + T | E – T | T T → T * F | F F → (E) | iL(G2[E])={ 带有+、-、*、扩号等运算的算术表达式 } G1[E]≠G2[E],但 L(G1[E]) = L(G2[E]) 称:文法 G1[E]、G2[E] 等价。 即:不同的文法,可以产生相同的语言。例: G[S]: S →bA A → aA|a句子: S => bA=> ba S => bA => baA => baa S => bA => baA => baaA => baaa …… S => bA => baA =>baaA =>… => baa…aA => baa…a ∴ L(G[S]) = { ban | n≥1 }例: G[S]: S → PQ P → aPb| ab Q → Qc|ε句子: S => PQ => abQ => ab S => PQ => aPbQ => aaPbbQ =+=> a…ab…b S => PQ=+=> a…ab…bQc =+=> a…ab…bc…c ∴ L(G[S]) = {anbncm | n≥1, m≥0 }§2.4 语法树和二义性1.语法树: 用图表示一个句型的推导过程。通常表示 成一棵倒立的树。树根表示文法开始符号; S 若有直接推导: …… …… αAβ=>αa1a2…anβ, α A β 则从结点A出发,划出n个分支, a1 a2 a3 … an 指向n个结点:a1 ,a2 ,… an语法树末端结点:再没有分支从中向下射出的结点。从左向右遍历语法树末端结点,形成该树表示的句型。例: G[E]: E → E + T | T T → T * F | F F → i |(E) E i*i+i 推导过程: E + T E => E + T => T + T => T * F + T T F => F * F + T => i * F + T T * F => i * i + T => i * i + F i => i * i + i F i 末端结点:i、*、i、+、i i 语法树对应的句型:i*i+i2.子树:由语法树的某个结点(子树根),连 同从它向下射出的部分组成的。子树的末端结点形成一个短语(相对于子树根). 子树: E1i1 (F2) ,i1 (T3) , E2 + T1i2 (F1) , T2 F3i1 * i2 (T2) ,i1 * i2 (E2) , T3 F1 * i3i3 (F3) ,i3 (T1) , F2 i2i1 * i2 + i3 (E1) i1总结:Ø 对于每个语法树,至少存在一个推导; Ø 对于每个推导,都有一个对应的语法树; Ø 若不同的推导产生相同的语法树,称这些 推导是等价的; E例: G[E]: E → E + T | T T → T * F | F E + T F → i |(E) T T * F 句型:T + F * 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 * F3.二义性: ? 句子的二义性:若文法G中,某一个句子有 两棵不同的语法树,称该句子是二义的。 例: G[E]: E → E + E | E – E | E * E | (E) | i 句子: i + i * i 如:2 + 3 * 4 语 E1 语 E1 法 法 树 E2 + E3 树 E2 * E3 1 2 i1 E4 * E5 E4 + E5 i3 i2 i3 i1 i2 2 +( 3 * 4)= 14 ( 2 + 3)* 4 = 20句子二义性的等价定义? 若文法G中,某一个句子存在两个不同的最左 推导,称该句子是二义的。? 若文法G中,某一个句子存在两个不同的最右 推导,称该句子是二义的。 例: G[E]: E → E + E | E – E | E * E | (E) | i 句子: i + i 语 E1 最左推导:E=>E+E=>i+E=>i+i 法 E2 + E3 最右推导:E=>E+E=>E+i=>i+i 树 i1 i2 误解:有两个不同的推导,就是二义的句子? 文法的二义性:如果一个文法包含有一个二 义性的句子,称该文法是二义的。 例: G[E]: E → E + E | E – E | E * E | (E) | i 存在句子: i + i * i, 有两颗不同的语法树 语 E1 语 E1 法 法 树 E2 + E3 树 E2 * E3 1 2 i1 E4 * E5 E4 + E5 i3 i2 i3 i1 i2 所以:文法G[E]是二义的说明:文法的二义性是由句子决定的, 不是由句型决定的。 例: G[E]: E →T | i T → T + T | T * T 存在句型:T+T*T ,对应两棵语法树 语 E 语 E 法 T 法 T 树 树 1 T + T 2 T * T T * T T + T但:该文法只有一个句子:i ∴文法是无二义的。文法的二义问题 —— 不可判定的。即:不存在一种算法,能在有限的步骤内判定 文法二义。原因:句子是无限的,判定了N个句子无二义, 可能第 N+1 个句子就是二义的。目前的做法:找一组充分条件,满足条件的文 法就是无二义的。(如:算符优先文法就是 无二义文法)? 语言的二义性:一般不提判定标准。 原因: 一个语言可能由多个等价的文法 定义。 即:G1[S]≠G2[S] , 但可能:L(G1[S]) = L(G2[S]) ∴ 对一个语言,可能存在无二义文法描述之。 若一个语言不存在无二义文法,称该语言为: 先天二义性的。 形式语言介绍 —— 乔姆斯基谱系 刻画形式文法表达能力的一个分类谱系, 它包括四个层次: ∩ ∩ ∩ 0型文法 1型文法 2型文法 3型文法文法 语言 自动机 限制 描述能力 0型 递归可枚举 图灵机 线性有界非确定图 1型 上下文相关 灵机 2型 上下文无关 非确定下推自动机 3型 正规语言 有限状态自动机 强 弱 文法特征: * 令:α、β∈(VN∪VT) , A、B ∈VN 文法 产生式 0-型 α→β, 且α中含有VN 1-型 α→β, 且:|α|≤|β| 2-型 A→β A→aB 或 A→a (右线性文法) 3-型 A→Ba 或 A→a (左线性文法)对描述程序语言的上下文无关文法,做如下限 制:⑴ 不含形如: P→P 的产生式⑵ 每个非终结符 P 必须都有用处,要求: ? S αPβ (P必须出现在某句型中) * ? P π,π∈VT (对P的推导一定可以终结)上述限制后的上下文无关文法,称为:化简的上下文无关文法。作业: P35 第 3, 7, 8, 9, 11 题第2章 高级语言及其语法描述2.1 编译程序需要重点考虑的程序语言特性2.2 符号和符号串2.3 上下文无关文法2.4 语法树和二义性2.5 形式语言介绍§2.1 编译程序需要重点考虑的程序语言特性 高级语言之间的差异也是在这里体现的。 1. 标识符与名字 ? 标识符:字母打头的字母数字串。 ? 名字:用标识符表示的,带有类型、值域的 程序语言对象。 例: aa —— 标识符 real aa —— 名字,实型变量, 值域、运算确定。 2. 名字的定义 类型 名字定义方式 典型语言显式定义 名字的类型必须定义 C, Pascal 名字的类型可以定义或者不定义,未定 FORTRAN隐式定义 义的名字的类型按照缺省定义处理。 (I-N规则) 名字的类型不必定义。根据运行时名 早期的BASIC, 不定义 字的取值动态确定。 VFP 影响 -- 目标程序的执行效率的高低。 ⑴ 能否静态分配存储空间; ⑵ 能否作静态语义检查 例: int aa aa=12.3; 类型错误(静态语义检查) 3.变量的作用域? 全程变量:主程序中定义。? 局部变量:过程/函数/分程序/对象 中定义。影响: Ø 存储空间能否复用。 Ø 变量重名时的实现方法。 如:采用最小作用域原则。 4.语义 同一语句,在不同的语言中的含义可能不同。例:数组 A[1..3,1..4],访问: A[2,3] Pascal:按行分配 FORTRAN:按列分配 a11 a12 a13 a14 1 a11 a12 a13 a14 a21 a22 a23 a24 2 a21 a22 a23 a24 a31 a32 a33 a34 a31 a32 a33 a34 3 1 2 3 4 访问: a23地址=a11地址+6 a23地址=a11地址+75.支持的数据类型,类型中允许的运算 ? 基本数据类型: 整型,实型,布尔,字符,字符串 … ? 复杂数据类型: 数组,记录,结构,指针,集合,类 …6.支持的语句 分支、循环、过程、函数…7. 存储空间分配方式? 静态存储分配? 动态存储分配 Ø 函数:允许递归调用时,每一次调用 需要一片数据区 Ø 动态数组 Ø 动态创建对象 Ø 用户可动态申请/释放数据空间 §2.2 符号和符号串 1.字母表: 元素的非空、有穷集合。 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{ε} = A8.符号串的方幂: 对任意符号串α, α0 =ε α1 =α α2 =αα … αn =ααn-1 (n>0) 例: α=ab 0 1 则:α =ε, α =ab , 2 3 α = abab , α = ababab9. 集合V的方幂:对任意集合V, 0 1 2 3 V ={ε} , V = V , V = V V , V = V V V n n-1 … V = V V (n>0) 例: V={a,b,c} 0V ={ε} 长度=0 的符号串的集合 1V ={a,b,c} 长度=1 的符号串的集合 2V ={aa,ab,ac,ba,bb,bc,ca,cb,cc}长度=2 的符号串的集合 3V ={aaa,aab,aac,aba,abb,abc…}长度=3 的符号串的集合 100V 长度=100 的符号串的集合 nV 长度=n 的符号串的集合10. 集合的闭包: 设V为集合, V+ = V1 ∪ V2 ∪ V3 …∪ Vn ∪… 正闭包 V* = V0 ∪ V1 ∪ V2 ∪ V3 … ∪ Vn ∪ … 闭包 两种闭包之间的关系: V* = V0 ∪ V+ V+ = V V* = V* V —— 两个集合的乘积§2.3 上下文无关文法 1.产生式(产生规则,简称规则): 一个有序对(A,α),通常写作: A∷=α  或 A→α A:符号,称为产生式左部; α:符号串,称为:产生式右部, 或:产生式的候选式产生式的书写方式称为:BNF范式 若有产生式: A→α1 A→α2 … A→αn 写成:A→α1|α2| … |αn 元符号 → :定义为 候选式 | :或2. 文法G[S]: 产生式的非空有穷集合
关 键 词:
高级语言及其语法描述21 ppt、pptx格式 免费阅读 下载 天天文库
 天天文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:高级语言及其语法描述21
链接地址: https://www.wenku365.com/p-39814218.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服点击这里,给天天文库发消息,QQ:1290478887 - 联系我们

本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】。本站是网络服务平台方,若您的权利被侵害,侵权客服QQ:1290478887 欢迎举报。

1290478887@qq.com 2017-2027 https://www.wenku365.com 网站版权所有

粤ICP备19057495号 

收起
展开