当前位置：文档之家 › 算符优先分析法详解

算符优先分析法详解

  • 格式：pdf
  • 大小：155.18 KB
  • 文档页数：4

1四川大学计算机学院金军1算符优先分析󰂄所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质。󰂄考虑下面的文法：󰂄EÆE+E|E-E|E*E|E/E|E↑E|(E)|i󰂄这是一个二义文法，有几种不同的规范归约；但是采用关于算符优先顺序和结合规则的规定，并按这种规定归约，那么归约过程就是唯一的。四川大学计算机学院金军2算符优先分析󰂄算符优先分析法是一种特别有利于表达式分析，宜于手工实现的语法分析方法。󰂄算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此，它不是一种规范归约法。󰂄借助于终结符之间的优先关系确定句柄。󰂄分析能力不强，仅能对算符优先文法进行分析。󰂄工具：优先表、总控程序、栈

四川大学计算机学院金军3算符优先文法󰂄现在按照算符优先分析法的设计思路，构造一种文法，通过它可以自动产生终结符的优先关系表。四川大学计算机学院金军4算符优先文法󰂄一个文法，如果它的任何产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：…QR…󰂄则我们称该文法为算符文法。󰂄在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表有终结符和非终结符组成的任意序列，包括空字。

四川大学计算机学院金军5算符优先文法󰂄假定G是一个不含ε产生式的算符文法。对于任何一对终结符a、b：󰂄(1)a=⋅b当且仅当文法G中含有形如P→…ab…或P →…aQb…的产生式；󰂄(2)a<⋅b 当且仅当G中含有形如P →…aR…的产生式，R而R⇒+b…或R ⇒+Qb…；󰂄(3)a⋅>b 当且仅当G中含有形如P →…Rb…的产生式，R而R⇒+…a或R ⇒+…aQ；󰂄如果一个文法G中的任何终结符对(a, b)至多只满足上述三种关系之一，则称G是一个算符优先文法。四川大学计算机学院金军6算符优先文法󰂄如果a和b在任何情况下不可能相继出现，则a、b之间无优先关系；󰂄注意：优先关系是有序的，要与数学中的‘<’或‘>’区分，a<⋅b不一定意味着b⋅>a。

2四川大学计算机学院金军7算符优先表的构造󰂄算符优先表的构造方法：󰂄通过检查G的每个产生式的每个候选式，可以首先找出满足a=·b的终结符对；󰂄为了找出所有满足关系<·和·>的终结符对，首先需要对G的每个非终结符P构造两个集合：󰂄FIRSTVT(P)󰂄LASTVT(P)四川大学计算机学院金军8算符优先表的构造󰂄FIRSTVT(P) ={a|P⇒+a…或P⇒+Qa…，a∈VT而Q∈VN}󰂄LASTVT(P) ={a|P⇒+…a或P⇒+…aQ，a∈VT而Q∈VN}󰂄有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系<·和·>的所有终结符对。

四川大学计算机学院金军9算符优先表的构造󰂄假定有产生式的一个候选式形为…aP…，那么，对任何b∈FISTVT(P)，a<·b；󰂄假定有产生式的一个候选式形为…Pb…，那么，对任何a∈LASTVT(P)，a·>b。四川大学计算机学院金军10FIRSTVT和LASTVT集合󰂄FIRSTVT(P)的构造：󰂄若有产生式P →a…或P →Qa…，则a∈FIRSTVT(P)；󰂄若a∈FIRSTVT(Q)，且有产生式P →Q…，则a∈FIRSTVT(P)。󰂄LASTVT(U)的构造：󰂄若有产生式U →…a或U →…aV，则a∈LASTVT(U)；󰂄若a∈LASTVT(V)，且有产生式U →…V，则a∈LASTVT(U)。

四川大学计算机学院金军11FIRSTVT构造算法󰂄建立一个二维布尔数组F[P, a]，使得F[P, a]为真的条件适当且仅当a∈FIRSTVT(P)；󰂄再用一个栈STACK，把所有初值为真的数组元素F[P, a]的符号对(P, a)全都放到栈中，对栈施加如下操作：󰂄如栈不空，弹出栈顶符号对记作(Q, a)，查看是否有形如PÆQ…的产生式，若有，且a∈FIRSTVT(P)，则将F[P, a]置为真，并把(P, a)入栈；󰂄重复上步，直到栈空为止。四川大学计算机学院金军12优先表构造算法󰂄有了每个非终结符P的FISTVT(P)和LASTVT(P)之后，就能构造文法G的优先表。其算法如下：

