实验4-LR(k)分析器.doc

1、实 验 四 LR（ k） 分 析 器 设 计一 、 实 验 目 的（ 1） 掌 握 下 推 机 这 一 数 学 模 型 的 结 构 和 理 论 ， 并 深 刻 理 解 下 推 自 动 机 在LR分 析 法 中 的 应 用 （ 即LR分 析 器 ） 。（ 2） 掌 握 LR分 析 法 的 思 想 ， 学 会 特 定 分 析 表 的 构 造 方 法 ， 利 用 给 出 的 分 析 表 进 行LR分 析 。二 、 实 验 内 容根 据 课 堂 讲 授 的 形 式 化 算 法 ， 编 制 程 序 实 现 对 以 下 语 法 进 行 自 底 向 上 语 法 分 析 的LR分 析 器 ，设 计 分 析 表

2、 ， 对 给 出 的 输 入 语 句 进 行 语 法 分 析 ， 判 断 是 否 符 合 相 应 的 文 法 要 求 。Program blockblock stmts stmts stmt stmts | stmt id = E ; | while ( bool ) stmt | blockbool E = EE E + T | T T id | num输入语句：三 、 实 验 要 求要 求 实 现 以 下 功 能 ：a) 设 计 分 析 表 和 语 句 的 输 入 ；b) 要 实 现 通 用 的 LR分 析 思 想 的 源 代 码 ；c) 输 出 对 语 句 的 语 法 分 析 判 断 结

3、 果 ， 如 果 可 能 给 出 错 误 的 信 息 提 示 。四 、 实 现 方 法根 据 课 本 的 LR分 析 器 模 型 和 LR分 析 算 法 ， 完 成 LR分 析 。 对 要 求 中 的 错 误 信 息 提 示 ， 指 的 是 对应 分 析 表 中 的 空 白 处 ， 每 一 个 空 白 的 地 方 都 应 该 有 对 应 的 错 误 情 况 ， 因 而 有 相 应 的 错 误 信 息 。注 意 这 里 的 语 法 分 析 ， 是 在 词 法 分 析 的 基 础 上 进 行 的 。五 、 识 别 活 前 缀 的 DFA六 、 SLR(1)分 析 表 Program - block

4、 Block - stmts Stmts - stmt stmts Stmts - eps Stmt - id = E; Stmt - while ( bool ) stmt Stmt - block Bool - E E = E E - E + T E - T T - id T - numFOLLOW(program) = #FOLLOW(block) = #, , id, while, FOLLOW(stmts) = FOLLOW(stmt) = , id, while, FOLLOW(bool) = )FOLLOW(E) = =, +, ;, )FOLLOW(T) = =, +, ;,

5、)七 、 主 要 代 码#ifndef LRANALYZER_H#define LRANALYZER_H#include #include #include #include #include “Automation.h“class LRAnalyzer : public QObjectQ_OBJECTpublic:explicit LRAnalyzer(QObject *parent = 0);bool begin(QString, QTableWidget *);bool loadTable(QString);private:Automation *lex;QString table303

6、0;QMap trans;QMap trans2;int deriveArg30;int deriveLeft30;#endif / LRANALYZER_H#include “LRAnalyzer.h“LRAnalyzer:LRAnalyzer(QObject *parent) : QObject(parent)lex = new Automation;lex-addKeyword(“while“); / 2000lex-addToken(“+“); / 1000lex-addToken(“=“); / 1001lex-addToken(“addToken(“=“); / 1003lex-a

7、ddToken(“); / 1004lex-addToken(“); / 1005lex-addToken(“(“); / 1006lex-addToken(“)“); / 1007lex-addToken(“;“); / 1008lex-addToken(“#“); / 1009trans.insert(1004, 0); trans2.insert(1004, “);trans.insert(1005, 1); trans2.insert(1005, “);trans.insert(1006, 2); trans2.insert(1006, “(“);trans.insert(1007,

8、3); trans2.insert(1007, “)“);trans.insert(1000, 4); trans2.insert(1000, “+“);trans.insert(1001, 5); trans2.insert(1001, “=“);trans.insert(1002, 6); trans2.insert(1002, “=“);trans.insert(1008, 8); trans2.insert(1008, “;“);trans.insert(3000, 9); trans2.insert(3000, “id“);trans.insert(3001, 10); trans2

9、.insert(3001, “num“);trans.insert(2000, 11); trans2.insert(2000, “while“);trans.insert(1009, 12); trans2.insert(1009, “#“);trans.insert(4001, 13); trans2.insert(4001, “block“); / blocktrans.insert(4002, 14); trans2.insert(4002, “stmts“); / stmtstrans.insert(4003, 15); trans2.insert(4003, “stmt“); /

10、stmttrans.insert(4004, 16); trans2.insert(4004, “bool“); / booltrans.insert(4005, 17); trans2.insert(4005, “E“); / Etrans.insert(4006, 18); trans2.insert(4006, “T“); / T/*1 Program - block2 Block - stmts 3 Stmts - stmt stmts4 Stmts - eps5 Stmt - id = E;6 Stmt - while ( bool ) stmt7 Stmt - block8 Boo

11、l - E E = E10 E - E + T11 E - T12 T - id13 T - num*/deriveArg1 = 1; deriveArg2 = 3;deriveArg3 = 2; deriveArg4 = 0;deriveArg5 = 4; deriveArg6 = 5;deriveArg7 = 1; deriveArg8 = 3;deriveArg9 = 3; deriveArg10 = 3;deriveArg11 = 1; deriveArg12 = 1;deriveArg13 = 1;deriveLeft2 = 4001; deriveLeft3 = 4002;deri

12、veLeft4 = 4002; deriveLeft5 = 4003;deriveLeft6 = 4003; deriveLeft7 = 4003;deriveLeft8 = 4004; deriveLeft9 = 4004;deriveLeft10 = 4005; deriveLeft11 = 4005;deriveLeft12 = 4006; deriveLeft13 = 4006;bool LRAnalyzer:loadTable(QString filePath)if (!freopen(filePath.toLatin1(), “r“, stdin)return false;char

13、 buf256;int line = 0;while (gets(buf)int pos = 0, cnt = 0;while (bufpos)if (bufpos = t)cnt+, pos+;elsewhile (bufpos != t line+;return true;bool LRAnalyzer:begin(QString src, QTableWidget *w)src.append(“#“);lex-begin(src);MatchResult rlt;QStack state;QStack optr;state.push(0);optr.push(1009);while (r

14、lt = lex-match(), rlt.type != 0)analyze:QString s = tablestate.top()transrlt.type;w-setRowCount(w-rowCount() + 1);w-setItem(w-rowCount() - 1, 0, new QTableWidgetItem(QString(“%1“).arg(w-rowCount();QString temp;for (QStack:iterator it = state.begin(); it != state.end(); it+)temp.append(QString(“%1 “)

15、.arg(*it);w-setItem(w-rowCount() - 1, 1, new QTableWidgetItem(temp);temp.clear();for (QStack:iterator it = optr.begin(); it != optr.end(); it+)temp.append(QString(“%1 “).arg(trans2*it);w-setItem(w-rowCount() - 1, 2, new QTableWidgetItem(temp);if (rlt.type != -1)w-setItem(w-rowCount() - 1, 3,new QTab

16、leWidgetItem(rlt.str + src.mid(rlt.line).replace(QRegExp(“nrst“), QString:null);elsew-setItem(w-rowCount() - 1, 3, new QTableWidgetItem(“Lexical Analyze Error“);return false;if (s.isEmpty()/qDebug() setItem(w-rowCount() - 1, 4, new QTableWidgetItem(“Error“);return false;else if (s0 = S)state.push(s.

17、mid(1).toInt();optr.push(rlt.type);w-setItem(w-rowCount() - 1, 4, new QTableWidgetItem(s);/qDebug() setItem(w-rowCount() - 1, 4, new QTableWidgetItem(s);if (s = “acc“)break;int r = s.mid(1).toInt();for (int i = 0; i deriveArgr; i+)optr.pop(), state.pop();optr.push(deriveLeftr);/qDebug() “Reduce“;sta

18、te.push(tablestate.top()transoptr.top().toInt();/qDebug() “Goto“;goto analyze;return true;八 、 运 行 截 图九 、 实 验 总 结 与 体 会在词法分析的基础上，实现了一个 SLR（1）分析器，可以对给定的文法进行 LR 分析，并输出分析过程。SLR（1）分析表通过文件加载。分析过程中遇到错误可以及时终止分析过程，防止低效处理。通过本实验，我熟悉了 SLR（1）分析表的构造方法，深刻理解了 LR 分析的过程。这个 SLR（1）分析表比较复杂，构造的时候出现了很多错误，导致程序无法正确分析。针对出错的地方，我对照程序的输出以及 DFA，找到了分析表中填写错误的项目，反复调试修改，完成了这个分析器。