第6章 自底向上优先分析法.pptVIP

第6章 自底向上的语法分析 自底向上分析方法，也称移进-归约分析法。 实现思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的可规约串时,（该句型或可规约串对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到输入串只剩结束符，栈中只剩文法的开始符号时则为分析成功，否则为出错。 自底向上分析的关键问题是在分析过程中如何确定可规约串。 第6章 自底向上的语法分析 例:文法G[S] S→aAcBe A→b A→Ab B→d 第6章 自底向上的语法分析 例:文法G[S] S→aAcBe A→b A→Ab B→d 第6章 自底向上的语法分析 6.1 自底向上优先分析概述 6.2 简单优先分析法 6.3 算符优先分析法 6.1 自底向上优先分析概述 优先分析法可分为以下两类： 简单优先分析法 在归约过程中考虑文法所有符号即包括终结符和非终结符之间的优先关系，按照这种关系确定规约过程中的可规约串（句柄），它的规约过程实际上是一种规范规约。该分析法准确、规范，但分析效率较低，实际使用价值不大。 算符优先分析法 在归约过程中，只考虑终结符之间的优先关系来确定可规约串，而与非终结符无关。这样去掉了单非终结符的归约，所以算符优先分析法的规约过程不是规范归约。但它简单，直观，效率较高，特别适用于表达式的分析。 6.2 简单优先分析法 简单优先分析法是按照文法符号（包括终结符和非终结符）之间的优先关系确定句柄。 6.2.1 优先关系的定义 6.2.2 简单优先文法的定义 6.2.3 简单优先分析算法 6.2.1 优先关系的定义 文法中任意两个符号X，Y按其在句型中可能会出现的相邻关系来确定它们的优先关系： X =? Y ? 文法G中存在产生式 A→…XY... X ? Y ? 文法G中存在产生式 A→...XB...，且B?+ Y... X ? Y ? 文法G中存在产生式 A→...BD...，且B?+ ...X，D?* Y... 6.2.1 优先关系的定义 例：文法G[S] S→bAb A→(B|a B→Aa) 6.2.1 优先关系的定义 例：文法G[S] S→bAb A→(B|a B→Aa) 6.2.1 优先关系的定义 优先关系矩阵 6.2.2 简单优先文法的定义 满足以下条件的文法是简单优先文法 在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。 在文法中任意两个产生式没有相同的右部。 不含空产生式。 6.2.2 简单优先文法的定义 6.2.3 简单优先分析算法 简单优先分析方法的组成部分 分析表 分析栈 分析算法 6.2.3 简单优先分析算法 分析算法步骤如下： 将输入符号串a1a2a3...an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性?下一个待输入符号ai+1时为止。 栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1?ak为止。即ak-1ak =? ak+1 =? ... =? ai ? ai+1。 由句柄ak...ai在文法的产生式中查找右部为ak...ai的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。 重复上述三步，直到归约完输入符号串，栈中只剩文法的开始符号为止。 6.2.3 简单优先分析算法 例：文法G[S] S→bAb A→(B|a B→Aa) 6.3 算符优先分析法 某些文法具有“算符”特性 表达式运算符（优先级、结合性） 人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性 只考虑算符之间的优先关系来确定可规约串 6.3 算符优先分析法 算符优先分析法只考虑算符（广义为终结符）之间的优先关系。 6.3.1 直观算符优先关系 6.3.2 算符优先文法的定义 6.3.3 算符优先关系表的构造 6.3.4 算符优先分析算法 6.3.1 直观算符优先关系 例G[E]： E→E+E|E-E|E*E|E/E|E?E|(E)|i 按公认的计算顺序规定优先级和结合性： i的优先级最高 ?优先级次于i，右结合 *和/优先级次之，左结合 +和-优先级最低，左结合 括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号 #的优先性低于与其相邻的算符 6.3.1 直观算符优先关系 算符优先关系表 6.3.2 算符优先文法的定义 定义：如果不含空产生式的上下文无关文法G中没有形如A?…BC…的产生式，其中A，B，C∈VN ，则称G为算符文法（OG）。 例 G[E]：E→E+E｜E-E｜E*E｜