精华内容
下载资源
问答
  • 2017-12-18 20:21:00

    结构

    • main.cpp包含了主函数和LL1语法分析过程的调用
    • Base.h和Base.cpp定义了类Base, 类Base用于存储产生式、符号表、FIRST集合FOLLOW集(还可应用于LR分析,故独立出来)
    • LL1.h和LL1.cpp定义了类

    LL1, 类LL1继承了Base, 用于生成预测表和分析输入语句.

    记号和规定

    记号和规定

    • $表示空ε, #表示终止
    • 大写字母为非终结符.
    • 用单个字母表示一个符号
    • 默认第一个产生式的左边那个非终结符就是开始符号
    • 输入的产生式分开写(比如A->a|b, 要输入A->a和A->b才能处理)

    代码

    Base.h

    #ifndef _BASE_H_
    #define _BASE_H_
    #include <iostream>
    #include <iomanip>
    #include <string>
    #include <vector>
    #include <set>
    
    #define maxsize 100
    
    using namespace std;
    
    struct node {  // 产生式的数据结构
        char left;
        string right;
    };
    
    class Base {
    protected:
        int T;
        node production[maxsize]; // 产生式集
    
        set<char> firstSet[maxsize];  // First集
        set<char> followSet[maxsize];  // Follow集
        vector<char> terminalNoEmpty; // 去$(空)的终结符
        vector<char> terminal;  // 终结符
        vector<char> nonterminal;  // 非终结符
    
        bool isNonterminal(char c);
        int getIndex(char target);  // 获得target在终结符集合中的下标
        int getNIndex(char target);  // 获得target在非终结符集合中的下标
        void getFirst(char target);  // 得到First(target)
        void getFollow(char target);  // 得到Follow(target)
    
    public:
        Base() {};
    
        void inputAndSolve();  // 处理和求出First和Follow集
        void displayFirstAndFollow();  // 输出First和Follow集
    
    };
    #endif 
    
    

    Base.cpp

    #include "Base.h"
    
    bool Base::isNonterminal(char c) { // 判断c是否为非终结符
        if (c >= 'A' && c <= 'Z')
            return true;
        return false;
    }
    int Base::getNIndex(char target) {  // 获得target在非终结符集合中的下标
        for (int i = 0; i<nonterminal.size(); i++) {
            if (target == nonterminal[i])
                return i;
        }
        return -1;
    }
    int Base::getIndex(char target) {  // 获得target在终结符集合中的下标
        for (int i = 0; i<terminalNoEmpty.size(); i++) {
            if (target == terminalNoEmpty[i])
                return i;
        }
        return -1;
    }
    
    void Base::getFirst(char target) {  // 求FIRST(target)
        int countEmpty = 0;  // 用于最后判断是否有空
        int isEmpty = 0;
        int targetIndex = getNIndex(target);
        for (int i = 0; i < T; i++) {
            if (production[i].left == target) {  // 匹配产生式左部
                if (!isNonterminal(production[i].right[0])) {  // 对于终结符,直接加入first
                    firstSet[targetIndex].insert(production[i].right[0]);
                }
                else {
                    for (int j = 0; j < production[i].right.length(); j++) { // X->Y1..Yj..Yk是一个产生式
                        char Yj = production[i].right[j];
                        if (!isNonterminal(Yj)) {  // Yj是终结符(不能产生空),FIRST(Yj)=Yj加入FIRST(X),不能继续迭代,结束
                            firstSet[targetIndex].insert(Yj);
                            break;
                        }
                        getFirst(Yj);// Yj是非终结符,递归 先求出FIRST(Yj)
    
                        set<char>::iterator it;
                        int YjIndex = getNIndex(Yj);
                        for (it = firstSet[YjIndex].begin(); it != firstSet[YjIndex].end(); it++) {
                            if (*it == '$')  // 遍历查看FIRST(Yj)中是否含有'$'(能产生空)
                                isEmpty = 1;
                            else
                                firstSet[targetIndex].insert(*it);//将FIRST(Yj)中的非$就加入FIRST(X)
                        }
                        if (isEmpty == 0)  // Yj不能产生空, 迭代结束
                            break;
                        else {   //  Yj能产生空
                            countEmpty += isEmpty;
                            isEmpty = 0;
                        }
                    }
                    if (countEmpty == production[i].right.length())//所有右部first(Y)都有$(空),将$加入FIRST(X)中
                        firstSet[getNIndex(target)].insert('$');
                }
            }
        }
    }
    
    void Base::getFollow(char target) {  // 求FOLLOW(target)
        int targetIndex = getNIndex(target);
        for (int i = 0; i<T; i++) {
            int index = -1;
            int len = production[i].right.length();
            for (int j = 0; j < len; j++) {  // 寻找target在产生式中的位置index
                if (production[i].right[j] == target) {
                    index = j;
                    break;
                }
            }
            if (index != -1 && index < len - 1) {  // 找到target在产生式中的位置index
                                                   // 存在A->αBβ, 将FIRST(β)中除了空$之外的所有放入FOLLOW(B)中
                                                   // 这里B对应target, β对应nxt
                char nxt = production[i].right[index + 1];
                if (!isNonterminal(nxt)) {  // β是终结符 FIRST(β)=β,直接插入β
                    followSet[targetIndex].insert(nxt);
                }
                else {  // β是非终结符
                    int hasEmpty = 0;
                    set<char>::iterator it;
                    int nxtIndex = getNIndex(nxt);  // 插入FIRST(β)中除了空$之外的所有
                    for (it = firstSet[nxtIndex].begin(); it != firstSet[nxtIndex].end(); it++) {
                        if (*it == '$')
                            hasEmpty = 1;
                        else
                            followSet[targetIndex].insert(*it);
                    }
    
                    if (hasEmpty && production[i].left != target) { // 存在A->αBβ且FIRST(β)->$
                                                                 // FOLLOW(A)放在FOLLOW(B)中
                        getFollow(production[i].left);
                        set<char>::iterator it;
                        char tmp = production[i].left;
                        int tmpIndex = getNIndex(tmp);
                        for (it = followSet[tmpIndex].begin(); it != followSet[tmpIndex].end(); it++)
                            followSet[targetIndex].insert(*it);
                    }
                }
            }
            else if (index != -1 && index == len - 1 && target != production[i].left) {  // 存在A->αB ,FOLLOW(A)放在FOLLOW(B)中
                getFollow(production[i].left);
                set<char>::iterator it;
                char tmp = production[i].left;
                int tmpIndex = getNIndex(tmp);
                for (it = followSet[tmpIndex].begin(); it != followSet[tmpIndex].end(); it++)
                    followSet[targetIndex].insert(*it);
            }
        }
    }
    
    void Base::inputAndSolve() {  // 处理和求出First和Follow集
        string s;
        cout << "输入的产生式的个数:" << endl;
        cin >> T;
        cout << "输入的产生式:" << endl;
        for (int index = 0; index < T; index++) {  // 处理每一个产生式
            cin >> s;
            string temp = "";  // 存储去掉空格的产生式
            for (int i = 0; i < s.length(); i++) {  // 去掉产生式中的' '
                if (s[i] != ' ')
                    temp += s[i];
            }
            production[index].left = temp[0];  // 产生式的左部
            for (int i = 3; i<temp.length(); i++) // 产生式的右部
                production[index].right += temp[i];
    
            for (int i = 0; i < temp.length(); i++) {  // 存储所有终结符和非终结符
                if (i == 1 || i == 2) continue;  // 跳过产生符号->
                if (isNonterminal(temp[i])) {  //插入一个非终结符
                    int flag = 0;
                    for (int j = 0; j < nonterminal.size(); j++) {
                        if (nonterminal[j] == temp[i]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) nonterminal.push_back(temp[i]);
                }
                else {                       //插入一个终结符
                    int flag = 0;
                    for (int j = 0; j < terminal.size(); j++) {
                        if (terminal[j] == temp[i]) {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) terminal.push_back(temp[i]);
                }
            }
        }
        terminal.push_back('#');
    
        for (int i = 0; i < terminal.size(); i++) { // 存储没有$符号的终结符
            if (terminal[i] != '$')
                terminalNoEmpty.push_back(terminal[i]);
        }
    
        // 获得first集
        for (int i = 0; i < nonterminal.size(); i++) {
            getFirst(nonterminal[i]);
        }
    
        // 获得follow集
        for (int i = 0; i < nonterminal.size(); i++) {
            if (i == 0)  // 开始符号, 先加入结束符号
                followSet[0].insert('#');
            getFollow(nonterminal[i]);
        }
    }
    
    void Base::displayFirstAndFollow() {  // 输出First和Follow集
        cout << "FIRST集合" << endl;
        for (int i = 0; i<nonterminal.size(); i++) {
            cout << nonterminal[i] << ": ";
            set<char>::iterator it;
            for (it = firstSet[i].begin(); it != firstSet[i].end(); it++)
                cout << *it << "  ";
            cout << endl;
        }
        cout << endl;
    
        cout << "FOLLOW集合" << endl;
        for (int i = 0; i<nonterminal.size(); i++) {
            cout << nonterminal[i] << ": ";
            set<char>::iterator it;
            for (it = followSet[i].begin(); it != followSet[i].end(); it++)
                cout << *it << "  ";
            cout << endl;
        }
        cout << endl;
    }

    LL1.h

    #ifndef _LL1_H_
    #define _LL1_H_
    
    #include"Base.h"
    
    class LL1 : public Base {
    private:
        vector<char> analyStack; // 分析栈
        vector<char> leftExpr;  // 剩余输入串
        int tableMap[100][100];  // 预测表
    
    public:
        LL1();
    
        void getTable(); // 生成预测表
        void analyExpression(string s);  // 分析输入语句s
        void printPredictTable();  // 输出预测表
        void getResult(); // 综合处理
    };
    #endif
    }

    LL1.cpp

    #include"LL1.h"
    
    LL1::LL1() {
        memset(tableMap, -1, sizeof(tableMap));
    }
    
    void LL1::getTable() {
        for (int index = 0; index < T; index++) {                          // 对于每个产生式(编号index):A->α
            int row = getNIndex(production[index].left);
            int emptyCount = 0;
            for (int i = 0; i < production[index].right.size(); i++) { // 1) 对FIRST(α)中的每个终结符号a,将index加入(A, a)中
                char tmp = production[index].right[i];
                if (!isNonterminal(tmp)) { // tmp是终结符          
                    if (tmp != '$')
                        tableMap[row][getIndex(tmp)] = index;
                    if (tmp == '$') {                              
                        emptyCount++;
                    }
                    break;
                }
                else {  // tmp是非终结符
                    set<char>::iterator it;
                    int tmpIndex = getNIndex(tmp);
                    // 对FIRST(tmp)中的每个终结符号a,将i加入(A, a)中
                    for (it = firstSet[tmpIndex].begin(); it != firstSet[tmpIndex].end(); it++) {
                        tableMap[row][getIndex(*it)] = index;
                    }
                    if (firstSet[tmpIndex].count('$') != 0) {      // 2) 如果空$在FIRST(tmp)中,继续看α中的下一个符号
                        emptyCount++;
                    }
                    else {
                        break;
                    }
                }
            }
    
            // 2) 如果空$在FIRST(α)中,对FOLLOW(A)中的每个终结符或结束符b,将i加入(A,b)中
            if (emptyCount == production[index].right.size()) {
                set<char>::iterator  it;
                for (it = followSet[row].begin(); it != followSet[row].end(); it++) {
                    tableMap[row][getIndex(*it)] = index;
                }
            }
        }
    }
    
    void LL1::analyExpression(string s) {
        for (int i = 0; i < s.size(); i++)
            leftExpr.push_back(s[i]);
        leftExpr.push_back('#');
    
        analyStack.push_back('#');
        analyStack.push_back(nonterminal[0]);  // 加入开始符号
    
        while (analyStack.size() > 0) {
            //cout<<"分析栈:";
            string outs = "";
            for (int i = 0; i < analyStack.size(); i++)
                outs += analyStack[i];
            cout << setw(15) << outs;
    
            //cout<<"剩余输入串:";
            outs = "";
            for (int i = 0; i < leftExpr.size(); i++)
                outs += leftExpr[i];
            cout << setw(15) << outs;
    
            // 匹配
            char char1 = analyStack.back();
            char char2 = leftExpr.front();
            if (char1 == char2 && char1 == '#') {
                cout << setw(15) << "Accepted!" << endl;
                return;
            }
            if (char1 == char2) {
                analyStack.pop_back();
                leftExpr.erase(leftExpr.begin());
                cout << setw(15) << "匹配:" << char1 << endl;
            }
            else if (tableMap[getNIndex(char1)][getIndex(char2)] != -1) {  // 预测表中有推倒项,可进行推导
                int tg = tableMap[getNIndex(char1)][getIndex(char2)];
                analyStack.pop_back();
    
                if (production[tg].right != "$") {
                    for (int i = production[tg].right.length() - 1; i >= 0; i--) // 注意这里是反向的
                        analyStack.push_back(production[tg].right[i]);
                }
    
                cout << setw(15) << "推导:" << production[tg].left << "->" << production[tg].right << endl;
            }
            else {  // 错误
                cout << setw(15) << "error!" << endl;
                return;
            }
        }
    }
    
    void LL1::printPredictTable() {
        // 表头
        for (int i = 0; i < terminalNoEmpty.size(); i++) {
            cout << setw(10) << terminalNoEmpty[i];
        }
        cout << endl;
        for (int i = 0; i < nonterminal.size(); i++) {
            cout << nonterminal[i] << ": ";
            for (int j = 0; j < terminalNoEmpty.size(); j++) {
                if (tableMap[i][j] == -1)
                    cout << setw(10) << "   ";
                else
                    cout << setw(10) << production[tableMap[i][j]].right;
            }
            cout << endl;
        }
        cout << endl;
    }
    
    void LL1::getResult() {
        inputAndSolve();
        displayFirstAndFollow();
        getTable();
        printPredictTable();
        //栈匹配
        string ss;
        cout << "请输入符号串:" << endl;
        cin >> ss;
        cout << setw(15) << "分析栈" << setw(15) << "剩余输入串" << setw(15) << "推导式" << endl;
        analyExpression(ss);
    
    }
    
    }

    main.cpp

    #include "LL1.h"
    #include<stdlib.h>
    
    int main() {
        // $表示空, #表示终止
        LL1 res;
        res.getResult();
        system("pause");
        return 0;
    }

    测试样例

    8
    E->TA
    A->+TA
    A->$
    T->FB
    B->*FB
    B->$
    F->(E)
    F->i
    
    
    i+i*i
    
    更多相关内容
  • 本资源使用C++实现了语法分析器,内容包括C++源代码与exe文件、input.txt和程序运行说明文档。该资源的文字版信息请访问博客《编译原理实践:C++实现语法分析器(学习笔记)》...
  • LL1语法分析器(c++).rar

    2019-06-04 23:12:45
    LL1语法分析器c++实现,first,follow,分析表算法详细注释,
  • 通过LR分析表及三个栈形成对输入表达式的判断! 。
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行
  • 学校老师布置的作业,编译原理实验LR(1)语法分析器,使用C++语言,已经通过VS2019调试通过,欢迎大家下载!
  • C++实现LL(1)法分析器:构造First集、Follow集,分析语法是否符合LL(1),并构造预测分析表。
  • 语法分析器语法分析器语法分析器语法分析器语法分析器语法分析器语法分析器语法分析器语法分析器
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行,代码注释丰富,希望与大家交流学习!欢迎大家下载!
  • 编译原理LR(1)语法分析器 C++实现

    千次阅读 2020-12-10 22:14:43
    LR(1)语法分析器 C++语言编写,已通过VS2019调试 文章目录LR(1)语法分析器一、测试结果二、测试文件三、核心代码四、完整代码感谢阅读!如有错误,恳请指正! 一、测试结果 二、测试文件 在D盘下建立test.txt和...

    LR(1)语法分析器

    C++语言编写,已通过VS2019调试


    一、测试结果

    部分测试结果截图
    部分测试截图


    二、测试文件

    在D盘下建立test.txttoken.txt两个文件(文件路径可自行修改)

    test.txt内容,第一行为终结符集
    =*i
    S->L=R
    S->R
    L->*R
    L->i
    R->L
    
    token.txt内容,为分析字符串
    *i=i
    

    三、核心代码

    void LR1_Analyse() {
    	 CSS_LR1 p;
    	 //初始项目 S’->.S ,# 
    	 p.start = css[0].start + "'";
    	 p.num = 0;//点在最前面 
    	 p.tail.push_back("#");
    	 p.next.push_back(css[0].start);
    
    	 I[0] = CLOSURE(p);//求闭包后的I[0]
    	 I[0].insert(I[0].begin(), p);
    	 I_count = 1;
    
    	 //计算项目集 
    	 for (int i = 0; i < I_count; i++) {//每个项目集  项目集I(i) 
    
    		 cout << "===================" << endl;
    		 cout << "现在在计算项目集I" << i << endl;
    		 showI(I[i]);//展示项目集 
    		 cout << "===================" << endl;
    
    		 //---------求ACTION的r部分-------------- 
    		 vector<CSS_LR1>::iterator t;
    		 for (t = I[i].begin(); t != I[i].end(); t++) {
    			 CSS_LR1 t2 = *t;
    			 if (t2.num == t2.next.size()) {
    				 int num = 0;
    				 for (int xp = 0; xp < CSSCount; xp++) {
    					 if (css[xp].start == t2.start && css[xp].next == t2.next) {
    						 num = xp;
    						 break;
    					 }
    				 }
    				 std::stringstream ss;
    				 ss << num;
    				 string s = ss.str();
    				 for (int q = 0; q < t2.tail.size(); q++) {
    					 ACTION[i][t2.tail[q]] = "r" + s;
    
    				 }
    				 if (t2.num == 1 && t2.next[0] == css[0].start) {
    					 ACTION[i]["#"] = "acc";
    
    				 }
    
    			 }
    
    		 }
    		 //-------------------------------------- 
    
    
    
    		 set<string>::iterator it;
    		 for (it = VN.begin(); it != VN.end(); it++) {  //每个非终结符
    			 vector<CSS_LR1> temp;
    			 for (int j = 0; j < I[i].size(); j++) {
    				 CSS_LR1 lr = I[i][j];
    				 if (lr.num < lr.next.size() && lr.next[lr.num] == *it) {
    					 //cout<<*it<<endl; 
    					 vector<CSS_LR1> t2;
    					 lr.num++;
    					 t2 = CLOSURE(lr);
    					 t2.push_back(lr);
    					 temp = temp + t2;
    
    				 }
    
    			 }
    			 //cout<<"temp.size"<< temp.size()<<endl;
    
    			 if (temp.size() > 0) {
    				 int k;
    				 for (k = 0; k < I_count; k++) {//找一找项目集是否已经存在 
    					 if (cmp_vector(I[k], temp)) {
    						 break;
    
    					 }
    
    				 }
    				 if (k == I_count) {
    					 //产生了新的项目集 
    					 I[I_count] = temp;
    					 cout << "  I" << i << " -- " << *it << "->" << "I" << I_count << endl << endl;
    					 GOTO[i][*it] = I_count;//更新goto表 
    					 I_count++;
    
    				 }
    				 else {
    					 //项目集已经存在,需要自己指向自己
    					 cout << "  I" << i << " -- " << *it << "->" << "I" << k << endl << endl;
    					 GOTO[i][*it] = k;
    
    
    				 }
    
    
    			 }
    
    
    		 }
    		 for (it = VT.begin(); it != VT.end(); it++) {  //每个终结符
    				 //cout<<"项目集I"<<i<<"输入"<<*it<<endl; 
    			 vector<CSS_LR1> temp;
    
    			 for (int j = 0; j < I[i].size(); j++) {
    				 CSS_LR1 lr = I[i][j];
    
    				 if (lr.num < lr.next.size() && lr.next[lr.num] == *it) {
    					 vector<CSS_LR1> t2;
    					 lr.num++;
    					 t2 = CLOSURE(lr);//闭包求出的结果不包含本身 
    					 t2.insert(t2.begin(), lr);/求闭包遇到了一些问题 
    					 //showI(t2);
    					 temp = temp + t2;
    
    				 }
    
    			 }
    			 //cout<<"temp.size"<< temp.size()<<endl;
    			 if (temp.size() > 0) {
    				 int k;
    				 for (k = 0; k < I_count; k++) {//找一找项目集是否已经存在 
    					 if (cmp_vector(I[k], temp)) {
    						 break;
    
    					 }
    
    				 }
    				 if (k == I_count) {
    					 //产生了新的项目集 
    					 I[I_count] = temp;
    					 cout << "  I" << i << " -- " << *it << "->" << "I" << I_count << endl << endl;
    					 std::stringstream ss;
    					 ss << I_count;
    					 string s = ss.str();
    					 ACTION[i][*it] = "S" + s;//更新AVTION表 
    					 I_count++;
    
    				 }
    				 else {
    					 //项目集已经存在,需要自己指向自己
    					 cout << "  I" << i << " -- " << *it << "->" << "I" << k << endl << endl;
    					 std::stringstream ss;
    					 ss << k;
    					 string s = ss.str();
    					 ACTION[i][*it] = "S" + s;
    				 }
    			 }
    		 }
    	 }
     }
    

    四、完整代码

    下载链接


    感谢阅读!

    如有错误,恳请指正!

    展开全文
  • LR(1)语法分析器-QT,C++

    2020-04-13 20:56:44
    基于QT,C++实现的LR(1)语法分析器。输入终结符、非终结符和项目集可以得到语法分析表,然后可以对字符串分析。界面随便写了写,没写分辨率适应屏幕。打开可能怪怪的,去UI调调就好。
  • 语法分析器C++

    2012-05-16 10:40:45
    编译原理语法分析器C++,编译原理试验可以用的
  • 语法分析器 c++实现

    2011-07-08 16:06:46
    C++实现的语法和语义分析/C++实现的语法和语义分析
  • 程序的预定表达式为: E->E+T, E->T, T->T*F, T->F, F->(E), F->i 对该表达进行自上而下的语法分析 输入匹配字符串时,结束输入最后加# 例:请输入分析的字符串:i+i*i#
  • 编译原理的课程设计,用c++完成了词法分析和语法分析的功能,附带结题报告。
  • 编译原理语法分析器C++版 有可运行的源程序
  • 十、实验二:设计SAMPLE语言的语法、语义分析器,输出四元式的中间结果。 检查要求: a)启动程序后,先输出作者姓名、班级、学号(可用汉语、英语或拼音)。 b)请求输入测试程序名,键入程序名后自动开始编译。 c)...
  • 一个简单的语法分析器的实现,毕业设计的题目 C++。 这是我毕业设计的代码,一个简单的LR(0)分析程序的实现,算法是课本给出的,代码是我写的。 C++ 语法分析 LR语法分析
  • 递归下降语法分析器C++实现

    热门讨论 2009-05-24 01:32:00
    一个简单的递归下降语法分析器C++实现,主要是理解编译原理
  • LL(1)语法分析器C++

    热门讨论 2009-12-23 22:59:18
    LL(1)语法分析器,是C++版的,绝对能运行,它的文法是依靠用文件输入的,你只要把你需要输入的文法写在"输入文件.txt"中就可以了
  • c++写的C-语法分析器源代码,用c++写的C-语法分析器源代码. 用c++写的C-语法分析器源代码,用c++写的C-语法分析器源代码.
  • 编译原理实验 预测分析词法分析器 c++语言编写,内附测试用例1.txt
  • 构建LL(1)预测分析表,并用C++编程实现LL(1)语法分析器 【输入形式】 一个句子 【输出形式】 若句子语法正确,输出"Syntax analysis is right" 若语法语法错误,输出"Error on syntax analysis" 注:输出不包括...

    【问题描述】

    给定以下文法G[E]:
    E->TE′
    E′->+TE′| ε
    T->FT′
    T′->*FT′| e
    F->a | (E)
    构建LL(1)预测分析表,并用C++编程实现LL(1)语法分析器

    【输入形式】
    一个句子

    【输出形式】
    若句子语法正确,输出"Syntax analysis is right"
    若语法语法错误,输出"Error on syntax analysis"
    注:输出不包括引号

    【样例输入】
    a+a*a

    【样例输出】
    Syntax analysis is right

    【构建基于LL(1)文法的预测分析表】
    先算出FIRST集和FOLLOW集
    FIRST集和FOLLOW集
    然后算出SELECT集
    SELECT集
    最后构建预测分析表
    预测分析表

    【程序思想】
    用一维数组VTVN存储终结符集和非终结符集,用二维字符串数组map存储预测分析表,写一个find函数用于匹配每个终结符和非终结符所在的行和列,用于后面在分析表中找产生式。用分析栈 st来协助分析,栈底要先放入终结符‘#’和开始符‘E’,不然没有办法分析正确。为了简化代码,我们用X和Y分别替代E’和T’,^代替ε,空格代表没有产生式。初始化一个全局变量index用于指示当前分析到输入字符串的哪一位,对于输入字符串中的每一位,分为终结符非终结符两种情况,如果是终结符,判断是否是‘#’,如果是且栈顶也是 ‘#’,则该语句语法正确,如果栈顶和当前字符相同但不是‘#’,栈顶弹出,index右移,判断下一个字符。如果是非终结符,就去预测分析表map中寻找栈顶和当前字符的产生式,如果找不到则分析错误,如果找到了,栈顶弹出,然后将产生式右部逆序入栈,进行下一轮分析。最后,记得输入的语句末尾要加上‘#’。

    【代码实现】

    #include<iostream>
    #include<stack>
    #include<vector>
    
    using namespace std;
    
    string s;
    int index = 0;
    
    //为了简化代码,我们用X和Y分别替代E'和T',^代替ε
    char VN[5] = { 'E','X','T','Y','F' };
    char VT[6] = { 'a','+','*','(',')','#' };
    
    string map[6][7] = {
    	" ","a","+","*","(",")","#",
    	"E","TX"," "," ","TX"," "," ",
    	"X"," ","+TX"," "," ","^","^",
    	"T","FY"," "," ","FY"," "," ",
    	"Y"," ","^","*FY"," ","^","^",
    	"F","a"," "," ","(E)"," "," "
    };
    
    
    int find(char c) {
    	switch (c) {
    	case 'E':
    		return 1;
    	case 'X':
    		return 2;
    	case 'T':
    		return 3;
    	case 'Y':
    		return 4;
    	case 'F':
    		return 5;
    	case 'a':
    		return 1;
    	case '+':
    		return 2;
    	case '*':
    		return 3;
    	case '(':
    		return 4;
    	case ')':
    		return 5;
    	case '#':
    		return 6;
    	default:
    		return 0;
    	}
    }
    
    void LL()
    {
    	stack<char> st;
    	st.push('#');
    	st.push('E');
    	int i = 0;
    	int temp;//如果找到了终结符且匹配正确则标记一下不用继续后续步骤直接开始下一轮
    	while (true)
    	{
    		char c = st.top();
    		temp = 0;
    		//栈顶是终结符
    		for (int it = 0; it < 6; it++)
    		{
    			if (VT[it] == c)
    			{
    				if (s[i] == '#' && c == '#')
    				{
    					cout << "Syntax analysis is right";
    					return;
    				}
    				if (s[i] == c)
    				{
    					st.pop();
    					i++;
    					temp = 1;
    					break;
    				}
    				else
    				{
    					cout << "Error on syntax analysis";
    					return;
    				}
    			}
    		}
    		//栈顶是非终结符
    		if (temp == 1)
    			continue;
    		int n1 = find(c);
    		int n2 = find(s[i]);
    		st.pop();
    		if (map[n1][n2] == " ")
    		{
    			cout << "Error on syntax analysis";
    			return;
    		}
    		int len = map[n1][n2].length();
    		for (int k = len - 1; k >= 0; k--)
    		{
    			if (map[n1][n2][k] == '^')
    				continue;
    			st.push(map[n1][n2][k]);//逆序进栈
    		}
    	}
    }
    
    
    int main()
    {
    	cin >> s;
    	int length = s.length();
    	s[length] = '#';
    	LL();
    	return 0;
    }
    
    /*
    a+a*a
    */
    

    【遇到的问题】
    (1) 由于粗心,在初始化map的时候,我输入时忘记了自己已经将E’替换成X,T’替换成Y,导致有的产生式写错,还有产生式前面的加号被我看漏了,后来调试程序才找到错误源头。
    (2) 还是由于粗心,我在写终结符的情况的时候,使用for循环遍历终结符数组时,将后面第二部分非终结符的情况也写入了这个for循环后面,而且由于样例输入前半部分字符非常巧合地找到了对的产生式,导致我debug了很久(在纸上演练了好几遍分析栈的过程)才发现这个错误。

    最后总结一下,这次的语法分析实验总的来说让我对计算机编译程序时的语法分析有了更深刻的了解,也提升了写LL(1)预测分析表的熟练度,收获很多。当然了,也再一次提醒自己,写代码要细心细心再细心一点,粗心的程序很容易浪费很多时间在调试的过程上。

    展开全文
  • 语法分析器的设计(c++实现)

    千次阅读 2020-11-20 15:30:49
    语法分析器的设计(c++实现) 读前必看,此篇语法分析器设计。 文章目录语法分析器的设计(c++实现)步骤代码运行截图 步骤 用 Visual C++作为实验开发环境,创建一个Win32 Console Application工程,(1)存储...

    语法分析器的设计(c++实现)

    读前必看,此篇语法分析器设计。



    步骤

    用 Visual C++作为实验开发环境,创建一个Win32 Console Application工程,(1)存储结构定义:以ParserDef.h和LexerDef.h为文件名;
    (2)基本操作的算法定义:以ParserAlgo.h和LexerAlgo.h为文件名;
    (3)调用基本操作的主程序:以ParserMain.cpp为文件名。
    编写程序:
    (1)文件LexerDef.h和LexerAlgo.h为实验一的内容。
    (2)文件ParserDef.h定义语法分析所需的全局变量等。
    (3)文件ParserAlgo.h实现对语法规则中各语法成分的分析子算法。
    (4)文件ParserMain.cpp实现针对本实验的简单语言语法规则的递归下降语法分析器。

    代码

    // ParserDef.h
    
    // An highlighted block
    #include "stdio.h"
    #include "string.h"
    char prog[100],token[8],ch;//prog[100],用来存储要处理的对象,token用来与关键字比较,ch用来存储一个字符
    char *rwtab[6]={"begin","if","then","while","do","end"};//关键字表
    int syn,p,m,n,sum;
    int flag;//flag与判断是否end有关
    
    // ParserAlgo.h
    
    // An highlighted block
    #include "ParseDef.h"
    
    void factor(void);//因式 factor
    void expression(void);//表达式 expression
    void yucu(void);
    void term(void);//项 term
    void statement(void);// 语句 statement
    void parser(void);
    void scaner(void);//扫描器
     
    
    /*调用各种递归子程序,完成语法分析的过程*/
    void parser(void)
    {
    	if(syn==1)//begin
    	{
    		scaner();       /*读下一个单词符号*/
    		yucu();         /*调用yucu()函数;*/
     
    		if(syn==6)//end
    		{
    			scaner();
    			if((syn==0)&&(flag==0))//出现#且flag=0
    			printf("success!\n");
    		}
    		else
    		{
    			if(flag!=1) printf("the string haven't got a 'end'!\n");//flag来判断是否end
    			flag=1;
    		}
    	}
    	else
    	{
    		printf("haven't got a 'begin'!\n");
    		flag=1;
    	}
     
    	return;
    }
     
    void yucu(void)
    {
    	statement();         /*调用函数statement();*/
     
    	while(syn==26)//分号
    	{
    		scaner();          /*读下一个单词符号*/
    		if(syn!=6)
    			statement();         /*调用函数statement();*/
    	}
     
    	return;
    }
     
    void statement(void)
    {
    	if(syn==10)
    	{
    		scaner();        /*读下一个单词符号*/
    		if(syn==18)
    		{
    			scaner();      /*读下一个单词符号*/
    			expression();      /*调用函数expression();*/
    		}
    		else
    		{
    			printf("the sing ':=' is wrong!\n");
    			flag=1;
    		}
    	}
    	else
    	{
    		printf("wrong sentence!\n");
    		flag=1;
    	}
     
    	return;
    }
     
    void expression(void)
    {
    	term();
     
      	while((syn==13)||(syn==14))
        {
        	scaner();             /*读下一个单词符号*/
          	term();               /*调用函数term();*/
        }
     
     	return;
    }
     
    void term(void)
    {
    	factor();
     
      	while((syn==15)||(syn==16))
        {
        	scaner();             /*读下一个单词符号*/
          	factor();              /*调用函数factor(); */
        }
     
    	return;
    }
     
    void factor(void)//因式处理函数
    {
    	if((syn==10)||(syn==11))//标识符,数字
    	{
    		scaner();
    	}
      	else if(syn==27)//开头是左括号(
        {
        	scaner();           /*读下一个单词符号*/
         	expression();        /*调用函数statement();*/
     
    		if(syn==28)//出现右括号)
    		{
    			scaner();          /*读下一个单词符号*/
    		}
          	else
    	  	{
    	  		printf("the error on '('\n");
          		flag=1;
         	}
        }
      	else
    	{
    		printf("the expression error!\n");
      		flag=1;
        }
     
      	return;
    }
     
    /*主要完成赋值种别码等词法分析功能*/
    void scaner(void)//扫描器,词法分析器内容
    {
    	sum=0;//数字初始化为0
     
    	for(m=0;m<8;m++)//初始化token
    		token[m++]=NULL;
     
    	m=0;//m为token的指针
    	ch=prog[p++];//数组指针+1
     
    	while(ch==' ')//遇到空格+1
    		ch=prog[p++];
     
    	if(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A')))//遇到字母
    	{
    		while(((ch<='z')&&(ch>='a'))||((ch<='Z')&&(ch>='A'))||((ch>='0')&&(ch<='9')))
    		{
    			token[m++]=ch;
    			ch=prog[p++];//p+1,下次循环使用
    		}
    		p--;//循环跳出,要-1
    		syn=10;//10,字母开头
    		token[m++]='\0';//\0为字符串结束符
     
    		/*判别是否为关键字*/
    		for(n=0;n<6;n++)//n为rwtab的指针
    		if(strcmp(token,rwtab[n])==0)//strcmp返回值为0,则两个参数大小相同
    		{
    			syn=n+1;
    			break;
    		}
    	}
     
     
    	else if((ch>='0')&&(ch<='9'))//遇到数字
    	{
    		while((ch>='0')&&(ch<='9'))
    		{
    			sum=sum*10+ch-'0';
    			ch=prog[p++];
    		}
    		p--;//回溯
    		syn=11;//11为数字
    	}
     
    	/*除数字和字母开头以外的其他符号*/
    	else
    	switch(ch)
    	{
    		case '<':
    			m=0;
    			ch=prog[p++];
    			if(ch=='>')
    			{
    				syn=21;
    			}
    			else if(ch=='=')
    			{
    				syn=22;
    			}
    			else
    			{
    				syn=20;
    				p--;//回溯
    			}
    		break;
     
    		case '>':
    			m=0;
    			ch=prog[p++];
    			if(ch=='=')
    			{
    				syn=24;
    			}
    			else
    			{
    				syn=23;
    				p--;
    			}
    		break;
     
    
    
    		case ':':
    			m=0;
    			ch=prog[p++];
    			if(ch=='=')
    			{
    				syn=18;
    			}
    			else
    			{
    				syn=17;
    				p--;
    			}
    			break;
     
    		case '+':
    			syn=13;
    		break;
     
    		case '-':
    			syn=14;
    		break;
     
    		case '*':
    			syn=15;
    		break;
     
    		case '/':
    			syn=16;
    		break;
     
    		case '(':
    			syn=27;
    		break;
     
    		case ')':
    			syn=28;
    		break;
     
    		case '=':
    			syn=25;
    		break;
     
    		case ';':
    			syn=26;
    		break;
     
    		case '#':
    			syn=0;
    		break;
     
    		default:
    			syn=-1;
    		break;
    	}
    }
     
    
    // ParserMain.cpp
    
    // An highlighted block
    /*
    待分析的简单语言的语法
    用扩充的BNF表示如下:
    ⑴<程序>::=begin<语句串>end
    ⑵<语句串>::=<语句>{;<语句>}
    ⑶<语句>::=<赋值语句>
    ⑷<赋值语句>::=ID:=<表达式>
    ⑸<表达式>::=<项>{+<项> | -<项>}
    ⑹<项>::=<因子>{*<因子> | /<因子>
    ⑺<因子>::=ID | NUM | (<表达式>)
    */
     
    #include "stdio.h"
    #include "string.h"
    #include "ParseAlgo.h"
     
    int main(void)
    {
    	p=flag=0;
    	printf("\nplease input a string (end with '#'): \n");
     
        /*从命令行读取要处理的对象,并存储在prog[]数组中*/
    	do
    	{
    		scanf("%c",&ch);
    		//printf("\n input %c now\n",ch);
    		prog[p++]=ch;
    	}while(ch!='#');
     
    	p=0;
    	scaner();//主要完成赋值种别码等词法分析功能
    	parser();//调用各种递归子程序,完成语法分析的过程
    	//getch();
    }
    

    运行截图

    (1)源程序begin a:=9; x:=2*3; b:=a+x end #
    在这里插入图片描述

    (2)源程序x:=a+b*c end #
    在这里插入图片描述
    (3)输入一段此简单语言的源程序,输入的简单语言字符串:
    在这里插入图片描述

    好了,到这里已经结束了,这是词法分析器的实现,有想了解详细过程和原理的可以留言或私信我。

    展开全文
  • C++语法分析器

    2013-04-04 09:40:15
    语法分析器 从别的地方弄来的 给大家用用 希望对大家有帮助
  • 实验一的基础上,设计lr(1)分析表,实现lr(1)语法分析器,输出分析过程
  • 这是一个简单的自顶向下语法分析器,其中的预测分析表是固定给出的,而分析过程严格按照教材的流程图走,输出的结果是表达式的分析栈。
  • 编译原理实践:C++实现语法分析器(学习笔记)实践说明输入举例(input.txt)输出举例(output.txt)编程平台代码实现基本思路语法分析部分预定义主函数定义语法分析主函数语句串分析函数语句分析函数(等号右边的)...
  • 编译原理c++语法分析器

    万次阅读 2017-05-31 22:54:27
    语法分析器  针对编译原理第三版-何炎祥主编的书中一个 LL(1)语法分析表,利用c++编写了语法分析程序,下附加代码: /* Name: LL(1)语法分析器  Copyright:  Author:y cc  Date: 18/04/17 16:26 Description: ...
  • Compile-递归下降语法分析(C++)

    千次阅读 2022-05-06 00:06:36
    编写识别由下列文法G[E]所定义的表达式的递归下降语法分析器。 E→E+T∣E−T∣TE \rightarrow E+T | E-T | TE→E+T∣E−T∣T T→T∗F∣T/F∣FT \rightarrow T*F | T/F |FT→T∗F∣T/F∣F F→(E)∣iF \rightarrow (E)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,414
精华内容 34,965
关键字:

语法分析器c++

c++ 订阅