复习程序语言语法描述.ppt

《复习程序语言语法描述.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、复习：程序语言的语法描述几个概念:考虑一个有穷字母表∑字符集其中每一个元素称为一个字符∑上的字(也叫字符串)是指由∑中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为ε用∑*表示∑上的所有字的全体,包含空字ε复习：程序语言的语法描述∑*的子集U和V的连接（积）定义为UV＝{

2、U&V}V自身的n次积记为Vn=VV…V规定V0={}，令V*=V0∪V1∪V2∪V3∪…称V*是V的闭包;记V＋＝VV*，称V+是V的正规闭包。复习：程序语言的语法描述上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合

3、(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。复习：程序语言的语法描述定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。通常，用表示：从1出发，经过一步或若干步，可以推出n。用表示：从1出发，经过0步或若干步，可以推出n。所以：即或定义：假定G是一个文法，S是它的开始符号。如果，则称是一个

4、句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。复习：程序语言的语法描述最左推导：任何一步都是对中的最左非终结符进行替换。最右推导：任何一步都是对中的最右非终结符进行替换。复习：程序语言的语法描述用一张图表示一个句型的推导,称为语法树。E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)(E+E)(E+i)(E*E+i)(E*i+i)(i*i+i)复习：程序语言的语法描述定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。语言的二义性：一个语言是二义性的，如果对

5、它不存在无二义性的文法。复习：程序语言的语法描述形式语言鸟瞰0型(短语文法，图灵机)：产生式形如：其中：(VTVN)*且至少含有一个非终结符；(VTVN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：

6、

7、

8、

9、，仅S例外。复习：程序语言的语法描述形式语言鸟瞰2型(上下文无关文法，非确定下推自动机)：产生式形如：A其中：AVN；(VTVN)*。3型(正规文法，有限自动机)：产生式形如：AB或A其中：VT*；A，BVN产生式形如：AB或A其中：VT*；A，BVN第3章　词法分析本章介绍编译第一个阶段词法分析的设计

10、原理和设计方法，要求明确此阶段的任务。理解通常的单词分类和构词规则。会使用单词的描述和识别机制。要求掌握正规文法、状态图、DFA、NFA、正规式和正规集的基本概念和它们之间的关系。掌握词法分析程序的手工实现方法。掌握词法分析程序的自动构造原理。教学目标3.1词法分析的任务3.2词法分析程序的输出形式3.3词法分析程序的设计与实现3.4正规式与有穷自动机3.5词法分析程序的自动生成工具LEX教学内容词法分析词法分析的任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号。词法分析器(LexicalAnalyzer)又称扫描器(Scanner)：执行词法分析的程序（1）分析和识别单词及属性，

11、包括识别语言的关键字、标识符、常数、运算符等；（2）跳过各种分隔符，如空格，回车，制表符等；（3）删除注释；（4）进行词法检查，报告所发现的错误；（5）建立符号表。词法分析的任务main()/*ADD*/{intx=10,y=20,sum;sum=x+y;}main、(、)、{、int、x、=、10、,、y、=、20、,、sum、;、sum、=、x、+、y、;、}词法分析单词的种类（1）关键字：if、for、while……（2）标识符：变量名、数组名……（3）常数：100，……（4）运算符：+、-、*（5）分界符：,、;、(、)词法分析程序的输出形式词法分析程序的输出形式-----二元式单词类

12、别单词的属性值单词类别可以用整数编码表示:一类一种或一字一种单词类别关键字标识符常数运算符分界符编码12345单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的