3四川大学计算机学院金军13优先表构造算法FOR 每一条产生式P→X1X2…XnFOR i:=1 TO n-1 DOBEGINIF Xi 和Xi+1 均为终结符THEN 置Xi=·Xi+1IF I<=n-2且Xi和Xi+2都为终结符，而Xi+1为非终结符，THEN置Xi=·Xi+2IF Xi为终结符而Xi+1为非终结符THENFOR FISTVT(Xi+1)中的每个a DO置Xi<·aIF Xi为非终结符而Xi+1为终结符THENFOR LASTVT(Xi)中的每个a DO置Xi ·>aEND四川大学计算机学院金军14算符优先表构造举例e·>d=·<·c·>·>b=·<·aedcba例：设文法G的产生式为：SÆaAcBeAÆAb|b BÆdFIRSTVT(S) = {a}FIRSTVT(A) = {b}FIRSTVT(B) = {d}LASTVT(S) = {e}LASTVT(A) = {b}LASTVT(B) = {d}

四川大学计算机学院金军15算符优先分析算法󰂄算符优先分析技术的基本思想是通过终结符号之间的优先关系，确定句型的句柄。󰂄算符优先分析仅适用于算符优先文法。󰂄算符优先分析法中，我们用“最左素短语”这个概念来刻画算符优先文法的“可归约串”。四川大学计算机学院金军16算符优先分析算法󰂄素短语是指这样的一个短语，它至少含有一个终结符，并且除它自身外，不再含有更小的素短语。󰂄最左素短语是指处于句型最左边的那个素短语。

四川大学计算机学院金军17算符优先分析算法󰂄算符优先文法句型（括在两个#号之间）的一般形式：#N1a1N2a2…NnanNn+1#󰂄其中每个ai都是终结符，Ni是可有可无的非终结符。四川大学计算机学院金军18算符优先分析算法󰂄一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串：Njaj…Niai+1󰂄aj-1<·aj󰂄aj=·aj+1, …, ai-1=·ai󰂄ai·>ai+1󰂄那么，ajNjaj+1…aiNi一定可归约为某终结符。󰂄算符优先分析算法就是根据这个最左素短语的定理构造的。

4四川大学计算机学院金军19算符优先分析算法󰂄工作原理：对当前句型不断寻找最左素短语进行归约的过程。寻找最左素短语时，首先找到最左素短语的末尾终结符，然后再向前搜索最左素短语的首终结符。󰂄使用的数据结构：栈，数组。󰂄有关约定：＃作为语句括号，视为终结符，其优先级最低。四川大学计算机学院金军20算符优先分析的优缺点󰂄优点：󰂄算符优先分析法能方便地构造表达式的语法分析器，分析速度也比较快；󰂄算符优先分析文法使用的范围比简单文发大的多；󰂄缺点：󰂄诊查错误的能力较弱，适用的范围小󰂄可能会把错误的句子识别正确；󰂄某些文法不满足算符优先文法的要求。

合集下载

算符优先分析算法(c语言)

算符优先分析算法(c语言)

1 / 13 编译原理实验

一 实验目的

设计、编制并调试一个算符优先分析算法，加深对此分析法的理解

二 实验过程

先在算符栈置“＄”，然后开始顺序扫描表达式，若读来的单词符号是操作数，这直接进操作数栈，然后继续读下一个单词符号。分析过程从头开始，并重复进行；若读来的是运算符θ2 则将当前处于运算符栈顶的运算符θ1的入栈优先数f与θ2的比较优先函数g进行比较。

2.2 各种单词符号对应的种别码

单词符号 种别码 单词符号 种别码

Main 1 * 17

Int 2 / 18

Char 3 == 39

if 4 != 40

else 5 <= 38

for 6 > 23

while 7 >= 37

letter（letter \digit）* 10 = 21

digit digit* 20 ; 34

= 14 ( 26

+ 15 ) 27

- 16 等等 …

2.3 算符优先程序的功能

完成一个交互式面向对象的算符优先分析程序，而一个交互式面向对象的算符优先分析程序基本功能是：

（1） 输入文法规则

（2） 对文法进行转换

（3） 生成每个非终结符的FirstVT和LastVT

（4） 生成算符优先分析表

（5） 再输入文法符号

（6） 生成移进规约步骤

三 设计源码

算符优先分析器

#include "stdio.h" 2 / 13 #include "stdlib.h"

#include "iostream.h"

char data[20][20]; //算符优先关系

char s[100]; //模拟符号栈s

char lable[20]; //文法终极符集

char input[100]; //文法输入符号串

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

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

第6章⾃底向上优先分析法

⾃底向上分析⽅法，也 称移进－归约分析法，粗略地说它的实现思想是对输⼊符号串⾃左向右进⾏扫描，并将输⼊符逐个移⼊⼀个后进先出栈中，边移⼊边分析，⼀旦栈顶符号串形成某个 句型的句柄时，（该句柄对应某产⽣式的右部），就⽤该产⽣式的左部⾮终结符代替相应右部的⽂法符号串，这称为归约。重复这⼀过程直到归约到栈顶中只剩⽂法 的开始符号时则为分析成功，也就确认输⼊串是⽂法的句⼦。本章将在介绍⾃底向上分析思想基础上，着重介绍算符优先分析法。

例6.1，设⽂法G[S]为：

（1）S→aAcBe

