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

第2章 高级语言及其语法描述;2.1 程序语言的语法和语义;“我是大学生”。是汉语的一个句子 用语法来描述：; 2 语义 定义程序的意义。 没有公认的形式系统描述语义。 ;3 高级语言的分类;2.3 程序语言的语法描述;二、符号串和符号串集合的运算 1.符号串相等：若x、y是集合上的两个符号串，则x＝y iff（当且仅当）组成x的每一个符号和组成y的每一个符号依次相等。 2.符号串的长度：x为符号串，其长度|x|等于组成该符 号串的符号个数。 例： x＝STV ， |x|=3 ;例：A＝{a,b},B={c,d}, AB= ？ ;6.符号串集合的闭包运算：设A是符号串集合，定义 A＋＝ A1 ∪ A2 ∪ A3 ∪……∪ An ∪…… 称为集合A的正则闭包。 A*＝ A0 ∪A＋ 称为集合A的闭包。; 为什么对符号、符号串、符号串集合以及它们的运算感兴趣？ 若A为某语言的基本字符集 A＝{a,b,……z,0,1,……,9, +,－,×,_/, ( , ), =……} B为单词集 B ={begin, end, if, then,else,for,……,标识符,常量,……} 则B ? A* 。 语言的句子是定义在B上的符号串。 若令C为句子集合，则C ? B * , 程序? C;三 文法的直观理解; 2.语法规则：我们通过建立一组规则（产生式），来描述句子 的语法结构。规定用“::=”表示“由……组成”。;由产生式推导句子：有了一组产生式之后，可以按照一定的 方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应产生式 的右部来替代产生式的左部，每次仅用一条产生式去进行推导。;句子 = 主语谓语;例：有一英语句子：The big elephant ate the peanut. 句子::=主语谓语 主语::=冠词形容词名词 冠词 ::=the 形容词::=big 名词::=elephant 谓语::=动词宾语 动词::=ate 宾语::=冠词名词 名词 ::=peanut;句子 = 主语谓语;上述推导可写成句子 = the big elephant ate the peanut; 4.语法???：我们用语法树来描述一个句子的语法结构。;1文法的定义;P = {无符号整数 → 数字串 ； 数字串 → 数字串 数字 ； 数字串 → 数字 ； 数字 →0； 数字 →1； ………… 数字 →9； } Z = 无符号整数；;几点说明：;2 推导与归约; 当符号串已没有非终结符号时，推导就必须终止。因为 终结符不可能出现在产生式左部，所以将在产生式左部出现的 符号称为非终结符号。; ＋ N==109;规范推导＝最右推导;3 语言的形式定义;例：{abna|n≥1},构造其文法 G1[Z]： Z→aBa, B→b|bB G2[Z]： Z→aBa, B→b|Bb;编译感兴趣的问题是:;4 文法分类; 文法和语言分类：0型、1型、2型、3型 这几类文法的差别在于对产生式施加不同的限制。;定义10： 1型文法： P： xUy → xuy 其中 U∈VN， x、y、u∈V*;定义11：2型文法： P： U → u 其中 U∈VN， u∈V*;（右线性） P： U → T 或 U → Tw 其中 U、w∈VN T∈VT;根据上述讨论，L0 L1 L2 L3 0型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。;5 语法树与二义性文法; 注意一个重要事实：文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法树的生成规律不同，但最终生成的语 法树形状完全相同。某些文法有此性质，而某些文法 不具此性质。; ;树与推导;P = {无符号整数 → 数字串 ； 数字串 → 数字串 数字 ； 数字串 → 数字 ； 数字 →0； 数字 →1； ………… 数字 →9； } Z = 无符号整数；;例：G[无符