《编译原理》第章文法和语言的形式定义.pdf

编译原理 武汉大学计算机学院 编译原理课程组 前述内容回顾 · 编译程序 · 编译方式与解释方式的根本区别 · 编译程序的工作过程 · 编译程序的结构 · 编译程序的组织方式 · 编译程序的构造 本章内容简介 · 文法的形式定义 · 语言的形式定义 · 为语言构造文法 · 和语法分析有关的概念 · 文法的实用限制 第2 章文法和语言的形式定义 编译程序使得高级语言源程序所描述的功能得以在计算 机上实现。编译程序的设计者就是高级语言的实现者，源程 序的编写者就是高级语言的使用者，他们必须遵循同样的准 则—— 高级语言程序的构成规则，才能使写出的源程序能够 被成功地翻译，文法就是描述的就是高级语言程序的构成规 则。 2.1 字母表与符号串 1.1 字母表 字母表是元素的有穷非空的集合。 字母表中的元素称为符号。 例如{a，b，……，y，z}，{0，1}等。 2.1 字母表与符号串 1.2 符号串与符号串集合 符号串是字母表中的符号所组成的任何有穷序列，通常用小 写的字母表示。不包含任何符号的符号串为空串，记为ε。 ①符号串的长度 ②符号串的连接 ③符号串集合的乘积 ④符号串的方幂 ⑤符号串集合的方幂 ⑥符号串集合的正闭包A+ ⑦符号串集合的闭包A* 2.2 文法及其分类 2.2.1 文法 1．终结符号 ： 终结符号是组成语言的基本符号，如保留字、标识符、常数、 运算符、界限符等。终结符号是语言的不可再分的基本符号。终 结符号形成的集合记为V 。 T 2．非终结符号 ： 非终结符号用来表示语言的语法成分（或语法范畴、语法单 位），例如“赋值语句”。非终结符号所形成的集合记为V 。 N V ∩V =∅ T N 2.2文法及其分类 3．产生式 产生式（规则）是一个有序对（α,β），通常写作 ： α→β（或α∷=β） + 其中α称为产生式的左部，β称为产生式的右部。α∈(V ∪V) ， T N * β∈(V ∪V) 。 T N 产生式是用来定义一个语法成分的。它描述了一个语法成分 的形成规则。例如标识符的构成规则可描述为： 标识符→字母|标识符字母|标识符数字 假如有若干条规则有相同的左部，通常写作： α→β |β |… |β 1 2 n 2.2文法及其分类 文法是产生式的有穷非空的集合。 文法G是一个四元组，G[S]=（V ，V ，P，S）。 T N V ——终结符号集。 T V ——非终结符号集。