编译原理课件-Chapt4-1.ppt

编译原理 第四章 语法分析—自上而下分析 本章主要内容 本章主要介绍语法分析的处理 语法分析的任务 自顶向下分析法 语法分析的任务 语法分析程序以单词串形式的源程序作为输入或分析的对象。 它的基本任务是： 根据语言的语法规则 ，分析源程序的语法结构，即分析如何由这些单词组成各种语法范畴 (如下标变量、各种表达式、各种语句、程序段或分程序，乃至整个源程序等等)，并在分析过程中，对源程序进行语法检查。 作为语法分析程序的输出，可以有多种不同的形式。在下面的讨论中，为简便起见，我们假定语法分析程序的输出，是用某种方法表示的语法树 语法分析 如何精确描述和刻画语言中的基本语法成分--如表达式、语句和函数？ 如何识别语法成分及语法错误并执行某些相关的处理动作？ 什么是语言 自然语言(Natural Language) 是人与人的通讯工具 语义(Semantics):环境、背景知识、语气、二义性——难以形式化 计算机语言(Computer Language) 计算机系统间、人机间通讯工具 严格的语法(Grammar)、语义(Semantics) ——易于形式化：严格 语言是用来交换信息的工具——功能性描述 什么是语言 语言 单词(Token)：满足一定规则字符(Character)串 句子(Sentence)：满足一定规则单词序列 语言(Language)：满足一定条件的句子集合 语言是字和组合字的规则——结构性描述 例：去吃我们中汉堡午 中午我们去吃汉堡 如何描述一种语言？ 1. 如果语言是有穷的（只含有有穷多个句子），可以通过枚举法将语言所有的句子列出表示。 例如，只含两个句子的语言：{“I am a teacher”, “You are students”}; 如何描述一种语言？ 2. 如果语言是无穷的，描述语言有两种途径： 制定有限条规则，用于产生所要描述的语言的全部句子（可无限多），这些规则构成了该语言的文法。 设计一种装置（算法或过程），它以某字母表上的符号串为输入，判别该符号串是否为所描述语言的句子。此装置称为自动机。 语言概述 程序设计语言——形式化的内容提取 程序设计语言(Programming Language)：组成程序的所有语句的集合 程序(Program)：满足语法规则的语句序列 语句(Sentence) ：满足语法规则的单词序列 单词(Token) ：满足词法规则的字符串 文法和语法分析 正规式的局限性：不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw | w是a和b的串} 文法和语法分析 高级语言的语法结构适合使用上下文无关文法描述。 文法及语言的形式定义 文法是对语言结构的定义与描述（或称为“语法”），即用适当条数的规则把语言的全部句子描述出来。 文法是以有穷的集合刻划无穷的集合的工具。 文法 文法能清晰地描述程序设计语言的语法构成易于理解。 文法能自动地构造有效的语法分析器，检查源程序是否符合语言规定的语法形式。 文法定义可以了解程序设计语言的结构，有利于将源程序转化为目标代码，以及检查出语法错误。 基于文法实现的语言易于扩展。 文法及语言的形式定义 例：有一句子：“He has a pen.”这是一个在语法、语义上都正确的句子，该句子的结构（称为语法结构）是由它的语法决定的 。在本例中它为“主谓宾结构”。 文法的形式定义 语法规则：我们通过建立一组规则，来描述句子的语法结构。 文法的形式定义 句子 ::= 主语谓语宾语 主语 ::= 代词 代词 ::= he 冠词 ::= a 名词 ::= pen 谓语 ::= 动词 动词 ::= has 宾语 ::= 冠词名词 名词 ::= pen 终结符号集VT = { he, has, a, pen} 非终结符号集VN = { ?句子?，?主语?，?谓语?，?冠词?，?形容词?，?名词? ，? 动词? ，?宾语? ，?名词?……} 产生式集合P = {?句子? → ?主语??谓语? ，……} 开始符号S = ?句子? 句子的推导___根据规则 由规则推导句子：有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应产生式的右部来替代产生式的左部，每次仅用一条规则去进行推导。 句子 = 主语谓语宾语 = 代词谓语宾语 = he 动词宾语 = he has 宾语 = he has 冠词名词 = he has a 名词 = he has a pen 上下文无关文法的形式定义 一个上下文无关文法G是一个四元式 G=(VT，VN，S，P)，其中 VT：终结符集合