课程说明 Read.pptVIP

首先要了解如何确切地描述或定义一种程序设计语言，其次才能识别和分析这种语言。20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言 。 语法分析程序以词法分析输出的符号串作为输入，在分析过程中检查这个符号串是否为该程序语言的句子。若是，输出该句子的分析树；若不是，则表示源程序存在语法错误，需要报告错误的性质和位置。例如，对于C程序语句“IF (a10) b=5；”，词法分析识别出了IF、(、标识符、…等单词符号，而语法分析则要检查这些单词之间的搭配、结构是否正确。IF后面是否为(，(后面是否为正确的表达式等等。 自底向上：从所给符号串x开始，在其中寻找与文法的某条规则右部相匹配的子串，并用该规则的左部取代此子串，重复此过程，步步向上规约，最后设法将符号串x规约到文法的起始符号Z。 本课程对自底向上不做进一步讨论 自顶向下的语法分析的一般过程 例：文法G： S → cAd A → ab A → a识别输入串w=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 ? cAd 2.选择(2)扩展A，得到推导S ? cAd ? cabd 3.回溯回到推导S ? cAd 4.选择(3)扩展A，得到推导S ? cAd ? cad 5. A没有选择了！回溯到推导S ? cAd 6.再回溯S有无另一个选择？没有！ 宣告分析失败。 自上而下的语法分析面临的问题 问题一：回溯Backtracking ---〉编译器效率低下，一般都在指数的数量级上 问题二： 文法的左递归性 S→Sa ---〉可能陷入无限循环 怎么办？ 编译原理实践--语法图 从EBNF表示式到语法图的转换 语法图转换实例 从语法图判断两条限制规则 1.从EBNF表示式到语法图的转换 2.语法图转换实例 归纳后的语法图 3.从语法图判断两条限制规则 找出图中每一个分支点，考察每一个分支点的分支的头符号是否相异 找出图中每一个透明结构，考察每一个透明结构的头符号集合和其跟随符号集合是否相异。 编译原理实践--形式语言基本知识 编译过程的核心就是翻译，这是一个十分复杂的信息加工过程，其加工的对象是用某种高级语言编写的程序。对于一个英文翻译来说，首先必须对英文有很深的了解，掌握英文的语法和词汇，才能进行翻译。而编译程序的任务就是将高级语言编写的程序翻译成机器语言程序，因此，在学习和掌握编译技术之前，就需要对高级语言有深刻的了解。 形式语言基本知识 形式语言的特征 形式语言的归纳定义 文法的分类 EBNF描述符 1 形式语言的特征 “自然”形成的语言--自然语言，如汉语 人为形式化定义的语言—形式语言 形式语言的特征 1)一个词汇表，即基本符号集 2)一组语法规则，可用语法图或EBNF表示 3)在语法规则里有起始符号、终结符号和非终结符号 4)语言必须由词汇表里的词汇按照语法规则书写出来 1.语言可以用L(T、N、P、S)四元组表示 2.语言L(T、N、P、S)是终结符串的集合,终结符串都从起始符S开始，并遵循下面两条推演规则推演出来。 3.符号串 可以从符号串 推演出来的条件是：仅当存在符号串 ，且每一个 可以直接从 推演出来。 4.从一个符号串 可以直接推演出一个符号串 的条件是，仅当 和 可以分别表示为： 且 是集合P的一个生成规则。 2 形式语言的归纳定义 3 文法的分类 0型文法 对文法的生成规则没有任何限制。在计算机语言应用中很少见 1型文法（上下文有关文法） 在推导过程中，要依据上下文才能作相应替换。实际程序设计语言可能包含这种上下文有关的成分，但不是主要的 2型文法（上下文无关文法） 是描述程序设计语言语法部分的主要