第六章 算符优先分析(编译原理)

算符优先分析算法1.该实验实现算符优先分析算法，由于时间关系，尚未实现用程序计算FIRSTVT，LASTVT，因此本实验的各种非终结符及其之间的优先关系人为初始化。

本实验参考例4.12及其优先关系表。

2.算符优先关系表参考课本74页表4.4+ * id ( ) #+ > < < < > >* > > < < > >id > > > >( < < < < =) > > > ># < < < < =3.结果如图4.源代码# include<stdio.h># include<stdlib.h># include<string.h># define MAX 50 //定义最大长度为50，可以变化struct sst{char s[MAX];int ps;//栈顶终结符指针int top;//栈顶指针};struct inputst{char in[MAX];int pin;//当前字符指针};//定义算符及其优先关系表char ch[6] = {'+','*','i','(',')','#'};char chrelation[6][6]={'>','<','<','<','>','>','>','>','<','<','>','>','>','>','@','@','>','>','<','<','<','<','=','@','>','>','@','@','>','>','<','<','<','<','@','=', };char rela(char c1,char c2){int i = 0,j = 0;while(ch[i] != c1)i++;while(ch[j] != c2)j++;return chrelation[i][j];}int is_VN(char c1){//判断是否为非终结符int i = 0;while(i < 6){if(ch[i] == c1)return 0;i++;}return 1;}void main(){struct sst S;for(int i = 0;i < MAX;i++){S.s[i] = ' ';}S.s[0] = '#';S.ps = 0;S.top = 0;struct inputst input;printf("请输入需分析的字符串，以#结尾，最大长度为%d:\n",MAX);scanf("%s",input.in);printf("%s\n",input.in);input.pin = 0;printf("s栈优先关系当前符号输入流动作\n");int cursor;while(1){if(rela(S.s[S.ps],input.in[input.pin]) == '<' || rela(S.s[S.ps],input.in[input.pin]) == '=') { for(cursor = 0;cursor <= S.top;cursor++)printf("%c",S.s[cursor]);printf(" %c ",rela(S.s[S.ps],input.in[input.pin]));printf(" %c ",input.in[input.pin]);printf(" ");for(cursor = input.pin+1;cursor < strlen(input.in);cursor++)printf("%c",input.in[cursor]);if(S.s[S.ps] == '#' && S.s[S.top] == 'N' &&rela(S.s[S.ps],input.in[input.pin]) == '=') {printf(" 接受\n");return;}else{ printf(" 移进\n");S.top++;S.ps = S.top;S.s[S.top] = input.in[input.pin++];}}else if(rela(S.s[S.ps],input.in[input.pin]) == '>'){for(cursor = 0;cursor <= S.top;cursor++)printf("%c",S.s[cursor]);printf(" %c ",rela(S.s[S.ps],input.in[input.pin]));printf(" %c ",input.in[input.pin]);printf(" ");for(cursor = input.pin+1;cursor < strlen(input.in);cursor++)printf("%c",input.in[cursor]);if(S.ps >0 && S.ps < S.top){if( is_VN(S.s[S.ps-1]) && is_VN(S.s[S.ps+1])){S.s[S.ps-1] = 'N';S.top = S.ps-1;S.ps = S.top -1;}printf(" 归约\n");}else{S.s[S.top] = 'N';S.ps = S.top -1;printf(" 归约\n");}}else{for(cursor = 0;cursor <= S.top;cursor++)printf("%c",S.s[cursor]);printf(" %c ",rela(S.s[S.ps],input.in[input.pin]));printf(" %c ",input.in[input.pin]);printf(" ");for(cursor = input.pin+1;cursor < strlen(input.in);cursor++) printf("%c ",input.in[cursor]);printf(" 出错!");return;}}}5.问题不知如何用计算机程序得到FIRSTVT，LASTVT。

实验四、算符优先分析算法
姓名：
学号：
班级：
指导老师：
时间：
计算机与信息技术学院
程序功能描述
实现算符优先分析算法，完成以下描述算术表达式的算符优先文法的算符优先分析过程。

G[E]:E→E+T∣E-T∣T
T→T*F∣T/F∣F
F→(E)∣i
说明：终结符号i 为用户定义的简单变量,即标识符的定义。

（1）构造该算符优先文法的优先关系矩阵或优先函数；（2）输入串应是词法分析的输出二元式序列，即某算术表达式“实验项目一”的输出结果，输出为输入串是否为该文法定义的算术表达式的判断结果；（3）算符优先分析过程应能发现输入串出错。

