国防科大编译原理第二章.ppt

练习：根据以下mini语言的语法说明(部分)写出其文法 Mini语言的程序由语句块构成；语句块由一到多条语句构成， 语句用分号分隔； 语句分为赋值语句、条件语句和循环语句； 赋值语句左部为变量(用var表示)，右部为算术表达式，中间用 等号连接；算术表达式为整数常量(用int表示)或变量，或由 算术表达式通过加、减运算符连接而成；条件语句由if关键字后跟 左括号、条件表达式、右括号、then关键字、语句块、end关键字 构成；循环语句由while关键字后跟左括号、条件表达式、右括号、 语句块、end关键字构成； … 如：a=1; b=a+2; if (a0) then a=a+b-1; end; while (a0) a=a-1; b=b+1; end; 2.3.3 形式语言鸟瞰 形式化方式定义语言。 1、文法分类： 0型文法：短语文法 （ 0型语言——递归可枚举语言） 产生式形式: ?→?,??(VN?VT)*且至少含一个非终结符,??(VN?VT)* 1型文法：上下文有关文法 产生式形式： ?→?, ??(VN?VT)*且至少含一个非终结符, ??(VN?VT)*,S不能出现在产生式的右部,除S→?外， 其他? →?,|?|?|?| 例：?A?→?γ? 2型文法：上下文无关文法（足以定义大多数程序设计语言) 产生式形式： A→?,A?VN,??(VN?VT)*。 3型文法：正规文法 右线性文法： A→?B , 或A→? , A、B?VN,??VT* 左线性文法： A→B?,或A→? , A、B?VN,??VT* 2、文法和计算模型： 文法所描述的语言可以用与之能力相当的“计算机”所识别。 反之， “计算机” 所能计算出来的问题——或者说，所识别的 语言可以用与之能力相当的文法所描述。 文法类型 计算模型 0型文法 图灵机（RAM机） 1型文法 线性界限机 2型文法 下推自动机 3型文法 有限状态机 * 第二章:高级语言机器语法描述 2.1 程序语言的定义 2.2 高级语言的一般特性 2.3 程序语言的语法描述 2.1 程序语言的定义-关于语言的一些概念 语言＝语法＋语义+语用。 一、字母表和符号串 字母表：符号的非空有限集 例：?={a，b，c} 符号：字母表中的元素 例： a，b，c 符号串：符号的有穷序列 例：a, aa, ac, abc，.. 空符号串：无任何符号的符号串(ε) 符号串集合：由符号串构成的集合。 二、单词符号和词法规则 单词符号：语言中具有独立意义的最基本结构。 词法规则：单词符号的形成规则。 2.1.1 语法：一个程序设计语言是一个符号系统。 语言的词法规则和语法规则定义了程序的结构形式,是判断输入字符串是否构成一个形式上正确程序的依据。 三、语法单位和语法规则 语法单位：由单词符号形成的具有更大的独立语法意义结构。 如表达式:0.5*X1+C,一般的程序语言的语法单位有表达式、 语句、分程序、函数、过程和程序等。 语法规则：语法单位的形成规则。 2.1.2 语义 一、语义问题 语义定义一个语言单词符号和语法单位的意义。离开语义, 语言只不过是一堆符号的集合。对于编译来说,只有了解程 序的语义，我们才能知道把它翻译成什么样的目标指令代码。 二、语义规则和程序 语义规则：程序语言的语义是指这样一组规则，使用它可以 定义一个程序的意义，这些规则称为语义规则。 程序：从本质(语义)上说,一个程序是描述一定数据的处理过程。 (从语法上看)程序设计语言中的程序和其他语法单位形成 一定层次结构。 程序的语法/语义问题： 层次结构中有哪些语法单位，其语义如何？ --2.2节 如何描述这些语法单位？ --2.3节。 2.2 高级语言的一般特性 2.1.1 高级语言的分类： 一、强制式语言 过程式语言。特点是命令驱动，面向语句。如C、PASCAL等。 二、应用式语言 函数式语言。特点是注重程序功能,从已有函数出发构造新的函数， 构造新函数的过程中对初始数据进行计算得到最终结果。如LISP等。 三、基于规则的语言 逻辑程序设计语言。特点是规则驱动,从事实出发,运用逻辑规则, 推导出问题的结果。程序基本结构包括事实和规则两部份。如PROLOG等 四、面向对象语言 把数据和对数据的操作封装在一起,构成对象。支持封装性、 继承性和多态性。 本课程主要讲解过程式语言程序的编译，因此涉及的语法和语义以过