编译原理-词法分析报告.docx

词法分析器实验报告n 实验要求自行设计单词的组成和分类，利用有穷自动机实现词法分析程序。n 实验内容(一) 功能描述对给定的正则表达式建立最小化DFA，并以此对输入的源程序做词法分析，输出源程序的Token序列(二) 程序原理l 算法一：根据正则表达式直接构建DFA该算法主要根据编译原理3.9.5节所讲述，根据正则表达式直接构建DFA。算法：从一个正则表达式r构造DFA。输入：一个正则表达式。输出：一个识别L（r）的DFAD。方法：1) 根据拓展的正则表达式（r）#构造出一个抽象语法树T。2) 使用3.9.3节和3.9.4节的方法，计算得到T的函数nullable,firstpos,lastpos,followpos。3) 使用以下所示的过程，构造出D的状态集Dstates和D的转换函数Dtran。所有节点的转换函数的并集便是DFAD。D的状态就是T中的位置集合。每个状态最初都是“未标记的”，当我们开始考虑某个状态的离开转换时，该状态变成“已标记的”。D的开始状态是firstpos（n0），其中节点n0是T的根节点。这个DFA的接受状态集合是那些包含了和结束标记#对应的位置的状态。初始化Dstates，使之只包含未标记的状态firstpos（n0）,其中n0是（r）#的抽象语法树的根节点；While(Dstates中存在未标记的状态S)标记S；For（每个输入符号a）令U为S中和a对应的所有位置p的followpos(p)的并集；If（U不在Dstates中）将U作为未标记的状态加入到Dstates中；DtranS,a=U;l 算法二：根据拓展的正则表达式（r）#构造出一棵抽象语法树T该算法的具体实现编译原理书中并没有涉及到，该算法的实现是经过本人思考而得。算法：根据拓展的正则表达式（r）#构造出一棵抽象语法树T。输入：拓展的正则表达式（r）#。输出：一棵抽象语法树T。方法：vector op (, ), |, *, +, #, cat ;char table7 = , , -, , , , , , , , , , , , , , , , , , , , , , , , , , , -, -, -, -, -, -, - , , , , , , ;1） 该正则表达式含有7种运算符，对这7种运算符建立优先级表。具体如下所示。其中，”#”是正则表达式结束符，”cat”是连接符。2） 准备两个栈，一个是操作符栈，用于保存正则表达式中的操作符（即上表所示的7个运算符）；另一个是语法树节点栈，用于保存语法树的节点。设操作符栈顶元素为otop，节点栈栈顶元素为ntop。3） 遍历正则表达式，得到正则表达式的元素r。 若r为操作符，判断Priority(otop，r)，Priority(otop，r)为r与otop的运算符优先级。若Priority(otop，r) = ，则将r入运算符栈。否则，依r的类型，对语法树节点栈进行相应操作，并对语法树插入新节点。若r为操作数，则插入节点栈，若发现有连续的操作数，则对操作符栈插入“cat”。当r = “#”时，将两个栈中的剩余元素处理完毕，结束遍历正则表达式，并得到一棵完整的抽象语法树。l 算法三：计算语法树nullable,firstpos,lastpos,followpos我们可以使用递归的过程计算nullable,firspos和lastpos。具体如下所示：节点nNullable(n)Firstpos(n)Lastpos(n)一个标号为null的叶子节点True一个位置为i的叶子节点Falseii一个or-节点 n = c1 | c2Nullable(c1) or Nullable(c2)Firstpos(c1) Firstpos(c2)Firstpos(c1) Firstpos(c2)一个cat-节点 n = c1 c2Nullable(c1) and Nullable(c2)If(Nullable(c1) Firstpos(c1) Firstpos(c2)Else Firstpos(c1)If(Nullable(c2) Firstpos(c1) Firstpos(c2)Else Firstpos(c2)一个star-节点 n = c1 *trueFirstpos(c1)Firstpos(c1)一个add-节点 n = c1 +falseFirstpos(c1)Firstpos(c1)Followpos的计算如下：1) 如果n是一个cat节点，且其左右子节点分别为c1,c2，那么对于lastpos（c1）中的每一个位置i，firstpos（c2）中的所有位置都在followpos(i)中。2) 如果n是一个star节点，并且i是lastpos（n）中的一个位置，那么firstpos（n）中的所有位置都在followpos（i）中。l 算法四：根据DFA，对源程序输出Token序列输入：源程序。输出：Token序列。方法：遍历源程序，判断是否为保留字，若是保留字，则直接输出该Token。否则，将读取的字符串送入有穷自动机，若DFA能够达到终结状态，表示源程序合法，输出该Token。否则，对该字符串报错。（三）程序总流程图(四) 程序源代码#include using namespace std;struct TreeNode string value; TreeNode *leftChild; TreeNode *rightChild; TreeNode (string v = , TreeNode *l = nullptr, TreeNode *r = nullptr) : value (v), leftChild (l), rightChild (r) *treeRoot;struct Program Program() Input(); Create(); struct Operator Operator() SetPriorityTable(); vector op (, ), |, *, +, #, cat ; bool IsOperator (const string &s) for (auto i = op.begin(); i != op.end(); +i) if (s = *i) return true; return false; mappair, char priorityTable; void SetPriorityTable() const int opSize = op.size(); char table7 = , , -, , , , , , , , , , , , , , , , , , , , , , , , , , , -, -, -, -, -, -, - , , , , , , ; for (int i = 0; i opSize; +i) for (int j = 0; j opSize; +j) priorityTablemake_pair (opi, opj) = tableij; char Priority (const string &a, const string &b) return priorityTablemake_pair (a, b); opr; struct Separator set separator =, +, -, *, (, ), , ;, |, #, . ,; bool operator() (const char &c) for (auto i = separator.begin(); i != separator.end(); +i) if (c = *i) return true; return false; separator; string inStr; void Input() ifstream inGrammer (grammer.txt); char c; while ( (c = inGrammer.get() != EOF) if (separator (c) inStr += string ( ) + c + ; else inStr += c; inStr += #; cout void Input() : inStr endl; void Create() stringstream ss (inStr); string tmp; stackpair operatorStack; stackpair nodeStack; int cnt = 0; while (ss tmp) +cnt; cout tmp ; if (tmp.size() = 1 & opr.IsOperator (tmp) if (tmp = #) cout endl; cout nodeStack.size() nodeStack.size() endl; cout operatorStack.size() operatorStack.size() endl; while (!operatorStack.empty() auto otop = operatorStack.top(); cout top: otop.first endl; if (otop.first = | | otop.first = cat) if (nodeStack.size() = 1) auto a = nodeStack.top(); nodeStack.pop(); treeRoot = new TreeNode (otop.first, a.first); nodeStack.push (make_pair (treeRoot, cnt); cout delete value insert otop.first endl; return; else operatorStack.pop(); auto a = nodeStack.top(); nodeStack.pop(); auto b = nodeStack.top(); nodeStack.pop(); treeRoot = new TreeNode (otop.first, b.first, a.first); nodeStack.push (make_pair (treeRoot, otop.second); cout delete value value insert otop.first endl; / cout operatorStack.top().first value endl; / assert (operatorStack.empty(); / assert (nodeStack.empty(); return; if (tmp = * | tmp = +) auto a = nodeStack.top(); nodeStack.pop(); nodeStack.push (make_pair (new TreeNode (tmp, a.first), cnt); cout delete value insert tmp endl; continue; if (tmp = ) while (operatorStack.top().first != () auto otop = operatorStack.top(); if (otop.first = | | otop.first = cat) operatorStack.pop(); auto a = nodeStack.top(); nodeStack.pop(); auto b = nodeStack.top(); nodeStack.pop(); nodeStack.push (make_pair (new TreeNode (otop.first, b.first, a.first), otop.second); cout delete value value insert otop.first endl; else if (otop.first = * | otop.first = +) operatorStack.pop(); auto a = nodeStack.top(); nodeStack.pop(); nodeStack.push (make_pair (new TreeNode (otop.first, a.first), otop.second); cout delete value insert otop.first = 2) operatorStack.pop(); auto a = nodeStack.top(); nodeStack.pop(); auto b = nodeStack.top(); nodeStack.pop(); nodeStack.push (make_pair (new TreeNode (cat, b.first, a.first), b.second); cout delete value value; cout insert cat ; operatorStack.push (make_pair (tmp, cnt); cout insert tmp ) if (otop.first = | | otop.first = cat) if (!operatorStack.empty() & opr.Priority (otop.first, tmp) = ) otop = operatorStack.top(); if (otop.first != cat) operatorStack.pop(); auto a = nodeStack.top(); nodeStack.pop(); auto b = nodeStack.top(); nodeStack.pop(); nodeStack.push (make_pair (new TreeNode (otop.first, b.first, a.first), b.second); cout delete value value insert otop.first ; operatorStack.push (make_pair (tmp, cnt); cout insert tmp; else if (opr.Priority (otop.first, tmp) = -) operatorStack.push (make_pair (tmp, cnt); cout insert tmp; else operatorStack.push (make_pair (tmp, cnt); cout insert tmp; else if (!nodeStack.empty() & operatorStack.empty() operatorStack.push (make_pair (cat, cnt); cout insert cat; nodeStack.push (make_pair (new TreeNode (tmp), cnt); cout insert tmp; else if (!operatorStack.empty() & !nodeStack.empty() & operatorStack.top().second nodeStack.top().second) operatorStack.push (make_pair (cat, cnt); cout insert cat; nodeStack.push (make_pair (new TreeNode (tmp), cnt); cout insert tmp; else nodeStack.push (make_pair (new TreeNode (tmp), cnt); cout insert tmp; cout endl; void Output (TreeNode *node = treeRoot) if (node) cout value leftChild); Output (node-rightChild); bool IsLeaf (const TreeNode *node) return node-leftChild = nullptr & node-rightChild = nullptr; map posNode; map posInt; map nullAble; mapTreeNode *, set firstPos; mapTreeNode *, setlastPos; mapint, setfollowPos; void GetPos (TreeNode *node, int &i) if (node = nullptr) return; if (IsLeaf (node) / if(node-value!=_null) / inOper.insert(node-value); posNodenode = +i; posInti = node; return; GetPos (node-leftChild, i); GetPos (node-rightChild, i); void GetNullable (TreeNode *node = treeRoot) if (node = nullptr) return; if (IsLeaf (node) if (node-value = _null) nullAblenode = false; else nullAblenode = true; return; else if (node-value = |) GetNullable (node-leftChild); GetNullable (node-rightChild); bool l = nullAblenode-leftChild; bool r = nullAblenode-rightChild; nullAblenode = l | r; else if (node-value = cat) GetNullable (node-leftChild); GetNullable (node-rightChild); bool l = nullAblenode-leftChild; bool r = nullAblenode-rightChild; nullAblenode = l & r; else if (node-value = *) nullAblenode = true; GetNullable (node-leftChild); GetNullable (node-rightChild); else if (node-value = +) nullAblenode = false; GetNullable (node-leftChild); GetNullable (node-rightChild); void GetFirstPos (TreeNode *node = treeRoot) if (node = nullptr) return; if (IsLeaf (node) if (node-value != _null) firstPosnode.insert (posNodenode); return; else if (node-value = |) GetFirstPos (node-leftChild); GetFirstPos (node-rightChild); set l = firstPosnode-leftChild; set r = firstPosnode-rightChild; set tmp (l); for (auto i = r.begin(); i != r.end(); +i) tmp.insert (*i); firstPosnode = tmp; else if (node-value = cat) if (nullAblenode-leftChild) GetFirstPos (node-leftChild); GetFirstPos (node-rightChild); set l = firstPosnode-leftChild; set r = firstPosnode-rightChild; set tmp (l); for (auto i = r.begin(); i != r.end(); +i) tmp.insert (*i); firstPosnode = tmp; else GetFirstPos (node-leftChild); GetFirstPos (node-rightChild); firstPosnode = firstPosnode-leftChild; else if (node-value = *) GetFirstPos (node-leftChild); GetFirstPos (node-rightChild); firstPosnode = firstPosnode-leftChild; else if (node-value = +) GetFirstPos (node-leftChild); GetFirstPos (node-rightChild); firstPosnode = firstPosnode-leftChild; void GetLastPos (TreeNode *node = treeRoot) if (node = nullptr) return; if (IsLeaf (node) if (node-value != _null) lastPosnode.insert (posNodenode); return; else if (node-value = |) GetLastPos (node-leftChild); GetLastPos (node-rightChild); set l = lastPosnode-leftChild; set r = lastPosnode-rightChild; set tmp (l); for (auto i = r.begin(); i != r.end(); +i) tmp.insert (*i); lastPosnode = tmp; else if (node