1、2.形式语言基本知识,编译原理实践,在讨论编译技术之前,编译过程的核心就是翻译，这是一个十分复杂的信息加工过程，其加工的对象是用某种高级语言编写的程序。对于一个英文翻译来说，首先必须对英文有很深的了解，掌握英文的语法和词汇，才能进行翻译。编译程序的任务就是将高级语言编写的程序翻译成机器语言程序，因此，在学习和掌握编译技术之前，就需要对高级语言有深刻的了解。,形式语言,首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能
2、用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言 。,形式语言基本知识,形式语言的特征形式语言的归纳定义文法的分类EBNF描述符,1 .形式语言的特征,“自然”形成的语言-自然语言，如汉语人为形式化定义的语言形式语言形式语言的特征1)一个词汇表，即基本符号集2)一组语法规则，可用语法图或EBNF表示3)在语法规则里有起始符号、终结符号和非终结符号4)语言必须由词汇表里的词汇按照语法规则书写出来,2 .形式语言的归纳定义,1.语言可以用L(T、N、P、S)四元组表示2.语言L(T、N、P、S)是终结符串的集合,终结符串都
3、从起始符S开始，并遵循下面两条推演规则推演出来。3.符号串 可以从符号串 推演出来的条件是：仅当存在符号串 ，且每一个 可以直接从 推演出来。4.从一个符号串 可以直接推演出一个符号串 的条件是，仅当 和 可以分别表示为：且 是集合P的一个生成规则。,3 .文法的分类,0型文法对文法的生成规则没有任何限制。在计算机语言应用中很少见1型文法（上下文有关文法）在推导过程中，要依据上下文才能作相应替换。实际程序设计语言可能包含这种上下文有关的成分，但不是主要的2型文法（上下文无关文法）是描述程序设计语言语法部分的主要文法3型文法（正则文法）高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3
4、型文法来描述的,四类文法之间的逐级“包含”关系,0型文法,3型文法,4 .EBNF(扩充BNF)描述符,BNF表示的整数生成规则:=|-|+ :=| 例：EBNF表示的整数生成规则integer=“+”|”-”digitdigit.EBNF表示式比BNF要清晰、简单得多,3.语句分析,编译原理实践,语句分析,语句分析概述自顶向下和自底向上简单辨认算法对文法的限制规则1对文法的限制规则2,1.语句分析概述,语句：能够从文法的起始符号出发推导出来的终结符号串；也称作句子语句分析，亦被称作句型分析、语法分析，是指语句辨认，或者语句识别。编译程序在阅读一个句子时进行的是辨认的过程，辨认一个语句是否属于
5、文法确定的语言,语句分析是编译过程的核心部分，它的主要任务是按照程序语言的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行语法检查，为语义分析和代码生成作准备。执行语句分析任务的程序叫语法分析程序或语法分析器。,语法分析程序以词法分析输出的符号串作为输入，在分析过程中检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树；若不是，则表示源程序存在语法错误，需要报告错误的性质和位置。例如，对于C程序语句“IF (a10) b=5；”，词法分析识别出了IF、(、标识符、等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确。IF后面是否为(，(后面是否为正确的
6、表达式等等。,2.自顶向下和自底向上,自顶向下：1)自起始符开始自顶向下建树，试图生成一个和所给符号串相一致的终结符号串2)在建树过程中，依照一定规律选择生成规则，展开为向下生长的树叶。每一步都试图将生成的尚未消除的最左叶片与输入符号匹配3)匹配失败后回溯4)如果按上述方法构造成功，则说明读入的符号串是文法的一个句子，反之不是文法的一个句子。,自底向上：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串，重复此过程，步步向上规约，最后设法将符号串x规约到文法的起始符号Z。本课程对自底向上不做进一步讨论,自顶向下的语法分析的一般过程,例：文法G： S cA
7、d A ab A a识别输入串w=cabd是否为该文法的句子,SSScAdcAd a b推导过程：S cAd cAd cabd,(1)S cAd (2) A ab (3) A a,识别输入串w=cad是否为该文法的句子1.S cAd 2.后选择(2)扩展A，得到推导S cAd cabd这时 w的第二个符号可以与叶子结点a得以匹配，但第三个符号d却不能与下一叶子结点b匹配怎么办？-查看A有无另一个选择，有！回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）构造推导S cAd cad,识别输入串w=caa的过程： 1.S cAd2.选择(2)扩展A，得到推导S cAd ca
8、bd3.回溯回到推导S cAd 4.选择(3)扩展A，得到推导S cAd cad5. A没有选择了！回溯到推导S cAd 6.再回溯S有无另一个选择？没有！ 宣告分析失败。,自上而下的语法分析面临的问题,问题一：回溯Backtracking编译器效率严重低下，一般都在指数的数量级上，只有理论上的意义而无实际意义问题二：文法的左递归性例：SSa可能陷入无限循环如何解决？,3.简单辨认算法,简单辨认算法（LL(1)分析法）：采用自顶向下的分析方法，语句分析的每个步骤仅允许由当时的分析状态（追踪的目标）和下一个要读入的符号决定，不允许有回溯的步骤。LL(1) ：第一个L是指对输入符号串的分析总是自左
9、(left)向右，第二个L是指对生成式目标的追踪也是自左(left)向右，括号中的1是指不论目标符号的追踪，还是对终结符号的读入都只是一个符号，从而决定生成规则的选择。,4.对文法的限制规则1,定义1：从一个符号串 推导出来的每一个符号串头一个终结符号的集合，定义为始端符集合，记为限制规则1：对每一个形如这样的生成规则 要求每一个 的始端符集合彼此必须是相异的。即：,5.对文法的限制规则2,定义2：能够直接跟随在非终结符A之后所有终结符号的集合，定义为A的跟随符集合，记为 ，定义3：对每一个形如的生成规则如果某 是空串或能导出空串，则限制规则2：对一个能够推导出空符号串的非终结符A，它的始端符集合必须与它的跟随符集合相异。,6.如何构造等价的LL(1)文法,消除左递归提取公因子在绝大多数情况下，它们都十分有用，并且具有可自动操作其应用程序的优点,4.语法图,编译原理实践,从EBNF表示式到语法图的转换语法图转换实例从语法图判断两条限制规则,1.从EBNF表示式到语法图的转换,2.语法图转换实例,归纳后的语法图,A,(,A,),A,+,x,3.从语法图判断两条限制规则,找出图中每一个分支点，考察每一个分支点的分支的头符号是否相异找出图中每一个透明结构，考察每一个透明结构的头符号集合和其跟随符号集合是否相异。,
