精华内容
下载资源
问答
  • 2021-05-22 01:14:54

    《LL1语法分析器_B12040921》由会员分享,可在线阅读,更多相关《LL1语法分析器_B12040921(15页珍藏版)》请在人人文库网上搜索。

    1、实 验 报 告(2014/2015学年 第二学期)课程名称编译原理实验名称语法分析器的构造实验时间2015年5月29日指导单位计算机学院软件工程系指导教师蒋凌云学生姓名Cjj班级学号B-学院(系)计算机学院专 业NIIT成 绩批阅人日期实 验 报 告实验名称语法分析器的构造指导教师蒋凌云实验类型上机实验学时4实验时间2015-5-14一、 实验目的和要求设计、编制、调试一个LL(1)语法分析程序,利用语法分析器对符号串进行识别,加深对语法分析原理的理解。要求设计并实现一个LL(1)语法分析器,实现对算数文法E-E+T|T T-T*F|F F-(E)|i 所定义的符号串进行识别。二、 实验环境(。

    2、实验设备)Mac OS X + Python三、 实验原理及内容AnalyseMachine:Load( )方法 载入文法规则,自动求出First集,Follow集,分析表Judge( )方法 判断某一字符串是否为当前文法的句子程序代码#coding:utf-8#LL(1)分析法#By:Importcjj#由于仓促,代码有很多地方不是科学,但是基本功能已经实现#2015-6-15class AnalyseMachine(object):def __init__(self):passdef load(self, Grammers):载入文法规则参数Grammers: 文法的规则列表self.Gr。

    3、ammers = Grammersself.noLeftRecursionGrammers = self.__NoLeftRecursion(self.Grammers)self.start = self.Grammers00self.nChars = self.__GetVn(self.noLeftRecursionGrammers)self.tChars = self.__GetVt(self.noLeftRecursionGrammers)self.firstSet = self.FirstSet(self.noLeftRecursionGrammers)self.followSet =。

    4、 self.FollowSet(self.noLeftRecursionGrammers)self.analyseTable = self.AnalyseTable(self.noLeftRecursionGrammers, self.firstSet, self.followSet)def Judge(self, string):判断字符串是否为当前文法的句子isMatch = FalseanalyseStack = #, self.startStringStack = list(string) + #print u=*25,u判断字符串=%s%string,u=*25print %-30s。

    5、%-12s%s%(u分析栈,u余留输入串,u所用生成式)try:while analyseStack:xm = analyseStack-1ai = StringStack0print %-20s%20s%10s%(.join(analyseStack),.join(StringStack), ),if xm in self.nChars:analyseStack.pop()expression = self.analyseTablexmaiif expression = ERROR:printraise ValueErrorprint expression,index = expressio。

    6、n.find(:=) + 3if self.__Split(expressionindex:):-1 != :analyseStack += self.__Split(expressionindex:):-1 #逆序加入elif xm = ai and xm != #:analyseStack.pop()StringStack.pop(0)elif xm = ai and xm = #:analyseStack.pop()isMatch = Trueprintexcept Exception as e:passresult = u%s 为文法定义的句子 if isMatch else u%s 。

    7、不是文法定义的句子print result%stringprint u=*25,u判断字符串=%s%string,=*25return isMatchdef FirstSet(self, Grammers):构造文法的First集speSymbol = :=Vn = self.nCharsVt = self.tCharsFirst = self.__SubExpressions(Grammers)#新建一个以所有非终结符作为键,以空列表作为值的字典FirstDict = for nChar in Vn:FirstDictnChar = lock = 1while First and lock=。

    8、 0:char = expressionindexif char = nChar:breakelif char in Vt:breakelif char not in nilChar:followLink2char.append(nChar)# print 1 add %s to follow %s%(nChar, char)breakelse:followLink2char.append(nChar)# print 2 add %s to follow %s%(nChar, char)index -= 1# print followLink2hasFollowChar = notFollow。

    9、Char = for nChar, links in followLink2.items():if not links:hasFollowChar.append(nChar)else:notFollowChar.append(nChar)# print hasFollowChar# print notFollowCharlock = 1while notFollowChar and lock 100:delChar = for nChar in notFollowChar:# print nChar is %s%nCharif set(followLink2nChar).issubset(se。

    10、t(hasFollowChar):for link in followLink2nChar:FollowDictnChar += FollowDictlinkdelChar.append(nChar)# print delChar, delChar# print hasFollowChar, hasFollowChar# print notFollowChar, notFollowCharfor char in delChar:hasFollowChar.append(char)notFollowChar.remove(char)lock += 1if lock = 100:print War。

    11、ning! The loop lock is walking.for nChar in Vn:FollowDictnChar = list(set(FollowDictnChar)return FollowDictdef AnalyseTable(self, Grammer, firstSet, followSet):建立文法的分析表Table = tChars = self.tCharsnChars = self.nCharsfor n_char in nChars:Tablen_char = for t_char in tChars:Tablen_chart_char = ERRORsub。

    12、Rules = for rule in Grammer:left_char = rule.split(:=)0rightExpressions = rule.split(:=)1subRules += left_char +:=+right_expression for right_expression in rightExpressions.split(|)for sub_rule in subRules:left_char, meetChars = self.__ExpressionAnalyse(sub_rule, firstSet, followSet)for meet_char in。

    13、 meetChars:Tableleft_charmeet_char=sub_rulereturn Tabledef __NoLeftRecursion(self, Grammers):消除文法规则的左递归RightFirstIndex = 4noLeftRecursionGrammers = for rule in Grammers:# print ruleindex = rule.find(:=) #左边终结符号的终止位置leftSymbol = rule:index #获取左边的非终结符rightFirstSymbol = ruleRightFirstIndex #获取右边的第一个符号i。

    14、f rightFirstSymbol = leftSymbol: #如果左边的非终结符与右边第一个符号相等,则进行消除左递归resultOne = symbol for symbol in ruleRightFirstIndex:.split(|) if leftSymbol not in symbol #单独取出含左非终结符的子表达式resultTwo = symbol for symbol in ruleRightFirstIndex:.split(|) if leftSymbol in symbol #单独取出不含左非终结符的子表达式# print resultTwonewLeftSym。

    15、bol = leftSymbol+ #引入一个新终结符resultOne = symbol + newLeftSymbol for symbol in resultOnerightExpressionOne = |.join(resultOne)expressionOne = rule0:RightFirstIndex+rightExpressionOne# print expressionOneresultTwo = symbol.replace(leftSymbol, )+newLeftSymbol for symbol in resultTworesultTwo.append()righ。

    16、tExpressionTwo = |.join(resultTwo)expressionTwo = newLeftSymbol+rule1:RightFirstIndex+rightExpressionTwo# print expressionTwonoLeftRecursionGrammers += expressionOne,expressionTwo #返回经过改写法消除直接左递归后的文法规则# print ruleelse:noLeftRecursionGrammers += rule #如果不含直接左递归,则直接返回return noLeftRecursionGrammersdef 。

    17、__GetVt(self, Grammer):获取文法中的终结符号Vt = speSymbol = :=Vn = self.__GetVn(self.noLeftRecursionGrammers)Vn.append(speSymbol)Vn.append()Vn.append(|)for grammer in Grammer:for symbol in Vn:grammer = grammer.replace(symbol,)for char in grammer:if char not in Vt:Vt.append(char)# for char in Vt:# print charre。

    18、turn Vtdef __GetVn(self, Grammer):获取文法中的非终结符号Vn = for grammer in Grammer:index = grammer.find(:=) #左边终结符号的终止位置char = grammer:indexif char not in Vn:Vn.append(char)return Vndef __SubExpressions(self, Grammer):获取文法的子规则集形如左边非终结符: 对应的右边的所有文法子规则speSymbol = :=_Grammer = for grammer in Grammer:_grammer = g。

    19、rammer.split(speSymbol)_Grammer_grammer0 = _grammer1#新建一个字典subExpressions 形如非终结符: 所有文法子规则subExpressions = for nChar, rightExpression in _Grammer.items():subExpressionsnChar = subExpression for subExpression in rightExpression.split(|)# print subExpressionsreturn subExpressionsdef __Split(self, Expre。

    20、ssion):将一个文法规则按单个字符切分char_list = length = len(Expression)for _ in xrange(length):char = Expression_if char = :char_list_ - 1 += charelse:char_list.append(char)return char_listdef __ExpressionAnalyse(self, expression, firstSet, followSet):建立分析表时,判断某个表达式应该填入分析表的哪一个位置tChars = self.tCharsnChars = self.n。

    21、Charsleft_char, rightChars = expression.split(:=)meetChars = for right_char in rightChars:if right_char = :meetChars += followSetleft_charbreakelif right_char in tChars:meetChars.append(right_char)breakelse:meetChars += firstSetright_charif not in firstSetright_char:breakelse:meetChars.remove()retur。

    22、n left_char, meetCharsif __name__ = __main__:import pprint# grammer_list = A:=BCc|gDB, B:=|bCDE, C:=DaB|ca, D:=|dD, E:=gAf|cgrammer_list = E:=E+T|T, T:=T*F|F, F:=(E)|i# grammer_list = S:=iCtSS|a, S:=eS|, C:=bll1am = AnalyseMachine()ll1am.load(grammer_list)print u消除文法左递归print ll1am.noLeftRecursionGra。

    23、mmersprint u非终极符print ll1am.nCharsprint u终结符print ll1am.tCharsprint uFirst集pprint.pprint(ll1am.firstSet)print uFollow集pprint.pprint(ll1am.followSet)print uLL(1)分析表pprint.pprint(ll1am.analyseTable)string1 = i+i*ill1am.Judge(string1)string2 = i*(i+i)ll1am.Judge(string2)string3 = i+i(i*i)ill1am.Judge(string3)实验结果:四、实验小结通过本次实验基本掌握了语法分析的原理和LL(1)语法分析方法,以及预测分析表的构造,了解了语法分析的过程。由于开始的时候不了解具体求法,感觉有点麻烦。但在仔细翻阅书本了解到了具体的分析方法后,就感觉手到擒来了。但是编写仓促,该程序虽然可以随意输入文法规则来分析,但是可能在一些小问题上还有待改进。如果有时间的话,还会好好改进一下的。

    更多相关内容
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行
  • LL1语法分析器(c++).rar

    2019-06-04 23:12:45
    LL1语法分析器,c++实现,first,follow,分析表算法详细注释,
  • 自己实现的编译原理的LL1语法分析器,是自己的实验作业,用Vs2017实现,可以直接运行,代码注释丰富,希望与大家交流学习!欢迎大家下载!
  • 可实现加分要求,实现所有文法而非课本给定文法的文法分析,并自动构造LL1分析表,仅供学弟学妹们参考思路,请勿直接当作作业提交,严禁发生抄袭等学术不端行为
  • 前言:编译原理实验要求做一个语法分析器,所以才有了这个项目 语法分析器 实验要求 PS:这里其实还可以选择算符优先分析法和SLR(1)分析法做的,但是由于我对预测分析法比较熟悉,所以… 测试用例 文字版: //...

    前言:编译原理实验要求做一个语法分析器,所以才有了这个项目

    LL1 语法分析器

    实验要求

    在这里插入图片描述

    PS:

    1. 这里其实还可以选择算符优先分析法和SLR(1)分析法做的,但是由于我对预测分析法比较熟悉,所以…
    2. 第五步的模拟分析过程这里我并没有实现…因为老师并没有要求实现这个模拟分析过程

    测试用例

    老师要求的测试用例:
    在这里插入图片描述
    我的测试用例:

    //直接左递归
    P——>Pa|b
    V——>Eabc|bc|Vabc|c
    
    E——>E+T|T
    T——>T*F|F
    F——>(E)|i
    
    //间接左递归
    S——>i|h|c|t|Qc
    Q——>Rb|b
    R——>Ba|a
    B——>Cf|H
    C——>Dd|d
    D——>Se|e
    H——>zy|x
    
    //无左递归
    S——>aSe|B
    B——>bBe|C
    C——>cCe|d
    
    //不是LL1文法
    S——>ABBA
    A——>a|ε
    B——>b|ε
    
    S——>AB|bC
    A——>b|ε
    B——>aD|ε
    C——>AD|b
    D——>aS|c
    
    S——>ABD|bC
    A——>b|ε
    B——>aD|ε
    C——>AD|b
    D——>aS|c
    
    S——>aAS|b
    A——>bA|ε
    

    实验步骤

    1、读取测试文件

    • FileUtil.java
    import java.io.*;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/2 23:30
     * 文件读取
     */
    public class FileUtil {
    
    
        /**
         * 读取文件文本内容
         * @param fileName
         * @return
         */
        public static BufferedReader readFile(String fileName) {
    
            BufferedReader bufferedReader = null;
            try {
                File myFile = new File(fileName);//通过字符串创建File类型对象,指向该字符串路径下的文件
    
                if (myFile.isFile() && myFile.exists()) { //判断文件是否存在
    
                    InputStreamReader Reader = new InputStreamReader(new FileInputStream(myFile), "UTF-8");
                    //考虑到编码格式,new FileInputStream(myFile)文件字节输入流,以字节为单位对文件中的数据进行读取
                    //new InputStreamReader(FileInputStream a, "编码类型")
                    //将文件字节输入流转换为文件字符输入流并给定编码格式
    
                    bufferedReader = new BufferedReader(Reader);
                    //BufferedReader从字符输入流中读取文本,缓冲各个字符,从而实现字符、数组和行的高效读取。
                    //通过BuffereReader包装实现高效读取
    
                } else {
                    System.out.println("找不到指定的文件");
                }
    
            } catch (Exception e) {
                System.out.println("读取文件内容出错");
                e.printStackTrace();
            }
    
            return bufferedReader;
    
        }
    
    
    }
    
    

    2、消除式子中可能存在的左递归

    • EliminateLeftRecursion.java
    import entity.Formula;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.util.*;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/2 22:36
     * 消除左递归(直接左递归和简介左递归)
     */
    public class EliminateLeftRecursion {
    
        //原始式子
        private Map<String,String> oldFormula = new HashMap<>();
        //消除左递归后的式子
        private Map<String,String> newFormula = new HashMap<>();
        //经过封装过的式子集合,主要作用是判断是否经历了间接左递归的递归查找过程
        private ArrayList<Formula> param = new ArrayList<>();
        //是否发生了左递归
        private boolean isHappenLeftRecursion;
    
        public boolean isHappenLeftRecursion() {
            return isHappenLeftRecursion;
        }
    
        public Map<String, String> getNewFormula() {
            return newFormula;
        }
    
        public Map<String, String> getOldFormula() {
            return oldFormula;
        }
    
    
        /**
         * 初始化数据
         * @param fileSrc
         */
        public EliminateLeftRecursion(String fileSrc) {
            BufferedReader bufferedReader = FileUtil.readFile(fileSrc);
            if (bufferedReader!=null){
                String lineText = null;
                while(true){
                    try {
                        if ((lineText = bufferedReader.readLine()) == null){
                            break;
                        }
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                    assert lineText != null;
                    String[]strings = lineText.split("——>");
                    Formula formulaEntity = new Formula(strings[0], strings[1]);
                    oldFormula.put(strings[0], strings[1]);
                    param.add(formulaEntity);
                }
            }
        }
    
        /**
         * 消除直接左递归
         * @param leftFormula
         * @param rightNonTerminal
         * @return
         */
        public boolean eliminateDirectLeftRecursion(String leftFormula, String rightNonTerminal) {
            //右侧由|分隔的符号集
            List<String> splitByLine = new ArrayList<>(Arrays.asList(rightNonTerminal.split("\\|")));
            int index = -1;
            //右侧大P所在的首部的字符串
            String oldFlag = null;
            int oldFlagIndex = 0;
            for (String string : splitByLine) {
                index = string.indexOf(leftFormula);
                if (index == 0) {
                    oldFlag = string;
                    break;
                }
                oldFlagIndex++;
            }
            //如果有直接左递归,进行消除直接左递归的操作
            if (index == 0) {
                //P'
                String newFlag = leftFormula + "'";
                //P'——>aP'|ε
                String newFormula1 = newFlag + "——>" + oldFlag.replace(leftFormula, "") + newFlag + "|ε";
                //移除直接左递归项
                splitByLine.remove(oldFlagIndex);
                //P——>bP'
                String newFormula2 = leftFormula + "——>";
                for (int i = 0; i < splitByLine.size(); i++) {
                    String str = splitByLine.get(i);
                    if (!str.equals("ε")){
                        newFormula2 = newFormula2 + str + newFlag;
                    }else{
                        newFormula2 = newFormula2 + str;
                    }
                    if (i + 1 < splitByLine.size()) {
                        newFormula2 = newFormula2 + "|";
                    }
                }
                String[] newFormulas1 = newFormula1.split("——>");
                String[] newFormulas2 = newFormula2.split("——>");
                newFormula.put(newFormulas1[0], newFormulas1[1]);
                newFormula.put(newFormulas2[0], newFormulas2[1]);
                isHappenLeftRecursion = true;
                return true;
            }else {
                newFormula.put(leftFormula, rightNonTerminal);
                return false;
            }
        }
    
        /**
         * 消除左递归
         * @return
         */
        public void eliminateLeftRecursion(){
            for(Formula formulaEntity: param){
                //如果已经进行过间接消除左查询,就不再循环
                if (formulaEntity.isRecursionFlag()){
                    continue;
                }
    
                //消除式子的直接左递归
                boolean flag = eliminateDirectLeftRecursion(formulaEntity.getLeft(), formulaEntity.getRight());
                //如果式子没有直接左递归,看看是否是间接左递归
                if (!flag){
                    String string1 = "";
                    //右侧由|分隔的符号集
                    List<String> splitByLine = new ArrayList<>(Arrays.asList(formulaEntity.getRight().split("\\|")));
                    //搜索是否有间接左递归
                    for (int i = 0;i < splitByLine.size();i++){
                        String string = splitByLine.get(i);
                        String flagNonTerminal = ""+string.charAt(0);
                        //判断是否存在首项是非终结符的
                        if (oldFormula.containsKey(flagNonTerminal)){
                            string = string.replaceFirst(flagNonTerminal, "");
                            //生成右边的式子
                            string1 = createRightFormulaString(formulaEntity.getLeft(), flagNonTerminal, string, i);
                            //如果最后面的符号是|,且是循环的最后一个元素的话,则去掉|
                            if (string1.charAt(string1.length()-1)=='|' && i==splitByLine.size()-1){
                                string1 = string1.substring(0, string1.length()-1);
                            }
                        }else{//如果首项不是终结符
                            string1 = string1 + string;
                            if (i+1<splitByLine.size()){
                                string1 = string1 + "|";
                            }
                        }
                    }
                    //消除式子的直接左递归
                    eliminateDirectLeftRecursion(formulaEntity.getLeft(), string1);
                }
    
                //清除已经递归了的元素中多余的式子
                for (Formula formulaEntity2: param){
                    if (formulaEntity2.isRecursionFlag()){
                        if (newFormula.containsKey(formulaEntity2.getLeft())){
                            String[]strings = newFormula.get(formulaEntity2.getLeft()).split("\\|");
                            for (String string: strings){
                                if (string.indexOf(formulaEntity.getLeft())==0){
                                    newFormula.remove(formulaEntity2.getLeft());
                                    break;
                                }
                            }
                        }
                    }
                }
            }
    
            //如果发生了消除左递归才进行打印
            if (isHappenLeftRecursion){
                System.out.println("消除左递归后的结果:");
                for (Map.Entry<String,String> entry: newFormula.entrySet()){
                    System.out.println(entry.getKey()+"——>"+entry.getValue());
                }
            }
        }
        
        public List<String> returnRightFormulaStringList(String flagNonTerminal, String leftFormula, String rightFormula){
            List<String> result = recursionSearch(flagNonTerminal, leftFormula);
            boolean flag = false;
            ListIterator<String> listIterator = result.listIterator();
            while(listIterator.hasNext()){
                String string = listIterator.next();
                if (string.equals("ε") && rightFormula.length()!=0){
                    List<String> list;
                    if (rightFormula.length() > 1){
                        String str1 = "" + rightFormula.charAt(0);
                        String str2 = rightFormula.replaceFirst(str1, "");
                        list = returnRightFormulaStringList(str1, leftFormula, str2);
                    }else{
                        String str1 = "" + rightFormula.charAt(0);
                        list = returnRightFormulaStringList(str1, leftFormula, "");
                    }
                    for (String s: list){
                        if (!s.equals("ε")){
                            listIterator.add(s+"ε");
                        }else{
                            if (rightFormula.length()<=1){//如果此时后面已经没有元素了且存在ε,则证明结果必有ε
                                //这里找一个特殊符号#代表ε,跟其他的多余的ε区分开来
                                listIterator.add("#"+"ε");
                            }
                        }
                    }
                    flag = true;
                }
            }
            if (flag){
                result.add("ε");
            }
            return result;
        }
    
        public String createRightFormulaString(String leftFormula, String flagNonTerminal, String string, int flag){
            List<String> result = returnRightFormulaStringList(flagNonTerminal, leftFormula, string);
            result.removeIf(str -> str.equals("ε"));
            String string1 = "";
            for (int j = 0;j < result.size();j++){
                String string2 = result.get(j);
                if (string2.indexOf(leftFormula) == 0){
                    newFormula.remove(flagNonTerminal);
                }
                int num = 0;
                for (int x = 0;x < string2.length();x++){
                    if (string2.charAt(x)=='ε'){
                        num++;
                    }
                }
                string2 = string2.substring(0, string2.length()-num);
                if (!string2.equals("ε")){
                    if (num == 0){
                        if (string2.equals("#")){
                            string1 = string1 + "ε";
                        }else{
                            string1 = string1 + string2 + string;
                        }
                    }else{
                        String str = "";
                        if (num <= string.length()){
                            str = string.substring(num, string.length());
                        }
                        if (string2.equals("#")){
                            string1 = string1 + "ε";
                        }else{
                            string1 = string1 + string2 + str;
                        }
                        result.set(j, string2.substring(0, string2.length()-1));
                    }
                }else{//如果是ε的话,后续得查看ε后面是否还有符号(终结符或非终结符)
                    string1 = string1 + result.get(j);
                }
                //后面还有元素,且该元素不为ε,就继续添加|分隔
                if (j+1<result.size() || flag < string.length()){
                    string1 = string1 + "|";
                }
            }
            return string1;
        }
    
        /**
         * 改变式子状态,如果进行过间接消除左递归的过程的,就设置recursionFlag为true
         * 即已经经过递归查找简介左递归的式子下次消除左递归就不用在遍历了
         * @param nonTerminal
         */
        public void perform(String nonTerminal){
            for(Formula formulaEntity: param){
                if (formulaEntity.getLeft().equals(nonTerminal)){
                    formulaEntity.setRecursionFlag(true);
                }
            }
        }
    
    
        /**
         * 递归向下搜寻、合并间接左递归
         * @param nonTerminal 式子本身的左终结符
         * @param targetCharacter 待搜寻的目标终结符
         * @return
         */
        public List<String> recursionSearch(String nonTerminal, String targetCharacter){
            String rightFormula = oldFormula.get(nonTerminal);
            List<String> rightFormulaCollection = new ArrayList<>(Arrays.asList(rightFormula.split("\\|")));
            perform(nonTerminal);
            newFormula.put(nonTerminal, rightFormula);
            for (int i = 0;i < rightFormulaCollection.size();i++){
                int index = -1;
                String string = rightFormulaCollection.get(i);
                index = string.indexOf(targetCharacter);
    
                //如果第一位是目的终结符,说明出现了间接左递归
                if (index == 0){
                    return rightFormulaCollection;
                }
    
                String flagNonTerminal = ""+string.charAt(0);
                if (oldFormula.containsKey(flagNonTerminal)){
                    List<String> result = recursionSearch(flagNonTerminal, targetCharacter);
                    String string1 = string.replace(flagNonTerminal,"");
                    String string2 = "";
                    for (int j = 0;j < result.size();j++){
                        string2 = result.get(j) + string1 + string2;
                        if (j+1 < result.size()){
                            string2 = "|" + string2;
                        }
                    }
                    String[]strings = string2.split("\\|");
                    rightFormulaCollection.addAll(Arrays.asList(strings));
                    rightFormulaCollection.remove(i);
                    newFormula.put(nonTerminal, rightFormula.replace(string, string2));
                }
            }
            return rightFormulaCollection;
        }
    
        //测试
        public static void main(String[] args) {
            EliminateLeftRecursion eliminateLeftRecursion = new EliminateLeftRecursion("./src/input.txt");
            eliminateLeftRecursion.eliminateLeftRecursion();
        }
    }
    
    

    消除左递归主要有两点

    1. 直接左递归
      直接左递归直接按照书本上的方法进行消除即可,如下:
    E——>E+T|T
    T——>T*F|F
    F——>(E)|i
    执行消除左递归后的结果:
    E——>TE'
    E'——>+TE'|ε
    T——>FT'
    T'——>*FT'|ε
    F——>(E)|i
    
    1. 间接左递归
      间接左递归这个就比较麻烦了,这个还得分情况,同样也是两种情况
    • 首字符是非终结符,且该非终结符对应的式子元素中不含 ε
      则将该非终结符式子中的元素添加到上一个式子的前面(想说清楚挺麻烦的,看例子吧),如下:
    S——>i|h|c|t|Qc
    Q——>Rb|b
    R——>Ba|a
    B——>Cf|H
    C——>Dd|d
    D——>Se|e
    H——>zy|x
    执行消除左递归后的结果:
    S——>bcS'|edfabcS'|dfabcS'|abcS'|xabcS'|zyabcS'
    S'——>edfabcS'|ε
    H——>zy|x
    
    • 首字符是非终结符,且该非终结符下对应的式子元素中含有 ε
      这个就异常的麻烦了,因为如果存在 ε ,就意味着不能只看首字符,还得看下一个字符是不是有左递归,如下:
    S——>AB|bC
    A——>b|ε
    B——>aD|ε
    C——>AD|b
    D——>aS|c
    执行消除左递归后的结果:
    A——>b|ε
    B——>aD|ε
    S——>bB|aD|ε|bC
    C——>bD|aS|c|b
    D——>aS|c
    

    PS:上面这个例子中是不存在左递归的,但是为了让大家方便理解才拿出来举例

    3、生成 First 集

    FirstCollection.java

    import java.util.*;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/2 22:37
     * 构建FIRST集
     */
    public class FirstCollection {
    
        private EliminateLeftRecursion eliminateLeftRecursion;
        private Map<String, Set<String>> firstCollectionMap = new HashMap<>();
    
        public Map<String, Set<String>> getFirstCollectionMap() {
            return firstCollectionMap;
        }
    
        public EliminateLeftRecursion getEliminateLeftRecursion() {
            return eliminateLeftRecursion;
        }
    
        public FirstCollection(String fileSrc) {
            //消除左递归
            this.eliminateLeftRecursion = new EliminateLeftRecursion(fileSrc);
            eliminateLeftRecursion.eliminateLeftRecursion();
            //生成First集
            createFirstCollection();
        }
    
        public void createFirstCollection(){
            Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
            for (Map.Entry<String,String> entry: formula.entrySet()){
                String leftNonTerminal = entry.getKey();
                Set<String> set = new HashSet<>();
                searchFirstCharacter(leftNonTerminal, set);
                firstCollectionMap.put(leftNonTerminal, set);
            }
    
            System.out.println();
            for (Map.Entry<String, Set<String>> entry: firstCollectionMap.entrySet()){
                System.out.println(entry.getKey() + "的FIRST集:" + entry.getValue().toString());
            }
        }
    
    
        /**
         * 递归向下查找式子第一个开头的字符
         * @param nonTerminal 终结符
         */
        public void searchFirstCharacter(String nonTerminal, Set<String> set){
            Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
            String[]strings = formula.get(nonTerminal).split("\\|");
            for (String string: strings){
                String firstCharacter = ""+string.charAt(0);
                //首字符是否是非终结符,若是则继续递归查找,若不是则直接添加进FIRST集合
                if (formula.containsKey(firstCharacter)){
                    searchFirstCharacter(firstCharacter, set);
                }else{
                    set.add(firstCharacter);
                }
            }
        }
    
        //测试
        public static void main(String[] args) {
            FirstCollection firstCollection = new FirstCollection("./src/input.txt");
            //进行消除左递归
            firstCollection.eliminateLeftRecursion.eliminateLeftRecursion();
            firstCollection.createFirstCollection();
    
    
            System.out.println();
            for (Map.Entry<String, Set<String>> entry: firstCollection.firstCollectionMap.entrySet()){
                System.out.println(entry.getKey() + "的FIRST集:" + entry.getValue().toString());
            }
        }
    }
    
    

    生成式子的 First 集这里就比较轻松了,只要对首字符进行分析就行了

    1. 首字符是终结符
      直接将该终结符添加进 First 集里面

    2. 首字符是非终结符
      其实这种情况是不会在我上面的代码中出现的,因为这里使用的式子是消除完左递归后的式子,理论上不会再出现首字符是非终结符的情况了…如果出现了这种情况,请参照前面消除左递归时的步骤来设计。

    4、生成 Follow 集

    • FollowCollection.java
    import java.util.*;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/2 22:37
     * 构建FOLLOW集
     */
    public class FollowCollection {
    
        private EliminateLeftRecursion eliminateLeftRecursion;
        private FirstCollection firstCollection;
        private Map<String, Set<String>> followCollectionMap = new HashMap<>();
    
        public EliminateLeftRecursion getEliminateLeftRecursion() {
            return eliminateLeftRecursion;
        }
    
        public FirstCollection getFirstCollection() {
            return firstCollection;
        }
    
        public Map<String, Set<String>> getFollowCollectionMap() {
            return followCollectionMap;
        }
    
        public FollowCollection(String fileSrc) {
            this.firstCollection = new FirstCollection(fileSrc);
            this.eliminateLeftRecursion = firstCollection.getEliminateLeftRecursion();
            createFollowCollection();
            System.out.println();
            for (Map.Entry<String, Set<String>> entry1 : followCollectionMap.entrySet()) {
                System.out.println(entry1.getKey() + "的FOLLOW集:" + entry1.getValue());
            }
        }
    
    
        public void createFollowCollection(){
            Map<String,String> formula = eliminateLeftRecursion.getNewFormula();
            for (Map.Entry<String,String> entry: formula.entrySet()){
                searchTargetNonTerminalCharacter(entry.getKey());
            }
            Map<String, Set<String>> map = followCollectionMap;
    
            for (Map.Entry<String, Set<String>> setMap: firstCollection.getFirstCollectionMap().entrySet()) {
                if (followCollectionMap.containsKey(setMap.getKey())){
                    for (Map.Entry<String, Set<String>> entry2 : followCollectionMap.entrySet()) {
                        Set<String> set = entry2.getValue();
                        ListIterator<String> listIterator = new ArrayList<>(set).listIterator();
                        while(listIterator.hasNext()){
                            String string = listIterator.next();
                            if (map.containsKey(string)){
                                //删除原来在Follow集中的代表Follow集的非终结符符号
                                listIterator.remove();
                                Set<String> targetList = map.get(string);
                                for (String str: targetList){
                                    //往Follow集里面添加新的元素
                                    listIterator.add(str);
                                }
                            }
                        }
                        Set<String> stringSet = new HashSet<>();
                        while(listIterator.hasPrevious()){
                            String string = listIterator.previous();
                            if (!(string.length()==1 && string.charAt(0)>=65 && string.charAt(0)<=90)){
                                stringSet.add(string);
                            }
                        }
                        stringSet.add("#");
                        entry2.setValue(stringSet);
                    }
                }else{
                    Set<String> set = new HashSet<>();
                    set.add("#");
                    map.put(setMap.getKey(), set);
                }
            }
        }
    
        /**
         * 查找目标非终结符的末尾字符
         * 查找结果可能是终结符也可能是非终结符
         * @param leftNonTerminal
         */
        public void searchTargetNonTerminalCharacter(String leftNonTerminal){
            Map<String,String> formula;
            //如果发生了左递归
            if (eliminateLeftRecursion.isHappenLeftRecursion()){
                formula = eliminateLeftRecursion.getNewFormula();
            }else{
                formula = eliminateLeftRecursion.getOldFormula();
            }
            String[]strings = formula.get(leftNonTerminal).split("\\|");
            for (String string: strings){   //待查找的式子
                for (Map.Entry<String,String> entry: formula.entrySet()){
                    //非终结符出现的位置
                    int index = string.indexOf(entry.getKey());
                    //搜索右边式子中是否有非终结符
                    if (index!=-1){
                        for (int i = index;i < string.length();i++){
                            String flag = ""+string.charAt(i);
                            if (i+1 < string.length() && string.charAt(i+1)=='\''){
                                flag = flag + "'";
                            }
                            if (flag.equals(entry.getKey())){
                                //没有单引号的兄弟,避免混淆
                                if (entry.getKey().length()==1 && i+1 < string.length() && string.charAt(i+1)=='\''){
                                    continue;
                                }
                                Set<String> set = new HashSet<>();
                                //如果非终结符出现在最末尾
                                if (i == (string.length()-entry.getKey().length())){
                                    //如果该终结符的follow集还未出现,则存放对应的follow集标识,后面再补上
                                    if(!followCollectionMap.containsKey(entry.getKey())){
                                        if (!leftNonTerminal.equals(entry.getKey())){
                                            set.add(leftNonTerminal);
                                            followCollectionMap.put(entry.getKey(), set);
                                        }
                                    }else{//如果已经出现,则直接赋值给它(PS:不能直接赋值给它,因为有可能前面已出现的也只是个标识...)
                                        set = followCollectionMap.get(entry.getKey());
                                        if (!leftNonTerminal.equals(entry.getKey())){
                                            set.add(leftNonTerminal);
                                            followCollectionMap.put(entry.getKey(), set);
                                        }
                                    }
                                }else{
                                    if (followCollectionMap.containsKey(flag)){
                                        set = followCollectionMap.get(flag);
                                    }
                                    String nextCharacter = ""+string.charAt(i+1);
                                    //得区分有单引号和没单引号的,真无语...
                                    if (i+2 < string.length() && string.charAt(i+2)=='\''){
                                        nextCharacter = nextCharacter + string.charAt(i+2);
                                    }
                                    //如果后面的符号不是非终结符,则直接加入到follow集中
                                    if (firstCollection.getFirstCollectionMap().containsKey(nextCharacter)){
                                        set.addAll(eliminateFirstCollectionEmptySet(nextCharacter));
                                        //查看后面的非终结符中是否存在ε空集,如果存在则要再添加follow集
                                        if (isContainEmptySet(nextCharacter)){
                                            set.add(leftNonTerminal);
                                        }
                                    }else{
                                        set.add(nextCharacter);
                                    }
                                    followCollectionMap.put(entry.getKey(), set);
                                }
                            }
                        }
                    }
                }
            }
        }
    
        /**
         * 消除First集中的ε
         * @param nonTerminal 目标非终结符对应的式子
         * @return 返回消除ε后的集合
         */
        public Set<String> eliminateFirstCollectionEmptySet(String nonTerminal){
            Set<String> set = firstCollection.getFirstCollectionMap().get(nonTerminal);
            Set<String> result = new HashSet<>();
            //去除First集中的ε
            for (String character : set) {
                if (!character.equals("ε")) {
                    result.add(character);
                }
            }
            return result;
        }
    
        /**
         * 查看相应First集中是否存在ε
         * @param nonTerminal 目标非终结符对应的式子
         * @return 存在则是true,否则是false
         */
        public boolean isContainEmptySet(String nonTerminal){
            Set<String> set = firstCollection.getFirstCollectionMap().get(nonTerminal);
            for (String string: set){
                if (string.equals("ε")){
                    return true;
                }
            }
            return false;
        }
    
        //测试
        public static void main(String[] args) {
            FollowCollection followCollection = new FollowCollection("./src/input.txt");
        }
    }
    
    

    首先,在右侧式子中寻找在非终结符集中存在的非终结符,找到非终结符后,判断非终结符后面是否有元素

    1. 如果非终结符后面没有元素或者后面元素是非终结符且该非终结符有ε,直接将该式子的Follow集直接添加进所找非终结符的Follow集中
    2. 如果非终结符后面有元素,判断该元素是否是非终结符,如果是终结符的话,则直接往Follow集里面添加,如果是非终结符的话就往下递归查找该非终结符的里面的元素

    5、判断是否是 LL1 文法

    • JudgeIsLL1.java
    import java.util.HashSet;
    import java.util.Map;
    import java.util.Set;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/10 11:12
     * 判断是不是LL1文法
     */
    public class JudgeIsLL1 {
    
        private FollowCollection followCollection;
        private FirstCollection firstCollection;
        //是否是LL1文法
        private boolean isLL1;
    
        public boolean isLL1() {
            return isLL1;
        }
    
        public FollowCollection getFollowCollection() {
            return followCollection;
        }
    
        public FirstCollection getFirstCollection() {
            return firstCollection;
        }
    
        public JudgeIsLL1(String fileSrc) {
            this.followCollection = new FollowCollection(fileSrc);
            this.firstCollection = followCollection.getFirstCollection();
            this.isLL1 = judgeIsLL1();
            System.out.println();
            if (isLL1){
                System.out.println("该文法是LL1文法");
            }else{
                System.out.println("该文法不是LL1文法");
            }
        }
    
        /**
         * 判断是否是LL1文法
         * @return
         */
        public boolean judgeIsLL1(){
            EliminateLeftRecursion eliminateLeftRecursion = followCollection.getEliminateLeftRecursion();
            boolean isHappenLeftRecursion = eliminateLeftRecursion.isHappenLeftRecursion();
            Map<String,String> formula;
            //如果发生了消除左递归
            if (isHappenLeftRecursion){
                formula = eliminateLeftRecursion.getNewFormula();
                boolean flag = formulaLoop(formula);
                return flag;
            }else{
                formula = eliminateLeftRecursion.getOldFormula();
                boolean flag = formulaLoop(formula);
                return flag;
            }
        }
    
        /**
         * 式子进行循环
         * @param formula
         * @return
         */
        public boolean formulaLoop(Map<String,String> formula){
            for (Map.Entry<String, String> entry: formula.entrySet()){
                String rightFormula = entry.getValue();
                String[]strings = rightFormula.split("\\|");
                for (int i = 0;i < strings.length;i++){
                    for (int j = i;j < strings.length;j++){
                        if (i != j){
                            boolean flag = judgeIsIntersect(entry.getKey(), strings[i], strings[j]);
                            if (!flag){
                                return false;
                            }
                        }
                    }
                }
            }
            return true;
        }
    
        /**
         * 判断式子是否是交集
         * @param leftNonTerminal
         * @param string1
         * @param string2
         * @return
         */
        public boolean judgeIsIntersect(String leftNonTerminal, String string1, String string2){
            Set<String> set1 = new HashSet<>();
            Set<String> set2 = new HashSet<>();
            searchFirstCharacter(string1, set1);
            searchFirstCharacter(string2, set2);
            Map<String, Set<String>> followCollectionMap = followCollection.getFollowCollectionMap();
            Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
            //如果存在ε的话
            if (set1.contains("ε") || set2.contains("ε")){
                boolean flag = compareFirstAndFollow(firstCollectionMap.get(leftNonTerminal), followCollectionMap.get(leftNonTerminal));
                if (!flag){
                    return false;
                }
            }
            //不论存在不存在ε都要判断这个,两个条件不是互斥的,都得进行判断
            for (String stingX: set1){
                for (String stringY: set2){
                    if (stingX.equals(stringY)){
                        return false;
                    }
                }
            }
            return true;
        }
    
        /**
         * 比较First集和Follow集是否有交集
         * @param first
         * @param follow
         * @return
         */
        public boolean compareFirstAndFollow(Set<String> first, Set<String> follow){
            if (follow==null || follow.size()==0){
                return true;
            }
            for (String sting1: first){
                for (String string2: follow){
                    if (sting1.equals(string2)){
                        return false;
                    }
                }
            }
            return true;
        }
    
    
        /**
         * 查找右边式子中的First集
         * @param nonTerminal
         * @param set
         */
        public void searchFirstCharacter(String nonTerminal, Set<String> set){
            String string = "" + nonTerminal.charAt(0);
            Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
            if (firstCollectionMap.containsKey(string)){
                set.addAll(firstCollectionMap.get(string));
            }else{
                set.add(string);
            }
        }
    
        public static void main(String[] args) {
            JudgeIsLL1 judgeIsLL1 = new JudgeIsLL1("./src/input.txt");
        }
    
    }
    
    

    判断过程:遍历右侧的每个式子,判断它们每个式子的First集是否有交集,并判断式子是否存在ε,如果存在ε,则判断Follow集和First集是否有交集。

    6、构建预测分析表

    • AnalyzeTable.java
    import java.util.*;
    
    /**
     * @Author 小关同学
     * @Create 2022/5/2 22:37
     * 预测分析表
     */
    public class AnalyzeTable {
        private JudgeIsLL1 judgeIsLL1;
        private FollowCollection followCollection;
        private FirstCollection firstCollection;
        private EliminateLeftRecursion eliminateLeftRecursion;
        private String[][] table;
        private Map<String,List<String>> formulaSplitted;
    
        //非终结符
        private Set<String> nonTerminalSet;
        //终结符
        private Set<String> terminalSet;
    
        public AnalyzeTable(String fileSrc) {
            this.judgeIsLL1 = new JudgeIsLL1(fileSrc);
            this.followCollection = judgeIsLL1.getFollowCollection();
            this.firstCollection = followCollection.getFirstCollection();
            this.eliminateLeftRecursion = firstCollection.getEliminateLeftRecursion();
        }
    
        public void init(){
            //判断是否是LL1文法
            if (judgeIsLL1.judgeIsLL1()){
                nonTerminalSet = new HashSet<>();
                terminalSet = new HashSet<>();
                Map<String, Set<String>> map = firstCollection.getFirstCollectionMap();
                for (Map.Entry<String, Set<String>> entry: map.entrySet()){
                    nonTerminalSet.add(entry.getKey());
                }
                Map<String, String> formula;
                //是否进行了消除左递归
                if (eliminateLeftRecursion.isHappenLeftRecursion()){
                    formula = eliminateLeftRecursion.getNewFormula();
                }else{
                    formula = eliminateLeftRecursion.getOldFormula();
                }
                for (Map.Entry<String,String> entry: formula.entrySet()){
                    String string = entry.getValue();
                    for (int i = 0;i < string.length();i++){
                        String character = "" + string.charAt(i);
                        if (!nonTerminalSet.contains(character) && !character.equals("|") && !character.equals("'")){
                            if (!character.equals("ε")){
                                terminalSet.add(character);
                            }
                        }
                    }
                }
                terminalSet.add("#");
                System.out.println("非终结符:" + nonTerminalSet);
                System.out.println("终结符:" + terminalSet);
            }
        }
    
        public void createTable(){
            List<String> nonTerminalList = new ArrayList<>(nonTerminalSet);
            List<String> terminalList = new ArrayList<>(terminalSet);
            table = new String[nonTerminalList.size()][terminalList.size()];
            for (int i = 0;i < nonTerminalList.size();i++){
                for (int j = 0;j < terminalList.size();j++){
                    table[i][j] = findFormula(nonTerminalList.get(i), terminalList.get(j));
                }
            }
    
            System.out.printf("%-5s","");
            for (int i = 0;i<terminalList.size();i++){
                System.out.printf("%-13s",terminalList.get(i));
            }
            System.out.println();
            for (int i = 0;i < nonTerminalList.size();i++){
                System.out.printf("%-5s",nonTerminalList.get(i));
                for (int j = 0;j < terminalList.size();j++){
                    System.out.printf("%-13s",table[i][j]);
                }
                System.out.println();
            }
        }
    
        public void splitFormula(){
            Map<String, String> formula;
            formulaSplitted = new HashMap<>();
            if (eliminateLeftRecursion.isHappenLeftRecursion()){
                formula = eliminateLeftRecursion.getNewFormula();
            }else{
                formula = eliminateLeftRecursion.getOldFormula();
            }
            for (Map.Entry<String,String> entry: formula.entrySet()){
                String[]strings = entry.getValue().split("\\|");
                List<String> list = new ArrayList<>(Arrays.asList(strings));
                formulaSplitted.put(entry.getKey(), list);
            }
        }
    
        public String findFormula(String nonTerminal, String terminal){
            List<String> strings = formulaSplitted.get(nonTerminal);
            Set<String> follow = followCollection.getFollowCollectionMap().get(nonTerminal);
            Set<String> first;
            for (String string: strings){
                first = searchFirstFromFormula(string);
                if (first.contains(terminal)){
                    return nonTerminal+"——>"+string;
                }
                if (first.contains("ε") || string.equals("ε")){
                    if (follow.contains(terminal)){
                        return nonTerminal+"——>ε";
                    }
                }
            }
            return "ERROR";
        }
    
        public Set<String> searchFirstFromFormula(String formula){
            Map<String, Set<String>> firstCollectionMap = firstCollection.getFirstCollectionMap();
            Set<String> set = new HashSet<>();
            String character = ""+formula.charAt(0);
            if (firstCollectionMap.containsKey(character)){
                set = firstCollectionMap.get(character);
            }else{
                set.add(character);
            }
            return set;
        }
    
    
        public static void main(String[] args) {
            AnalyzeTable analyzeTable = new AnalyzeTable("./src/input.txt");
            analyzeTable.init();
            //如果不是LL1算法就不用构造预测分析表
            if (analyzeTable.judgeIsLL1.judgeIsLL1()){
                analyzeTable.splitFormula();
                System.out.println();
                System.out.println("预测分析表为:");
                analyzeTable.createTable();
            }
        }
    
    }
    

    初始化数据,比较右侧每个式子 First 集,如果该 First 集包含目标的终结符,则将该式子添加到该位置,如果该 First 集包含ε且待查找的终结符在 Follow 集里面,然后就添加非终结符+箭头+ ε 的式子

    为了完成以上的任务,还需要创建一个 Formula 类保存数据。以上就是设计的主要方案。

    
    /**
     * @Author 小关同学
     * @Create 2022/5/3 23:55
     */
    public class Formula {
        //右侧式子
        private String right;
        //左侧非终结符
        private String left;
        //是否已经进行过间接消除左递归
        private boolean recursionFlag;
    
        public Formula() {
        }
    
        public Formula(String left, String right) {
            this.right = right;
            this.left = left;
        }
    
        public String getRight() {
            return right;
        }
    
        public void setRight(String right) {
            this.right = right;
        }
    
        public String getLeft() {
            return left;
        }
    
        public void setLeft(String left) {
            this.left = left;
        }
    
        public boolean isRecursionFlag() {
            return recursionFlag;
        }
    
        public void setRecursionFlag(boolean recursionFlag) {
            this.recursionFlag = recursionFlag;
        }
    
        @Override
        public String toString() {
            return right + "——>" + left;
        }
    }
    
    

    实验结果

    在这里插入图片描述

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

    最后

    项目地址如下:
    Github 地址:https://github.com/guanchanglong/GrammaticalAnalysis.git
    麻烦各位可否在看代码的时候顺手给一颗星 ^ _ ^,举手之劳感激不尽。

    PS:也可以到我的个人博客查看更多内容
    个人博客地址:小关同学的博客

    展开全文
  • ll1文法分析器实现c++

    2020-12-24 10:53:32
    ll1文法分析器实现c++
  • 根据某一文法编制调试 LL (1 )分析程序, 以便对任意输入的符号串进行分析。 2. 构造预测分析表,并利用分析表和一个栈来实现对上述程序设计语言的分析程序。 3.分析法的功能是利用 LL(1)控制程序根据显示栈...
  • ll1语法分析器实验报告.doc 南京信息工程大学实验(实习)报告实验(实习)名称LL(1)文法语法分析设计实验(实习)日期11月28日得分指导教师林美华系计算机专业计算机科学与技术年级2011班次计科3班姓名王欣学号...

    41528d3028836879cd698677c3999917.gifll1语法分析器实验报告.doc

    南京信息工程大学实验(实习)报告实验(实习)名称LL(1)文法语法分析设计实验(实习)日期11月28日得分指导教师林美华系计算机专业计算机科学与技术年级2011班次计科3班姓名王欣学号20112308915一.实验目的1.熟悉判断LL(1)文法的方法及对某一输入串的分析过程。2.学会构造表达式文法的预测分析表。二.实验内容编写一个语法分析程序,对于给定的输入串,能够判断识别该串是否为给定文法的句型。三.实验步骤从键盘读入输入串,并判断正误;若无误,由程序自动构造FIRST、FOLLOW集以及SELECT集合,判断是否为LL(1)文法;若符合LL(1)文法,由程序自动构造LL(1)分析表;由算法判断输入符号串是否为该文法的句型【源代码】INCLUDE“STDIOH“INCLUDE“STDLIBH“DEFINEMAXRULENUM8DEFINEMAXVNNUM5DEFINEMAXVTNUM5DEFINEMAXSTACKDEPTH20DEFINEMAXPLENGTH20DEFINEMAXSTLENGTH50STRUCTPRNODE/产生式右部结构/{INTRCURSOR/右部序号/STRUCTPRNODENEXT}STRUCTPNODE/产生式结点结构/{INTLCURSOR/左部符号序号/INTRLENGTH/右部长度//注当RLENGTH1时,RCURSOR1为空产生式/STRUCTPRNODERHEAD/右部结点头指针/}CHARVNMAXVNNUM1/非终结符集/INTVNNUMCHARVTMAXVTNUM1/终结符集/INTVTNUMSTRUCTPNODEPMAXRULENUM/产生式/INTPNUM/产生式实际个数/CHARBUFFERMAXPLENGTH1CHARCH/符号或STRINGCH/CHARSTMAXSTLENGTH/要分析的符号串/STRUCTCOLLECTNODE/集合元素结点结构/{INTNVT/在终结符集中的下标/STRUCTCOLLECTNODENEXT}STRUCTCOLLECTNODEFIRSTMAXVNNUM1/FIRST集/STRUCTCOLLECTNODEFOLLOWMAXVNNUM1/FOLLOW集/INTANALYSETABLEMAXVNNUM1MAXVTNUM11/预测分析表存放为产生式的编号,1用于存放结束符,多1用于存放1/INTANALYSESTACKMAXSTACKDEPTH1/分析栈/INTTOPANALYSE/分析栈顶//INTREVERSESTACKMAXSTACKDEPTH1/颠倒顺序栈//INTTOPREVERSE/倒叙栈顶/VOIDINIT/初始化/INTINDEXCHCHARCH/返回VN在VN表中的位置100、VT在VT表中的位置,1表示未找到/VOIDVT/输入终结符/VOIDVN/输入非终结符/VOIDSHOWCHARRAYCHARCOLLECT,INTNUM/输出VN或VT的内容/VOIDP/产生式输入/BOOLCHECKPCHARST/判断产生式正确性/VOIDFIRSTINTU/计算FIRST集,UXX/VOIDADDFIRSTINTU,INTNCH/加入FIRST集/BOOLHAVEEMPTYINTNVN/判断FIRST集中是否有空1/VOIDFOLLOWINTV/计算FOLLOW集/VOIDADDFOLLOWINTV,INTNCH,INTKIND/加入FOLLOW集,KIND0表加入FOLLOW集,KIND1加入FIRST集/VOIDSHOWCOLLECTSTRUCTCOLLECTNODECOLLECT/输出FIRST或FOLLOW集/VOIDFIRSTFOLLOW/计算FIRST和FOLLOW/VOIDCREATEAT/构造预测分析表/VOIDSHOWAT/输出分析表/VOIDIDENTIFYCHARST/主控程序,为操作方便//分析过程显示操作为本行变换所用,与教程的显示方式不同/VOIDINITSTACK/初始化栈及符号串/VOIDSHOWSTACK/显示符号栈中内容/VOIDPOP/栈顶出栈/VOIDPUSHINTR/使用产生式入栈操作/INCLUDE“LL1H“VOIDMAINVOID{CHARTODO,CHINITVNVTPGETCHARFIRSTFOLLOWPRINTF“所得FIRST集为“SHOWCOLLECTFIRSTPRINTF“所得FOLLOW集为“SHOWCOLLECTFOLLOWCREATEATSHOWATTODO Y WHILE Y TODO{PRINTF“\N是否继续进行句型分析Y/N“TODOGETCHARWHILE Y TODOTODOGETCHAR}IF Y TODO{INTIINITSTACKPRINTF“请输入符号串以结束“CHGETCHARI0WHILE CHPTNEXTNULLPIRHEADPTN4WHILE \0 BUFFERN{QTPRNODEMALLOCSIZEOFPRNODEQTRCURSORINDEXCHBUFFERNQTNEXTNULLPTNEXTQTPTQTN}PIRLENGTHN3I/调试时使用/}ELSEPRINTF“输入符号含非法在成分,请重新输入\N“}}/判断产生式正确性/BOOLCHECKPCHARST{INTNIF100INDEXCHST0RETURNFALSEIF ST1RETURNFALSEIF ST2RETURNFALSEFORN3 \0 STNN{IF1INDEXCHSTNRETURNFALSE}RETURNTRUE}/FIRSTFORI0IPTRCURSOR{/注此处因编程出错,使空产生式时RLENGTH同样是1,故此处同样可处理空产生式/ADDFIRSTU,PTRCURSORBREAK}ELSE{IFNULLFIRSTPTRCURSOR100{FIRSTPTRCURSOR}ADDFIRSTU,PTRCURSORIFHAVEEMPTYPTRCURSOR{BREAK}ELSE{PTPTNEXT}}J}IFJPIRLENGTH/当产生式右部都能推出空时/ADDFIRSTU,1}}}/加入FIRST集/VOIDADDFIRSTINTU,INTNCH/当数值小于100时NCH为VT//当处理非终结符时,ADDFIRST不添加空项1/{STRUCTCOLLECTNODEPT,QTINTCH/用于处理VN/PTNULLQTNULLIFNCHNVTNCHBREAKELSE{QTPTPTPTNEXT}}IFNULLPT{PTSTRUCTCOLLECTNODEMALLOCSIZEOFSTRUCTCOLLECTNODEPTNVTNCHPTNEXTNULLIFNULLFIRSTU100{FIRSTU100PT}ELSE{QTNEXTPT/QT指向FIRST集的最后一个元素/}PTPTNEXT}}ELSE{PTFIRSTNCH100WHILENULLPT{CHPTNVTIF1CH{ADDFIRSTU,CH}PTPTNEXT}}}/判断FIRST集中是否有空1/BOOLHAVEEMPTY

    展开全文
  • 编译原理语法分析器的Python实现-LL1文法,属于编译原理课程相关作业。输出结果保存为csv文件,直观了解分析全过程
  • Java实现LL1语法分析器

    千次阅读 多人点赞 2020-07-14 20:42:39
    一、实验目的 加深对语法分析器工作过程的理解;加强对预测分析法实现语法分析程序的掌握;能够 采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段 进行语法翻译。 二、实验内容 ...

    实验内容要求

    一、实验目的 加深对语法分析器工作过程的理解;加强对预测分析法实现语法分析程序的掌握;能够 采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段 进行语法翻译。

    二、实验内容 用预测分析法编制语法分析程序,语法分析程序的实现可以采用任何一种编程语言和工 具。

    三、实验要求: 1. 对语法规则有明确的定义; 2. 编写的分析程序能够对测试用例进行正确的语法分析; 3. 对于遇到的语法错误,能够做出简单的错误处理,给出简单的错误提示,保证顺 利完成语法分析过程; 4. 实验报告要求用文法的形式对语法定义做出详细说明,说明语法分析程序的工作 过程,说明错误处理的实现。

    四、实验步骤 1. 定义目标语言的语法规则; 2. 求解预测分析方法需要的符号集和分析表; 3. 依次读入测试用例,根据预测分析的方法进行语法分析,直到源程序结束; 4. 对遇到的语法错误做出错误处理。

    实验步骤

    设计一个主类用来进行文件的输入,和结果的输出;然后按照四步走的策略来创建相对于的类操作。
    第一步:创建LeftRecursion类来消除左递归,获取原始的产生式、终结符、非终结符;消除左递归之后的产生式、终结符和非终结符。然后简化产生式,每一个产生式只包含一个候选式。
    第二步:创建FirstAndFollow类来求FIRST集和FOLLOW集。
    第三步:创建AnalyzeTable类来获取分析表。
    第四步:创建LL1Stack类来对测试用例进行入栈操作求解结果。
    为了完成以上的任务,还需要创建一个Grammar类保存数据。以上就是设计的主要方案。

    • LL1 .java
    import java.io.File;
    import java.io.FileNotFoundException;
    import java.util.*;
    
    /*
    * 实验的主要方法:
    * 1、消除左递归
    *       1.1构造出终结符集、非终结符集
    *       1.2把消除左递归得到的产生式进行简化,即一条产生式里面只有一个候选式
    * 2、构造FIRST集和FOLLOW集
    * 3、构造预测分析表
    * 4、构造符号栈和输入串栈进行测试实例分析
    * */
    
    public class LL1 {
    
        //原始的产生式
        static ArrayList<String> expression;
        //语法器
        static Grammar grammar;
    
        public static void main(String []args) throws FileNotFoundException {
    
            grammar=new Grammar();
            expression=new ArrayList<>();
    
            //采用文件读入的方式
            File file=new File("E:\\code\\bytest\\test11\\test4.txt");
            try(Scanner input=new Scanner(file)) {
                while (input.hasNextLine()){
                    String line=input.nextLine();
                    if (line.equals("")){//采用空一行这种方式,下一行就是测试用例
                        grammar.setTestEx(input.nextLine());
                        break;
                    }else {
                        expression.add(line);
                    }
                }
            }
    
            //消除左递归
            LeftRecursion leftRecursion=new LeftRecursion();
            leftRecursion.setExpression(expression);
            leftRecursion.work();
    
            //分别给语法器开始设置非终结符集、终结符集、文法开始符号、简化之后的产生式
            grammar.setNa(leftRecursion.getNa());
            grammar.setNt(leftRecursion.getNt());
            grammar.setStart(leftRecursion.getStart());
            grammar.setSimpleExpression(leftRecursion.getSimpleExpression());
    
            System.out.println();
            System.out.println("--------------------------------------------------");
            System.out.println("消除左递归");
            System.out.println();
    
            System.out.println("产生式");
            for(Map.Entry<Character, ArrayList<String>> entry : grammar.getSimpleExpression().entrySet()){
                for (String s:entry.getValue()){
                    System.out.println(entry.getKey()+"->"+s);
                }
            }
    
            System.out.println("--------------------------------------------------");
            System.out.println("非终结符");
            for (Character na:grammar.getNa().keySet()){
                System.out.printf("%-10c",na);
            }
            System.out.println();
    
            System.out.println("--------------------------------------------------");
            System.out.println("终结符");
            for (Character nt:grammar.getNt().keySet()){
                System.out.printf("%-10c",nt);
            }
            System.out.println();
            System.out.println("--------------------------------------------------");
            System.out.println("读取测试用例");
            System.out.println(grammar.getTestEx());
    
            //开始构造FIRST集和FOLLOW集
            FirstAndFollow firstAndFollow=new FirstAndFollow(grammar);
            firstAndFollow.work();
            grammar.setFirst(firstAndFollow.getFirst());
            grammar.setFollow(firstAndFollow.getFollow());
    
            System.out.println("--------------------------------------------------");
            System.out.println("FIRST集");
            for (Character na:grammar.getNa().keySet()){
                String FirstSet=grammar.getFirst().get(na).toString().replace("[","");
                FirstSet=FirstSet.replace("]","");
                System.out.println("FIRST("+na+")={"+FirstSet+"}");
            }
            System.out.println("--------------------------------------------------");
            System.out.println("FOLLOW集");
            for (Character na:grammar.getNa().keySet()){
                String FollowSet=grammar.getFollow().get(na).toString().replace("[","");
                FollowSet=FollowSet.replace("]","");
                System.out.println("FOLLOW("+na+")={"+FollowSet+"}");
            }
    
            //构造预测分析表
            AnalyzeTable analyzeTable=new AnalyzeTable(grammar);
            analyzeTable.work();
            grammar.setAnalyzeTable(analyzeTable.getAnalyzeTable());
            System.out.println("--------------------------------------------------");
            System.out.println("预测分析表");
            System.out.printf("%-11s","");
            for (Character nt:grammar.getNt().keySet()){
                if (nt!='ε') {
                    System.out.printf("%-10s", nt);
                }
            }
            System.out.println();
            for (Character na:grammar.getNa().keySet()){
                System.out.printf("%-10s",na);
                for (int i=1;i<=grammar.getNt().size();i++){
                    if(grammar.getAnalyzeTable()[grammar.getNa().get(na)][i]!=null){
                        System.out.printf("%-10s",na+"->"+ grammar.getAnalyzeTable()[grammar.getNa().get(na)][i]);
                    }else{
                        System.out.printf("%-10s","");
                    }
                }
                System.out.println("");
            }
            System.out.println("--------------------------------------------------");
            System.out.println("预测分析步骤");
            System.out.println();
    
            //利用LL1开始测试测试用例
            LL1Stack stack=new LL1Stack(grammar);
            stack.work();
        }
    }
    
    • Grammar.java
    import java.util.*;
    
    public class Grammar {
        //非终结符
        /*
        * 这里解释一下为什么要采用Map,而不是采用Set,因为我觉得采用map方便生成预测分析表,可以利用键对应的值,找到产生式在
        * 分析表中的位置。如 E->FA.要找到它在分析表中的位置,先要确定E在哪一行,直接判断FIRST(E)对应的符号所在哪一列,才可
        * 以确定表达式的位置,这样也有利于最后的测试用例测试。
        * */
        private Map<Character,Integer> Na;
        //终结符
        private Map<Character,Integer> Nt;
        //原始的产生式
        private ArrayList<String> expression;
        //简化之后的产生式
        private Map<Character,ArrayList<String>> simpleExpression;
        //开始符
        private Character start;
        //测试实例
        private String testEx;
        //分析表
        private String[][] analyzeTable;
    
    
        //first集
        private Map<Character, HashSet<Character>> First;
        //Follow集
        private Map<Character, HashSet<Character>> Follow;
    
        public Grammar() {
            Na=new LinkedHashMap<>();
            Nt=new LinkedHashMap<>();
            simpleExpression=new LinkedHashMap<>();
            Follow=new HashMap<>();
            First=new HashMap<>();
        }
    
        public Map<Character, Integer> getNa() {
            return Na;
        }
    
        public void setNa(Map<Character, Integer> na) {
            Na = na;
        }
    
        public Map<Character, Integer> getNt() {
            return Nt;
        }
    
        public void setNt(Map<Character, Integer> nt) {
            Nt = nt;
        }
    
        public ArrayList<String> getExpression() {
            return expression;
        }
    
        public void setExpression(ArrayList<String> expression) {
            this.expression = expression;
        }
    
        public Map<Character, ArrayList<String>> getSimpleExpression() {
            return simpleExpression;
        }
    
        public void setSimpleExpression(Map<Character, ArrayList<String>> simpleExpression) {
            this.simpleExpression = simpleExpression;
        }
    
        public Character getStart() {
            return start;
        }
    
        public void setStart(Character start) {
            this.start = start;
        }
    
        public Map<Character, HashSet<Character>> getFirst() {
            return First;
        }
    
        public void setFirst(Map<Character, HashSet<Character>> first) {
            First = first;
        }
    
        public Map<Character, HashSet<Character>> getFollow() {
            return Follow;
        }
    
        public void setFollow(Map<Character, HashSet<Character>> follow) {
            Follow = follow;
        }
    
        public String getTestEx() {
            return testEx;
        }
    
        public void setTestEx(String testEx) {
            this.testEx = testEx;
        }
    
        public String[][] getAnalyzeTable() {
            return analyzeTable;
        }
    
        public void setAnalyzeTable(String[][] analyzeTable) {
            this.analyzeTable = analyzeTable;
        }
    }
    
    
    • LeftRecursion.java
    import java.util.*;
    
    public class LeftRecursion {
        //非终结符
        private Map<Character,Integer> Na;
        //终结符
        private Map<Character,Integer> Nt;
        //原始的产生式
        private ArrayList<String> expression;
        //简化之后的产生式
        private Map<Character,ArrayList<String>> simpleExpression;
        //开始符
        private Character start;
    
        private int countNa;//非终结符的数量
        private int countNt;//终结符的数量
    
        public Map<Character, Integer> getNa() {
            return Na;
        }
    
        public void setNa(Map<Character, Integer> na) {
            Na = na;
        }
    
        public Map<Character, Integer> getNt() {
            return Nt;
        }
    
        public void setNt(Map<Character, Integer> nt) {
            Nt = nt;
        }
    
        public ArrayList<String> getExpression() {
            return expression;
        }
    
        public void setExpression(ArrayList<String> expression) {
            this.expression = expression;
        }
    
        public Map<Character, ArrayList<String>> getSimpleExpression() {
            return simpleExpression;
        }
    
        public void setSimpleExpression(Map<Character, ArrayList<String>> simpleExpression) {
            this.simpleExpression = simpleExpression;
        }
    
        public Character getStart() {
            return start;
        }
    
        public void setStart(Character start) {
            this.start = start;
        }
    
        public LeftRecursion(){
            Na=new LinkedHashMap<>();
            Nt=new LinkedHashMap<>();
            simpleExpression=new LinkedHashMap<>();
        };
    
        public LeftRecursion(Map<Character, Integer> na, Map<Character, Integer> nt, ArrayList<String> expression, Character start) {
            Na = na;
            Nt = nt;
            this.expression = expression;
            this.start = start;
        }
    
        //初始化得到初始的终结符和非终结符
        public void  init(){
            boolean hasKong=false;
            countNa=1;
            countNt=1;
            start=expression.get(0).charAt(0);
            for (String str:expression){
                String []term=str.split("->");
                if (!Na.containsKey(term[0].charAt(0))) {
                    Na.put(term[0].charAt(0), countNa);
                    countNa++;
                }
            }
            //输出初始的非终结符
            System.out.println("--------------------------------------------------");
            System.out.println("非终结符");
            for (Character na:Na.keySet()){
                System.out.printf("%-10c",na);
            }
            System.out.println();
            for (String str:expression){
                String []term=str.split("->");
                String []candidate=term[1].split("\\|");
                for (String s:candidate){
                    for (int i=0;i<s.length();i++){
                        if (!Na.containsKey(s.charAt(i))&&!Nt.containsKey(s.charAt(i))){
                            if (s.charAt(i)!='ε') {
                                Nt.put(s.charAt(i), countNt);
                                countNt++;
                            }else{
                                hasKong=true;
                            }
                        }
                    }
                }
            }
    
    
            if (!Nt.containsKey('#')) {
                Nt.put('#', countNt++);
            }
    
            if (hasKong){
                Nt.put('ε', countNt++);
            }
            //输出初始的终结符
            System.out.println("--------------------------------------------------");
            System.out.println("终结符");
            for (Character nt:Nt.keySet()){
                System.out.printf("%-10c",nt);
            }
        }
    
        //输出原始的产生式
        private void printOrigin(){
            System.out.println("原始产生式");
            for (String ex:expression){
                Character na=ex.charAt(0);
                String []parts=ex.split("->");
                String []candidates=parts[1].split("\\|");
                for (String s:candidates){
                    System.out.println(na+"->"+s);
                }
            }
        }
    
    
        /*
        *完全消除左递归
        *
        * 如果文法G不含回路,也不含ε产生式,则下列算法可消除左递归(完全)
        * 1、把G的非终结符按任意顺序排列成P1,…,Pn
        * 2、for i:=1 to n do
        *            for j:=1 to i-1 do
        *               把形如 Pi  → P j γ  的规则改写成 P i  →  δ1 | ...   | δk γ,  其中 P i  → δ1 γ | ...   | δk γ ;
        *               消除关于Pi的直接左递归
        * 3、化简由2得到的文法(取消无用非终结符产生式)
        *
        * */
        private void allLeftTest(){
            for (int i=0;i<expression.size();i++){
                String []str=expression.get(i).split("->");
                String []candidate=str[1].split("\\|");
                String newExpression=str[1];
                Character c=str[0].charAt(0);
                ArrayList<String>notNeedChange=new ArrayList<>();
                notNeedChange.addAll(Arrays.asList(candidate));
                boolean hasLeft=false;
                for (int j=0;j<=i-1;j++){
                    candidate=newExpression.split("\\|");
                    newExpression="";
                    for (int k=0;k<candidate.length;k++){
                        if (candidate[k].charAt(0)==expression.get(j).charAt(0)){
                            String []toReplace=expression.get(j).split("->");
                            if (expression.get(j).contains("|")){
                                candidate[k]=toReplace[1].replaceAll("\\|",candidate[k].substring(1)+"|")+candidate[k].substring(1);
                            }else {
                                candidate[k] = toReplace[1] + candidate[k].substring(1);
                            }
                        }
                        if (candidate[k].charAt(0)==c)
                            hasLeft = true;
                        newExpression+=candidate[k];
                        if (k!=candidate.length-1)
                            newExpression+="|";
                    }
                    candidate=newExpression.split("\\|");
                }
                if (i==0) {
                    for (int j = 0; j < candidate.length; j++) {
                        if (candidate[j].charAt(0) == c) {
                            hasLeft = true;
                            break;
                        }
                    }
                }
    
                if (hasLeft){
                    disLeft(i,c,candidate);
                    if (!Nt.containsKey('ε')) {
                        Nt.put('ε', countNt);
                    }
                }else{
                    ArrayList<String> right=new ArrayList<>();
                    if (simpleExpression.get(c)!=null) {
                        right.addAll(simpleExpression.get(c));
                    }
                    right.addAll(notNeedChange);
                    simpleExpression.put(c,right);
                }
            }
        }
    
        private void disLeft(int index,Character c,String []test){
    
            //出现左递归的话需要做出改变的候选式子,即带左递归的式子
            ArrayList<String>needChange=new ArrayList<>();
            //不带左递归的候选式
            ArrayList<String>notNeedChange=new ArrayList<>();
            //先找到一个合适的非终结符,来替代
            char reCh = 'A';
            for (int i='A'-'A';i<26;i++){
                reCh= (char) ('A'+i);
                if (!Na.containsKey(reCh)&&!Nt.containsKey(reCh)){
                    break;
                }
            }
            //找到造成左递归的候选式
            for (String s:test){
                if (s.charAt(0)==c){
                    needChange.add(s);
                }else{
                    notNeedChange.add(s);
                }
            }
    
            //增加到非终结符集
            Na.put(reCh,countNa++);
    
            ArrayList<String> right=new ArrayList<>();
            //获取原来已经简化的产生式
            if (simpleExpression.get(c)!=null) {
                right.addAll(simpleExpression.get(c));
            }
            //消除左递归
            for (int i=0;i<notNeedChange.size();i++){
                right.add(notNeedChange.get(i)+reCh);
            }
            simpleExpression.put(c,right);
    
            //新的产生式
            ArrayList<String> right2=new ArrayList<>();
            for (String string:needChange){
                string=string.substring(1)+reCh;
                right2.add(string);
            }
            right2.add("ε");
            simpleExpression.put(reCh,right2);
    
        }
    
        //直接消除左递归。这个方法不能完全消除左递归
        public void testLeftRecur(){
            for (String str:expression){
                //判断有没有左递归
                boolean hasLeft=false;
                String []term=str.split("->");
                String []candidate=term[1].split("\\|");
                //出现左递归的话需要做出改变的候选式子,即带左递归的式子
                ArrayList<String>needChange=new ArrayList<>();
                //不带左递归的候选式
                ArrayList<String>notNeedChange=new ArrayList<>();
    
                //逐个查看候选式,以确定那些需要修改
                for (String s:candidate){
                    //出现左递归吗
                    if (s.charAt(0)==term[0].charAt(0)) {
                        needChange.add(s);
                        hasLeft=true;
                    }
                    else
                        notNeedChange.add(s);
                }
    
    
    
                //出现左递归了
                if (hasLeft){
                    //先找到一个合适的非终结符,来替代
                    char reCh = 'A';
                    for (int i=0;i<26;i++){
                        reCh= (char) ('A'+i);
                        if (!Na.containsKey(reCh)&&!Nt.containsKey(reCh)){
                            break;
                        }
                    }
                    //增加到非终结符集
                    Na.put(reCh,countNa++);
                    ArrayList<String> right=new ArrayList<>();
                    //获取原来已经简化的产生式
                    if (simpleExpression.get(term[0].charAt(0))!=null) {
                        right.addAll(simpleExpression.get(term[0].charAt(0)));
                    }
                    //消除左递归
                    for (String string:notNeedChange){
                        right.add(string+reCh);
                    }
                    simpleExpression.put(term[0].charAt(0),right);
                    ArrayList<String> right2=new ArrayList<>();
                    for (String string:needChange){
                        string=string.substring(1)+reCh;
                        right2.add(string);
                    }
                    right2.add("ε");
                    simpleExpression.put(reCh,right2);
                    Nt.put('ε',countNt);
                }else {
                    ArrayList<String> right=new ArrayList<>();
                    if (simpleExpression.get(term[0].charAt(0))!=null) {
                        right.addAll(simpleExpression.get(term[0].charAt(0)));
                    }
                    right.addAll(notNeedChange);
                    simpleExpression.put(term[0].charAt(0),right);
                }
            }
        }
    
        public void work(){
            printOrigin();
            init();
            allLeftTest();
    //        testLeftRecur();
        }
    
    }
    
    
    • FirstAndFollow.java
    import java.util.*;
    
    public class FirstAndFollow {
        private Map<Character, HashSet<Character>> First;
        private Map<Character, HashSet<Character>> Follow;
        private Grammar grammar;
    
        public FirstAndFollow(Grammar grammar) {
            this.grammar = grammar;
            First=new HashMap<>();
            Follow=new HashMap<>();
        }
    
        public Map<Character, HashSet<Character>> getFirst() {
            return First;
        }
    
        public void setFirst(Map<Character, HashSet<Character>> first) {
            First = first;
        }
    
        public Map<Character, HashSet<Character>> getFollow() {
            return Follow;
        }
    
        public void setFollow(Map<Character, HashSet<Character>> follow) {
            Follow = follow;
        }
    
        public Grammar getGrammar() {
            return grammar;
        }
    
        public void setGrammar(Grammar grammar) {
            this.grammar = grammar;
        }
    
        //求FIRST集
        private void getFirstSet(){
            for (Character character:grammar.getNa().keySet()){
                    First.put(character, getNaFirstSet(character));
            }
        }
    
    
        /*
        * 具体方法:
        * 1.若X ∈VT,则FIRST(X)={X}
        * 2.若X∈VN,且有产生式X→a…,则把a加入到FIRST(X)中;若X→ɛ也是一条 产生式,则把 ɛ 也加到FIRST(X)中。
        * 3.若X→Y…是一个产生式且Y∈VN,则把FIRST(Y)中的所有非ɛ元素都加到 FIRST(X)中;
        * 若X → Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符, 而且,对于任何j,1≤j ≤i-1, FIRST(Yj)都
        * 含有ɛ (即Y1..Y(i-1)=>ɛ),则把 FIRST(Yj)中的所有非ɛ元素都加到FIRST(X)中;
        * 特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有ɛ,则把 ɛ 加到FRIST(X)中。
        * */
    
        private HashSet<Character> getNaFirstSet(Character character){
            HashSet<Character> term=new HashSet<>();
            for (String ex:grammar.getSimpleExpression().get(character)){
                //第一个字符是终结符
                if (grammar.getNt().containsKey(ex.charAt(0))){
                    term.add(ex.charAt(0));
                }
                //第一个字符是非终结符
                else{
                    if (First.get(ex.charAt(0))!=null){
                        term.addAll(First.get(ex.charAt(0)));
                    }else {
                        term.addAll(getNaFirstSet(ex.charAt(0)));
                    }
                }
            }
            return term;
        }
    
        //求FOLLOW集
        private void getFollowSet(){
            for (Character character:grammar.getNa().keySet()){
                Follow.put(character, getNaFollowSet(character));
            }
        }
    
        /*
        * 1、对于文法的开始符号S,置#于FOLLOW(S) 中;
        * 2、若A→α B β是一个产生式,则把FIRST(β)\{ɛ}加至FOLLOW(B)中;
        * 3、若A→α B是一个产生式,或A→ αBβ是 一个产生式而β可以推导出ɛ (即 ɛ FIRST(β)), 则把FOLLOW(A)加至FOLLOW(B)中。
         * */
        private HashSet<Character> getNaFollowSet(Character c){
            HashSet<Character> term=new HashSet<>();
            if (c==grammar.getStart()){
                term.add('#');
            }
            for (Map.Entry<Character, ArrayList<String>> entry : grammar.getSimpleExpression().entrySet()){
                for (String s:entry.getValue()){
    //                System.out.println(entry.getKey()+"->"+s);
                    if (s.indexOf(c)!=-1){
                        if (s.indexOf(c)==s.length()-1){
                            if (entry.getKey()!=c) {
                                if (Follow.get(entry.getKey()) != null) {
                                    term.addAll(Follow.get(entry.getKey()));
                                } else {
                                    term.addAll(getNaFollowSet(entry.getKey()));
                                }
                            }
                        }else{
                            //所求非终结符后的第一个字符
                            Character last=s.charAt(s.indexOf(c)+1);
                            //如果是终结符
                            if (grammar.getNt().containsKey(last)){
                                term.add(last);
                            }
                            //如果是非终结符
                            else{
                                HashSet<Character> firstToAdd=new HashSet<>(First.get(last));
                                firstToAdd.remove('ε');
                                term.addAll(firstToAdd);
                                if (grammar.getSimpleExpression().get(entry.getKey()).contains("ε")&&entry.getKey()!=c){
                                    if (Follow.get(entry.getKey())!=null){
                                        term.addAll(Follow.get(entry.getKey()));
                                    }
                                    else {
                                        term.addAll(getNaFollowSet(entry.getKey()));
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return term;
        }
    
        public void work(){
            getFirstSet();
            getFollowSet();
        }
    }
    
    • AnalyzeTable.java
    public class AnalyzeTable {
    
        //分析表
        private String[][] analyzeTable;
        private Grammar grammar;
    
        public AnalyzeTable(Grammar grammar) {
            this.grammar=grammar;
            analyzeTable=new String[grammar.getNa().size()+1][grammar.getNt().size()+1];
        }
    
        public String[][] getAnalyzeTable() {
            return analyzeTable;
        }
    
        public void setAnalyzeTable(String[][] analyzeTable) {
            this.analyzeTable = analyzeTable;
        }
    
        public Grammar getGrammar() {
            return grammar;
        }
    
        public void setGrammar(Grammar grammar) {
            this.grammar = grammar;
        }
    
    
        /*
        *预测分析表的构造方法
        * 1、对文法G的每个产生式A→α执行第2步 和第3步;
        * 2、对每个终结符a∈FIRST(α),把A→α加至M[A,a]中,
        * 3、若ɛ∈FIRST(α),则对任何b∈FOLLOW(A) , 把A→α加至M[A,b]中,
        * 4、把所有无定义的M[A,a]标上“出错标志”。
         * */
    
        private void genTable(){
            for (Character Na:grammar.getNa().keySet()){
                int row=grammar.getNa().get(Na);
                for (Character Nt:grammar.getFirst().get(Na)){
                    //第3步的情况
                    if (Nt=='ε'){
                        for (Character follow:grammar.getFollow().get(Na)){
                            analyzeTable[row][grammar.getNt().get(follow)]="ε";
                        }
                    }else {
                        //执行第1步
                        for (String s:grammar.getSimpleExpression().get(Na)) {
                            //这里还需要进一步判断是因为一个非终结符有可能对应多个产生式,我们需要寻找出遇到这个终结符时对应的产生式
    
                            //如果这个产生式的第一个符号是终结符且等于当前遇到的终结符
                            if (grammar.getNt().containsKey(s.charAt(0))){
                                if (Nt==s.charAt(0)){
                                    analyzeTable[row][grammar.getNt().get(Nt)]=s;
                                    break;
                                }
                            }else{
                                if (grammar.getFirst().get(s.charAt(0)).contains(Nt)){
                                    analyzeTable[row][grammar.getNt().get(Nt)]=s;
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    
        public void work(){
            genTable();
        }
    
    
    
    }
    
    • LL1Stack.java
    import java.util.Stack;
    
    public class LL1Stack {
        private Grammar grammar;
        //这个是符号栈
        private Stack<Character> analyzeStack;
        //这个是输入串栈
        private Stack<Character> remain;
    
        public LL1Stack(Grammar grammar) {
            this.grammar = grammar;
            analyzeStack=new Stack<>();
            remain=new Stack<>();
            remain.push('#');
            //将输入串反向压栈
            for (int i=grammar.getTestEx().length()-1;i>=0;i--){
                remain.push(grammar.getTestEx().charAt(i));
            }
            analyzeStack.push('#');
            analyzeStack.push(grammar.getStart());
        }
    
        public Grammar getGrammar() {
            return grammar;
        }
    
        public void setGrammar(Grammar grammar) {
            this.grammar = grammar;
        }
    
        public Stack<Character> getAnalyzeStack() {
            return analyzeStack;
        }
    
        public void setAnalyzeStack(Stack<Character> analyzeStack) {
            this.analyzeStack = analyzeStack;
        }
    
        public Stack<Character> getRemain() {
            return remain;
        }
    
        public void setRemain(Stack<Character> remain) {
            this.remain = remain;
        }
    
        /*
        * LL1分析器工作步骤:
        * 1、如果X=a='#,分析成功退出
        * 2、如果X=a!='#,X推出,a指向写一个输入符号
        * 3、X为非终结符,查找分析表。M[x,a]是候选式反序压栈;M[x,a]=空串,弹栈什么都不压;M[x,a]为空白,出错
        * 4、然后x!=a,出错
        * */
        private void analyze(){
            System.out.printf("%-21s%-24s%-20s%-20s\n","步骤","符号栈","输入串","所用产生式");
            System.out.printf("%-25d%-25s%-25s%-25s\n",0,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"");
            int step=1;
            while (!remain.empty()){
                if (analyzeStack.peek()==remain.peek()&&remain.peek()=='#'){
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"分析成功,输入合法");
                    break;
                }
                else if (analyzeStack.peek()==remain.peek()&&remain.peek()!='#'){
                    analyzeStack.pop();
                    remain.pop();
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"");
                    step++;
                }
                else if (grammar.getNa().containsKey(analyzeStack.peek())){
                    if (grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())]==null){
                        System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"这里出错了,不存在M["+analyzeStack.peek()+","+remain.peek()+"]");
                        break;
                    }
                    else if (grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())].equals("ε")){
                        Character na=analyzeStack.pop();
                        System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),na+"->"+"ε");
                        step++;
                    }else {
                        String ex=grammar.getAnalyzeTable()[grammar.getNa().get(analyzeStack.peek())][grammar.getNt().get(remain.peek())];
                        Character na=analyzeStack.pop();
                        for (int i=ex.length()-1;i>=0;i--){
                            analyzeStack.push(ex.charAt(i));
                        }
                        System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),na+"->"+ex);
                        step++;
                    }
    
                }else{
                    System.out.printf("%-25d%-25s%-25s%-25s\n",step,printStack(analyzeStack.toString()),new StringBuilder(printStack(remain.toString())).reverse().toString(),"这里出错了,"+analyzeStack.peek()+"!="+remain.peek());
                    break;
                }
            }
        }
    
        //不会正则表达式的蒟蒻只能这样子写了
        private String printStack(String s){
            s=s.replace(", ","");
            s=s.replace("[","");
            s=s.replace("]","");
            return s;
        }
    
        public void work(){
            analyze();
        }
    
    }
    

    实验结果

    1、输入数据:
    E->E+T|T
    T->T*F|F
    F->(E)|i

    i*i+i
    输出结果:i*i+i是合法的
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2、输入数据
    E->E+T|T
    T->T*F|F
    F->(E)|i

    i*ii
    输出结果:i*ii是不合法的

    在这里插入图片描述

    展开全文
  • SyntacticLL1 分析器 用于编译器 TP 的 LL1 语法分析器 由 Sofia Rebeca Legal Bernal 和 Atilio David Gomez Riveros 编写的 TP 06/13/2015
  • 编译原理课程设计,开发的一款基于java的语法分析器,用到LL1文法
  • LL1语法分析器

    2008-06-12 00:24:24
    判断是否是LL1文法,提取左公共因子,消除左递归
  • C++实现LL(1)法分析器:构造First集、Follow集,分析语法是否符合LL(1),并构造预测分析表。
  • 附测试用例
  • 自定义一个文法集,输入文法产生式,计算文法的FIRST,FOLLOW和SELECT集合, 利用SELECT集合构造预测分析表,接着用预测分析程序,栈 和预测分析表对输入串进行分析,给出分析过程。
  • 本次上传的是编译原理语法分析LL1文法程序部分,耗费了我2个星期的时间,真的是煞费苦心。里面增加了很多注释,大家应该能够看懂,有需要的朋友赶紧下载吧!希望对大家有所帮助!!!
  • LL(1)语法分析器.zip

    2020-06-13 23:22:13
    编译原理作业。从左到右扫描每行该语言源程序的符号,拼成单词,换成统一的内部表示(token)送给语法分析程序。
  • 设计、编制并调试一个语法分析程序,加深对语法分析原理的理解。
  • 该系统由java实现,能够对输入串进行词法和语法分析,用LL(1)文法对输入串进行语法分析,在Ecplise运行,编译原理课程设计。
  • 编译原理实验-LL1语法分析器(自动生成First、Follow)java 博主在做实验时,参考众多他人代码,发现bug众多,在[@moni_mm]代码基础上,与伙伴把能看到的BUG都做出修正,同时增添了一个GUI展示。再次我将代码做出...
  • 本资源使用C++实现了语法分析器,内容包括C++源代码与exe文件、input.txt和程序运行说明文档。该资源的文字版信息请访问博客《编译原理实践:C++实现语法分析器(学习笔记)》...
  • 编译原理 LL1语法分析 湖南大学
  • LL1语法分析器3(WINDOW).rar LL1语法分析器3(WINDOW).rar
  • 编译原理-LL1语法分析器(消除左递归+消除回溯)

    万次阅读 多人点赞 2018-11-25 20:58:30
    编译原理-LL1语法分析器(消除左递归+消除回溯) 实验要求: 要求一 1、 给出文法如下: G[E]: E-&gt;T|E+T; T-&gt;F|T*F; F-&gt;i|(E); 2、 根据该文法构造相应的LL(1)文法及LL(1)分析表,并为该文法...
  • 编译原理课设 LL1语法分析器,注释掉的一部分代码是可以扩展的部分
  • LL1语法分析,编译原理实验,非常好的程序
  • 代码片段和文件信息属性大小日期时间名称---------------------------------------文件5412008-12-1620:48语法程序\语法程序.dsw文件337922008-12-1620:48语法程序\语法程序.ncb文件337922008-...

空空如也

空空如也

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

ll1语法分析器