精华内容
下载资源
问答
  • 2022-05-04 16:21:48

    实验要求

    根据给出的简单语言的语法构成规则(见下面),编制LL(1)语法分析器,要在词法分析输出的单词基础上进行语法分析,输出相应的语法分析结果和错误信息。
    E->E+T|E-T|T
    T->T*F|T/F|F
    F->(E)|i
    上式中, i 为整数或标识符,对于整数和标识符的识别可以借助实验1。
    关于错误信息:不要求错误种类,只需给出出错位置。

    代码中的函数
    open_inputf():打开input.txt
    ● void inf_nextc(): 读入文件的内容-若是空,返回0
    int is_number(char number):判断是否为整常量,是的话返回1
    int is_oper(char letter): //暂时猜测:判断是不是±/()这几个符号,是的话返回1
    //cq猜测:判断当前列有无对应的文法,如果有则返回当前第几列
    int is_endc()://是不是±
    /() i 这几个符号–终结符,是的话返回1

    ● int str_put_stack() :入栈(字符栈),如果是整常量,i入栈。同时把我们输入的2+33转为i+i3(即转为一般化)
    char get_str_stack_top():获取栈顶元素
    char out_str_stack():出栈(字符栈)
    char out_analy_stack() :出栈(分析栈)
    void put_analy_stack(char letter):入栈(分析栈)

    ● get_product_form(): 有横纵坐标,返回预测表对应的产生式
    open_LL1analyf():将input.txt内容读入分析器

    ● LL1_analy():预测分析过程,先把#E压入栈中,导序入栈—如果抽到我们的话,我觉得主要回报的就是栈的弹出和进入

    1.  如果分析栈-字符栈一样的话,这可以是字符栈输出,
      
    2. 分析栈-字符栈都为#作为栈顶—>分析正确

    3.  如果得到的分析栈顶不是终结符的话,则查二维表(横坐标是自己,纵坐标是字符栈顶),strcmp(相等才是0),只有二者(product_form与“1”即无产生式)相等时候才会提示分析储出错。当既不是1也不是0时,将其逆序压入分析栈。
      

    代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define analy_stack_cap 30
    #define str_stack_cap 30
    #define row_num 5
    #define col_num 8
    char ch;
    char analy_stack_top;
    const char* product_form;
    int str_stack_content_num, str_stack_current_num;
    char str_stack[str_stack_cap];
    int analy_stack_current_num=2;
    char analy_stack[analy_stack_cap]={'#', 'E'};
    const char fat_row[]={'E', 'A', 'T', 'B', 'F'};
    const char fat_col[]={'i', '+', '-', '*', '/', '(', ')', '#'};
    const char* const forecast_analy_table[row_num][col_num]={
    	{"TA", "1", "1", "1", "1", "TA", "1", "1"},
    	{"1", "+TA", "-TA", "1", "1", "1", "0", "0"},
    	{"FB", "1", "1", "1", "1", "FB", "1", "1"},
    	{"1", "0", "0", "*FB", "/FB", "1", "0", "0"},
    	{"i", "1", "1", "1", "1", "(E)", "1", "1"}
    };
    int error_location=1;
    FILE *inputf, *LL1f;
    
    void open_inputf(){
    	if((inputf=fopen("input.txt", "r"))==NULL){
    		printf("打开input失败\n");
    		exit(0);
    	}
    }
    
    void inf_nextc(){
    	if((ch=fgetc(inputf))==EOF){
    		ch=0;
    	}
    }
    
    int is_number(char number){
    	if(ch>=48 && ch<=57)
    		return 1;
    	return 0;
    }
    
    int is_oper(char letter){
    	int col=0;
    	for(int i=1; i<col_num-1; i++){
    		if(fat_col[i]==letter){
    			col=1;
    			break;
    		}
    	}
    	return col;
    }
    
    int is_endc(char letter){
    	int endc_mark=0;
    	for(int i=0; i<col_num-1; i++){
    		if(fat_col[i]==letter){
    			endc_mark=1;
    			break;
    		}
    	}
    	return endc_mark;
    }
    int str_put_stack(){
    	int i=0, result=0;
    	inf_nextc();
    began:
    	if(ch==' '){
    		inf_nextc();
    		goto began;
    	}else if(is_number(ch)){
    		if(ch!='0'){
    			do{
    				inf_nextc();
    			}while(is_number(ch));
    		}else{
    			inf_nextc();
    			if(is_number(ch)){
    				printf("扫描至 %d 行\n", error_location);
    				return result;
    			}
    		}
    		if(ch=='.'){
    			inf_nextc();
    			if(is_number(ch))
    				do{
    					inf_nextc();
    				}while(is_number(ch));
    			else{
    				printf("扫描至 %d 行\n", error_location);
    				return result;
    			}
    		}
    		str_stack[i++]='i';
    		goto began;
    	}else if(is_oper(ch) ){
    		str_stack[i++]=ch;
    		inf_nextc();
    		goto began;
    	}else if(ch=='#'){
    		str_stack[i++]=ch;
    		do{
    			inf_nextc();
    		}while(ch==' ');
    		if(ch=='\n'){
    			error_location++;
    		}
    		str_stack_current_num=str_stack_content_num=i;
    		printf("第 %d 行扫描完成\n", error_location-1);
    		result=1;
    	}else{
    		printf("全文扫描至 %d 行\n", error_location);
    	}
    	return result;
    }
    
    char get_str_stack_top(){
    	return str_stack[str_stack_content_num-str_stack_current_num];
    }
    
    char out_str_stack(){
    	char letter=str_stack[str_stack_content_num-str_stack_current_num--];
    	str_stack[str_stack_content_num-str_stack_current_num-1]=' ';
    	return letter;
    }
    
    char out_analy_stack(){
    	char letter=analy_stack[--analy_stack_current_num];
    	analy_stack[analy_stack_current_num]=0;
    	return letter;
    }
    
    void put_analy_stack(char letter){
    	analy_stack[analy_stack_current_num++]=letter;
    }
    
    const char* get_product_form(char rowc, char colc){
    	int row=0, col=0;
    	for(; row<row_num; row++)
    		if(fat_row[row]==rowc)
    			break;
    	for(; col<col_num;col++)
    		if(fat_col[col]==colc)
    			break;
    	return forecast_analy_table[row][col];
    }
    
    void open_LL1analyf(){
    	if((LL1f=fopen("LL1.txt", "w"))==NULL){
    		printf("打开LL1.txt失败");
    		exit(0);
    	}
    }
    
    int LL1_analy(){
    	int i=1;
    	fprintf(LL1f, " %4s %14s %15s %13s\n", "步骤", "分析栈", "剩余输入串", "所用产生式");
    began:
    	ch=get_str_stack_top();
    abegan:
    	analy_stack_top=out_analy_stack();
    	if(is_endc(analy_stack_top)){
    		if(analy_stack_top==ch){
    			fprintf(LL1f, " %-4d %13s%c %15s    %c %-5s\n", i, analy_stack, analy_stack_top, str_stack, ch, "匹配");
    			out_str_stack();
    			i++;
    			goto began;
    		}else{
    			fprintf(LL1f, " %-4d %13s%c %15s    %s\n", i, analy_stack, analy_stack_top, str_stack, "出错,终止");
    			printf("语法错误,程序终止\n");
    		}
    	}else{
    		if(analy_stack_top=='#'){
    			if(analy_stack_top==ch){
    				fprintf(LL1f, " %-4d %13s%c %15s    %s\n", i, analy_stack, analy_stack_top, str_stack, "接受");
    				analy_stack[0]='#';
    				analy_stack[1]='E';
    				analy_stack_current_num=2;
    				memset(str_stack, 0, sizeof(str_stack));
    				printf("语法正确\n");
    				return 1;
    			}else{
    				fprintf(LL1f, " %-4d %13s%c %15s    %s\n", i, analy_stack, analy_stack_top, str_stack, "出错,终止");
    				printf("语法错误,程序终止\n");
    			}
    		}else{
    			product_form=get_product_form(analy_stack_top, ch);
    			if(strcmp(product_form, "1")){
    				fprintf(LL1f, " %-4d %13s%c %15s    %c%s%s\n", i, analy_stack, analy_stack_top, str_stack, analy_stack_top, "->", product_form);
    				i++;
    				if(strcmp(product_form, "0")){
    					int num=strlen(product_form);
    					while(num--){
    						put_analy_stack(product_form[num]);
    					}
    				}
    				goto abegan;
    			}else{
    				fprintf(LL1f, " %-4d %13s%c %15s    %s\n", i, analy_stack, analy_stack_top, str_stack, "出错,终止");
    				printf("语法错误,程序终止\n");
    			}
    		}
    	}
    	return 0;
    }
    
    int main(){
    	open_inputf();
    	open_LL1analyf();
    	while(str_put_stack()){
    		if(LL1_analy()){
    		}else{
    			getchar();
    			break;
    		}
    	}
    	fclose(LL1f);
    	fclose(inputf);
    	return 1;
    }
    修改下路径即可
    
    
    更多相关内容
  • 编译原理LL1文法实验 编译原理LL1文法实验 PAGE / NUMPAGES 编译原理LL1文法实验 实验二自上而下语法分析 实验目的和要求 根据某一文法编制调试递归下降分析程序以便对任意输入的符号串进行分析选做 根据某一文法...
  • 本次上传的是编译原理语法分析LL1文法程序部分,耗费了我2个星期的时间,真的是煞费苦心。里面增加了很多注释,大家应该能够看懂,有需要的朋友赶紧下载吧!希望对大家有所帮助!!!
  • 语言为C++,使用了set,map容器,输入格式:S -> Aa | g | e,支持多‘|’ 符号,采用文件输入
  • 实验是对LL1文法的代码实现,仅供学习交流参考使用,禁止用于商业用途,如有错误,请批评斧正.同时欢迎各位大佬交流
  • 编译原理LL1文法分析

    2021-12-10 23:11:42
    LL1

    编译原理LL1文法分析

    LL(1)文法是一个自顶向下语法分析算法

    基本流程

    在这里插入图片描述

    1.读取文法

    ​ 这里的终结符、非终结符是可以用字符串来表示,而不是单个字符,同时也要求了我们不同了的符号需要用一个空格来隔开,在输入文法时也要求间隔开来。例如:A -> A a | b

    ​ 对象声明:

        /**
         * 终结符
         */
        private Vector<String> T = new Vector<>();
        /**
         * 非终结符
         */
        private Vector<String> NT = new Vector<>();
        /**
         * 产生式
         */
        private Map<String, Vector<String>> production = new HashMap<>();
    

    ​ 文法读取txt文件,具体txt文件以行读取,对每一行的"->“分割,”->“左边就是非终结符,若NT中不存则加入NT中,右边部分再以”|"分割,分割成多个产生式,将所有所有产生式加入到对应的NT的产生式production中;在所有文法读取完毕之后,对已经建立起来的产生式集进行扫描,若不在NT中字符串则将其加入到N中作为终结符。

        /**
         * 读取文法
         * 终结符非终结符
         *
         * @param fileName 路径
         */
        public void readGrammar(String fileName) {
            File file = new File(fileName);
            try {
                BufferedReader reader = new BufferedReader(new FileReader(file));
                String line = null;
                while ((line = reader.readLine()) != null) {
                    System.out.println("line: " + line);
                    //添加文法
                    String[] lr = line.split("->");
                    String[] rs = lr[1].split("\\|");
                    Vector<String> rights = new Vector<>();
                    for (String right : rs) {
                        rights.add(right.trim());
                    }
                    production.put(lr[0].trim(), rights);
                    addNt(lr[0].trim());
                }
                System.out.println("文法: " + production);
                System.out.println("非终结符:" + NT);
                addN();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        /**
         * 添加非终结符
         */
        private void addNt(String left) {
            if (!NT.contains(left)) {
                NT.add(left);
            }
        }
        /**
         * 添加终结符
         */
        private void addN() {
            for (String left : production.keySet()) {
                for (String right : production.get(left)) {
                    String[] strs = right.split(" ");
                    for (String str : strs) {
                        if (NT.contains(str) || T.contains(str)) {
                            continue;
                        } else {
                            T.add(str);
                        }
                    }
                }
            }
            System.out.println("终结符:" + T);
        }
    

    2.消除左递归

    在这里插入图片描述

    ​ 消除左递归有立即消除和非立即消除,立即消除就是非终结符自己的产生式之间来进行替换,非立即消除则就是利用前(i-1)个非终极符的产生式来替换第 i 个中的产生式,然后再对于第 i 个产生式自己进行立即消除。因此下面实现了两个函数来作为这两种消除方式,同时包括以及辅助函数。

    函数名参数描述
    eliminateImmediateLeftRecursion(String Ai)Ai:非终结符消除直接左递归
    eliminateLeftRecursion()消除左递归
    isFirst(String right, String Ai)right:产生式右部;Ai:非终结符判读右部的第一个字符串是否为Ai非终结符
    replaceLast(String right, String Ai, String newAi)right:右部;Ai非终结符;newAi:新非终结符非终结符替换,删除原来的非终结符,将新的非终结符加入末尾
    replace(String right, String Ai, String newAi)right:右部;Ai非终结符;newAi:新非终结符非终结符替换,将非终结符替换为新终结符

    ​ 辅助函数

        /**
         * 判断右部第一个字符是否为Ai
         *
         * @param right 右部
         * @param Ai    字符
         * @return True包含 False不包含
         */
        private boolean isFirst(String right, String Ai) {
            String[] strs = right.trim().split(" ");
            return Ai.trim().equals(strs[0].trim());
        }
        /**
         * 字符替换
         *
         * @param right 右部
         * @param Ai    旧字符
         * @param newAi 新字符
         * @return 新字符串
         */
        private String replaceLast(String right, String Ai, String newAi) {
            String newRight = "";
            String[] strs = right.trim().split(" ");
            for (String str : strs) {
                if (str.equals(Ai) || " ".equals(str)) {
                    continue;
                }
                newRight += str + " ";
            }
            newRight += newAi;
            return newRight.trim();
        }
        /**
         * 字符替换
         *
         * @param right 右部
         * @param Ai    旧字符
         * @param newAi 新字符
         * @return 新字符串
         */
        private String replace(String right, String Ai, String newAi) {
            String newRight = "";
            String[] strs = right.trim().split(" ");
            for (String str : strs) {
                if (str.equals(Ai)) {
                    newRight += newAi + " ";
                    continue;
                } else if (" ".equals(str)) {
                    continue;
                }
                newRight += str + " ";
            }
            return newRight.trim();
        }	
    

    ​ 消除立即左递归,传入一个非终结符Ai,要知道能调用这个函数则证明会产生一个新的非终结符来存储一个新的产生式,然后扫描 Ai的所有产生式,若产生式中第一个字符串就是Ai的话,那么需要产生式中原来的Ai删除,将新的非终结符加入到末尾,这里用到的也就是replaceLast函数;若不包含就在原来的产生式后面加上新的非终结符来调用;最后需要在新的非终结符中加入$的产生来结束递归,更新到产生式集合中即可。

    ​ 非立即消除左递归,在第i个非终结符时,扫描所有产生式,若产生式第一个字符串就是前i-1个的非终结符中的一个,就需要将这个终结符替换成这个非终结符的所有产生式,若不是则保证原来的产生式即可,最后判断自己的产生式中第一个字符串是否为自身,若是则执行消除立即左递归函数,注意执行完之后需要跳过一个i ,将i增大一个数,因为消除立即左递归加入了一个新的非终结符到NT中,而这个非终结符就这个下一个i中,新的非终结符也不存在左递归的情况,所以需要直接跳过。

    /**
         * 消除立即左递归
         *
         * @param Ai 字符
         */
        private void eliminateImmediateLeftRecursion(String Ai) {
            String newAi = Ai + "'";
            NT.insertElementAt(newAi, NT.indexOf(Ai));
            Vector<String> rights1 = new Vector<>();
            Vector<String> rights2 = new Vector<>();
            for (String right : production.get(Ai)) {
                if (isFirst(right, Ai)) {
                    String newRight = replaceLast(right, Ai, newAi);
                    rights2.add(newRight);
                } else {
                    String newRight = right.trim() + " " + newAi;
                    rights1.add(newRight);
                }
            }
            rights2.add("$");
            production.replace(Ai, rights1);
            production.put(newAi, rights2);
        }
        /**
         * 消除左递归
         * 产生式 无环 和 $
         */
        public void eliminateLeftRecursion() {
            for (int i = 0; i < NT.size(); i++) {
                String Ai = NT.get(i);
                //新的右部
                Vector<String> newIrights = new Vector<>();
                for (String iRight : production.get(Ai)) {
                    //iRight是否包含aj
                    boolean flag = false;
                    for (int j = 0; j < i; j++) {
                        String Aj = NT.get(j);
                        if (isFirst(iRight, Aj)) {
                            flag = true;
                            for (String jRight : production.get(Aj)) {
                                String newIright = replace(iRight, Aj, jRight);
                                newIrights.add(newIright);
                            }
                        }
                    }
                    //未替换 加入原来的右部
                    if (!flag) {
                        newIrights.add(iRight);
                    }
                }
                //i==0时,newIrights未维护
                if (i != 0) {
                    production.replace(Ai, newIrights);
                }
                //消除直接左递归
                for (String iRight : production.get(Ai)) {
                    if (isFirst(iRight, Ai)) {
                        eliminateImmediateLeftRecursion(Ai);
                        i++;
                        break;
                    }
                }
            }
            System.out.println("新文法:" + production);
        }
    

    ​ 执行示例:

    我们输入:
    A -> a B | B b
    B -> A c | d
    

    ​ 执行结果如下:

    在这里插入图片描述

    3.提取左公共因子

    ​ 提取左公因子我们用一个新的对象 产生式树,也就是将我们现在的产生式建立一颗树,因为这样可用很好的找到我们公共最大前缀,这颗树其实就相当于我们熟悉的字典树, 找到公共最大前缀之后对其进行提取,提取之后同时也会产生新的非终结符加入到NT中即可。

    ​ 首先我们来建立这颗 产生式树,加入我们的新对象,对于每一个非终结符建立起一颗树,树根就是 我们的非终结符,productionTree利用HashMap存储可快速定义到我们需要的树。

        /**
         * 产生式树
         */
        private Map<String, TreeNode> productionTree = new HashMap<>();
    

    ​ 定义我们树的节点,树节点包含节点、很多孩子节点,同时每个树节点存在一个标识isLast,表示此节点是否为一个产生式的末尾,这对于后面的递归就很大的作用,因为有了这样的标识我们递归到此节点时就可以判断是否进行提取。

    /**
     * @author zzj
     * @date 2021-12-6 03:42:55
     */
    public class TreeNode {
        /**
         * 孩子节点
         */
        public Vector<TreeNode>childNodes =new Vector<>();
        /**
         * 是否为结束标志
         */
        public boolean isLast = false;
        /**
         * 节点的值
         */
        public String nodeVal;
    
        @Override
        public String toString() {
            return "TreeNode{" +
                    "childNodes=" + childNodes +
                    ", isLast=" + isLast +
                    ", nodeVal='" + nodeVal + '\'' +
                    '}';
        }
    }
    

    ​ 首先我们利用递归来建立这些以非终结符为根的树。用到两个函数,buildProductionTree()建立产生式树,对于每一个非终结符的所有产生式进行addProductionToTree()函数。

    ​ buildProductionTree()对于每一个非终结符建立起一个数根,然后这个非终结符所有的产生式,将产生以空格分割成字符串数组,从0层开始,进行addProductionToTree递归。

    ​ addProductionToTree(),参数为根节点,字符串数组,树的层数。字符串数组的大小也就表明了该产生式能走到树的层数,这也就是递归出口,出口对于产生式的字符串数组也就是走到的最后一层的节点,这里将isLast表识为true,证明此节点为一个产生式末尾。对于产生式就是一个$的情况,我们不需要对其建立节点,直接返回即可。结点建立的过程中,一些值的节点已经建立我们直接跳过进行下一步节点,若该节点不存在则建立节点加入到根节点之后再进行下一步递归。

        /**
         * 建立产生式树
         */
        public void buildProductionTree() {
            for (String left : production.keySet()) {
                TreeNode root = new TreeNode();
                for (String right : production.get(left)) {
                    String[] strs = right.split(" ");
                    addProductionToTree(root, strs, 0);
                }
                productionTree.put(left, root);
            }
            System.out.println("产生式树:" + productionTree);
        }
        /**
         * 添加产生式到树结点
         *
         * @param root  树结点
         * @param right 产生式
         * @param i     产生式位置
         */
        private void addProductionToTree(TreeNode root, String[] right, int i) {
            if (right[0].equals("$")) {
                return;
            }
            if (i == right.length) {
                root.isLast = true;
                return;
            }
            for (TreeNode childNode : root.childNodes) {
                if (childNode.nodeVal.equals(right[i])) {
                    addProductionToTree(childNode, right, i + 1);
                    return;
                }
            }
            TreeNode newChildNode = new TreeNode();
            newChildNode.nodeVal = right[i];
            root.childNodes.add(newChildNode);
            addProductionToTree(newChildNode, right, i + 1);
        }
    

    ​ 输入示例建立树:

    A -> a a a a | a a b c | a a b d | a a
    非终结符A的产生式如下图:
    图示中标红的节点则表示为该节点为一个产生式的结尾
    

    在这里插入图片描述

    ​ 有了上面这个图我们就能很清楚的两个产生式之间的最大公共前缀。下面我们根据这个树来提取我们最大公共前缀。

    ​ 辅助函数isPrefix()来判断产生式中前缀是否为prefix

    /**
         * 判断是否包含前缀
         *
         * @param right
         * @param prefix
         * @return
         */
        private boolean isPrefix(String right, String prefix) {
            String[] str1 = right.trim().split(" ");
            String[] str2 = prefix.trim().split(" ");
            if(str2.length>str1.length)
            {
                return false;
            }
            for (int i = 0; i < str2.length; i++) {
                if (!str1[i].equals(str2[i])) {
                    return false;
                }
            }
            return true;
        }
    

    ​ 提取左公共因子,下面对树节点采用后序遍历,也就是自底向上,自底向上能够很好的确定我们的最大公共因子,深入底部在此以上的父节点就是我们的公共因子。

    ​ leftFactoring后序遍历入口,对每个非终结符进行getLeftFactorProduction()。

    ​ getLeftFactorProduction()函数需要维护我们的前缀prefix,每到一个节点将其值加入到prefix中,返回值int也很重要,这决定我们是否提取。每到一个结点,递归其子节点,对其返回值用total相加,若total值大于2,则证明子节点下面有两个文法经过于此,调用updateProduction()函数进行在产生式集中提取,为何这个节点能成为最大的公共前缀,因为每提取一次公共因子我们的total值都会变为1,想上传的最大值就为1,自底向上所以就能保证在下面的时候就进行提取公共因子。

    ​ updateProduction()获取到最大公共前缀,我们就能在产生中进行提取合并,产生新的非终结符。因为这一步产生的新的非终结符可能很多,我们保证新产生的非终结符在NT中不存在,利用循环决定加入“ ‘ ” 的个数。得到的非终结符加入道NT中,然后遍历原来的非终结符的所有产生式,匹配我们的最大前缀成功匹配的就提取替换,不匹配保证原来的产生式即可。

        /**
         * 提取左公因子 获得新文法
         */
        public void leftFactoring() {
            for (int i = 0; i < NT.size(); i++) {
                String left = NT.elementAt(i);
                if (productionTree.containsKey(left)) {
                    getLeftFactorProduction(left, productionTree.get(left), "");
                }
            }
            System.out.println("新文法:" + production);
        }
        /**
         * 获取产生式最大公共前缀
         *
         * @param left   非终结符
         * @param root   树节点
         * @param prefix 前缀
         * @return 占有公共前缀结点数量
         */
        private int getLeftFactorProduction(String left, TreeNode root, String prefix) {
            int total = 0;
            for (TreeNode childNode : root.childNodes) {
                total += getLeftFactorProduction(left, childNode, prefix.trim() + " " + childNode.nodeVal);
            }
            if (root.isLast) {
                total++;
            }
            if (total >= 2) {
                total = 1;
                if (!prefix.equals("")) {
                    updateProduction(left, prefix);
                }
            }
            return total;
        }
        /**
         * 更新产生式
         *
         * @param left   非终结符
         * @param prefix 前缀
         */
        private void updateProduction(String left, String prefix) {
            String newLeft = left + "'";
            while (NT.contains(newLeft)) {
                newLeft += "'";
            }
            NT.insertElementAt(newLeft, NT.indexOf(left) + 1);
            Vector<String> rights1 = new Vector<>();
            Vector<String> rights2 = new Vector<>();
            for (String right : production.get(left)) {
                //匹配到前缀
                if (isPrefix(right, prefix)) {
                    String newRight = prefix.trim() + " " + newLeft;
                    if (!rights1.contains(newRight)) {
                        rights1.add(newRight.trim());
                    }
                    String tmp = right.replaceFirst(prefix.trim(), "").trim();
                    rights2.add("".equals(tmp) ?"$":tmp);
                } else {
                    rights1.add(right.trim());
                }
            }
            production.replace(left, rights1);
            production.put(newLeft, rights2);
        }
    

    ​ 输入示例执行结果:

    A -> a a a a | a a b c | a a b d | a a
    
    第二个新文法即为我们执行提取左公因子的结果
    

    在这里插入图片描述

    4.求FIRST集

    在这里插入图片描述

    ​ 我们创建新的对象来存储我们FIRST集合

        /**
         * first集
         */
        private Map<String, HashSet<String>> FIRST = new HashMap<>();
    

    ​ 参照龙书上的描述来实现我们求FIRST程序。首先将所有非终结符以First(x)=x的形式存入FIRST对象中;依照描述我们的 字 符 也 将 加 入 到 F I R S T 集 合 中 。 然 后 遍 历 所 有 的 非 终 结 符 , 对 非 终 结 符 的 所 有 文 法 进 行 扫 描 , 获 取 文 法 的 第 一 个 字 符 , 若 该 字 符 在 F I R S T 集 合 中 , 则 该 字 符 的 F I R S T 集 合 将 加 入 到 第 一 个 字 符 的 F I R S T 集 合 中 ; 对 于 文 法 中 第 一 个 字 符 为 字符也将加入到FIRST集合中。然后遍历所有的非终结符,对非终结符的所有文法进行扫描,获取文法的第一个字符,若该字符在FIRST集合中,则该字符的FIRST集合将加入到第一个字符的FIRST集合中;对于文法中第一个字符为 FIRSTFIRSTFIRSTFIRST的情况,因为 的 F I R S T 集 合 为 的FIRST集合为 FIRST,则对于这个非终结符的FIRST集合中加入$。我们将上述描述多执行几遍来达到最终效果,因为第一次执行时,需要的非终结符FIRST集合还不存在,需要执行生成了再第二遍时使用。

    ​ 辅助函数:

        /**
         * 获取右部的第一个字符
         *
         * @param right
         * @return
         */
        public String getFirstStr(String right) {
            String[] strs = right.trim().split(" ");
            return strs[0];
        }
    
        /**
         * 获取FIRST集合
         */
        public void getFirst() {
            FIRST.clear();
            //将所有终结符加入到FIRST集合
            for (String t : T) {
                HashSet<String> firsts = new HashSet<String>();
                firsts.add(t);
                FIRST.put(t, firsts);
            }
            HashSet<String> tmp = new HashSet<String>();
            tmp.add("$");
            FIRST.put("$", tmp);
            //非终结符
            int k = 0;
            while (k < 5) {
                for (String Ai:NT) {
                    //所有文法
                    for (String right : production.get(Ai)) {
                        //是否需要加入$
                        boolean flag = true;
                        //第一个token
                        String first = getFirstStr(right);
                        //终结符  非终结符就是自己  $  //&& !FIRST.get(first).isEmpty()
                        if (FIRST.containsKey(first) ) {
                            for (String firstNext : FIRST.get(first)) {
                                if (firstNext.equals("$")) {
                                    continue;
                                } else {
                                    flag = false;
                                    if (!FIRST.containsKey(Ai)) {
                                        HashSet<String> firsts = new HashSet<>();
                                        firsts.add(firstNext);
                                        FIRST.put(Ai, firsts);
                                    } else {
                                        FIRST.get(Ai).add(firstNext);
                                    }
                                }
                            }
                            if (flag) {
                                if (!FIRST.containsKey(Ai)) {
                                    HashSet<String> firsts = new HashSet<>();
                                    firsts.add("$");
                                    FIRST.put(Ai, firsts);
                                } else {
                                    FIRST.get(Ai).add("$");
                                }
                            }
                        }
                    }
                }
                k++;
            }
            System.out.println("First集:" + FIRST);
        }
    

    5.求FOLLOW集

    在这里插入图片描述在这里插入图片描述

    ​ 创建我们的FOLLOW集合对象

        /**
         * follow
         */
        private Map<String, HashSet<String>> FOLLOW = new HashMap<>();
    

    ​ 同样根据龙书描述,但我们的程序中字符KaTeX parse error: Expected 'EOF', got '#' at position 12: 表示为空,这里我们使用#̲表示结束标记。首先在FOLLO…,包含则执行我们3)规则。上述过程也执行多次来达到最终状态,与求FIRST集合同理。

    ​ 辅助函数:

        /**
         * 获取当前字符的下一个字符
         * @param right 右部
         * @param B 当前字符
         * @return 返回字符串
         */
        public String getNextStr(String right,String B)
        {
            String strs[] = right.trim().split(" ");
            for (int i =0;i<strs.length;i++)
            {
                if(strs[i].equals(B)&&i+1<strs.length)
                {
                    return strs[i+1];
                }
            }
            return " ";
        }
        /**
         * 判断右部是否包含 B
         * @param right 右部
         * @param B 字符
         * @return true包含
         */
        public boolean isContain(String right,String B)
        {
            String strs[] = right.trim().split(" ");
            for (String str:strs)
            {
                if(str.equals(B))
                {
                    return true;
                }
            }
            return false;
        }
    
        /**
         * 添加follow
         * @param left
         * @param hs
         */
        public void addFollow(String left,HashSet<String> hs)
        {
            if(FOLLOW.containsKey(left))
            {
                FOLLOW.get(left).addAll(hs);
            }
            else{
                FOLLOW.put(left,hs);
            }
        }
    
        /**
         * 获取Follow集
         */
        public void getFollow() {
            FOLLOW.clear();
            HashSet<String> follows = new HashSet<String>();
            follows.add("#");
            FOLLOW.put(NT.elementAt(0), follows);
    
            //若A->αBβ是一个产生式,则把First(β)-{ε}加入到Follow(B)中
            //若A->αB是一个产生式,或者A->αBβ是一个产生式且β->ε,则把Follow(A)加入到Follow(B)中
            int k = 0;
            while (k < 5) {
                for (String A:NT)
                {
                    for (String right:production.get(A))
                    {
                        if(right.equals("$"))
                        {
                            continue;
                        }
                        for (String B:NT)
                        {
                            if(A.equals(B))
                            {
                                continue;
                            }
                            if(isContain(right,B))
                            {
                                //B后面的字符
                                String b = getNextStr(right,B);
                                if(!" ".equals(b))
                                {
                                    addFollow(B, (HashSet<String>) FIRST.get(b).clone());
                                    FOLLOW.get(B).remove("$");
                                    if(FIRST.get(b).contains("$")&&FOLLOW.containsKey(A))
                                    {
                                        addFollow(B, FOLLOW.get(A));
                                    }
                                }
                                else
                                {
                                    //B后无字符
                                    if(FOLLOW.containsKey(A))
                                    {
                                        addFollow(B, FOLLOW.get(A));
                                    }
                                }
    
                            }
                        }
                    }
                }
                k++;
            }
            System.out.println("Follow集:"+FOLLOW);
        }
    

    6.获取分析表

    在这里插入图片描述

    ​ 在实现了FIRST和FOLLOW集后我们的分析表就能很快实现,根据龙书上提出的方法完成我们的分析表,创建分析表对象

        /**
         * 分析表
         */
        private Map<Pair<String, String>, String> Table = new HashMap<>();
    

    ​ 遍历所有的非终结符的产生式,提取产生式的第一个第一字符,判断其FIRST集合中是否包含 , 若 包 含 则 在 分 析 表 中 加 入 该 非 终 结 符 的 所 有 F O L L O W 集 合 ; 反 之 不 包 含 ,若包含则在分析表中加入该非终结符的所有FOLLOW集合;反之不包含 FOLLOW,则将第一个字符的FIRST集合加入值分析表中。

        /**
         * 获得分析表
         */
        public void getTable()
        {
            for (String A:NT)
            {
                for (String right:production.get(A))
                {
                    String first=getFirstStr(right);
                    right = A +"->"+ right;
                    if(FIRST.get(first).contains("$"))
                    {
                        for (String a:FOLLOW.get(A))
                        {
                            Pair<String,String> symbol =new Pair<>(A,a);
                            Table.put(symbol,right);
                        }
                    }
                    else
                    {
                        for (String a:FIRST.get(first))
                        {
                            Pair<String,String> symbol =new Pair<>(A,a);
                            Table.put(symbol,right);
                        }
                    }
                }
            }
            System.out.println("分析表:"+Table);
        }
    

    7.建立语法树

    在这里插入图片描述

    ​ 首先输入字符串进行语法分析,根据龙书步骤,首先在输入字符后面加上结束标志#,同时在栈里面最先也加入结束标志#,两个结束表示用于匹配时结束程序。

    ​ 循环栈,查看栈顶元素,维护输入字符串下标,若栈顶元素与当前字符串下标的字符相等,弹出栈顶,字符串下标右移;当栈顶为终结符或在分析表中查询不到有值的情况跳过;最后一种情况就在分析表中查找的有值,我们取出分析表的值,将栈顶推出,然后将分析表的值倒置后加入栈中,同时要去除掉产生式是$字符。我们的语法树结点嵌套在最后一个情况,当从分析表中取出产生式时,我们利用栈将产生式记录下来,在后面用来建立我们的语法树。

    ​ 接下来建立语法书,根据我们存储的产生式的栈,循环栈直到空,每次取出栈顶的产生式,将其建立节点,符号->左边的为父节点,右边的全是其子节点,但子节点中只需要加入终结符的子节点,因为非终结符节点将以此创建;栈的好处是因为能模仿低估具有树结构的顺序,我们将每次建立其节点存储到新的节点栈中,每次加入这个节点栈时判断,当前要加入的节点的产生式中是否包含 已经在栈中的节点的非终结符,如果包含,取出节点栈栈顶节点,将其作为要加入节点的子节点,直到栈顶节点不包含为止 ,再将要加入的节点压入栈中。最后我们的节点栈中存储的一个节点就是我们的语法树的树根。

        /**
         * 语法分析
         * @param input 输入字符串
         */
        public void parser(String input)
        {
            //加入结束标志
            input +=" #";
            String[] inputs =input.trim().split(" ");
            int k = 0;
            Stack<String> analysis =new Stack<>();
            //加入结束标志
            analysis.add("#");
            analysis.add(S);
            while (!analysis.isEmpty())
            {
                //查看栈顶
                String top = analysis.peek();
                if(top.equals(inputs[k]))
                {
                    //栈顶与输入匹配
                    String tmp =  analysis.pop();
                    System.out.println("匹配:"+tmp);
                    k++;
                }
                else if(T.contains(top))
                {
                    //终结符包含top
    			   break;
                }
                else if(!Table.containsKey(new Pair<>(top,inputs[k])))
                {
                    //分析表中不存在
                    break;
                }
                else
                {
                    //分析表中取出产生式
                    String str = Table.get(new Pair<>(top,inputs[k]));
                    analysis.pop();
                    System.out.println("输出:"+str);
                    //加入语法栈
                    stack.add(str);
                    String []strs =str.split("->");
                    String []strss = strs[1].split(" ");
                    Collections.swap(Arrays.asList(strss),0,strss.length-1);
                    analysis.addAll(Arrays.asList(strss));
                    analysis.remove("$");
                }
            }
        }
    
        /**
         * 根据产生式创建节点
         * @param str   文法
         * @return 节点
         */
        public TreeNode createNode(String str)
        {
            String[] strs = str.trim().split("->");
            TreeNode root =new TreeNode(strs[0]);
            String[] strss = strs[1].trim().split(" ");
            for (String tmp:strss)
            {
                if(T.contains(tmp)||tmp.equals("$"))
                {
                    TreeNode tmpNode=new TreeNode(tmp);
                    root.childNodes.add(tmpNode);
                }
            }
            return root;
        }
        /**
         * 建立语法树
         */
        public void buildTree()
        {
            //节点栈
            Stack<TreeNode> stackNode =new Stack<>();
            while (!stack.isEmpty())
            {
                //文法
                String str = stack.pop();
                TreeNode newNode =createNode(str);
                //在栈中寻找子节点  栈顶是否子节点
                while (!stackNode.isEmpty()&&isContain(str.trim().split("->")[1],stackNode.peek().nodeVal))
                {
                    TreeNode childNode = stackNode.pop();
                    newNode.childNodes.add(childNode);
                }
                stackNode.add(newNode);
            }
            if(stackNode.size()!=1)
            {
                System.out.println("错误!!!!!!!!!!!!!!!");
            }
            root=stackNode.pop();
            System.out.println(root);
        }
    
    展开全文
  • 编译原理LL1文法实现

    2012-12-23 16:41:08
    编译原理LL1文法实现,使用D盘下TXT文档输入字符串例子
  • 编译原理课程设计,LL1文法的实现。采用MFC。输入文法,分别求出每一个非终结符FIRST 集FOLLOW集和SELECT集,画出预测分析表,判定读入的文法是否是LL(1)文法,给定的任意符号串判定是否是文法中的句子,将分析过程...
  • 编译原理LL1实验

    2015-06-30 12:12:09
    实现了LL1算法,有详细的实验报告截图等等
  • 编译原理LL1文法MFC

    2015-06-30 17:02:27
    编译原理开发设计,采用LL1文法,界面MFC设计。
  • 编译原理语法分析器的Python实现-LL1文法,属于编译原理课程相关作业。输出结果保存为csv文件,直观了解分析全过程
  • 编译原理课程实验-LL(1) 语法分析实验实验目的:1.了解 LL(1)语法分析是如何根据语法规则逐一分析词法分析所得到的单词,检查语法错误,即掌握语法分析过程;2.掌握LL(1)文法判别调剂和 LL(1)语法分析器的设计与...
  • 自己实现的编译原理LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行,代码注释丰富,希望与大家交流学习!欢迎大家下载!
  • 大学编译原理实验用,LL1文法(C++编写)。不错的资源
  • 编译原理——LL1分析程序实验(C#)

    千次阅读 2019-09-15 16:25:40
      编制一个能识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序),输出对输入符号串的分析过程。 实验内容   对于这个实验,核心内容是Process类。该类是一个带有三个参数的构造函数。将初始...

    LL(1)分析程序实验目的与要求

      编制一个能识别由词法分析给出的单词符号序列是否是给定文法的正确句子(程序),输出对输入符号串的分析过程。

    实验内容

      对于这个实验,核心内容是Process类。该类是一个带有三个参数的构造函数。将初始分析栈,输入的句子,预测分析表作为参数注入该类,调用BeginAnalyze()函数进行分析,同时Process本身属性在函数的循环中发生迭代变化,其自身的属性代表了每一分析步骤的结果,打印即可。

    实验步骤

    • 主函数内容:先打印出给定文法,预测分析表,然后对用户输入,构造Process类,进行分析。
    • 获取推导所用的产生式或匹配:GetProductionRule()
      需要调用GetRowIndex(StackTop)和 GetColIndex(Terminal)根据分析栈的栈顶元素与输入字符串首字符来获取预测分析表的内容。
    • 反转字符串函数 Reverse(string s):该函数用于将产生式元素逆序入栈
                private string Reverse(string s)
                {
                    char[] cs= s.ToCharArray();
                    Array.Reverse(cs);
                    return new string(cs);
                }
    

      值得一提的是本程序并没有使用Stack数据结构来完成,而是使用了对字符串的操作来代替Stack。

    在这里插入图片描述
    在这里插入图片描述

    using System;
    using System.Collections.Generic;
    using static System.Console;
    
    namespace LL1
    {
    
        class Program
        {
            /// <summary>
            /// 文法
            /// </summary>
            static List<string> Grammar = new List<string>()
            {
                "E->TB","B->+TB|ε",
                "T->FY","Y->*FY|ε",
                "F->i|(E)"
            };
            /// <summary>
            /// 预测分析表
            /// </summary>
            /// <param name="args"></param>
            static string[,] predictTab =
            {
                {"  ",   "i",     "+",    "*",    "(",    ")",    "#" },
                {"E"   ,   "TB",   "NULL", "NULL", "TB",  "NULL", "NULL" },
                {"B"  ,   "NULL",  "+TB", "NULL", "NULL", "ε",   "ε"},
                {"T"   ,   "FY",   "NULL", "NULL", "FY",  "NULL", "NULL" },
                {"Y"  ,   "NULL",  "ε",   "*FY", "NULL", "ε",   "ε" },
                {"F"   ,   "i",     "NULL", "NULL", "(E)",  "NULL", "NULL" }
            };
    
            static void Main(string[] args)
            {
                DisplayG();
                DisplayTab();
                WriteLine("请输入要分析的串:");
                string inputString = ReadLine();
                WriteLine("--------------------------------------------------------------------------");
                string symbolStack = "#E";
                Process process = new Process(symbolStack, inputString, predictTab);
                process.BeginAnalyze();
            }
    
    
            /// <summary>
            /// 打印文法列表
            /// </summary>
            static void DisplayG()
            {
                WriteLine("文法列表  (将课件例题中的 E' 换成了 B , T' 换成了 Y)");
                foreach (string s in Grammar)
                {
                    WriteLine(s);
                }
                WriteLine("--------------------------------------------------------------------------");
            }
            /// <summary>
            /// 打印预测分析表
            /// </summary>
            static void DisplayTab()
            {
                WriteLine("{0,35}", "预测分析表");
                for (int i = 0; i < predictTab.GetLength(0); i++)
                {
                    for (int j = 0; j < predictTab.GetLength(1); j++)
                    {
                        Write($"{predictTab[i, j],-10}");
                    }
                    WriteLine();
                }
                WriteLine("--------------------------------------------------------------------------");
            }
    
            class Process
            {
                public int index;//步骤
                public string symbolStack;//分析栈
                public string residueString;//剩余串
                public string productionRule;//产生式或匹配
                public string[,] predictTab;//预测表
    
                public Process(string symbolStack, string inputString, string[,] predictTab)
                {
                    this.index = 1;
                    this.symbolStack = symbolStack;
                    this.residueString = inputString;
                    this.predictTab = predictTab;
                }
                
                //当前输入符号
                public string Terminal
                {
                    get
                    {
                        return residueString.Substring(0, 1);
                    }              
                }
                //分析栈栈顶元素
                public string StackTop
                {
                    get
                    {
                        return symbolStack.Substring(symbolStack.Length - 1, 1);
                    }
                }
                //产生式首字符
                public string ruleTop
                {
                    get
                    {
                        return productionRule.Substring(0,1);
                    }
                }
                /// <summary>
                /// LL(1) 分析
                /// </summary>
                public void BeginAnalyze()
                {                
                    while (true)
                    {
                        productionRule = GetProductionRule();
                        Display();
                        symbolStack = symbolStack.Substring(0, symbolStack.Length - 1);
                        if (productionRule== "ε")
                        {
                            index++;
                            continue;
                        }
                        if (ruleTop == Terminal)
                        {
                            if (residueString.Length == 1)
                            {
                                WriteLine("     分析完成,匹配成功!");
                                return;
                            }
                            else
                            {
                                residueString = residueString.Substring(1, residueString.Length-1);
                                if (productionRule.Length > 1)
                                {
                                    symbolStack += Reverse(productionRule.Substring(1, productionRule.Length - 1));
                                }
                            }
                        }
                        else
                        {
                            residueString = residueString.Substring(0, residueString.Length);
                            symbolStack += Reverse(productionRule);
                        }
                        index++;
                    }
                }
    
                /// <summary>
                /// 获取推导所用的产生式或匹配
                /// </summary>
                /// <returns></returns>
                private string GetProductionRule()
                {                
                    int row = GetRowIndex(StackTop);
                    int col = GetColIndex(Terminal);
                    string rule = predictTab[row, col];
                    if (rule == "NULL")
                    {
                        Error();
                    }               
                    return rule;
                }
    
                /// <summary>
                /// 根据栈顶元素获取行号
                /// </summary>
                /// <param name="stackTop"></param>
                /// <returns></returns>
                private int GetRowIndex(string stackTop)
                {
                    int index = -1;
                    for(int i = 0; i < predictTab.GetLength(0); i++)
                    {
                        if (predictTab[i, 0] == stackTop)
                        {
                            index = i;
                        }
                    }
                    if (index == -1)
                    {
                        Error();
                    }
                    return index;
                }
    
                /// <summary>
                /// 根据当前终结符获取列号
                /// </summary>
                /// <param name="terminal"></param>
                /// <returns></returns>
                private int GetColIndex(string terminal)
                {
                    int index = -1;
                    for (int i = 0; i < predictTab.GetLength(1); i++)
                    {
                        if (predictTab[0, i] == terminal)
                        {
                            index = i;
                        }
                    }
                    if (index == -1)
                    {
                        Error();
                    }
                    return index;
                }
    
                /// <summary>
                /// 反转字符串
                /// </summary>
                /// <param name="s"></param>
                /// <returns></returns>
                private string Reverse(string s)
                {
                    char[] cs= s.ToCharArray();
                    Array.Reverse(cs);
                    return new string(cs);
                }
                
                /// <summary>
                /// 打印当前步骤
                /// </summary>
                private void Display()
                {
                    WriteLine($"{index,-20}{symbolStack,-20}{residueString,-20}{productionRule,-20}");
                }
    
                /// <summary>
                /// 出错处理程序
                /// </summary>
                private void Error()
                {
                    WriteLine("!!!!!!!!!!!!!!  语句非法  !!!!!!!!!!!!!!");
                    Environment.Exit(0);
                }
    
            }
            
        }
    }
    
    展开全文
  • LL(1)分析器 实验实验要求 简单要求: 至少做到对下列已知的文法,用LL(1)分析法对任意输入的符号串进行分析: (1)E->TG (2)G->+TG (3)G->ε (4)T->FS (5)S->*FS (6)S->ε (7)...

    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();
    
    }
    
    
    展开全文
  • 编译原理--LL1文法.zip

    2020-05-17 17:35:39
    LL(1)语法分析器的设计与实现
  • 通过课程设计进一步理解高级语言在计算机中的执行过程,加深对编译原理中重点算法和编译技术的理解,提高自己的编程能力,培养好的程序设计风格。同时通过某种可视化编程语言的应用,具备初步的Windows环境下的编程...
  • 通过完成预测分析法的语法分析程序,了解预测分析法和递归子程序法的区别和联系。使了解语法分析的功能,掌握语法分析程序设计的原理和构造方法,训练掌握开发应用程序的基本方法。
  • 编译原理LL1文法的mfc实现,其中包括对LL1文法的First集合的算法,Follow集合的算法 select集合的算法 还包括消除左递归 提取左因子
  • LL1分析法,对于给定文法进行判断是否位LL1文法,并做相应变换使之满足LL1输出格式,对于给定的表达式和字符串输出预测分析过程 功能代码完善而全面,有图形化界面供大家参考。
  • 1.掌握LL(1)分析法的基本原理 2.掌握LL(1)分析表的构造方法 3.掌握LL(1)驱动程序的构造方法 4.加深对LL(1)分析法的理解 二.实验内容及要求 已知某LL(1)文法包含的产生式(其中E为开始符)及产生式相应的SELECT集...
  • import hjzgg.first.First; import java.util.LinkedHashMap; import java.util.Map; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; public class Follow { ... pr...
  • 编译原理 LL1文法分析

    2010-12-11 16:59:01
    很好的LL1文法分析工程,详细解析了LL1文法分析的过程。
  • "右线性文法错误!" ); } new First(mp).firstKernealCode(); } } 本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4454618.html,如需转载请自行联系原作者 ...
  • 编译原理实验LL(1)文法的判断及转换 作者: 日期: ? 2016.11.30 LL(1)文法的判断及转换 目录 TOC \o "1-3" \h \z \u 一实验名称 2 二实验目的 2 三实验原理 2 1First集定义 2 2Follow集定义 2 3Select集定义 3 4含左...
  • System.out.println("右线性文法错误!"); } First first= newFirst(mp); first.firstKernealCode(); Follow follow= newFollow(mp, first.getFirstSet()); follow.followKernealCode(); AnalysisTable ...
  • 编译原理-LL1文法分析-java
  • 编译原理 LL1文法的判断和句子识别

    万次阅读 2017-02-23 21:14:14
    编译原理 LL1文法的判断和句子识别 LL1文法概述 点击查看百度百科 对文法G的句子进行确定的自顶向下语法分析的充分必要条件是,G的任意两个具有相同左部的 产生式A—>α|β 满足下列条件: (1)如果α、β...
  • 编译原理实验——LL(1)文法分析 1、实验目的与内容 先输入一段文法,自动提取左公共因子,消除左递归,构建预测分析表。在输入一个表达式,进行表达式的分析。 文法由文件输入,如上图所示,要分析的表达式由控制台...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 806
精华内容 322
关键字:

编译原理ll1文法实验