精华内容
下载资源
问答
  • 编译原理 LL1文法分析器 实验二 (详细代码) 左递归&First&Follow&Select&预测分析表
    千次阅读
    2021-10-20 10:48:15

    LL(1)分析器 实验二

    实验要求

    简单要求:

    至少做到对下列已知的文法,用LL(1)分析法对任意输入的符号串进行分析:

    (1)E->TG

    (2)G->+TG

    (3)G->ε

    (4)T->FS

    (5)S->*FS

    (6)S->ε

    (7)F->(E)

    (8)F->I

    高要求:

    1、手动输入文法

    2、显示文法的非终结符的Follow集

    3、显示规则的可选集合

    3、构造预测分析表

    4、对任意输入的符号串进行分析

    记号和规定

    • 空串:$
    • 符号栈终止符:#
    • 规定第一个产生式的左边那个非终结符就是开始符号

    简单要求的固定文法(无左递归)

    (1)E->TG

    (2)G->+TG

    (3)G->ε

    (4)T->FS

    (5)S->*FS

    (6)S->ε

    (7)F->(E)

    (8)F->I

    First Follow Select 集合

    非终结符First集Follow集Select集
    E( I# )( I
    T( I+ # )( I
    G+ ε# )+ # )
    F( I+ * # )( I
    S* ε+ # )* + # )

    产生式对应的SELECT集

    非终结符产生式Slect集
    EE->TG( I
    TT->FS( I
    GG->+TG+
    GG->ε# )
    SS->*FS*
    SS->ε+ # )
    FF->(E)(
    FF->II

    分析表

    I+*#
    ETGTGsynchsynch
    TFSFSsynchsynchsynch
    G+TGεε
    F(E)Isynchsynchsynchsynch
    Sε*FSεε

    简单要求(固定文法递归的预测分析)

    在主函数中构造一个RecursionSimple对象调用run方法即可运行

    运行示例

    [递归式固定文法]请输入需要分析的字符串:
    I
    [递归式固定文法]*****输入的字符串符合该文法*****success*****
    [递归式固定文法]请输入需要分析的字符串:
    ***
    [递归式固定文法]#####输入的字符串符不合该文法#####error#####
    [递归式固定文法]请输入需要分析的字符串:
    (I)
    [递归式固定文法]*****输入的字符串符合该文法*****success*****
    

    头文件 RecursionSimple.h

    #pragma once
    
    #include<iostream>
    using namespace std;
    
    
    //简单的递归版本 固定文法 
    class RecursionSimple{
    	public:
    		static const string name;
    		static enum over{Run,Error,Success};
    		int isOver;
    		char cur;
    		int len;
    		int pos;//当前指向的字符位置
    		string text;//需要分析的文本
    
    		//文法函数
    		void E();
    		void T();
    		void G();
    		void S();
    		void F();
    
    		//执行函数
    		void run();
    		//读入数据 在末尾插入#
    		void cinData();
    		//输入的字符串符合文法
    		void success();
    		//输入的内容不符合文法处理函数
    		void error();
    		//获取下一个字符 如果已经到了末尾则执行 error()
    		void next();
    		//输出结果
    		void coutResult();
    
    
    };
    
    
    

    源文件 RecursionSimple.cpp

    #include "RecursionSimple.h"
    
    #define IS_OVER if(isOver!=Run)return;
    
    const string RecursionSimple::name = "[递归式固定文法]";
    
    void RecursionSimple::E(){
    	IS_OVER
    	T();
    	G();
    }
    
    void RecursionSimple::T(){
    	IS_OVER
    	F();
    	S();
    }
    
    void RecursionSimple::G(){
    	IS_OVER
    	if(cur == '+'){
    		next();
    		T();
    		G();
    	} else if(cur != '+' && cur != ')' && cur != '#')error();
    }
    
    void RecursionSimple::S(){
    	IS_OVER
    	if(cur == '*'){
    		next();
    		F();
    		S();
    	} else if(cur != '+' && cur != ')' && cur != '#')error();
    }
    
    void RecursionSimple::F(){
    	IS_OVER
    	if(cur == '('){
    		next();
    		E();
    		if(cur == ')')next(); else error();
    
    	} else if(cur == 'I'){
    		next();
    	} else error();
    }
    
    void RecursionSimple::run(){
    	cout << "文法:\n" << "E->TG\n" << "G->+TG\n" << "G->ε\n" << "T->FS\n" << "S->*FS\n" << "S->ε\n" << "F->(E)\n" << "F->I\n";
    	cinData();//读入数据 并初始化
    	next();//获取第一个字符
    	E();//分析开始(首个非终结符函数)
    	if(cur == '#')success();
    	else error();
    	coutResult();//输出结果
    }
    
    void RecursionSimple::cinData(){
    	cout << name << "请输入需要分析的字符串:" << endl;
    	cin >> text;
    	text += '#';
    	pos = 0;
    	isOver = false;
    	len = text.length();
    }
    
    void RecursionSimple::success(){
    	isOver = Success;
    }
    
    void RecursionSimple::error(){
    	isOver = Error;
    }
    
    void RecursionSimple::next(){
    	if(pos < len){
    		cur = text[pos++];
    		return;
    	}
    	error();
    }
    
    void RecursionSimple::coutResult(){
    	if(isOver==Success)	cout << name << "*****输入的字符串符合该文法*****success*****" << endl;
    	else cout << name << "#####输入的字符串符不合该文法#####error#####" << endl;
    }
    
    
    
    

    高要求(任意文法非递归的预测分析)

    1. 读入文法
    2. 确定终结符与非终结符
    3. 去除左递归
    4. First集 Follow集
    5. 判断是否为LL(1)文法(First与Follow元素不相交)
    6. Select集
    7. 预测分析表
    8. 分析

    解析

    1. 读入文法: A -> @B a | c | $

      • 先输入左边 (在这里输入含有 # 的会结束文法输入)
      • 再输入右边 (同时输入各种可能 用 | 隔开 非终结符要在前面加@ ,#号结束本次右边输入)
      • 不可以包含下划线
      • 包含$的将自动转换为$单个字符
    2. 确定终结符与非终结符

    3. 去除左递归

      • 先将间接左递归转换为直接左递归
      • 将所有直接左递归消除
      • 删除所有不可达的产生式
    4. First集 Follow集

      • First集:
        • 遍历每一个左部为x的产生式
        • 如果产生式右部第一个字符为终结符,则将其计入左部非终结符的First集
        • 如果产生式右部第一个字符为非终结符
        • 求该非终结符的First集
        • 将该非终结符的去掉$的First集计入左部的First集
        • 若存在$,继续往后遍历右部
        • 若不存在$,则停止遍历该产生式,进入下一个产生式
        • 若已经到达产生式的最右部的非终结符(即右部的First集都含有空串),则将$加入左部的First集
        • 处理数组中重复的First集中的终结符
      • Follow集:
        • 如果x为起始符,x的Follow集添加#
        • 遍历每一个右部包含非终结符x的产生式
        • 如果x的下一个字符是终结符,添加进x的Follow集
        • 如果x的下一个字符是非终结符,把该字符的First集加入x的Follow集(不能加入空串)
        • 如果下一字符的First集有空串并且该产生式的左部不是x,则把左部的Follow集加入x的Follow集
        • 如果x已经是产生式的末尾,则把左部的Follow集添加到x的Follow集里
    5. 判断是否为LL(1)文法:First与Follow元素不相交

    6. Select集: First集(除去ε) [+ Follow集(如果First集存在ε)]

    7. 预测分析表

      • 遍历每一个左部为x的产生式
      • 如果x右边首字符串为 空串 则添加x的Follow集
      • 如果x右边首字符串为 终结符 则添加该终结符
      • 如果x右边首字符串为 非终结符 则添加x的First集
    8. 分析

      • 分析栈放入 S# (S为起始非终结符) 文本栈放入 文本#
      • 获取分析栈顶l与文本栈顶m
      • l如果为空串则直接出栈l
      • l如果为终结符 看l是否等于m 相等则匹配(一起出栈) 否则报错
      • l如果为非终结符 看l的分析表是否有m 有则一起出栈 否则报错
      • 分析栈与文本栈都全部出栈 则分析成功!

    运行示例

    示例一 固定文法

    [郭坤 软工一班 20192758]
    欢迎使用LL1文法分析器,输入1使用固定文法,否则自定义文法:1
    *****固定文法*****
    E->TG
    G->+TG|$
    T->FS
    S->*FS|$
    F->(E)|I
    
    
    First集
    E:{ ( I }
    F:{ ( I }
    G:{ $ + }
    S:{ $ * }
    T:{ ( I }
    
    Follow集
    E:{ # ) }
    F:{ # ) * + }
    G:{ # ) }
    S:{ # ) + }
    T:{ # ) + }
    
    是否为LL1文法:是
    
    Select集
    E:{ ( I }
    F:{ ( I }
    G:{ # ) + }
    S:{ # ) * + }
    T:{ ( I }
    
    预测分析表
                       #         (         )         *         +         I
             E    @empty        TG    @empty    @empty    @empty        TG
             F    @empty       (E)    @empty    @empty    @empty         I
             G         $    @empty         $    @empty       +TG    @empty
             S         $    @empty         $       *FS         $    @empty
             T    @empty        FS    @empty    @empty    @empty        FS
    
    请输入待识别的符号串(空格分割,直到遇到#截止)
    ( I ) #
    
                  分析栈                    剩余输入串              推导式
                      E#                          (I)#               E->TG
                     TG#                          (I)#               T->FS
                    FSG#                          (I)#              F->(E)
                  (E)SG#                          (I)#              ( 匹配
                   E)SG#                           I)#               E->TG
                  TG)SG#                           I)#               T->FS
                 FSG)SG#                           I)#                F->I
                 ISG)SG#                           I)#              I 匹配
                  SG)SG#                            )#          S 空串出栈
                   G)SG#                            )#          G 空串出栈
                    )SG#                            )#              ) 匹配
                     SG#                             #          S 空串出栈
                      G#                             #          G 空串出栈
                       #                             #            @Accept!
    

    示例二 任意文法

    [郭坤 软工一班 20192758]
    欢迎使用LL1文法分析器,输入1使用固定文法,否则自定义文法:0
    输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
    左边的非终结符:A @B c | d # B @A | f # #
    右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割!非终结符前加@):
    *****结束右边的输入*****
    A->Bc|d
    输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
    左边的非终结符:右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割!非终结符前加@):
    *****结束右边的输入*****
    B->A|f
    输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]
    左边的非终结符:*****结束文法输入*****
    *****输入的文法如下*****
    A->Bc|d
    B->A|f
    
    *****消除间接左递归*****
    A->d|Ac|fc
    B->A|f
    
    *****消除直接左递归*****
    A->dA_|fcA_
    B->A|f
    A_->$|cA_
    
    *****删除不可达的文法*****
    A->dA_|fcA_
    A_->$|cA_
    
    
    First集
    A:{ d f }
    A_:{ $ c }
    
    Follow集
    A:{ # }
    A_:{ # }
    
    是否为LL1文法:是
    
    Select集
    A:{ d f }
    A_:{ # c }
    
    预测分析表
                       #         B         c         d         f
             A    @empty    @empty    @empty       dA_      fcA_
            A_         $    @empty       cA_    @empty    @empty
    
    请输入待识别的符号串(空格分割,直到遇到#截止)
    f c c c #
    
                  分析栈                    剩余输入串              推导式
                      A#                         fccc#            A_->fcA_
                   fcA_#                         fccc#              f 匹配
                    cA_#                          ccc#              c 匹配
                     A_#                           cc#             A_->cA_
                    cA_#                           cc#              c 匹配
                     A_#                            c#             A_->cA_
                    cA_#                            c#              c 匹配
                     A_#                             #         A_ 空串出栈
                       #                             #            @Accept!
    

    代码

    类头文件 ArbitraryGrammar.h

    #pragma once
    #include<iostream>
    #include<vector>
    #include<list>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<iomanip>
    #include<string>
    using namespace std;
    
    /*
    - 空串:$
    - 符号栈终止符:#
    */
    
    //产生式
    struct Production{
    	string left;    //产生式左边 非终结符
    	vector<vector<string>> right;   //产生式右边
    
        Production(string l,vector<vector<string>>r){ left = l;right = r; }
        Production(string l){ left = l; }
    
        string getRightString(int i){//获得右边所有元素联合的串
            string s = "";
            for(auto r : right[i])s += r;
            return s;
        }
        void insert(vector<string> temp){
            right.push_back(temp);
        }
        void insert(string temp){
            vector<string>v;
            v.push_back(temp);
            right.push_back(v);
        }
        string toString(){
            string str = left + "->";
            for(auto s : right[0])str += s;
            int len = right.size();
            for(int i = 1;i < len;i++){
                str += "|";
                for(auto s : right[i])str += s;
            }
            return str;
        }
    };
    
    //任意文法的LL(1)分析类
    class ArbitraryGrammar{
    public:
        ArbitraryGrammar();         //构造函数
        void run();                 //运行程序
        void displayGrammarHint(string s);  //打印系统提示语句 中间夹杂当前文法
        void displayGrammar();      //打印当前的文法
        void displayResultTable();  //打印分析结果表
        void displayAnalyzedTable();//打印预测分析表
        bool isNonTer(string x);    //判断是否是 非终结符
        bool isTer(string x);       //判断是否是 终结符
        void inputText();           //待分析的字符串输入 输入#号结束
        void display();             //打印First集,Follow集,Select集
    protected:
    
    
    
        int  getNonTerPos(string x);//获取非终结符下标
        int  getTerPos(string x);   //获取终结符下标
        void init();                //初始化
        void load();                //加载数据 调用其他方法
        void inputGrammar();        //输入文法 输出#号结束
    
        bool isLL1Grammar;          //是否为LL1文法
        bool isLoad;                //是否加载了数据
        bool isAnalyzed;            //是否已经分析了输入的字符串
        string Start;               //起始符
    
    
        //文本是否已经分析完毕
        vector<Production> prod;    //产生式集合
        vector<string>text;         //拆分后的 待分析文本
        vector<vector<string>>resultTable;//分析后生成的结果分析表 0 分析栈 1 剩余输出串 2 推导式
        vector<bool>used;          //dfs看看哪些文法是访问了的
    
        vector<set<string>> first;  //First集
        vector<set<string>> follow; //Follow集
        vector<set<string>> select; //select集
    
        map<string,int> terAndEnd;  //终结符与#
        map<string,int> ter;        //终结符
        map<string,int> nonTer;     //非终结符 string为非终结符 int为对应编号
    
    
        vector<vector<int>> table;  //分析表[非终结符][终结符]-> 存储的是产生式prod的下标 
    
        void judgeLL1Grammar();     //判断文法是否为LL(1)文法 First与Follow不相交
        void getFirst(string x);    //获取某个非终结符的First集
        void getAllFirst();         //获取所有非终结符的First集
        void getFollow(string x);   //获取某个非终结符的Follow集
        void getAllFollow();        //获取所有非终结符的Follow集
        void getAllSelect();        //获取产生式的Select集
        void getAnalyzTable();      //获取预测分析表
        string getTableE(int prodPos,int rightPos);    //获取预测分析表中的元素 -1 empty -2 synch 
        void getResultTable();      //获取分析后的结果表
        string getVectorString(vector<string> v);//将字符串集合整合为一个字符串
        string getListString(list<string> li);//将字符串集合整合为一个字符串
        void dfs(int x);
        void simplify();
        void removeDirectly(int i);
        void removeIndirect(int i,int len);//消除间接做递归 产生式下标i 产生式数len
        void removeAllDirectly();
        void removeAllIndirect();
        void removeLeftRecursion(); //消除左递归
        void resize(int len);       //更新容器大小
    };
    
    
    
    
    

    类源文件 ArbitraryGrammar.cpp

    #include "ArbitraryGrammar.h"
    
    ArbitraryGrammar::ArbitraryGrammar(){
        //init();
    }
    
    bool ArbitraryGrammar::isNonTer(string x){
        return nonTer.find(x) != nonTer.end();
    }
    
    bool ArbitraryGrammar::isTer(string x){
        return terAndEnd.find(x)!=terAndEnd.end();
    }
    
    int ArbitraryGrammar::getNonTerPos(string x){
        return nonTer.at(x);
    }
    
    int ArbitraryGrammar::getTerPos(string x){
        return terAndEnd.at(x);
    }
    
    void ArbitraryGrammar::init(){
        /*产生式
        (1)E->TG
        (2)G->+TG
        (3)G->ε
        (4)T->FS
        (5)S->*FS
        (6)S->ε
        (7)F->(E)
        (8)F->I
        */
    
        
    
        for(auto t : ter)terAndEnd.insert(t);
        int ii = terAndEnd.size();
        terAndEnd["#"] = ii;
    
    
    
        Start = prod[0].left;
    
        int size = nonTer.size();
        
        resize(size);
    
        isLoad = false;
    }
    
    void ArbitraryGrammar::inputText(){
        //待分析的字符串输入 输入#号结束
        cout << endl;
        cout << "请输入待识别的符号串(空格分割,直到遇到#截止)" << endl;
        vector<string>().swap(text);
        string sin;cin >> sin;
        while(sin.find('#') == string::npos){
            text.push_back(sin);
            cin >> sin;
        }
        isAnalyzed = false;//输入了新的文本 设置为没有被分析
    }
    
    void ArbitraryGrammar::inputGrammar(){
        //输入所有非终结符
        string s,ss;
        set<string>st;
        vector<Production>P;
        
        while(1){
            cout << "输入文法(A -> a | @Bc [格式])[@B右边的非终结符前加@,输入#结束]" << endl;
            cout << "左边的非终结符:";
            cin >> s;
            if(s.find('#') != string::npos){
                cout << "*****结束文法输入*****" << endl;
                break;
            }
            if(s.find('@') != string::npos || s.find('_') != string::npos || s.find('$') != string::npos){
                cout << "*****输入不合法 不能含有 @ 下划线 $ *****" << endl;
                continue;
            }
            int pos;
            if(isNonTer(s)){
                pos = getNonTerPos(s);
            } else{
                int pos = nonTer.size();
                nonTer[s] = pos;
            }
            st.erase(s);//消除未使用的非终结符
            cout << "右边的产生式 可以用 | 分割(每个终结符、非终结符、和'|' 都需要有空白分割!非终结符前加@):" << endl;
            vector<vector<string>>V;
            vector<string>v;
            bool flag = 0;
            while(1){
                cin >> ss;
                if(ss.find('#') != string::npos){
                    if(v.empty()){
                        cout << "*****产生式为空,不计入*****" << endl;
                        flag = 2;
                        break;
                    }
                    cout << "*****结束右边的输入*****" << endl;
                    V.push_back(v);
                    v.clear();
                    break;
                }
                if(ss.find('_') != string::npos){
                    cout << "*****输入不合法 不能含有下划线*****" << endl;
                    flag = 1;
                    break;
                }
                if(ss.find('$') != string::npos){
                    v.push_back("$");
                    continue;
                }
                if(ss.find('@') != string::npos){
                    if(ss[0] != '@'){
                        cout << "*****输入不合法 @不在字符串首*****" << endl;
                        flag = 1;
                        break;
                    }
                    if(ss.size() == 1){
                        cout << "*****输入不合法 @后面没有非终结符串*****" << endl;
                        flag = 1;
                        break;
                    }
                    for(int i=1;i<ss.size();i++)
                        if(ss[i] == '@'){
                            cout << "*****输入不合法 一个非终结符存在多个@ *****" << endl;
                            flag = 1;
                            break;
                        }
                    string nt = ss.substr(1);
                    if(!isNonTer(nt))st.insert(nt);//计入非终结符序列
                    v.push_back(nt);
                    continue;
                }
                if(ss == "|" && !v.empty()){
                    V.push_back(v);
                    v.clear();
                    continue;
                }
                v.push_back(ss);
            }
            if(flag)continue;
            //成功输入一组文法
            Production pr = Production(s,V);
            for(auto vv : V){
                for(auto x : vv){
                    if(!isNonTer(x) && x != "$"){
                        int ii = ter.size();
                        ter[x] = ii;
                    }
                }
            }
            P.push_back(pr);
            cout << pr.toString() << endl;
        }
    
        displayGrammarHint("输入的文法如下");
    
        if(!st.empty()){
            cout << "存在终结符没有对应的产生式!--> ";
            for(auto x : st)cout << x << " ";
            cout << endl << "请重新输入文法!" << endl;
            nonTer.clear();
            ter.clear();
            prod.clear();
            inputGrammar();
        }
    
        //更新prod
        prod.swap(P);
    
    }
    
    void ArbitraryGrammar::run(){
    
        
    
        cout << "[郭坤 软工一班 20192758]" << endl;
        cout << "欢迎使用LL1文法分析器,输入1使用固定文法,否则自定义文法:";
        string sin;
        getline(cin,sin);
        if(sin == "1"){
            prod.push_back(Production("E",{{"T","G"}}));
            prod.push_back(Production("G",{{"+","T","G"},{"$"}}));
            prod.push_back(Production("T",{{"F","S"}}));
            prod.push_back(Production("S",{{"*","F","S"},{"$"}}));
            prod.push_back(Production("F",{{"(","E",")"},{"I"}}));
    
    
            ter["+"] = 0;
            ter["*"] = 1;
            ter["("] = 2;
            ter[")"] = 3;
            ter["I"] = 4;
    
            nonTer["E"] = 0;
            nonTer["G"] = 1;
            nonTer["T"] = 2;
            nonTer["S"] = 3;
            nonTer["F"] = 4;
    
            init();
            displayGrammarHint("固定文法");
    
        } else{
            inputGrammar();
            init();
            removeLeftRecursion();
        }
    
        load();
    }
    
    void ArbitraryGrammar::load(){
    
        isLoad = true;
    
        getAllFirst();
        getAllFollow();
    
        judgeLL1Grammar();
    
        getAllSelect();
    
        display();
    
        if(isLL1Grammar){
            getAnalyzTable();
            displayAnalyzedTable();
    
            while(true){
                inputText();
                getResultTable();
                displayResultTable();
                cout << endl << "是否继续分析一组文本? y|Y" << endl;
                string s;
                cin >> s;
                if(s[0] != 'y' && s[1] != 'Y')break;
    
            }
    
        }
    }
    
    void ArbitraryGrammar::display(){
        if(isLoad){
            cout << endl;
            cout << "First集" << endl;
            for(auto x : nonTer){
                cout << x.first << ":{ ";
                for(auto f : first[x.second]){
                    cout << f << " ";
                }
                cout << "}" << endl;
            }
    
            cout << endl;
            cout << "Follow集" << endl;
            for(auto x : nonTer){
                cout << x.first << ":{ ";
                for(auto f : follow[x.second]){
                    cout << f << " ";
                }
                cout << "}" << endl;
            }
    
            cout << endl;
            cout << "是否为LL1文法:" << ( isLL1Grammar ? "是" : "不是" ) << endl;
    
            cout << endl;
            cout << "Select集" << endl;
            for(auto x : nonTer){
                cout << x.first << ":{ ";
                for(auto f : select[x.second]){
                    cout << f << " ";
                }
                cout << "}" << endl;
            }
        }
    
    
    }
    
    void ArbitraryGrammar::displayResultTable(){
        if(isLL1Grammar){
    
            if(!isAnalyzed)getResultTable();//如果没有分析 则进行分析
    
            //分析表结果表输出
            int w0 = 20,w1 = 30,w2 = 20;
            cout << endl;
            cout << setw(w0) << "分析栈" << setw(w1) << "剩余输入串" << setw(w2) << "推导式" << endl;
            for(int i = 0;i < resultTable[0].size();i++){
                cout << setw(w0) << resultTable[0][i] << setw(w1) << resultTable[1][i] << setw(w2) << resultTable[2][i] << endl;
            }
        } else{
            cout << "当前文法不合法LL(1)规范,不可以打印LL(1)结果分析表" << endl;
        }
    }
    
    void ArbitraryGrammar::displayGrammar(){
        for(auto & p : prod)cout << p.toString() << endl;
    }
    
    void ArbitraryGrammar::displayGrammarHint(string s){
        cout << "*****" << s << "*****" << endl;
        displayGrammar();
        cout << endl;
    }
    
    void ArbitraryGrammar::displayAnalyzedTable(){
        if(isLL1Grammar){
            int width = 10;
            cout << endl;
            cout << "预测分析表" << endl;
    
            //打印终结符
            cout << setw(width) << "";
            for(auto s : terAndEnd){
                cout << setw(width) << s.first;
            }
    
            cout << endl;
            //打印预测的产生式
            for(auto nt : nonTer){
                cout << setw(width) << nt.first;
                int pos = getNonTerPos(nt.first);
                for(auto t : terAndEnd){
                    int i = table[nt.second][t.second];
                    cout << setw(width) << getTableE(pos,i);
                }
                cout << endl;
            }
        }
    }
    
    void ArbitraryGrammar::judgeLL1Grammar(){
        //First与Follow都不相交的才属于LL1文法
        int len = nonTer.size();
        for(int i = 0;i < len;i++){
            set<string>tmp;
            set_intersection(first[i].begin(),first[i].end(),follow[i].begin(),follow[i].end(),inserter(tmp,tmp.begin()));
            if(!tmp.empty()){
                isLL1Grammar = false;
                return;
            }
        }
        isLL1Grammar = true;
    }
    
    void ArbitraryGrammar::getFirst(string x){
        bool flag = 0;  //记录非终结符的First集是否有空串 
        int tot = 0;    //记录一个非终结符产生式含有空串的产生式
        int pos = getNonTerPos(x);//该非终结符对应的下标
        
    
        for(auto v : prod[pos].right){
            //如果右部的第一个字符是终结符 
            if(isTer(v[0])){
                first[pos].insert(v[0]);
            }
            //如果是非终结符
            else{
                //从左到右遍历右部 
                for(int j = 0;j < v.size();j++){
                    //如果遇到终结符,直接将该终结符放入first集 并结束
                    if(isTer(v[j])){
                        first[pos].insert(v[j]);
                        break;
                    }
                    //遇到空串
                    if(v[j][0] == '$'){
                        //是最后一个符号 则加入first中
                        if(j == v.size() - 1){
                            first[pos].insert("$");
                            break;
                        }
                        //不是最后一个符号 ---其实可以去除它!
                        continue;
                    }
                    //不是终结符,求该非终结符的First集
                    getFirst(v[j]);
                    for(string it : first[getNonTerPos(v[j])]){
                        if(it[0] == '$'){//查看是否有空串在该非终结符的first中
                            flag = 1;
                        } else{//将该非终结符的first的非空串元素添加到first集中
                            first[pos].insert(it);
                        }
                    }
                    //没有空串就不必再找下去了 
                    if(flag == 0)break;
                    else{//有空串 则继续循环
                        flag = 0;//更新状态
                        tot++;
                    }
                }
                //如果右部所有符号的First集都有空串] = 则符号x的First集也有空串 
                if(tot == v.size()){
                    first[pos].insert("$");
                }
            }
        }
        
        
    }
    
    void ArbitraryGrammar::getAllFirst(){
        //getFirst
        for(auto i : nonTer)getFirst(i.first);
    }
    
    void ArbitraryGrammar::getAllFollow(){
        //起始非终结符的follow放入#
        follow[0].insert("#");
        //getFollow
        for(auto i : nonTer)getFollow(i.first);
    }
    
    void ArbitraryGrammar::getFollow(string x){
        int pos = getNonTerPos(x);
    
    
        //找到非终结符x出现的位置
        for(int i = 0;i < prod.size();i++){
            for(auto v : prod[i].right){
                int index = -1;
                int len = v.size();
                for(int j = 0;j < len;j++){
                    if(v[j] == x){
                        index = j;
                        break;
                    }
                }
                if(index == -1)continue;//没有包含x结束本次循环
                //如果找到了x] = 并且它不是最后一个字符 
                if(index < len - 1){
                    //如果下一个字符是终结符,添加进x的Follow集 
                    string next = v[index + 1];
                    if(isTer(next))follow[pos].insert(next);
                    else{
                    //如果下一个字符是非终结符 
                        bool flag = 0;
                        //遍历下一个字符的First集
                        for(string it : first[getNonTerPos(next)]){
                            if(it[0] == '$')flag = 1;
                            else follow[pos].insert(it);
                        }
                        //如果有空串并且左部不是它本身(防止陷入死循环)] = 当前非终结符的Follow集是x的Follow集
                        string l = prod[i].left;
                        if(flag && l != x){
                            getFollow(l);
                            for(string it : follow[getNonTerPos(l)]){
                                follow[pos].insert(it);
                            }
                        }
                    }
                } else if(index == len - 1 && x != prod[i].left){
                    //如果x在产生式的末尾,则产生式左部的Follow集应该添加到x的Follow集里 
                    string l = prod[i].left;
                    getFollow(l);
                    for(string it : follow[getNonTerPos(l)]){
                        follow[pos].insert(it);
                    }
                }
            }
        }
    }
    
    
    void ArbitraryGrammar::getAllSelect(){
        //Slect集 = First集(除去ε) [+ Follow集(如果First集存在ε)]
        for(auto m : nonTer){
            string x = m.first;
            int pos = m.second;
            if(first[pos].find("$") != first[pos].end()){
                //First存在空串 
                set_union(first[pos].begin(),first[pos].end(),follow[pos].begin(),follow[pos].end(),inserter(select[pos],select[pos].begin()));
                //取出select中的空串 $
                select[pos].erase("$");
            } else{//不存在空串
                for(auto s : first[pos])select[pos].insert(s);
            }
        }
    }
    
    void ArbitraryGrammar::getAnalyzTable(){
        
        for(int i = 0;i < prod.size();i++){
            for(int j = 0;j < prod[i].right.size();j++){
                string tmp = prod[i].right[j][0];
                int pos = getNonTerPos(prod[i].left);
                //如果产生式右部的第一个字符串是终结符
                if(isTer(tmp) || tmp[0] == '$'){
                    //该终结符是空串,遍历左部的follow集,更新table
                    if(tmp[0] == '$'){
                        for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                    } else{//该终结符不是空串,更新table
                        table[pos][getTerPos(tmp)] = j;
                    }
                } else{
                    //如果产生式右部的第一个字符是非终结符,遍历它的First集,更新table
                    int tmpPos = getNonTerPos(tmp);
                    for(auto f : first[tmpPos]){//添加 除空串$ 以外的所有元素
                        if(f[0] != '$')table[pos][getTerPos(f)] = j;
                    }
                    //如果有空串,遍历左部的follow集,更新table  
                    if(first[tmpPos].find("$") != first[tmpPos].end()){
                        for(auto f : follow[pos])table[pos][getTerPos(f)] = j;
                    }
                }
            }
        }
    }
    
    string ArbitraryGrammar::getTableE(int prodPos,int rightPos){
        if(rightPos == -1)return "@empty";
        //if(1 == -2)return "@synch";
        return prod[prodPos].getRightString(rightPos);
    }
    
    void ArbitraryGrammar::getResultTable(){
        if(isAnalyzed)return;//分析过就不需要再分析了
    
        isAnalyzed = true;
    
        auto rs = &resultTable;
        //重置结果表
        vector<vector<string>>().swap(*rs);
        rs->resize(3);
        list<string>a,b;//a-->分析栈 b->剩余输出串栈
        auto A = &rs->at(0),B = &rs->at(1),C = &rs->at(2);
        //把开始符和#push进分析栈
        a.push_back(Start);
        a.push_back("#");
        //把整个串push进剩余符号vector
        for(auto i : text)b.push_back(i);
        b.push_back("#");
        //如果剩余输入串长度不为0,就一直循环
        while(b.size() > 0){
            //输出分析栈内容
            A->push_back(getListString(a));
            //输出剩余输入串内容
            B->push_back(getListString(b));
            
            //获取分析栈首元素与剩余输入串首元素
            string sa = a.front(),sb = b.front();
            int pa;
    
            if(sa == sb){
                if(sa == "#"){//如果可以匹配,并且都为# 
                    C->push_back("@Accept!");//输入串符合文法!
                    return;
                } else{//如果可以匹配,并且都为终结符 
                    a.pop_front();
                    b.pop_front();
                    C->push_back(sb + " 匹配");
                }
            }else if(isNonTer(sa)&& isTer(sb) &&table[pa = getNonTerPos(sa)][getTerPos(sb)] > -1){
                //如果在预测分析表中有值
                int index = table[pa][getTerPos(sb)];
                a.pop_front();
                if(getTableE(pa,index) != "$"){
                    //E#->TG# 倒叙插入
                    for(int i = prod[pa].right[index].size() - 1;i >= 0;i--){
                        a.push_front(prod[pa].right[index][i]);
                    }
                    C->push_back(prod[pa].left + "->" + getVectorString(prod[pa].right[index]));
                } else{//空串出栈
                    C->push_back(sa + " 空串出栈");
                }
            } else{
                C->push_back("@Error!");
                return;
            }
        }
    }
    
    string ArbitraryGrammar::getVectorString(vector<string> v){
        string tmp = "";
        for(auto i : v)tmp += i;
        return tmp;
    }
    
    string ArbitraryGrammar::getListString(list<string> li){
        string tmp = "";
        for(auto i : li)tmp += i;
        return tmp;
    }
    
    //消除间接左递归
    void ArbitraryGrammar::removeIndirect(int pa,int len){
    
    
    
        for(int pb = pa; pb < len; pb++){
                 //相互循环遍历 一层层的消除间接左递归
            bool flag = false;
            vector<vector<string>> tmp;
            vector<vector<string>> & Ar = prod[pa].right;//检查的产生式右边Ar
            vector<vector<string>> & Br = prod[pb].right;//搜寻的产生式右边Br
            string Bl = prod[pb].left;//搜寻的产生式 左边
            //A->Bc B->Cd => A->Cdc
            for(auto & a : Ar)
                if(a[0] == Bl){//Ar中发现有以Bl开头的式子 
                    //将B中非终结符式子Cd筛选出来
                    for(auto & b : Br)
                        if(b[0]!=Bl&&b[0]!="$")
                            tmp.push_back(b);
                    //找到Bl开头元素
                    flag = true;
                    break;
                }
            if(flag){
                //使用n--反向读取方式 避免因为删除导致的数组下标错误
                int n = Ar.size();
                while(n--){
                    if(Ar[n][0] == Bl){//Ar中发现有以Bl开头的式子 
                        //取出tmp中的元素Cd加上a中的c 然后放入Ar中  Cdc
                        for(auto t : tmp){
                            int nn = Ar[n].size();
                            for(int k = 1;k < nn;k++)
                                t.push_back(Ar[n][k]);
                            //放入Ar中 A->CDc
                            Ar.push_back(t);
                        }
                        //删除A->Bc项
                        Ar.erase(Ar.begin() + n);
                    }
                }
            }
        }
    }
    
    void ArbitraryGrammar::removeAllDirectly(){
        //固定了原本产生式数量 即使后续增加不会改变 因此之后遍历原有的产生式
        int len = prod.size();
        for(int i = 0;i < len;i++)removeDirectly(i);
    
        //扩容
        len = prod.size();//获取扩容后的大小
        resize(len);
    
    
        displayGrammarHint("消除直接左递归");
    }
    
    void ArbitraryGrammar::removeAllIndirect(){
        int len = prod.size();
        for(int i = 0;i < len;i++)removeIndirect(i,len);
    
        displayGrammarHint("消除间接左递归");
    }
    
    void ArbitraryGrammar::removeLeftRecursion(){
        //先消除所有间接左递归 再消除所有 直接左递归
        removeAllIndirect();
        removeAllDirectly();
        simplify();
    }
    
    void ArbitraryGrammar::resize(int len){
        first.resize(len);
        follow.resize(len);
        select.resize(len);
        table.resize(len);
        for(auto & i : table){
            i.resize(terAndEnd.size());
            for(auto & x : i)x = -1;//设置为-1 empty
        }
    }
    
    //消除直接左递归 
    void ArbitraryGrammar::removeDirectly(int pos){
        string l = prod[pos].left;//获取左边
        //遍历看看有没有左递归元素
        bool isLeftRecursion = false;
        for(auto & i : prod[pos].right){
            if(i[0] == l){
                isLeftRecursion = true;
                break;
            }
        }
            
        if(!isLeftRecursion)return;
    
        //创建A_并放入prod中
        string l_ = l + '_';
        auto A_ = Production(l_);
    
        //nonTer 添加A_
        nonTer[l_] = prod.size();
    
        prod.push_back(A_);
    
        //----这里不知道为什么 不能放在前面声明r(会导致到下面循环时 r变空 只能放在这里了)
        auto & r_ = prod[prod.size() - 1].right;
        //添加空串到A_中
        r_.push_back({"$"});
        auto &r = prod[pos].right;
    
        //遍历A右边 寻找递归左元素
        for(int x = 0;x < r.size();x++){
            if(r[x][0] == "$")continue;//跳过空串
            if(r[x][0] == l){//A->Ab => A_->bA_
                vector<string>v;
                for(int i = 1;i < r[x].size();i++)
                    v.push_back(r[x][i]);//b
                v.push_back(l_);//bA_
                r_.push_back(v);//添加A_->nA_
                r.erase(r.begin()+x);//删掉A->Ab
                x--;//回退一格
            } else{//A->c => A->cA_
                r[x].push_back(l_);//cA_
            }
        }
    }
    
    
    void ArbitraryGrammar::dfs(int x){
        if(used[x]) return;
        used[x] = 1;
        for(vector<string> &v : prod[x].right)
            for(string &s:v)
                if(isNonTer(s))
                    dfs(getNonTerPos(s));
    }
    
    //化简 没有使用的文法扔掉
    void ArbitraryGrammar::simplify(){
        //还没做好
        vector<bool>().swap(used);
        used.resize(prod.size());
        
        dfs(0);
    
        vector<Production> res;
        for(int i = 0; i < prod.size(); i++)
            if(used[i])
                res.push_back(prod[i]);
    
        prod.swap(res);
    
        resize(prod.size());
    
        nonTer.clear();
        for(int p = 0;p < prod.size();p++)
            nonTer[prod[p].left] = p;
    
    
        displayGrammarHint("删除不可达的文法");
    }
    
    

    主函数 main.cpp

    #include <iostream>
    #include <cmath>
    #include "ArbitraryGrammar.h"
    using namespace std;
    
    int main(){
    	
    	ArbitraryGrammar ag = ArbitraryGrammar();
    	ag.run();
    
    }
    
    
    更多相关内容
  • java 编译原理 ll1 文法分析 first follow select 集的 求解
  • ll1文法分析器实现c++

    2020-12-24 10:53:32
    ll1文法分析器实现c++
  • 我在学编译原理课的时候编的,把文法写进文件,然后运行程序即可.产生的DFA在屏幕上显示,分析表写到文件里面.
  • 语言为C++,使用了set,map容器,输入格式:S -> Aa | g | e,支持多‘|’ 符号,采用文件输入
  • LL(1)文法是消除左递归和回溯之后的文法,这里是利用栈将文法移进和匹配的过程显示出来,但是输出是随意写的,可以稍作调整,让输出更加的美化!
  • 完整版LL(1)分析过程模拟课程设计报告
  • SLR(1)文法分析器 基于Python3的SLR(1)文法分析器。目前的功能: 分析文法各非终结符号的FOLLOW(A)集合 分析文法所有的有效项目集族 计算文法的SLR(1)分析矩阵 简单的输入串分割(词法分析)功能 判断输入串是否为...
  • 需要创建一个名字叫project.txt的文件来存储要识别的文法
  • 算符优先文法分析

    2013-03-14 00:40:37
    对用户自定义的文法进行算符优先的分析,友好的人际交互界面,计算FIRStVT和LASTVT,并且对一段输入进行分析
  • 编译原理-LL1文法分析-java
  • 编译原理-LL1文法分析-java
  • 实现功能:针对任意的文法,编写相应的左递归消除、左公共因子提取程序,求解相应的FIRST、FOLLOW集,构造预测分析表,并编写LL(1)语法分析程序,并给出测试句子的分析过程。(注:左递归消除和左公共因子如果在实验...
  • 算符优先_文法分析_

    2021-09-30 13:51:10
    算符优先文法分析,实现了算符优先表以及对输入串的具体分析
  • 给出一个文法G,再给出一个程序段s,程序可以根据所给出的文法G对输入的程序段s进行SLR分析。在对文法进行分析的过程中会输出FIRST集、FOLLOW集、状态集、分析过程等,最终会输出程序的正误。
  • 文法分析 编译原理

    2012-04-13 16:35:49
    2) 根据文法产生式的结构,分析文法的4个部分,分别写入定义好的文法数据结构的相应部分; 3) 整理文法的结构,判断该文法文法类型,是否为0型,1型,2型或3型文法,并输出判断结果; 4) 在计算机屏幕或者...
  • LL(1)分析法,就是指从左到右扫描输入串(源程序),同时采用最左推导,且对每次直接推导只需向前看一个输入符号,便可确定当前所应当选择的规则。实现LL(1)分析的程序又称为LL(1)分析程序或LL(1)分析器。
  • LR(0)文法分析,加上一个简单的例子来进行分析,每一步过程都有的,非常详细。

    目录

    LR(0)文法的字面含义

    LR(0)分析表的构造

    写在最后


    LR(0)文法的字面含义

    LR(0)分析法是其他LR分析法构造的基础,L表示从左往右扫描,R表示反向构造出一个最右推导,k表示向前看k个字符,缺省为1。在学习LR(0)分析时,首先要了解几个概念:分析表(包括动作ACTION,和状态转移GOTO两个部分),分析栈(包括文法分析栈和状态栈),下面是LR(0)分析器工作过程示意图:

    然后最重要的是在进行文法分析是可能产生的动作:移进(shift),规约,接受(accept,简称acc),报错。

    LR(0)分析表的构造

    在了解了上面的基本概念后就可以开始构造分析表了,下面是一个例题。

    给出文法G[S]为:

    (1)S->aAcBe

    (2)A->Ab

    (3)A->b

    (4)B->d

    1)构造识别活前缀的DFA

    2)构造LR(0)分析表

    3)对输入串abbcde#进行分析。

     1)首先先写出他的拓广文法(拓广文法:在初始状态的前面加上一个S',如这里的S'->S就是拓广出来的,拓广文法的作用就是让构造的DFA只有一个初态和终态,例如在这个文法中初态:S'->·S,终态(acc):S'->S·),

     

    然后是DFA的构造:主要是分清楚·符号在哪个位置:(1)在非终结符的前面,状态集要增加,如:下面的表中的I2状态,由于·符号后面是非终结符A,就要增加以A开始的状态集。(2)在终结符的前面,状态集不变,如I3状态,·符号后面是终结符c,I3状态不变(3)在末尾,是规约状态。如I8。 

    2) 对输入串abbcde#进行分析首先要构造LR(0)分析表,就是将上面的DFA按照规则填入表中:ACTION是遇到终结符,GOTO是遇到非终结符,Si意思是移进,并且i进入状态栈,ri表示用第i个式子规约,根据情况看哪些状态要出栈,i指的是上面拓广文法的前面标号。

    3)分析过程在上面这张图的下半部分,具体步骤是:

    (1)首先状态栈有0,根据LR(0)分析表状态0遇到输入串的第一个a,ACTION为S2,a进入符号栈。

    (2)状态栈栈顶是2,遇到b,ACTION是S4,4进入状态栈,b进入符号栈。

    (3)状态栈栈顶是2,遇到b,ACTION是r2(注意这里b不进入符号栈),利用第二个式子来规约,A进入符号栈,4状态出栈,然后栈顶是2,遇到A,GOTO是3,3进入状态栈。(这里加粗是因为进行了两步才完成,下面只分析两步的)

    (4)……

    (5)状态栈栈顶是6,遇到c,ACTION是r3(注意这里c不进入符号栈),利用第三个式子来规约,A进入符号栈,3、6状态出栈,然后栈顶是2,遇到A,GOTO是3,3进入状态栈

    (6)……

    (7)……

    (8)状态栈栈顶是8,遇到e,ACTION是r4(注意这里e不进入符号栈),利用第四个式子来规约,B进入符号栈,8状态出栈,然后栈顶是5,遇到B,GOTO是7,7进入状态栈

    (9)……

    (10)状态栈栈顶是9,遇到#,ACTION是r1(注意这里#不进入符号栈),利用第一个式子来规约,S进入符号栈,2、3、5、7、9状态都要出栈,然后栈顶是0,遇到S,GOTO是1,1进入状态栈

    (11)状态栈栈顶是1,遇到#,ACTION是acc,说明该串的输入分析结束了,结果是接受状态。

    写在最后

    希望大家看完有所收获,如果有错误的话,欢迎大家在评论区指出,共勉。

     

    展开全文
  • C++版LL(1)文法分析

    2011-05-18 18:05:25
    是编译原理的实习,关于LL(1)的文法分析程序,鄙人的拙手作品,多多谅解!
  • java写的算符优先文法分析器 包括括号匹配,进出栈操作……
  • 运用数据结构——栈,来编写的递归下降LL(1)文法的C++代码,实现大学教材《编译原理(第3版)》的课本习题文法的程序编码。

    基本信息

    项目名称: 文法分析器
    编译语言:C++
    运行环境:Devcpp
    操作系统:Windows 10

    项目内容

    1 题目

    对如下课本《编译原理(第3版)》P100,第3题,用递归下降法写出分析程序,输入两个符号串进行测试,一个符号串为符合文法的句子,另一个不是该文法的句子。

    例题 3. 已知文法G[S]:

    S->MH | a
    H->LSo |ε
    K->dML |ε
    L->eHf
    M->K | bLM

    判断G是否是LL(1)文法,如果是,构造LL(1)分析表。

    2 程序代码

    main.cpp

    /*
        项目名称:三级项目1 文法分析器
        学号: xxxxxxxx
        姓名:汕大学长 
        班级:19计算机 
        时间:2021/12/19 
    */
    #define  _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    
    #define STACK_INIT_SIZE 100  //存储空间初始分配两
    #define STACKINCREMENT 10    //存储空间分配增量
    
    //------------栈 结构定义与功能函数-----------// 
    typedef struct{
    	char *base;
    	char *top;
    	int stacksize;
    }SqStack; 
    
    int InitStack(SqStack &S);  //初始化一个空栈 
    int Push(SqStack &S, char e); //插入元素 
    int Pop(SqStack &S, char &e); //弹出元素
    
    int InitStack(SqStack &S){
    	//构造一个空栈S
    	S.base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
    	if(!S.base)exit(OVERFLOW);  //存储分配失败
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    	return 1; 
    } //InitStack
    
    int Push(SqStack &S, char e){
    	//插入元素e为新的栈顶元素
    	if(S.top - S.base>=S.stacksize){ //栈满,追加存储空间
    		S.base = (char *)realloc(S.base, 
    		            (S.stacksize+STACKINCREMENT) * sizeof(char));
    		if(!S.base)exit(OVERFLOW); //存储分配失败
    		S.top = S.base + S.stacksize;
    		S.stacksize += STACKINCREMENT; 
    	}
    	*S.top++ = e;
    	return 1; 
    } //Push
    
    int Pop(SqStack &S, char &e){
    	// 若栈不空,则删除S的栈顶元素,用e返回其值
    	if(S.top == S.base)return 0;
    	e = * --S.top;
    	return 1; 
    } //Pop
    
    
    
    //-------------文法规则函数---------------// 
    int S_1(SqStack &S,char e); // S->MH | a;
    int H(SqStack &S,char e);   // H->LSo | #
    int K(SqStack &S,char e);   // K->dML | #
    int L(SqStack &S,char e);   // L->eHf
    int M(SqStack &S,char e);   // M->K | bLM
    
    
    int S_1(SqStack &S,char e){
    	switch(e){
    		case 'a':
    			Push(S,'a');
    			break;
    		case 'o':
    		case 'd':
    		case 'e':
    		case 'b':
    		case '#':
    			Push(S,'H');
    			Push(S,'M');
    			break;
    		default:
    			return 0;
    	}
    	
    	return 1;
    }
    
    int M(SqStack &S,char e){
    	switch(e){
    		case 'o':
    		case 'd':
    		case 'e':
    		case '#':
    			Push(S,'K');
    			break;
    		case 'b':
    			Push(S,'M');
    			Push(S,'L');
    			Push(S,'b');
    			break;
    		default:
    			return 0;
    	}
    	
    	return 1;
    }
    
    int H(SqStack &S,char e){
    	switch(e){
    		case 'o':
    		case 'f':
    		case '#':
    			break;
    		case 'e':
    			Push(S,'o');
    			Push(S,'S');
    			Push(S,'L');
    			break;
    		default:
    			return 0;
    	}
    	
    	return 1;
    }
    
    int L(SqStack &S,char e){
    	switch(e){
    		case 'e':
    			Push(S,'f');
    			Push(S,'H');
    			Push(S,'e');
    			break;
    		default:
    			return 0;
    	}
    	
    	return 1;
    }
    
    int K(SqStack &S,char e){
    	switch(e){
    		case 'o':
    		case 'e':
    		case '#':
    			break;
    		case 'd':
    			Push(S,'L');
    			Push(S,'M');
    			Push(S,'d');
    			break;
    		default:
    			return 0;
    	}
    	
    	return 1;
    }
    
    //--------------递归下降LL(1)方法------------// 
    int check(SqStack &S, SqStack &S_temp){
    	// 匹配函数 
    	char e;
    	char e_top;
    	Push(S,'#');
        Push(S,'S'); //初始化栈内容 #S 
        
        int flag=1;  //匹配成功标志 
    	Pop(S,e_top);  //e_top='S'
        Pop(S_temp,e); //获取待匹配栈元素
    	while(1){
            while(e_top==e){ //弹出匹配的元素 
                if(e_top=='#'&&e=='#'){
        	        printf("匹配成功。\n\n");
        	        return 1; 
    	        }
    	        Pop(S,e_top);
                Pop(S_temp,e);
    		}
            switch(e_top){ //文法规则处理算法 
    		    case 'S':
    			    flag = S_1(S,e);
    			    break;
    		    case 'H':
    			    flag = H(S,e);
    			    break;
    		    case 'K':
    			    flag = K(S,e);
    			    break;
    		    case 'L':
    			    flag = L(S,e);
    			    break;
    		    case 'M':
    			    flag = M(S,e);
    			    break;
    			default:
    				flag=0; //匹配失败标识 
    	    }
    	    
    	    if(flag==0){
    	    	printf("匹配失败。\n\n");
        	    return 0; 
    		}
    	    
    	    Pop(S,e_top);
    	} 
    	
    	return 1;
    }
    
    
    void menu(){  //开始界面 
    	printf("Please enter number to choose the funtion.\n");
    	printf("0. Exit\n");
    	printf("1. Enter\n");
    }
    
    //----------------主函数--------------// 
    int main() {
    	char e;  //栈元素 
    	char e_top;  //栈顶元素 
        SqStack S,S_temp;  //检测栈S,分析(读入)栈S_temp
    	InitStack(S);
    	InitStack(S_temp); //初始化为空栈
    	
    	int num;
    	while(1){
    		menu();
    		printf("Number:");
    		scanf("%d",&num);
    		if(num==0) break;
    		
    		printf("\n请输入需测试的符号串,并以'#'号结尾。\n");
    	    printf("符号串:");
    	    fflush(stdin);	//强制刷新输入缓冲区,防止换行符的干扰 
            while(1){ //获取输入符号串 
        	    scanf("%c",&e);
        	    Push(S,e);
        	    if(e=='#') break;
    	    }
    	
    	    while(S.top != S.base){ //获得分析栈(余留串) 
    		    Pop(S,e);
    		    Push(S_temp,e);
    	    }
    
            check(S,S_temp); //匹配函数,开始判断
    	}
    	
        return 1;
    }
    
    

    3 结果截图

    测试符号串实验结果
    bef#匹配成功
    acc#匹配失败

    实验结果如下图所示:
    请添加图片描述

    展开全文
  • XML文法分析

    2020-03-04 11:00:43
    文中介绍了XML语法的基本规则,及对XML文法作了分析
  • * 采用LL(1)表分析法实现表达式文法的语法检验。 * (0)E ->TX * (1)X ->+TX (2)X ->-TX (3)X ->ε * (4)T ->FY * (5)Y ->*FY (6)Y ->/FY (7)Y ->ε * (8)F ->(E) (9)F ->i * 思路:其中i指代数字。先通过词法分析,...
  • Antlr教程文法分析

    2014-08-28 11:50:32
    文法分析器类主要用于把读入的字节流根据规则分段
  • 文法分析c语言版

    2013-04-05 10:46:27
    采用LL(1)表分析法实现表达式文法的语法检验。 * (0)E ->TX * (1)X ->+TX (2)X ->-TX (3)X ->ε * (4)T ->FY * (5)Y ->*FY (6)Y ->/FY (7)Y ->ε * (8)F ->(E) (9)F ->i * 思路:其中i指代数字。先通过词法...
  • LL1文法分析

    2015-06-27 19:40:15
    (1)LL(1)文法的判定(假设文法符合的First和Follow集未知)要求:输入文法,输出判定该文法是否是LL(1)的。根据select集,预测分析表来判定的。
  • 文法分析

    千次阅读 2018-03-25 20:34:57
    1、递归下降语法分析(RDP)我们知道,对于一个CFG而言,不管规则多么复杂,规则集中总是会有非终结符到终结符的简单推导,就像递归中的出口一样。例如:这样的特点是递归下降法能够顺利执行递归的基本条件。RDP做的...

    1、递归下降语法分析(RDP)

    我们知道,对于一个CFG而言,不管规则多么复杂,规则集中总是会有非终结符到终结符的简单推导,就像递归中的出口一样。例如:

    这样的特点是递归下降法能够顺利执行递归的基本条件。

    RDP做的事情就是把每个非终结符看作是函数,从这个非终结符推导出的规则是函数体。例如:

    可以看到,函数体内部的书写范式是:

    case 终结符{eat(终结符);处理下一个;}

    RDP是一种预测分析,预测的意思是:接下来要做什么可以通过case后面那个终结符知道。如果一条规则中,->后面的非终结符是不明确的,RDP就失效了,例如:

    A->A+B

    A->A-B

    A->a

    B->b

    函数A应写作:

    void A(void){

        switch(tok){

        case ?:A();eat(+);B();

        case ?:A();eat(-);B();

        case a:eat(a)

        }

    }

    2、Nullable、FIRST和FOLLOW

    为方便后面的讨论(例如,将递归下降法表示成一张表),引入三个定义:

    (1)Nullable的定义:

    若非终结符A可以推导出空串,则Nullable(A)为真,表示A是"可空的"。

    (2)FIRST的定义:

    FIRST(A)表示非终结符A推导的规则中,->后面的第一个终结符;

    FIRST(ABC...)=FIRST(A)∪FIRST(B)∪FIRST(C)∪...,如果ABC是可空的。

    (3)FOLLOW的定义:

    对于非终结符A,如果在任意推导中出现At,其中t是终结符,那么t∈FOLLOW(A),如果是ABCt这种情况,但BC是可空的,那么也有t∈FOLLOW(A)

    例如:

     

    Nullable

    FIRST

    FOLLOW

    X

    yes

    a c

    a c d

    Y

    yes

    c

    a c d

    Z

    no

    a c d

     

    虽然可以通过观察法找到答案但是形式化的计算更不容易出错,在知道了

    Nullable以后,我们完全可以从定义出发,列式计算,例如:

    因为X,Y都是可空的,则FIRST(Z)={d}∪FIRST(X)∪FIRST(Y)。

    计算FOLLOW同样有一些捷径,例如X的FOLLOW,因为观察到规则集中有XYZ,那么Y的FIRST一定是X的FOLLOW的子集,又因为Y是可空的,所以Z的FIRST也一定是X的FOLLOW的子集,于是可毫不费力地写出{a c d}

    3、构造分析预测表

    由此可以得到2中文法对应的表:

     

    A

    c

    d

    X

    X->a

    X->Y

    X->Y

    X->Y

    Y

    Y->

    Y->

    Y->c

    Y->

    Z

    Z->XYZ

    Z->XYZ

    Z->d

    Z->XYZ

    初看这个规则可能会觉得变扭,下面给出具体计算步骤:

    ①在X行,找到由X推导的规则:

    X->Y

    X->a

    计算FOLLOW(x)、FIRST(Y)和FIRST(a),FOLLOW(x)={a c d},FIRST(Y)={c},FIRST(a)={a},请注意:终结符的FIRST就是它本身。于是可将X->a写到(X, a)处,由于Y是可空的,所以,对于每个FOLLOW(x)都要写上X->Y

    ②在Y行,找到由Y推导的规则:

    Y->

    Y->c

    计算FOLLOW(Y)、FIRST( )、FIRST(c),它们分别是{a c d}、{ }、{c}。于是可将Y->c写到(Y, c)处,由于Y-> 中的终结符为空,所以这条规则要写到任何一个Y行、FOLLOW(Y)列处。

    ③仿上,相信你懂了。

    另外,寻找FOLLOW的时候,有几种情况要注意:

    ①产生式中没有显然的FOLLOW但是可以通过其他产生式导出,例如:

    其中的E'没有明显的FOLLOW,但是可以通过规则替换找到。结果如下:

    ②对于AB来说,如果已经知道了B的FOLLOW,又知道B可以为空,那么A的FOLLOW一定包含B的FOLLOW。

    这是显然的,熟练运用可以提高寻找效率。

    4、LL(1)文法

    3中的表存在歧义,即推导规则不唯一,例如X行a列就有两个规则。

    如果每个表项只有一个规则,则与这个表对应的文法叫LL(1)文法(第一个L表示"从左到右分析",即left-to-right parsing;第二个L表示"最左推导",即left-most derivation;1表示超前查看一个字符)。

    歧义产生的根源在于存在左递归,可以通过改写文法规则消除左递归,同时不影响原意,例如把:

    改成:

    有公共左因子的时候,递归下降分析也会出问题,可以通过提取公共左因子来解决:

    这样处理以后得到的表是无歧义的,得到表的步骤和前文一样,略。

    5、LR分析

    LL(k)文法的弱点在于在看到k个右边的符号后就必须做出预测。

    下面要介绍的LR分析可以延缓这种预测。

    (1)LR(0)

    表示left-to-right parsing,right-most derivation,0 word look-ahead。

    ①理解使用的符号

        s表示shift,后面的数字是状态号

        r表示reduce,后面的数字是产生式编号

        g表示go-to,后面的数字是状态号

        a表示accept

        空格表示潜在的错误状态

    那么shift和go-to有什么区别?区别是:shift用在终结符的转移,go-to用在非终结符的转移。

    ②如何通过文法构造DFA?

    引入符号.做闭包运算。

    来看一个LR(0)的例子:

     

    从这个图可以得到如下的DFA:

    然后得到下表:

     

    (

    )

    x

    ,

    $

    S

    L

    1

    s3

     

    s2

      

    g4

     

    2

    r2

    r2

    r2

    r2

    r2

      

    3

    s3

     

    s2

      

    g7

    g5

    4

        

    a

      

    5

     

    s6

     

    s8

       

    6

    r1

    r1

    r1

    r1

    r1

      

    7

    r3

    r3

    r3

    r3

    r3

      

    8

    s3

     

    s2

      

    g9

     

    9

    r4

    r4

    r4

    r4

    r4

      

    LR(0)的缺点是可能出现reduce-reduce冲突或者shift-reduce冲突,发生这样的情况是因为:在当前状态下有多个可用的reduce规则;或者既可以reduce,又可以通过吃掉下一个字符发生转移,例如:

    这是某个LR(0)文法对应的DFA的一部分,当下一个符号是+时,究竟是用E->T.来规约,还是按E->T.+E来发生转移?这就是shift-reduce冲突。

    (2)SLR

    SLR表示Simple LR,它赋予了LR向前看一个符号的能力,可以一定程度上解决上述的冲突。但是注意,SLR仍然是可能存在冲突的(具体可以参见虎书的课后习题)。

    SLR的特别之处在于利用了FOLLOW集合,它规定:

    对于一个状态中的每条规约规则A->a.

    只有当遇到FOLLOW(A)的时候才执行规约,否则不执行。

    可以看一个例子:

    这个文法对应的DFA如下:

    按照SLR的规则,得到如下的表:

     

    x

    +

    $

    E

    T

    1

    s5

      

    g2

    g3

    2

      

    a

      

    3

     

    s4

    r2

      

    4

    s5

      

    g6

    g3

    5

     

    r3

    r3

      

    6

      

    r1

      

    也就是说,例如对状态3,FOLLOW(E)={$},那么就只有当遇$时才规约,又例如对状态6,也一样。对状态5,FOLLOW(T)={+,$},那么只在这两处规约即可。

    对比一下,如果不按SLR而是LR(0),那么表就有歧义了:

    由此可见SLR确实消去了歧义。

    (3)LR(1)

    一种比SLR更强大的文法是LR(1)。它的每一项由(A->a.b,x)组成,x叫做超前查看符号。

    在计算闭包的过程中,每一项的超前超前查看符通过如下算法计算:

    开始项的超前查看符总是?,表示无关紧要。

    不妨通过一个例子来理解:

    计算过程:

    于是得到:

    类似地可以构造DFA:

    (4)LALR(1)

    叫做Look-Ahead LR(1),它的分析范围比LR(1)小,但是表达起来更方便。方便在哪里?

    LALR(1)将LR(1)中除lookahead以外,其它地方完全相同的item给合并掉。比如下图中:

    不同颜色圈起来的四对状态是可以合并的。这样,在转换成表格的时候就简化了许多。

     

    6、使用Bison

    (1)基本格式

    FIRST PART

    %%

    SECOND PART

    %%

    THIRD PART

    第一部分写定义

    第二部分和CFG对应,写要执行的C语句

    第三部分写其他C语句,例如main。

    (2)一个例子

    ①calc.y

    %{

    void yyerror(char *s);

    #include<stdio.h>

    #include<stdlib.h>

    int symbols[52];

    int symbolVal(char symbol);

    void updateSymbolVal(char symbol,int val);

    %}

     

    %union {int num; char id;}

    %start line

    %token print

    %token exit_command

    %token <num> number

    %token <id> identifier

    %type <num> line exp term

    %type <id> assignment

     

    %%

    line: assignment ';' {;}

        | exit_command ';' {exit(EXIT_SUCCESS);}

        | print exp ';' {printf("Printing %d\n",$2);}

        | line assignment ';' {;}

        | line print exp ';' {printf("Printing %d\n",$3);}

        | line exit_command ';' {exit(EXIT_SUCCESS);}

        ;

     

    assignment: identifier '=' exp {updateSymbolVal($1,$3);}

        ;

     

    exp: term {$$=$1;}

        | exp '+' term {$$=$1+$3;}

        | exp '-' term {$$=$1-$3;}

        ;

     

    term: number {$$=$1;}

        | identifier {$$=symbolVal($1);}

        ;

    %%

     

    int computeSymbolIndex(char token){

        int idx=-1;

        if(islower(token)){

            idx=token-'a'+26;    

        }else if(isupper(token)){

            idx=token-'A';

        }

        return idx;

    }

     

    int symbolVal(char symbol){

        int bucket=computeSymbolIndex(symbol);

        return symbols[bucket];

    }

     

    void updateSymbolVal(char symbol,int val){

        int bucket=computeSymbolIndex(symbol);

        symbols[bucket]=val;

    }

     

    int main(void){

        int i;

        for(i=0;i<52;i++){

            symbols[i]=0;    

        }

        return yyparse();

    }

     

    void yyerror(char* s){fprintf(stderr,"%s\n",s);}

    ②calc.l

    %{

    #include"y.tab.h"

    %}

     

    %%

    "print" {return print;}

    "exit" {return exit_command;}

    [a-zA-Z] {yylval.id=yytext[0];return identifier;}

    [0-9]+ {yylval.num=atoi(yytext);return number;}

    [ \t\n] ;

    [-+=;] {return yytext[0];}

    . {ECHO;yyerror("unexpected character");}

    %%

     

    int yywrap(void){return 1;}

    编译运行:

    展开全文
  • LR(0)文法分析程序

    2020-12-24 14:39:31
    LR(0)文法如下:G[E]:E→aA∣bBA→cA∣dB→cB∣d改写为扩展文法后进行分析。#include #include #include #include #include #include #include #include using namespace std;//初始化,包括读取文件中的文法及初始化...
  • 实现算符优先文法分析程序;完成对以下表达式文法的分析程序。 G[E]: E->E+T E->T T->T*F T->F F->(E) F->i
  • LL(1)文法分析

    2009-11-03 22:40:49
    文法为:(使用c++ builder2007) *(1) E->TG *(2) G->+TG *(3 G->-TG *(4) G->^ *(5) T->FS *(6) S->*FS *(7) s->/FS *(8) S->^ *(9) F->(E) *(10) F->i

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,694
精华内容 9,877
关键字:

文法分析