（2）A→b

（3）A→Ab

（4）B→d 对输⼊串abbcde#进⾏分析，检查该符号串是否是G[S]的句⼦。

由于⾃底向上分析的移进－归约过程是⾃顶向下最右推导的逆过程，⽽最右推导为规范推导，⾃左向右的归约过程也称为规范归约。

容易看出对输⼊串abbcde的最右推导为：S aAcBe aAcde aAbcde abbcde

由此我们可以构造它的逆过程即归约过程。

先设⼀个后进先出的符号栈，并把句⼦左括号”#”号放⼊栈底。对上述分析过程也可看成⾃底向上构造语法树的过程，每步归约都是构造⼀棵⼦树，最后当输⼊串结束时刚好构造出整个语法树。在上述移进－归约或⾃底向上构造语法树的过程中，考虑⼏个问题：u 何时移进？u 何时归约？u 将哪个字符串归约？

当 ⼀个⽂法⽆⼆义性时，那么它对⼀个句⼦的规范推导是唯⼀的，规范规约也必然是唯⼀的。因⽽每次归约时要找当前句型的句柄，也就是说，任何时候栈中的符号串 和剩余的输⼊串组成⼀个句型，当句柄出现在栈顶符号串中时，则可⽤句柄归约，这样⼀直归约到输⼊串只剩结束符，⽂法符号栈中只剩开始符号。

由此可见，⾃底向上分析的关键问题是在分析过程中如何确定句柄，即如何知道何时在栈顶符号串中已形成某句型的句柄。然⽽⾃底向上的分析算法很多，我们仅在本章和第7章介绍⽬前常⽤的算符优先分析和LR类分析法。

6.1 ⾃底向上优先分析法概述优先分析法⼜可分简单优先法和算符优先分析法。l 简单优先分析法的基本思想是对⼀个⽂法按⼀定原则求出该⽂法所有符号（即终结符和⾮终结符）之间的优先关系，按照这种关系确定归约过程中的句柄，它的归约过程实际上是⼀种规范规约。l 算符优先分析法的基本思想则是只规定算符之间的优先关系，即只考虑终结符之间的优先关系，由于算符优先分析不考虑⾮终结符之间的优先关系，在归约过程中只要找到句柄就归约，并不考虑归约到那个⾮终结符名，因⽽算符优先归约不是规范归约。

算符优先算法

算符优先算法

while(i < len)

{

if( ch[i] >= '0' && ch[i] <= '9' )//判断位数

{ int value = 0;

while( ch[i] >= '0' && ch[i] <= '9' )//字符数字串转换为十进制数

{

value = value * 10;

value = value + (ch[i]-48); i++;

}

Push( value );//将最终的数字压入栈

cout << "Stack1: " << value << "进栈!" << endl;

}

else {

if( F(Stack2[n-1]) <= G(ch[i]) )//当前字符优先级小于下一字符优先级则把下一字符压进栈

{

jmp: Push( ch[i] );

cout << "Stack2: " << Stack2[n-1] << "进栈!" << endl;

}

else//当前字符优先级小于下一字符优先级

{

int j;

for(j = n-1;j >= 1;j--)//循环处理栈Stack2字符

{

if(Stack2[j] == '+')//栈顶运算符为'+'则执行加法运算

{

int t1,t2,t3;

cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;//将操作数栈顶上的两个操作数做出栈处理

t1 = Pop( Stack1[m-1] );

cout << "Stack1: " << Stack1[m-1] << "出栈!" << endl;

t2 = Pop( Stack1[m-1] );

t3 = t1 + t2;//根据运算符栈顶的运算符运算

Push( t3 );//将运算结果压进操作数栈

cout << "Stack1: " << Stack1[m-1] << "进栈!" << endl;

算符优先分析过程模拟

算符优先分析过程模拟

算符优先分析过程模拟

一、需求分析 ......................................................................

1

二、概要设计 ......................................................................

2

三、详细设计 ......................................................................

5

四、测试结果 ....................................................................

10

五、总结............................................................................ 12

华东交通大学课程设计报告

算符优先分析是自底而上分析方法的一种，这种方法是对输入符号

串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边

分析，一旦栈顶符号串形成某个句型的句柄或可规约串时（该句柄或可归

约串对应产生式的右部），就用该产生式的左部非终结符代替相应右部的文

法符号串，重复这样的归约过程，一直到只剩文法的开始符号时则为分析

成功，也就是确认输入串是该文法的句子。 而算符优先分析的基本思想则是只规定算符之间的优先关系，也就

是只考虑终结符之间的优先关系，由于算符优先分析不考虑非终结符之间

的优先关系，在归约过程中只要找到可归约的串就归约，并不考虑归约到

那个非终结符名。

在定义具体的由于算符优先关系之前，先说明由于算符优先关系符

的定义，有三中由于算符优先关系符，分别是>,<,=

设G是一个不含ε产生式的算符文法，a,b是任意两个终结符，A，