算符优先语法分析设计原理与实现技术-实验报告-及源代码-北京交通大学(共14页).doc
精选优质文档-倾情为你奉上算符优先语法分析设计原理与实现技术XXX 1028XXX 计科1XXX班功能描述能够有效识别以下算符优先文法E E+T | E-TT T*F | T/F | FF (E) | i所描述算术表达式主要数据结构描述数据结构功能描述string 存储该算符优先文法，对栈顶元素进行规约时要用到map<char, int>符号表中的元素映射成整数map<int, int>将用整数表示的符号映射到响应的行或列map<int, char>将整数映射成相应的字母表中的符号int 分析栈程序结构描述n 设计方法1. 由文法构造算符优先矩阵+-*/()i#+>><<<><>->><<<><>*>>>><><>/>>>><><>(<<<<<=<)>>>>>>i>>>>>>#<<<<<<=2. 根据算符优先矩阵算数表达式的词法分析结果进行语法分析，分析算法为：数据结构：符号栈S - 存放所有读进的符号（计数i）K - 符号栈使用深度a - 工作单元R, Q - 变量分析算法：先找最左素短语的尾部（>） 再找最左素短语的头部（<）以分析表达式i+i*i为例，详细过程如下：n 函数定义函数原型功能描述void init()各种初始化操作，主要是建立符号与整数、整数与行列号、整数与符号之间的映射，也包括各全局变量的初始化void isVt(int )判断某整数所代表的符号是否是终结符号或#void comp(int a, int b)比较两整数所代表的字符的优先关系void advance()从输入文件中读入一个词bool parser()算符优先分析函数，根据算符优先矩阵进行语法分析int main(int argc, char *argv)主函数，参数argv1代表输入文件n 函数调用关系maininitisVtadvanceparsercompn 程序执行图程序测试测试用例一：(a+b*c)+d+e+a*c/b首先调用实验一的词法分析程序，得到如下分析结果：(19, '(')(12, 'a')(14, '+')(12, 'b')(16, '*')(12, 'c')(20, ')')(14, '+')(12, 'd')(14, '+')(12, 'e')(14, '+')(12, 'a')(16, '*')(12, 'c')(17, '/')(12, 'b')在以此分析结果作为本程序实验结果的输入，得到如下分析结果：该结果显示了详细的分析过程，且表明该表达式是一个符合该文法的表达式测试用例二：(a+b*c)+d*-a*c+(a+b同样调用实验一的词法分析程序，得到如下结果：(19, '(')(12, 'a')(14, '+')(12, 'b')(16, '*')(12, 'c')(20, ')')(14, '+')(12, 'd')(16, '*')(15, '-')(12, 'a')(16, '*')(12, 'c')(14, '+')(19, '(')(12, 'a')(14, '+')(12, 'b')以此分析结果作为本实验程序的输入，得到如下语法分析结果：实验结果表明，在分析过程中出现了错误，分析过程未完成，该样例是一个非法的表达式学习总结Ø 按算符优先关系所确定的应被规约的子串恰好是当前举行的最左素短语Ø 尽管算符优先分析也属于自底向上语法分析的范畴，但却不是严格的从左至右的规范分析，每步所得的句型自然也不是一个规范句型Ø 采用上述策略进行算符优先分析时，尽管我们也指出了每一最左素短语应规约到的非终结符号，然而每次在查找最左素短语时，起主导作用的是终结符号间的优先关系，两终结符号之间究竟是哪个非终结符号无关宏旨/ operator_prior.cpp : Defines the entry point for the console application./#include "stdafx.h"#include <stdio.h>#include <ctype.h>#include <map>#include <vector>#include <string>#define ID 12#define ADD 14#define SUB 15#define MUL 16#define DIV 17#define LP 19#define RP 20#define EOI 31#define SHARP 32#define EQ 0#define BT 1#define LT 2#define UD 3#define N_Base 1000using namespace std;FILE *fp;int lookahead, yylineno;bool success;map<int, int> intToint;map<char, int> charToint;map<int, char> intTochar;string grammer8 = "E+T", "E-T", "T", "T*F", "T/F", "F", "(E)", "i"int prior_matrix99 = BT, BT, LT, LT, LT, BT, LT, BT, BT, BT, LT, LT, LT, BT, LT, BT, BT, BT, BT, BT, LT, BT, LT, BT, BT, BT, BT, BT, LT, BT, LT, BT, LT, LT, LT, LT, LT, EQ, LT, UD, BT, BT, BT, BT, UD, BT, UD, BT, BT, BT, BT, BT, UD, BT, UD, BT, LT, LT, LT, LT, LT, UD, LT, EQ;void init() success = true; yylineno = 0; intTointADD = 0; intTointSUB = 1; intTointMUL = 2; intTointDIV = 3; intTointLP = 4; intTointRP = 5; intTointID = 6; intTointSHARP = 7; charToint'+' = ADD; charToint'-' = SUB; charToint'*' = MUL; charToint'/' = DIV; charToint'(' = LP; charToint')' = RP; charToint'i' = ID; intTocharADD = '+' intTocharSUB = '-' intTocharMUL = '*' intTocharDIV = '/' intTocharLP = '(' intTocharRP = ')' intTocharID = 'i' intTocharSHARP = '#' intTocharN_Base = 'N'bool isVt(int a) if (a >= N_Base) return false; else return true;int comp(int a, int b) int x = intTointa; int y = intTointb; return prior_matrixxy;void advance() if (fscanf(fp, "(%d", &lookahead) = EOF) lookahead = SHARP; else char ch; do ch = fgetc(fp); if (ch = 'n' | ch = EOF) break; while (true); yylineno+;void parser() int stack100, top = 0; int i, j, k, ii, jj; stacktop+ = SHARP; advance(); do for (i = 0; i < top; i+) printf("%c", intTocharstacki); printf("t%cn", intTocharlookahead); for (i = top - 1; i >= 0; i-) if (isVt(stacki) break; int res = comp(stacki, lookahead); if (res = LT | res = EQ) stacktop+ = lookahead; advance(); else if (res = BT) int temp = stacki; for (j = i - 1; j >= 0; j-) if (isVt(stackj) if (comp(stackj, temp) = LT) break; else temp = stackj; for (k = 0; k < 8; k+) if (int)grammerk.length() = top - 1 - j) ii = j + 1; jj = 0; do if (grammerk.at(jj) >= 'A' && grammerk.at(jj) <= 'Z') if (isVt(stackii) break; else if (charTointgrammerk.at(jj) != stackii) break; ii+; jj+; while (ii < top && jj < (int)grammerk.length(); if (ii >= top) break; if (k >= 8) success = false; return ; top = j + 1; stacktop+ = N_Base; else success = false; return ; if (stack0 = SHARP && stack1 = N_Base && stack2 = SHARP) printf("#N#n"); break; while (true); success = true;int main(int argc, char *argv) if (argc = 2) fp = fopen(argv1, "r"); init(); parser(); if (success) printf("This is a legal expression."); else printf("This is a illegal expression."); else printf("参数错误！n"); return 0;专心-专注-专业
