编译原理 第2章-文法和语言.ppt

第二章文法和语言的基本知识
形式语言理论是编译的重要理论基础。本章主要介绍编译理论中用到的有关形式语言理论的最基本概念,重点介绍如何采用形式化的方法描述程序设计语言。
第二章文法和语言的基本知识
字母表和符号串
文法和语言的形式定义
短语、直接短语和句柄
语法树和文法的二义性
文法和语言的分类
概述
对程序设计语言的描述是从语法、语义和语用三个因素来考虑。
语法是对语言结构的定义。
语用则是从使用的角度去描述语言。
语义是描述了语言的含义。
概述
例如赋值语句s=2**r*(r+h)的
非形式化的描述为:
语法:赋值语句由一个变量,后随一个赋值号“=”,再在其后面跟一个表达式构成。
语义:首先计算语句右部表达式的值,然后把所得结果送给左部变量中。
语用:赋值语句可用来计算和保存表达式的值。
概述
这种非形式化的描述,不够清晰和准确,为了精确定义和描述程序设计语言,需采用形式化的方法。所谓形式化的方法,是用一整套带有严格规定的符号体系来描述问题的方法。
形式语言理论是编译的重要理论基础。重点介绍如何采用形式化的方法描述程序设计语言。
字母表和符号串
元素的非空有穷集合。
例如,∑={ a, b, c }
1. 字母表
根据字母表的定义,Σ是字母表,它由a、b、c三个元素组成。
字母表和符号串
是一个字母表,由0、1两个元素组成。
注意:
例如,∑' ={0, 1}
(2) 字母表中的元素, 可以是字母、数字或其他符号。
(1) 字母表中至少包含一个元素。
字母表和符号串
字母表中的元素称为符号或称为字符。
例如,前述例子中
2. 符号(字符)
a、b、c 是字母表Σ中的符号;
0、1 是字母表Σ'中的符号。
字母表和符号串
例如,设有字母表∑={ a, b, c }
符号的有穷序列称为符号串。
符号串总是建立在某个特定字母表上的且只由字母表上的有穷多个符号组成。
则有符号串 a,b,ab,ba, cba,
abc…
3. 符号串(字)
字母表和符号串
说明:
不包含任何符号的符号串, 称为空符号串,用ε表示。
符号串中符号的顺序是很重要的。
ab和ba是字母表Σ上的两个不同的符号串。
空符号串由0个符号组成,其长度|ε|=0