（4）设计两个测试用例（尽可能完备，正确和出错），并给出测试结果。

备注：程序中判断该输入串是否为该文法定义的算术表达式的结果，若是则输出“accept”，若不是则输出“error”。

该二元式序列要以“#”为结尾。

主要数据结构描述
程序结构描述
程序测试:
测试1：(i+i*i)
输出：
输入二：i+i*ii
输出：
学习总结
算符优先文法关键点就在于判断各个终结符号的优先级，构造算符优先矩阵是个难点，程序里面没有实现，而是直接定义了优先矩阵，这是需要完善的地方，试试能不能在程序中动态地构造优先矩阵。

另外对于算符优先文法，失败的条件是比较两个非终结符的优先关系，若优先关系表中为空，就返回error.。

编译原理算符优先分析程序设计算符优先分析（Operator Precedence Parsing）是一种基于文法的自下而上的语法分析方法，用于构造一个将输入串转化为语法分析树的分析器。

它通过根据每一个终结符号和非终结符号之间的优先级关系，来判断是否可以进行规约操作。

算符优先分析的基本思想是，为每一个终结符和非终结符分配一个优先级，然后根据这些优先级来决定如何进行规约操作。

一般来说，基本的终结符都有一个固定的优先级，而非终结符的优先级则由其所对应的产生式右部中的终结符优先级来决定。

算符优先分析的核心在于构造一个优先级关系表，用于指导规约过程。

这个表一般由产生式构造得到，每个终结符和非终结符对应一行和一列，表中的每个元素表示两个符号之间的优先级关系。

算符优先分析的步骤如下：1.根据给定的文法，确定每个终结符号和非终结符号的优先级。

2.构造优先关系表，填入每两个符号之间的优先关系。

3.初始化分析栈和输入栈，将栈底符号设为文法开始符号，并将输入串入栈。

4.重复以下步骤，直到分析完成：a.查找栈顶和当前输入符号之间的优先关系。

b.如果栈顶符号的优先级较低或相等，则进行规约操作，将栈顶的符号替换为相应的非终结符号。

c.如果栈顶符号的优先级较高，则进行移进操作，将当前输入符号移入栈中。

d.如果找不到优先关系，则出现错误，分析失败。

算符优先分析的优点是简单明了，且规约过程中不需要回溯，效率较高。

然而，由于它只适用于算符优先文法，而不是所有的上下文无关文法，因此适用范围有限。

在实际编程中，我们可以通过编写算符优先分析程序来对给定的文法进行分析。

程序可以根据文法自动生成优先关系表，然后根据输入串和优先关系表进行分析。

下面是一个简单的算符优先分析程序设计：```python#定义终结符和非终结符的优先级priority = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0}#构造优先关系表def build_table(:table = {}for symbol1 in priority.keys(:row = {}for symbol2 in priority.keys(:if symbol1 == '(' and symbol2 == ')':row[symbol2] = 'r'elif symbol1 == ')' and symbol2 == '(':row[symbol2] = 'e'elif priority[symbol1] > priority[symbol2]:row[symbol2] = '>'elif priority[symbol1] < priority[symbol2]:row[symbol2] = '<'else:row[symbol2] = 'e'table[symbol1] = rowreturn table#算符优先分析程序def operator_precedence_parsing(table, input_str): input_stack = list(input_str)input_stack.append('#')analysis_stack = ['#']while len(analysis_stack) > 0:top = analysis_stack[-1]if top in priority.keys( and input_stack[0] in priority.keys(:relation = table[top][input_stack[0]]if relation == '>':analysis_stack.popprint('Reduce by', top)elif relation == '<':analysis_stack.append(input_stack.pop(0)) print('Shift', analysis_stack[-1])elif relation == 'e':analysis_stack.popinput_stack.pop(0)print('Error')returnelse:print('Error')returnelse:print('Error')return#测试代码table = build_tableinput_str = input('Please enter a valid expression: ')operator_precedence_parsing(table, input_str)```以上是一个简单的算符优先分析程序设计，实现了根据输入串和优先关系表进行分析的过程。

目录一、设计目的 (1)二、设计原理 (1)三、设计思想 (2)四、设计要求 (3)五、设计流程图及程序 (4)六、运行结果及分析 (14)七、设计总结 (16)八、参考文献 (16)算符优先词法分析器一、设计目的算符优先算法是自底而上分析方法的一种。

所谓自底向上分析，也称移进—规约分析，粗略地说他的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出的栈中，边移进边分析，一旦栈顶符号串形成某个句型的句柄或可规约串是，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一部规约。

重复这一过程直到规约到栈中只剩文法的开始符号是则为分析成功，也就确认输入串是文法的句子。

而算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。

本课程设计的主要目的：1、通过本次课程设计，全面系统的了解编译原理程序构造的一般原理和基本实现方法，尤其是对自底向上的优先分析方法的认识和理解；2、提高对编译程序工作基本过程及其各阶段基本任务的分析技能；3、加强对编译程序的生成过程、构造工具及编译程序总流程框图的理解，巩固所学的课本知识。

二、设计原理算符优先分析法是一种有效的自底向上的分析方法。

自底向上分析方法面临的主要问题是如何确定可归约串，而算符优先分析法根据两个终结符号之间的优先关系比较，成功的解决了可归约串的问题。

算符优先分析法是采用最左素短语进行归约的，严格来讲不属于规范规约的范畴。

因此，在设计以前我们必须要知道什么是素短语和最左素短语。

所谓素短语就是指句型中具有这样性质的短语：至少含有一个终结符，且除了自身之外，不再含有任何更小的素短语的短语。

最左素短语，是指在句型的所有素短语中，处于句型最左边的素短语。

了解了素短语和最左素短语，那么如何构造这种算法呢？首先，根据非终结符的FIRSTVT集和LASTVT集找出它们之间的优先关系，构造算符优先矩阵。

然后，由此矩阵构造相应符号串的算符优先分析表并编写程序。

编译原理中算符优先分析的教学探讨算符优先分析法是编译原理课程中的重点和难点之一。

本文针对相等、小于和大于优先关系，分析了优先归约关系的本质，提出了优先关系和最左素短语的分析模型。

关键词：编译原理；归约；优先关系；最左素短语1引言计算机科学与技术学科强调4个方面的专业能力：计算思维能力，算法设计与分析能力，程序设计与实现能力，计算机系统的认知、分析、设计和运用能力。

这也是计算机科学与其他学科的重要区别。

相关的理论是计算机学科的基础。

理论方面的知识是计算机的真正灵魂。

理论是从计算机应用当中抽象出来的，目的在于使用抽象出来的理论去更好地指导实践[1]。

程序设计与实现能力在编译原理课程得到了具体的体现。

编译原理是计算机学科中少有的从实践到理论，再从理论到实践的一门专业课程。

编译技术不断进步，已经成为计算机科学中发展最迅速、最成熟的一个重要分支。

编译技术集中体现了计算机科学发展的重要成果与精华[2]。

程序语言及其编译的研究在计算机科学中的始终处于非常重要的地位。

编译程序构造的基本原理和技术蕴涵计算机科学解决问题的思路和抽象、解决问题的方法，也广泛应用于一般软件的设计和实现，其中的设计思想、算法、思维方式和技术都可能会对学生今后的发展产生比较大的影响。

编译原理对计算机专业的学生的重要性与高等数学对理科学生的重要性几乎可以相提并论。

同时，由于这门课程涉及其他多门课程的知识，使得它成为大学阶段中最难学的课程之一。

自下而上语法分析中的算符优先分析方法是是编译原理课程中的重点和难点之一。

算符优先分析法使用终结符号之间的归约顺序进行语法结构的分析。

在算术表达式中，有运算符号的优先级和结合性的规定，而算符优先分析法的实质就是仿效表达式的计算过程而设计的。

其本质是对终结符之间的优先关系和最左素短语进行分析。

2终结符之间的优先关系2.1算符优先文法上下文无关文法G，如果没有形如P→ε或P→...QR...的产生式，则称G为算符文法。

编译原理课程设计报告评分：签字：编译原理课程设计二——算符优先分析程序设计实验目的了解掌握算符优先分析的基本方法、内容；学会科学思考并解决问题，提高程序设计能力。

实验内容与要求用算符优先分析方法设计一个分析解释程序，对输入的赋值语句、输出语句、清除语句进行词法分析、语法分析、表达式求值并存储于指定变量中；若存在错误，提示错误相关信息。

文法表示：S→v=E|E?|clearE→E+T|E-T|TT→T*F|T/F|FF→(E)|v|c单词种别码设计：= 1？ 2+ 3- 4* 5/ 6（7）8v 9c 10clear 11# 12N 13实验环境系统环境为windows系统，编译环境为VS2015,编程语言为C++。

实验过程过程一：构建firstVT()和lastVT()算法分析：对于firstVT()构建，对于每个非终结符F的产生式，第一个终结符或者‘|’后的第一个终结符应该在其firstVT()集合内，且若非终结符T能推出非终结符F则firstVT(T)包含first（F）。

lastVT()的构造类似，对于每个非终结符F的产生式，非终结符后的第一个终结符都属于lastVT （F）, 且若非终结符T能推出非终结符F则lastVT(T)包含first（F）。

算法实现主要函数：void get_firstVT()//求firstVT();void get_lastVT()//求lastVT();结果：FirstVT(S){=,?,l,+,-,*,/,(,v,c,}FirstVT(E){+,-,*,/,(,v,c,}FirstVT(T){*,/,(,v,c,}FirstVT(F){(,v,c,}LastVT(S){=,?,l,+,-,*,/,),v,c,}LastVT(E){+,-,*,/,),v,c,}LastVT(T){*,/,),v,c,}LastVT(F){),v,c,}过程二：构建优先符号表算法分析:（1）在产生式中两个相邻的终结符优先顺序相等（2）对于小于关系，首先扫描终结符a标记flag=1，再扫描到非终结符Q，此时判断若flag=1，则对所有b∈FristVT{Q}，a<b.（3）对于大于关系，首先扫描非终结符Q在前标记flag=1，再扫描终结符a在后此时判断若flag=1，对所有b∈LastVT{Q}，b>a.算法结果：其中-2表示不会出现，1表示>,-1表示<,0表示=.字母l表示clear.过程三：词法分析算法分析：详见课程设计一算法主要函数：int letter()//判断是否为字母int digit()//判断是否为数字int str_to_num()//数字字符串转化为整数int reserve(char **k)//处理保留字int sysmbol(identifier *id)//处理标识符，查找符号表并存放位置若没有则添加int constant(constnumber *con)//存入常数表，并返回它在常数表中的位置void WordAnalyze( constnumber *con, identifier *id, char sentence[],int &point,int &syn,int &sym_point)//词法分析void Insert_to_symboltbl(int syn, int value, int &point)//把二元组加入symbol表算法结果：得到语句的所有单词二元组symbolTBL表,存放种别码syn及其值val，其中对于种别码为9的变量val为标志符的入口标志，对于种别码为10的的常量val为存放的值。

编译原理之算符优先分析1.算符优先分析：1.1定义是⼀种简单直观、⼴泛使⽤、便于⼿⼯实现的⾃下⽽上的语法分析⽅法。

1.2原理定义算符之间的某种优先关系，寻找“归约串”，并进⾏归约1.3相关知识拓展1.3.1 算符⽂法:产⽣式的右部不包含两个相继的⾮终结符，即不包含形如：.....QR.....1.3.2 算符优先⽂法:任何终结符对(a,b)⾄多⼀种优先级关系。

1.3.3 构造优先关系表步骤：(1)写出FIRSTVT、LASTVTFIRSTVT(P)={a|P->a.....或P->Qa......}LASTVT(P)={a|P->.....a或P->......aQ} (2)列表，根据优先级填表 1.确定同⼀产⽣式的末尾终结符之间⽆优先关系 2.确定=，再使⽤FIRSTVT、LASTVT1.4 算符优先分析算法 素短语：⾄少包含⼀个终结符且不包含更⼩的终结符，如p*p或 i 最左素短语：最左侧的素短语 缺点：跳过了所有单⾮产⽣式所对应的归约步骤。

（单⾮产⽣式：形如：P->Q ,右部只有⼀个⾮终结符的产⽣式）1.5 构造优先函数使⽤构造优先函数代替优先表f:表⼊栈优先函数、g：表⽐较优先函数1.6 举例S→a|Λ|(T) T->T,S|S(1)基本了解：FIRSTVT(P)={a|P->a.... or Qa....}; LASTVT(P)={a|P->...a or P->....aQ}所以对于：S→a|Λ|(T) 则FIRSTVT(S)={a,Λ,(}对于：S→a|Λ|(T) 则LASTVT(S)={a,Λ,)}对于：T->T,S|S 则FIRSTVT(T)={, ,a,Λ,(}对于：T->T,S|S 则LASTVT(T)={, ,a,Λ,)}(2)优先关系aΛ(),a>>Λ>>(<<<=<)>>,<<<>>,<<<>>由于G[S]中任何终结符对（a,b）之多只有⼀种关系成⽴，所以，G[S]为算符优先⽂法。