编译原理课件-Cha

《编译原理课件-Cha》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析—自上而下分析编译原理本章主要内容本章主要介绍语法分析的处理语法分析的任务自顶向下分析法四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器语法分析的任务语法分析程序以单词串形式的源程序作为输入或分析的对象。它的基本任务是：根据语言的语法规则，分析源程序的语法结构，即分析如何由这些单词组成各种语法范畴(如下标变量、各种表达式、各种语句、程序段或分程序，乃至整个源程序等等)，并在分析过程中，对源程序进行语法检查。作为语法分析程序的输出，可以有多种不同的形式。在下面的讨论中，

2、为简便起见，我们假定语法分析程序的输出，是用某种方法表示的语法树语法分析如何精确描述和刻画语言中的基本语法成分--如表达式、语句和函数？如何识别语法成分及语法错误并执行某些相关的处理动作？什么是语言自然语言(NaturalLanguage)是人与人的通讯工具语义(Semantics):环境、背景知识、语气、二义性——难以形式化计算机语言(ComputerLanguage)计算机系统间、人机间通讯工具严格的语法(Grammar)、语义(Semantics)——易于形式化：严格语言是用来交换信息的工具——功能性描述什么是语言语言单词(Token)：满足一定规则

3、字符(Character)串句子(Sentence)：满足一定规则单词序列语言(Language)：满足一定条件的句子集合语言是字和组合字的规则——结构性描述例：去吃我们中汉堡午中午我们去吃汉堡如何描述一种语言？1.如果语言是有穷的（只含有有穷多个句子），可以通过枚举法将语言所有的句子列出表示。例如，只含两个句子的语言：{“Iamateacher”,“Youarestudents”};如何描述一种语言？2.如果语言是无穷的，描述语言有两种途径：制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。设计一种装置（算法或过程

4、），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。语言概述程序设计语言——形式化的内容提取程序设计语言(ProgrammingLanguage)：组成程序的所有语句的集合程序(Program)：满足语法规则的语句序列语句(Sentence)：满足语法规则的单词序列单词(Token)：满足词法规则的字符串文法和语法分析正规式的局限性：不能用于描述配对或嵌套的结构例1：配对括号串的集合例2：{wcw

5、w是a和b的串}仅能表示给定结构的固定次数的重复或者没有指定次数的重复适合描述和识别语言的单词符号；文法和语法分析高级语言的

6、语法结构适合使用上下文无关文法描述。文法及语言的形式定义文法是对语言结构的定义与描述（或称为“语法”），即用适当条数的规则把语言的全部句子描述出来。文法是以有穷的集合刻划无穷的集合的工具。文法文法能清晰地描述程序设计语言的语法构成易于理解。文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。基于文法实现的语言易于扩展。文法及语言的形式定义例：有一句子：“Hehasapen.”这是一个在语法、语义上都正确的句子，该句子的结构（称为语法结构）是由它的语法决

7、定的。在本例中它为“主谓宾结构”。文法的形式定义语法规则：我们通过建立一组规则，来描述句子的语法结构。文法的形式定义<句子>::=<主语><谓语><宾语><主语>::=<代词><代词>::=he<冠词>::=a<名词>::=pen<谓语>::=<动词><动词>::=has<宾语>::=<冠词><名词><名词>::=pen<>括起来的部分是语言的一个语法实体（称为语法单位、语法范畴、语法变量等）规定用“::=”表示“由……组成”终结符号集VT={he,has,a,pen}非终结符号集VN={句子，主语，谓语，冠词，形容词，名词，动词

8、，宾语，名词……}产生式集合P={句子→主语谓语，……}开始符号S=句子句子的语法组成句子的推导___根据规则由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条规则去进行推导。<句子>=><主语><谓语><宾语>=><代词><谓语><宾语>=>he<动词><宾语>=>hehas<宾语>=>hehas<冠词><名词>=>hehasa<名词>=>hehasapen<句子>::=<主语><谓语><宾语><主语>::=<代词

9、><代词>::=he<冠词>::=a<名词>::=pen<谓语>: