實驗4LRk分析器

1、實驗四 LR（k）分析器設計一、實驗目的 （1）掌握下推機這一數(shù)學模型的結構和理論，并深刻理解下推自動機在LR分析法中的應用（即LR分析器）。 （2）掌握LR分析法的思想，學會特定分析表的構造方法，利用給出的分析表進行LR分析。二、實驗內(nèi)容根據(jù)課堂講授的形式化算法，編制程序?qū)崿F(xiàn)對以下語法進行自底向上語法分析的LR分析器，設計分析表，對給出的輸入語句進行語法分析，判斷是否符合相應的文法要求。Program ® blockblock ® stmts stmts ® stmt stmts | estmt ® id = E ; | while ( bool )

2、stmt | blockbool ® E <= E | E >= EE ® E + T | T T ® id | num輸入語句：三、實驗要求要求實現(xiàn)以下功能：a)設計分析表和語句的輸入；b)要實現(xiàn)通用的LR分析思想的源代碼；c)輸出對語句的語法分析判斷結果，如果可能給出錯誤的信息提示。四、實現(xiàn)方法根據(jù)課本的LR分析器模型和LR分析算法，完成LR分析。對要求中的錯誤信息提示，指的是對應分析表中的空白處，每一個空白的地方都應該有對應的錯誤情況，因而有相應的錯誤信息。注意這里的語法分析，是在詞法分析的基礎上進行的。五、識別活前綴的DFA六、SLR(1)分析

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

4、 FOLLOW(stmt) = , id, while, FOLLOW(bool) = )FOLLOW(E) = <=, >=, +, ;, )FOLLOW(T) = <=, >=, +, ;, )七、主要代碼#ifndef LRANALYZER_H#define LRANALYZER_H#include <QObject>#include <QStack>#include <QMap>#include <QTableWidget>#include "Automation.h"class LRAnaly

5、zer : public QObject Q_OBJECTpublic: explicit LRAnalyzer(QObject *parent = 0); bool begin(QString, QTableWidget *); bool loadTable(QString);private: Automation *lex; QString table3030; QMap<int, int> trans; QMap<int, QString> trans2; int deriveArg30; int deriveLeft30;#endif / LRANALYZER_

6、H#include "LRAnalyzer.h"LRAnalyzer:LRAnalyzer(QObject *parent) : QObject(parent) lex = new Automation; lex->addKeyword("while"); / 2000 lex->addToken("+"); / 1000 lex->addToken("="); / 1001 lex->addToken("<="); / 1002 lex->addToken(

7、">="); / 1003 lex->addToken(""); / 1004 lex->addToken(""); / 1005 lex->addToken("("); / 1006 lex->addToken(")"); / 1007 lex->addToken(""); / 1008 lex->addToken("#"); / 1009 trans.insert(1004, 0); trans2.insert

8、(1004, ""); trans.insert(1005, 1); trans2.insert(1005, ""); trans.insert(1006, 2); trans2.insert(1006, "("); trans.insert(1007, 3); trans2.insert(1007, ")"); trans.insert(1000, 4); trans2.insert(1000, "+"); trans.insert(1001, 5); trans2.insert(1001,

9、"="); trans.insert(1002, 6); trans2.insert(1002, "<="); trans.insert(1003, 7); trans2.insert(1003, ">="); trans.insert(1008, 8); trans2.insert(1008, ""); trans.insert(3000, 9); trans2.insert(3000, "id"); trans.insert(3001, 10); trans2.insert(30

10、01, "num"); trans.insert(2000, 11); trans2.insert(2000, "while"); trans.insert(1009, 12); trans2.insert(1009, "#"); trans.insert(4001, 13); trans2.insert(4001, "block"); / block trans.insert(4002, 14); trans2.insert(4002, "stmts"); / stmts trans.inse

11、rt(4003, 15); trans2.insert(4003, "stmt"); / stmt trans.insert(4004, 16); trans2.insert(4004, "bool"); / bool trans.insert(4005, 17); trans2.insert(4005, "E"); / E trans.insert(4006, 18); trans2.insert(4006, "T"); / T /* 1Program -> block 2Block -> stmts

12、 3Stmts -> stmt stmts 4Stmts -> eps 5Stmt -> id = E; 6Stmt -> while ( bool ) stmt 7Stmt -> block 8Bool -> E <= E 9Bool -> E >= E 10E -> E + T 11E -> T 12T -> id 13T -> num */ deriveArg1 = 1; deriveArg2 = 3; deriveArg3 = 2; deriveArg4 = 0; deriveArg5 = 4; derive

13、Arg6 = 5; deriveArg7 = 1; deriveArg8 = 3; deriveArg9 = 3; deriveArg10 = 3; deriveArg11 = 1; deriveArg12 = 1; deriveArg13 = 1; deriveLeft2 = 4001; deriveLeft3 = 4002; deriveLeft4 = 4002; deriveLeft5 = 4003; deriveLeft6 = 4003; deriveLeft7 = 4003; deriveLeft8 = 4004; deriveLeft9 = 4004; deriveLeft10 =

14、 4005; deriveLeft11 = 4005; deriveLeft12 = 4006; deriveLeft13 = 4006;bool LRAnalyzer:loadTable(QString filePath) if (!freopen(filePath.toLatin1(), "r", stdin) return false; char buf256; int line = 0; while (gets(buf) int pos = 0, cnt = 0; while (bufpos) if (bufpos = 't') cnt+, pos+

15、; else while (bufpos != 't' && bufpos != '0') tablelinecnt.append(bufpos+); line+; return true;bool LRAnalyzer:begin(QString src, QTableWidget *w) src.append("#"); lex->begin(src); MatchResult rlt; QStack<int> state; QStack<int> optr; state.push(0); o

16、ptr.push(1009); while (rlt = 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<int>:ite

17、rator it = state.begin(); it != state.end(); it+) temp.append(QString("%1 ").arg(*it); w->setItem(w->rowCount() - 1, 1, new QTableWidgetItem(temp); temp.clear(); for (QStack<int>:iterator it = optr.begin(); it != optr.end(); it+) temp.append(QString("%1 ").arg(trans2*

18、it); w->setItem(w->rowCount() - 1, 2, new QTableWidgetItem(temp); if (rlt.type != -1) w->setItem(w->rowCount() - 1, 3, new QTableWidgetItem(rlt.str + src.mid(rlt.line).replace(QRegExp("nrst"), QString:null); else w->setItem(w->rowCount() - 1, 3, new QTableWidgetItem("

19、;Lexical Analyze Error"); return false; if (s.isEmpty() /qDebug() << "Error" w->setItem(w->rowCount() - 1, 4, new QTableWidgetItem("Error"); return false; else if (s0 = 'S') state.push(s.mid(1).toInt(); optr.push(rlt.type); w->setItem(w->rowCount() - 1, 4, new QTableWidgetItem(s); /qDe