编译原理-课件-第三章-语法分析1.ppt

规范推导和规范归约最左推导和最右推导：对于一个推导序列中的每一步?直接推导，都是对最左（最右）非终结符进行替换。最右推导也称规范推导，它的逆过程称为最左归约，也称规范归约。.若用?表示归约，设A→a是文法G中的一个规则，则对于.xAy?xay有xayxAy?32【例】文法G[S]:S→ABA→A0|1BB→0|S1请给出句子101001的最左和最右推导。最左推导：S?AB?1BB?10B?10S1?10AB1?101BB1?1010B1?101001最右推导：S?AB?AS1?AAB1?AA01?A1B01?A1001?1B1001?10100133【例】有文法如下,G[E]：E→E+T|TT→T*F|FF→(E)|i该文法的开始符号是？非终结符号集是？终结符号集是？如何得到句子i+i*i?开始符号是E非终结符号集是E、T、F终结符号集是i、(、)、+、*E?E+T?T+T?F+T?i+T?i+T*F?i+F*F?i+i*F?i+i*i34【例】程序语言中，program→declaration_listdeclaration_list→declaration_listdeclaration|declaration例】程序语言中，D→TLT→int|long|shortL→id|L,id36【、描述程序设计语言的文法必定都是递归的。2、递归规则的存在，使得能用有穷个规则来定义无穷的语言（的句子）。37注：1句型分析的相关基本概念?短语、直接短语、句柄、素短语?句型和句子?语法树和文法的二义性39短语和直接短语设G[S]是一个文法，w=αβδ是该文法的一个句型，如果有S?*αAδ，A∈VN,且A?+β,β∈V+,则称β是句型w中相对于A的短语。如果有S?*αAδ，A→β,则称β是句型w中相对于A的直接短语。40句柄句型的句柄：一个句型的最左直接短语。任何句型的句柄总是存在，且惟一。【例】对于文法G[S]：S→ABA→Aa|bBB→a|Sb求句型baSb的全部短语、直接短语和句柄？该句型的短语有Sb、a、ba及自身baSb；直接短语有Sb、a；其中a为句柄。41??练习设有文法G[S]：S→aAcBeA→Ab|bB→d1、考虑句型aAbcde，判断b是否为其一个短语？2、求句型aAbcde的短语、直接短语和句柄。短语：Ab、d、aAbcde直接短语：Ab、d句柄：Ab42素短语?含有终结符的短语，如果它不存在也具有同样性质的真子串，则该短语为素短语。43语法分析器在编译过程中的位置44语法分析器?语法分析器的输入?Token序列：词法分析产生的输出，是各个单词都正确的源程序，是一个有限序列。语法分析器的功能?按照语言的语法构成规则,识别输入的Token序列能否构成一个句子。规则是用文法的产生式来定义的。?对给定的输入单词串，如何判定它是不是一个句子？语法分析器的输出?分析树（语法树）：如何表示和构造语法树？?错误处理信息：定位、继续编译45??*第三章语法分析(1)文法和语言的形式化定义自上而下分析方法自下而上分析方法13.1文法和语言语言概述文法概述形式语言分类23.1.1语言概述一、语言某一字母表上符号串（句子）的集合。语言研究的三个方面：语法—构成语言句子的各个记号之间的组合规律。语义—按照各种表示方法所描述的各个记号的特定的含义。语用—在各个记号所出现的行为中，它们的来源、使用和影响。3什么是符号与字母表？?字母表：由若干元素（符号、字母）所组成的有限非空集合。常用大写英文字母A,B…或希腊字母Σ表示。?符号：可以相互区别的记号（元素）。例如：Σ={0