精华内容
下载资源
问答
  • 编译原理中词法分析和部分语法分析知识点总结,内容详细,PPT
  • 吐血整理,老师上课的全部知识,34页全部罗列:程序设计语言,状态图,有限状态机,词法分析,正则表达式,Thompson构造法,上下文无关文法预测分析表,FIRST集:所有产生式右边的第一个终结符 FOLLOW集。。。若文法...
  • 概述 读一段程序和读一篇文章的处理是有...以上就对应了编译的前三个阶段 词法分析 语法分析 语义分析 **但是编译的目的是让计算机或者运行环境(而不是人脑)理解程序的含义,所以语义分析的阶段就特别困难,因为...

    概述

    读一段程序和读一篇文章的处理是有相似之处的
    首先需要能够认出一个个字符(字,单词或者标点)
    然后理解文章的结构(段落,句子,句子内部主谓宾等结构)
    最后再结合一些前置的知识和上下文,推导、理解每一句的含义,最后理解整个文章的含义

    以上就对应了编译的前三个阶段 词法分析 语法分析 语义分析
    但是编译的目的是让计算机或者运行环境(而不是人脑)理解程序的含义,所以语义分析的阶段就特别困难,因为人脑可以自然的学习和理解语言,但我们却不知道人脑是怎么做到的。我们只能保证语言的形式可以以语法树的结构来表示和验证,而语义的部分由形式本身来确定。这种由完全由形式确定语义的语言称作形式语言(formal language),它可以使让机器无歧义地理解程序这一目的变得容易实现。理解形式语言与自然语言的不同能够将编译的研究领域与自然语言识别的领域区分开来。

    所以我们最终会由一棵语法树来生成机器能够理解的机器代码,这个过程中会涉及到许多的优化技术,以及底层相关的知识。同时为了保证语言本身的跨平台特性,或者是出于优化的需要和编译器实现的模块化要求,通常会先由语法树生成中间代码,这个过程中进行与平台无关的优化。再由中间代码生成机器相关的代码,中间掺杂进行机器相关的优化。

    总结来说,编译器的实现大概以中间代码生成为界分为了前端和后端
    整体步骤是:词法分析->语法分析->语义分析(类型检查,中间代码生成和优化)->目标代码生成和优化

    因为有像LLVM这样的项目,我们设计一门语言可以只完成编译器的前端,生成某种形式的中间代码,然后和LLVM的后端对接,LLVM可以针对中间代码进行优化,并生成指定机器格式的优化后的机器代码。
    当然,这些优化技术本身也有相当的学习价值,基本上可以说是基础库开发的idea来源,因为他们本身就是如何改变程序的结构来达到目的(优化性能,优化表现形式等)的典范。

    词法分析与形式系统

    为什么讲词法分析会提到正则语言,自动机,形式语言和形式系统这些东西?
    这是我上编译原理课的时候最为困惑不解的地方。

    事实上形式语言的语法syntax本身就由词法Lexical和语法grammar共同决定,要解析出语法树(syntax tree),两者就不可分割
    词法分析的前置是形式语言的字母表,要得出一个token流或符号表
    语法分析的前置是推导规则构建的自动机,要得出一棵语法树
    前者的输出是后者的输入

    一些形式语言的词法本身也是由另一种形式语言定义的,比如C语言的词法中标识符和数字常量的定义可以由正则表达式定义。正则表达式是正则语言的表述工具,它内部实现了自动机。
    而用来描述grammar的语言CFG又是另一种形式语言。
    所以词法分析和语法分析的本质都是形式语言的推导,或规约。他们的实现就是构建这么一个以字母表和自动机为基础的形式系统。

    形式语言与形式系统

    由一个字母表按一定规律推导出的一个语言就是形式语言,它的文法就是形式语言的文法
    比如由ASCII字母表可以推导出C语言,C是一种形式语言

    • 注意推导是有规则的,因此虽然ASCII字母表也能推导出一部分英语,但是并不是所有的英语都有明确的规则(正如学英语时总会有违反语法的例外场景,事实上就算语法错了根据人也能够理解)而所有正确的C语言程序一定是可以按语法规则规约的

    而形式语言的推导类似于初中所做的等式推导题
    由一个已知的条件集合和一组规则,经过多步的推导,推出了希望证明的结论
    每一步推导都有想要证明的结论,使用的已知条件(比如各种代数规则,交换律结合律之类的),和使用的规则
    推导成功就能把结论放入已知条件集合中,作为下一步推导的依据

    一个已知条件(形式语言的程序),结论(程序符合语法)加上推导和转化规则(词法/语法规则)构成了形式系统,比如一个编译器的语法解析器(Syntax Parser)

    • 补充:形式语言的意义在于,将语法和语义分割开来。我们可以用多种形式的语法描述同一种语义,比如abbaa, 可以描述为abba*或者ab+a+。这是后期一些优化的理论基础。

    正则语言

    正则语言是最简单的形式语言
    它的字母表有空字符串,普通字符集,代表特殊操作的有并/或(’|’),拼接/且(’’), 重复/闭包(*).
    其他的常用扩展有(0或1次(?),1或更多次(+),指定次数{m,n},自定义字符集如[^a-z] 等)

    推导规则就是匹配运算的自动机(连接,并,闭包这些运算也是匹配)
    结论就是匹配成功,或者不成功

    上下文无关文法/语法

    一个推导中,产生式左边(也就是结论)只有一个非终结符的形式语言文法syntax称为上下文无关文法

    只有一个非终结符,就意味着推导到某一步不需要根据前后文(也就是上下文)来确定该用什么规则继续推导。无论这个符号出现在哪里,它的推导方式都是相同的。

    终结符就是不可再分的原子token,代表了不可再推导的状态
    非终结符是由非终结符和终结符递归构成的,代表了可以继续推导的状态

    注意一点 正则文法和上下文无关文法的区别是正则文法无法记忆状态,只能知道当前状态是什么。

    正则文法的推导不允许递归,也就是用结论推结论(数学归纳法),而上下文无关文法的非终结符的推导支持递归

    不支持递归推导意味着什么?
    比如要匹配一些递归嵌套的结构
    例如(((i+1) * 2) -7)/2)使用正则文法无法将其识别为一个表达式,还有将类似if …else…的嵌套识别为一个if块都不能用正则文法推导

    但是正则语言可以判断操作的数量是否能够被状态数K整数。如果总状态数为2,就是判断操作出现的奇偶性。像是成对出现的标签的匹配是可以用正则表达式去做的,这其中没有用到递归推导,只是识别一个开始和一个对应的结束 ,如果输入本身不满足成对出现,最后一定会匹配不成功。

    递归本身和记忆自身状态等价,因此也可以说正则文法没有记忆之前状态的功能。一些正则表达式中有像是可以指定出现次数,还有回溯这样的功能,这其实已经超出了正则语言的范畴。

    展开全文
  • 11、编译程序逻辑结构:词法分析-语法分析-语义分析和中间代码生成-代码优化-目标代码生成 12、遍:对源程序或源程序的中间形式从头到尾扫描一遍,并做有关的分析加工,生成新的源程序的中间形式或生成目标程序 13、...
  • 编译原理语法分析

    万次阅读 多人点赞 2019-04-29 17:01:40
    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析器所提供的单词序列进行语法检测和结构分析...

    语法分析程序



    一、作业目的和要求

    通过设计、编制、调试一个典型的语法分析程序(任选有代表性的语法分析方法,如LL(1)、递归下降分析法、LR、算符优先分析法)等,作为编制语法分析程序的依据,对词法分析器所提供的单词序列进行语法检测和结构分析,实现并进一步掌握常用的语法分析方法。


    二、作业内容

    选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象(例如表达式、if、while、for等等),给出其文法规则描述(注意,文法规则的描述要符合所选分析方法的要求,比如用LL(1)分析法,文法必须是LL(1)文法),设计并实现一个完整的语法分析程序。

    • 输入:源程序以文件的形式输入。
    • 输出:对于输入的源程序,如果输入源程序是给定文法定义的合法程序,则输出”success”,如果不是,即输入源程序有错误,则输出“Error”,并且尽可能指出出错位置和原因。

    三、作业要求

    1、说明语法分析的源语言是什么?
    能分析的语法成分有哪些(比如if、while、表达式、switch等等)。
    给出每个语法规则的文法描述。(可以自定义语法成分,设计合理的语法规则。)

    运用的Java语言写成的语法分析程序,
    语法成分包括:if选择结构,while循环结构,for循环结构。

    2、说明选择的语法分析方法是哪种?描述总体设计思路和主要的流程图。

    语法分析的方法是LL(1)文法。

    • 设计思路:

    • 1.构造单个文法符号X的first集:
      如果X为终结符,First(X)=X;
      如果X->ε是产生式,把ε加入First(X);
      如果X是非终结符,如X->YZW。从左往右扫描产生式右部,把First(Y)加入First(X); 如果First(Y)不包含ε,表示Y不可为空,便不再往后处理;如果First(Y)包含ε,表示Y可为空,则处理Z,依次类推。
      构造文法符号串的first集,如:X->YZW;求YZW的first集
      从左往右扫描该式,加入其非空first集:把First(Y)加入First(YZW)
      若包含空串,处理下一个符号:如果First(Y)包含空串,便处理Z;不包含就退出;处理到尾部,即所有符号的first集都包含空串 把空串加入First(YZW)。

    • 2.在计算First(X)集之后的基础上:
      (1)$属于FOLLOW(S),S是开始符;
      (2)查找输入的所有产生式,确定X后紧跟的终结符;
      (3)如果存在A->αBβ,(α、β是任意文法符号串,A、B为非终结符),把first(β)的非空符号加入follow(B);
      (4)如果存在A->αB或A->αBβ 但first(β)包含空,把follow(A)加入follow(B)。

    • 3.构造预测分析表:
      对于每个产生式A->α,first(α)中的终结符a,把A->α加入M[A,a]。
      如果空串在first(α)中,说明可为空,找它的follow集,对于follow(A)中的终结符b,把A->α加入M[A,b];
      如果空串在first(α)中,且 “$”也在follow(A)中,说明A后可以接终结符,故把A->α加入M[A,$]中。

    • 4.执行分析:
      输入一个串,文法G的预测分析表,输出推导过程:
      $ 和 开始符S入栈,栈顶符号X,index指向分析串的待分析符号a。
      栈非空执行以下循环:
      如果X==a,表示匹配,符号栈弹出一个,index++指向下一个符号;
      否则,如果X是终结符,出错;
      否则,如果查表为error,出错;
      否则,查表正确,弹出栈顶符号,把其右部各个符号进栈,令X为栈顶符号。

    • 流程图:
      在这里插入图片描述
      在这里插入图片描述

    3、编程实现,程序中编写的各种函数,需要给出注释,说明函数的作用。
    通过实现接口中的方法来完成语法分析的功能。

    package Try;
    
    interface MyAnalyseFun {
        void Init();//初始化
        void getVnVt();//获取非终结符和终结符的集合
        void getFirst(Character c);//first集
        void getFirst(String s);//任意字符的first集
        void getFollow(char c);//follow集
        void createTable();//构造表
        void analyzeLL();//LL(1)分析过程
        String find(char X, char a);//查找
        void insert(char X, char a,String s);//插入
        void displayLL();//输出分析过程
        void ouput();//其他输出信息
    }
    

        package Try;
        
        import java.io.*;
        import java.util.*;
        
        public class MyAnalyse implements MyAnalyseFun{
            /**
             * 几个比较重要的参数
             * @param MyfirstSet 终结符的first集合
             * @param MyfirstSetX 任意符号的first集合
             * @param start 文法的开始符
             * @param MyfollowSet follow集
             * @param VnSet 终结符的集合
             * @param VtSet 终结符的集合
             * @param inputStrings 文法拓展的输入
             * @param outputSet 输出的集合
             * @param table 分析表
             * @param MyAnaStatck 分析栈
             * @param strInput 需要使用预测分析器的输入串
             * @param MyAction 分析动作
             * @param Index 分析的索引值
             */
            //从文件中读入时后台无法识别空串ε,因此用符号&代替空串ε
    
        //first集是终结符的first集
        protected HashMap<Character, HashSet<Character>> MyfirstSet = new HashMap<>();
        //firstX集是指任意符号串的first集
        protected HashMap<String, HashSet<Character>> MyfirstSetX = new HashMap<>();
        //文法的开始符
        protected Character start = 'S';
        //follow集
        protected HashMap<Character, HashSet<Character>> MyfollowSet = new HashMap<>();
    
        //存储非终结符的结合
        protected HashSet<Character> VnSet = new HashSet<>();
        //存储终结符的结合
        protected HashSet<Character> VtSet = new HashSet<>();
        protected HashMap<Character, ArrayList<String>> outputSet = new HashMap<>();
        //输入文法
        //S->a|^|(T)
        //T->SU
        //U->,SU|&
    //    protected String [] inputStrings = {   "S->a",
    //                                        "S->^",
    //                                        "S->(T)",
    //                                        "T->SU",
    //                                        "U->,SU",
    //                                        //"U->ε",
    //                                        "U->&"   };
        //定义分析表
        protected String [][] table;
        //分析栈
        protected Stack<Character> MyAnaStatck = new Stack<>();
        //定义要分析的输入串
        protected String strInput = "(a,a)$";
        //对动作的初始化
        protected String MyAction = "";
        int Index = 0;
    
        //从文件中读入
        protected String[] inputStrings = getSource();
    
        protected MyAnalyse() {
        }
    
        public static void main(String[] args){
            MyAnalyse test = new MyAnalyse();
    
            test.getVnVt();
            test.Init();
            test.createTable();
            test.analyzeLL();
            test.ouput();
            
        }
    
        //从文件中读入文法的方法
        public  static  String[] getSource(){
            StringBuffer temp = new StringBuffer();
            FileInputStream fis= null;
            try {
                fis = new FileInputStream("E:\\readin.txt");
                byte[] buff=new byte[1024];
                int len=0;
                while((len=fis.read(buff))!=-1){
                    temp.append(new String(buff,0,len));
                }
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                try {
                    fis.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return temp.toString().split("\n");
        }
    
        //初始化
        @Override
        public void Init() {
            for (String s1 : inputStrings) {
                //"S->a",
                //"S->^",
                //"S->(T)",
                //"T->SU",
                //"U->,SU",
                //"U->&"
                String[] str = s1.split("->");//通过符号“->”分隔每行的文法
                char c = str[0].charAt(0);//取得左边的非终结符
                ArrayList<String> list = outputSet.containsKey(c) ? outputSet.get(c) : new ArrayList<>();
                list.add(str[1]);//添加文法右边的内容到集合中
                outputSet.put(c, list);
            }
            //求非终结符的first集
            for (Character c1 : VnSet)
                getFirst(c1);
    
            for (Character c2 : VnSet) {
                ArrayList<String> l = outputSet.get(c2);
                for (String s2 : l)
                    getFirst(s2);
            }
            //求出follow集
            getFollow(start);
            for (Character c3 : VnSet) {
                getFollow(c3);
            }
        }
    
        @Override
        public void getVnVt() {//取出终结符和非终结符的集合
            for (String s3 : inputStrings) {
                String[] str = s3.split("->");
                VnSet.add(str[0].charAt(0));
            }
            for (String s4 : inputStrings) {
                String[] str = s4.split("->");
                String right = str[1];
                for (int i = 0; i < right.length(); i++)
                    if (!VnSet.contains(right.charAt(i)))
                        VtSet.add(right.charAt(i));
            }
        }
    
        @Override
        public void getFirst(Character c) {
            ArrayList<String> list = outputSet.get(c);
            HashSet<Character> set = MyfirstSet.containsKey(c) ? MyfirstSet.get(c) : new HashSet<Character>();
            // c为终结符 直接添加
            if (VtSet.contains(c)) {
                set.add(c);
                MyfirstSet.put(c, set);
                return;
            }
            // c为非终结符 处理其每条产生式
            for (String s5 : list) {
                // c 推出空串 直接添加
                if (s5 == Character.toString('&')) {
                    set.add('&');
                }
                // X -> Y1Y2Y3… 情况
                else {
                    // 从左往右扫描生成式右部
                    int i = 0;
                    while (i < s5.length()) {
                        char tn = s5.charAt(i);
                        //先处理防止未初始化
                        getFirst(tn);
                        HashSet<Character> tvSet = MyfirstSet.get(tn);
                        // 将其first集加入左部
                        for (Character tmp : tvSet)
                            set.add(tmp);
                        // 若包含空串 处理下一个符号
                        if (tvSet.contains('&'))
                            i++;
                            // 否则退出 处理下一个产生式
                        else
                            break;
                    }
                }
            }
            MyfirstSet.put(c, set);
        }
    
        @Override
        public void getFirst(String s) {
            HashSet<Character> set = (MyfirstSetX.containsKey(s))? MyfirstSetX.get(s) : new HashSet<Character>();
            // 从左往右扫描该式
            int i = 0;
            while (i < s.length()) {
                char tn = s.charAt(i);
                HashSet<Character> tvSet = MyfirstSet.get(tn);
                // 将其非空 first集加入左部
                for (Character tmp : tvSet)
                    if(tmp != '&')
                        set.add(tmp);
                // 若包含空串 处理下一个符号
                if (tvSet.contains('&'))
                    i++;
                    // 否则结束
                else
                    break;
                // 到了尾部 即所有符号的first集都包含空串 把空串加入
                if (i == s.length()) {
                    set.add('&');
                }
            }
            MyfirstSetX.put(s, set);
        }
    
        @Override
        public void getFollow(char ch) {
            ArrayList<String> list = outputSet.get(ch);
            HashSet<Character> setA = MyfollowSet.containsKey(ch) ? MyfollowSet.get(ch) : new HashSet<Character>();
            //如果是开始符 添加 $
            if (ch == start) {
                setA.add('$');
            }
            //查找输入的所有产生式,确定c的后跟 终结符
            for (Character cha : VnSet) {
                ArrayList<String> l = outputSet.get(cha);
                for (String s : l)
                    for (int i = 0; i < s.length(); i++)
                        if (s.charAt(i) == ch && i + 1 < s.length() && VtSet.contains(s.charAt(i + 1)))
                            setA.add(s.charAt(i + 1));
            }
            MyfollowSet.put(ch, setA);
            //处理c的每一条产生式
            for (String s : list) {
                int i = s.length() - 1;
                while (i >= 0 ) {
                    char tn = s.charAt(i);
                    //只处理非终结符
                    if(VnSet.contains(tn)){
                        // 都按 A->αB&  形式处理
                        //若&不存在   followA 加入 followB
                        //若&存在,把&的非空first集  加入followB
                        //若&存在  且 first(&)包含空串   followA 加入 followB
    
                        //若&存在
                        if (s.length() - i - 1 > 0) {
                            String right = s.substring(i + 1);
                            //非空first集 加入 followB
                            HashSet<Character> setF = null;
                            if( right.length() == 1 && MyfirstSet.containsKey(right.charAt(0))) {
                                setF = MyfirstSet.get(right.charAt(0));
                            }
                            else{
                                if(!MyfirstSetX.containsKey(right)){
                                    HashSet<Character> set = new HashSet<Character>();
                                    MyfirstSetX.put(right, set);
                                }
                                setF = MyfirstSetX.get(right);
                            }
                            HashSet<Character> setX = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                            for (Character cha : setF) {
                                if (cha != '&') {
                                    setX.add(cha);
                                }
                            }
                            MyfollowSet.put(tn, setX);
    
                            // 若first(&)包含&   followA 加入 followB
                            if(setF.contains('&')){
                                if(tn != ch){
                                    HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                    for (Character cha : setA) {
                                        setB.add(cha);
                                    }
                                    MyfollowSet.put(tn, setB);
                                }
                            }
                        }
                        //若&不存在   followA 加入 followB
                        else{
                            // A和B相同不添加
                            if(tn != ch){
                                HashSet<Character> setB = MyfollowSet.containsKey(tn) ? MyfollowSet.get(tn) : new HashSet<Character>();
                                for (Character cha : setA)
                                    setB.add(cha);
                                MyfollowSet.put(tn, setB);
                            }
                        }
                        i--;
                    }
                    //如果是终结符往前扫描  如 A->aaaBCDaaaa  此时&为 CDaaaa
                    else i--;
                }
            }
        }
    
        @Override
        public void createTable() {//构造预测分析表的格式
            //终结符数组
            Object[] VtArray = VtSet.toArray();
            //非终结符数组
            Object[] VnArray = VnSet.toArray();
            // 预测分析表初始化
            table = new String[VnArray.length + 1][VtArray.length + 1];
            table[0][0] = "Vn/Vt";
            //初始化首行首列
            for (int i = 0; i < VtArray.length; i++)
                table[0][i + 1] = (VtArray[i].toString().charAt(0) == '&') ? "$" : VtArray[i].toString();
            for (int i = 0; i < VnArray.length; i++)
                table[i + 1][0] = VnArray[i] + "";
            //全部置error
            for (int i = 0; i < VnArray.length; i++)
                for (int j = 0; j < VtArray.length; j++)
                    table[i + 1][j + 1] = "error";
    
            //插入生成式
            for (char A : VnSet) {
                ArrayList<String> l = outputSet.get(A);
                for(String s : l){
                    HashSet<Character> set = MyfirstSetX.get(s);
                    for (char a : set)
                        insert(A, a, s);
                    if(set.contains('&'))  {//如果包含&
                        HashSet<Character> setFollow = MyfollowSet.get(A);
                        if(setFollow.contains('$'))//判断follow集中是否包含$
                            insert(A, '$', s);
                        for (char b : setFollow)
                            insert(A, b, s);
                    }
                }
            }
        }
    
        @Override
        public void analyzeLL() {
            System.out.println("-------------------1.LL分析过程-------------------");
            System.out.println("|               分析栈        输入串     动作|  ");
            MyAnaStatck.push('$');
            MyAnaStatck.push('S');
            displayLL();//调用分析过程方法
            char X = MyAnaStatck.peek();
            while (X != '$') {
                char a = strInput.charAt(Index);
                if (X == a) {
                    MyAction = "match " + MyAnaStatck.peek();
                    MyAnaStatck.pop();
                    Index++;
                } else if (VtSet.contains(X))
                    return;
                else if (find(X, a).equals("error"))
                    return;
                else if (find(X, a).equals("&")) {
                    MyAnaStatck.pop();
                    MyAction = X + "->&";
                } else {
                    String str = find(X, a);
                    if (str != "") {
                        MyAction = X + "->" + str;
                        MyAnaStatck.pop();
                        int len = str.length();
                        for (int i = len - 1; i >= 0; i--)
                            MyAnaStatck.push(str.charAt(i));
                    } else {
                        System.out.println("error at '" + strInput.charAt(Index) + " in " + Index);
                        return;
                    }
                }
                X = MyAnaStatck.peek();
                displayLL();
            }
            System.out.println("LL(1)文法分析成功!");
            System.out.println("-------------------LL分析过程-------------------");
        }
    
        @Override
        public String find(char X, char a) {
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a)
                            return table[i][j];
                    }
            }
            return "";
        }
    
        @Override
        public void insert(char X, char a, String s) {//插入
            if(a == '&')
                a = '$';
            for (int i = 0; i < VnSet.size() + 1; i++) {
                if (table[i][0].charAt(0) == X)
                    for (int j = 0; j < VtSet.size() + 1; j++) {
                        if (table[0][j].charAt(0) == a){
                            table[i][j] = s;
                            return;
                        }
                    }
            }
        }
    
        @Override
        public void displayLL() {// 对输入串(a,a)$ 输出 LL(1)分析过程
            Stack<Character> s = MyAnaStatck;
            System.out.printf("%23s", s );//输出第一列:分析栈
            System.out.printf("%13s", strInput.substring(Index));//输出第二列:输入串
            System.out.printf("%10s", MyAction);//输出第三列:动作
            System.out.println();
        }
    
        @Override
        public void ouput() {
            // 输出终结符的first集
            System.out.println("-------------------2.first集-------------------");
            for (Character c : VnSet) {
                HashSet<Character> set = MyfirstSet.get(c);
                System.out.printf("%10s",c + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------first集-------------------");
            // 输出任意符号串的first集
            System.out.println("-------------------firstX集-------------------");
            Set<String> setStr =  MyfirstSetX.keySet();
            for (String s : setStr) {
                HashSet<Character> set = MyfirstSetX.get(s);
                System.out.printf("%10s",s + "  ->   ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------firstX集-------------------");
            // 输出follow集
            System.out.println("-------------------3.follow集-------------------");
    
            for (Character c : VnSet) {
                HashSet<Character> set = MyfollowSet.get(c);
                System.out.print("Follow " + c + " : ");
                for (Character cha : set)
                    System.out.print(cha+" ");
                System.out.println();
            }
            System.out.println("-------------------follow集-------------------");
            //构造LL1文法预测分析表
            System.out.println("-------------------4.LL1预测分析表-------------------");
    
            for (int i = 0; i < VnSet.size() + 1; i++) {
                for (int j = 0; j < VtSet.size() + 1; j++) {
                    System.out.printf("%8s", table[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("-------------------LL1预测分析表-------------------");
        }
    }
    

    四、结果分析

    1、输入正确的源程序截图:
    将符号ε替换为&
    在这里插入图片描述

    输出结果截图:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    2、输入错误的源程序截图:
    输入错误文法
    在这里插入图片描述
    输出结果截图:
    在这里插入图片描述
    3、总结(自己的心得体会、你编写的语法分析程序的优缺点)
    S->a|^|(T)
    T->SU
    U->,SU|ε

    • 优点:文法分析过程比较详细,任务整个完成过程是充实的,这个实验报告相当于对编译原理理论课的一次实践尝试,能收获很多课堂上面学不到的知识,同时也能巩固老师所教授的知识。

    • 缺点:在写程序的时候,卡在了空串那个点。最开始尝试直接在程序中定义文法时,ε能在程序中分析成功。后来在用读入文件的方式定义文法时,控制台出现乱码,这个点解决起来花了一点时间,最后决定将符号ε替换为&,程序才能运行成功。

    展开全文
  • 编译原理知识点总结

    2019-11-12 19:27:01
    编译语言及其语法描述 (一)常用的高级语言: FORTRAN 数值计算 COBOL 事务处理 PASCAL 结构程序设计 ADA 大型程序,嵌入式实时系统 PROLOG 逻辑程序设计 ALGOL 算法语言 C/C++ 系统程序设计 JAVA Internet程序...

    编译语言及其语法描述

    (一)常用的高级语言:
    FORTRAN 数值计算
    COBOL 事务处理
    PASCAL 结构程序设计
    ADA 大型程序,嵌入式实时系统
    PROLOG 逻辑程序设计
    ALGOL 算法语言
    C/C++ 系统程序设计
    JAVA Internet程序设计
    (二) 与机器语言或汇编语言比较高级语言的优点:
    1、比较接近于数学语言和工程语言,比较直观,自然,和易于理解。
    2、便于验证其正确性,便于改错。
    3、编写效率高。
    4、易于移植。
    (三)程序语言由两方面定义:
    a,语法
    1、程序本质上是一定字符集上的字符串。
    2、语法:一组规则,用它可以产生一个合式(well-formed)的程序。
    3、词法规则:单词符号的形成规则。
    单词符号:是语言中具有独立意义的最基本结构。一般包括:常数,标识符,基本字,算符,界符等
    描述工具:有限自动机
    4、语法规则:语法单位的形成规则。
    语法单位通常包括:表达式,语句,分程序,过程,程序,函数等。
    描述工具:上下文无关文法
    5、E---->i
    E---->E+E
    E---->E*E
    E---->(E)
    5、语法规则和词法规则定义了程序的形成结构,定义语句单位的意义属于语义问题。

    b,语义
    语义:一组规则,用它可以定义一个程序的意义。
    描述方法:
    1>自然语言描述:隐藏错误,二义性,不完整性。
    2>形式描述:
    操作语义(PL/1)
    指称语义 (ADA)
    代数语义(PASCAL)

    展开全文
  • 编译原理-语法分析详解

    千次阅读 多人点赞 2020-12-20 20:57:58
    一文带你读懂语法分析编译原理)一、前言二、前置知识三、自顶向下的语法分析1、自顶向下的分析会遇到的问题a. 二义性问题b. 回溯问题c. 左递归引起的无穷推导问题2、解决以上问题a. 二义性问题 一、前言   最近...

    一、前言

      最近刚考完编译原理,抽出一点时间,来把学的知识总结一下,以便之后的回顾。在这篇博客里可能会稍作全面地讲解语法分析(学生角度),涉及到FIRST集和FOLLOW集的求取、自顶向下的语法分析和自底向上的语法分析。其中自顶向下的语法分析会包含预测分析法和递归下降法以及LL文法的介绍;自底向上的语法分析则会包含算符优先、LR(0)、SLR(1)、LR(1)和LALR(1)的介绍。内容比较多,只需要学习部分内容的话,按需目录跳转即可。

    二、前置知识

      既然大家已经准备学习语法分析,那这里我就默认大家已经了解过编译原理的一些基本概念(如:语言、文法、产生式等基础概念)和学习过编译器前端的词法分析。
      首先来看一下语法分析的概念:
      语法分析(syntax analysis)是编译程序的核心部分,其任务是检查词法分析器输出的单词序列是否是源语言中的句子,亦即是否符合源语言的语法规则。
      简单来说,语法分析就是读取词法分析产生的单词序列,看是否满足该语言的语法。比如c语言中,int double =,这种不符合语言语法规范的错误就是在语法分析中检查出来的。
      当然,语法分析远远不只有检查语句语法规范的功能,还涉及到符号表的管理、错误分析报告、为语义分析提供入口(语法制导翻译)等等。但在这里不是我们讨论的重点。
      要想判断一个句子是否所属某一语言,一般可以通过两种角度:句子的产生(推导)和句子的识别(归约)。
      产生句子的方式是从文法的开始符号开始,逐步推导出该单词序列,也称为自顶向下的语法分析;而识别句子的方式则是逐步将构成程序的单词序列归约为文法的开始符号,称为自底向上的语法分析

    三、自顶向下的语法分析

    1、自顶向下的分析会遇到的问题

      自顶向下分析实际上是一种试探性的过程,可能导致分析效率极低甚至失败。通常,在自顶向下的分析过程中会遇到二义性问题、左递归引起的无限推导和回溯问题。

    a. 二义性问题

      对于文法G,如果L(G)中存在一个具有两棵或两棵以上分析树(或最左推导)的句子(或句型),则称G是二义性的。
      如果对于一个文法G,属于L(G)的一个句子s有多个最左推导,那在对句子s进行自顶向下的语法分析过程中将会在某一步推导遇到多个可选的产生式,此时便无法确定选用哪个产生式进行推导。若想继续分析下去,就要尝试某个产生式,如果在之后的推导过程中出现问题,就要回溯到这个分叉点,重新选择另一个产生式进行尝试,直至停止或接受。
      如下图的产生式集合:
    在这里插入图片描述
      如果我们要对id+id*id进行自顶向下的语法分析,则会出现二义性问题。如:
    在这里插入图片描述
      句子id+id*id有两个最左推导,所以存在二义性问题。
      出现二义性通常是因为文法提供的信息不全,比如上面的id+id*id,常识来看乘的运算优先级要大于加,而在上面的文法中优先级是一样的,所以为了设置算符的优先级,我们可以提供更加详细语法信息。改造过的产生式集合如下:
    在这里插入图片描述
      在改造过的文法中,乘的优先级是大于加的,所以不会出现二义性问题。具体为什么乘的优先级大于加,可以参考后面的算符优先文法
      但同样,修改后的文法的产生式集合规模会大规模地增加。

    b. 回溯问题

      假设某个产生式的左部是E,则该产生式的右部称为E的候选式。如果对于非终结符E有多个候选式存在公共前缀,则自顶向下的语法分析程序便不能准确地选择产生式进行推导,只能进行试探,出现错误要回溯到上一个分支点,再选择其它的产生式进行尝试。
      对于以下产生式集合:
    在这里插入图片描述

      如果我们要对(id)进行自顶向下的语法分析,从文法的开始符号E开始推导。想要推导出句子的第一个符号(,我们有1和2两个产生式可以选择,假设我们选择2作为最先推导的产生式,得到以下推导:
    在这里插入图片描述
      推导的产生式序列是:2->4,得到了(c),第一个(可以匹配,但到id的时候匹配错误,所以要回溯到上一步推导,选择其它可选择的产生式进行尝试。
      我们可以发现,对一个句子的推导可能会产生大量的回溯,效率极低。

    c. 左递归引起的无穷推导问题

      如果对于一个文法G,存在以下情况,则称为文法G是递归的:
    在这里插入图片描述
      简单来说如果非终结符A能在有限步推导后得到A开头的句型,则称该文法是递归的。如果只通过了一步推导,称为直接左递归;如果通过了大于一步的推导,则称为间接左递归
      同上,对于以下产生式集合,进行对id+id*id的自顶向下语法分析:
    在这里插入图片描述
      我们可以发现,产生式1是左递归的,因此在分析的过程中可能会出现一直使用产生式1进行推导的情况:
    在这里插入图片描述
      这样便会出现无穷推导。

    2、解决部分问题

    a. 二义性问题

      许多文法的二义性是由于概念不清、语法变量的定义不明确导致的(比如:算符的优先级不明确、对某个非终结符定义不清等等),此时可以通过引入新的语法变量改写文法来解决。
      实际上,二义性问题没有特别形式化的解法,需要一定的经验和创造力来对文法进行改造,所以这里不对其进行详细讲解。

    b. 提取左因子

      如之前所说的,若一个非终结符有多个拥有公共前缀的候选式,对该非终结符进行推导的时候就难以选择合适的产生式进行推导,因此会产生回溯问题。这里,我们便可以使用提取左因子的方式在一定程度上规避回溯问题。
      提取左因子其实和简单数学中的提取公因式差不多。对某一非终结符A的候选式,提取它们不为ε的最大公共前缀C和公共前缀后的文法符号串S,引入新的语法变量A',并引入产生式A'->S,用A'替换掉候选式中的公共前缀后的文法符号串,使其出现这样的形式:A->CA' A'->S
      上面的解释可能过于生硬,这里我们对一下产生式集合进行提取左因子的操作:
    在这里插入图片描述

      我们可以明显地发现产生式1和2的右部存在公共前缀(,对非终结符E,如果下一个要推导出的终结符是(,我们只能对产生式1或2进行试探,出现错误后再回退选择另一个产生式进行尝试。因此我们可以提取产生式1和2右部的最大公共前缀(,然后引入新的文法变量M和新的产生式来消除产生式1和2的公共前缀。
    在这里插入图片描述
      进行完以上改造后,该产生式集合不再有某一文法变量的候选式存在公共前缀问题。对非终结符E,如果下一个要推导出的终结符是(,我们只能选择产生式1进行推导,这样就消除了公共前缀引起的回溯问题。
      需要注意的是,提取左因子并不能完全消除回溯,只能消除由公共前缀引起的回溯。这个问题我们将在后面进行讨论。

    c. 消除左递归

      我们已经知道,左递归分为直接左递归间接左递归,虽具体的消除方式不同,但思想还是一致的,那就是将左递归转换成右递归
      这里我们可以讨论下为什么转换为右递归即可消除无穷推导。实际上到底是左递归还是右递归会引起无穷推导,是与单词序列的读取方向有关。对于自顶向下的语法分析,我们默认是使用的最左推导,也就是每次关注尽量左的非终结符。所以每次推导完,关注的是推导后最左边的非终结符,而由左递归的定义可知,最左边的非终结符与产生式左部是一样的,所以一旦套起娃,便会出现无穷推导。
    在这里插入图片描述
      红框圈起来的是最左推导关注的目标非终结符。因此不难理解,对于右递归,最左推导不会出现无穷推导。
    在这里插入图片描述
      红框圈起来的是最左推导关注的目标非终结符。对右递归,即使进行推导,关注的非终结符也不会是引起无穷推导的因子。
      同样的,如果我们使用的是最右推导,那右递归便是引起无穷推导的因素,需要将其转换为左递归。
      言归正传,我们回到消除左递归的问题上。根据之前说的,我们可以将左递归转换成右递归。
    在这里插入图片描述
      这里改造看起来有点抽象,但实际上是比较容易理解的。通过分析原产生式,我们不难发现,产生的句子是这样的结构:
    在这里插入图片描述
      我们通过A'构建一个左右递归转换的桥梁,便可得到等价转换。当然,如果βε,那我们就不用大费周折进行转换,直接调转即可。
    在这里插入图片描述
      通过以上的做法便可以消除直接左递归。消除间接左递归的方法也是将左递归转换为右递归,但我们需要进行一些略微复杂的操作。
      看以下的产生式集合:
    在这里插入图片描述
      我们很容易发现A->Ac是存在直接左递归的。然而,如果将A->Sd带入S->Aa,会得到S->Sda,所以同样存在间接左递归。
      为了消除间接左递归,我们首先要为每个非终结符编号,这里我们将A编为1,S编为2,然后按编号从小到大遍历产生式左部为目标非终结符的产生式,将其产生式右部的其它非终结符通过其它产生式进行替换。如果发现存在直接左递归,就使用上面的方法进行消除,不存在的话就跳过直到遍历完成。
    在这里插入图片描述
      在进行变量代换的时候不一定要带到底,当明显发现不存在左递归之后就可以适当地停止,比如上面图片中的步骤2,对A'的替换就是适可而止的。

    3、LL(1)文法

      存在回溯问题的分析我们可以称之为不确定的自顶向下分析,而存在回溯问题的分析我们称之为确定的自顶向下分析。然而,确定的自顶向下分析不能分析全部的文法,只能分析满足一定条件的文法。LL(1)文法就是能够满足确定的自顶向下分析条件的文法。
      能够彻底消除回溯,实现确定的自顶向下分析的文法有以下要求:

    1. 无二义性
    2. 无左递归
    3. 任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同

      前两点在之前已经讲解过了,而通过分析不难发现提取左因子是满足第三点的一个充分条件。如果某一非终结符的候选式存在公共前缀,那很明显是不满足第三点的。
      确定的自顶向下分析首先从文法的开始符号出发,每一步推导都根据当前句型的最左非终结符A和当前输入符号a,选择A的某个候选式α(alpha)来替换A,并使得从α(alpha)推导出的第一个终结符恰好是a。但不能存在多个候选式推导出的第一个终结符是a,这样就不能确定选择哪个产生式进行推导。
      为了表示第一个终结符这个概念,我们要引入FIRST集这个概念。

    a. FIRST集的概念以及求解

      FIRST集的概念如下:
    在这里插入图片描述
      简单来说就是某个串的FIRST集就是这个串能推导出的第一个终结符的集合(该终结符必须在最左边)。
      我们可以给出以下规则:
    在这里插入图片描述
      求非终结符的FIRST集的时候主要关注产生式左部的符号和产生式右部的最左侧符号。比如我们要求A的FIRST集,先找到所有左部为A的产生式,然后遍历这些产生式的右部:如果右部第一个符号是终结符,那么把这个终结符加入到A的FIRST集中;如果右部是ε,把ε加入到A的FIRST集中;如果右部第一个符号是非终结符B,将该非终结符B的FIRST集加入A的FIRST集中,但需要注意的是,如果B的FIRST集存在ε,向FIRST(A)中添加FIRST(B)的时候就要去掉ε,然后加上下一个符号C的FIRST集,如果FIRST(C)还有ε就继续向后推演,以此类推。
      对于最后一种比较复杂的情况,我们有以下结论:
    在这里插入图片描述
      对于这种比较复杂的情况,有没有ε取决于连续的最后一个FIRST集含ε的符号是不是产生式右部的最后一个符号。因为只有产生式右部所有符号都有可能推导出ε,产生式左部的符号才能推导出ε
      需要注意的是,我们认为一个终结符的FIRST集就是它本身

    b. FOLLOW集的概念以及求解

      在LL(1)文法中,如果存在A->ε这样的产生式,就代表在推导过程中,我们可以直接利用这种空产生式消掉A。比如当前串是Aab,我们可以利用A->εA推导为空,串将变为ab
      在这种存在空产生式的情况下,仅仅利用FIRST集就明显不够了。因为对于某个要推导出的终结符a,我们可以将现在的待推导非终结符推导为空,然后利用下个符号最左推导出a(即判断下个符号的FIRST集是否包含该终结符a)。
      因此我们便要引入FOLLOW集这个概念,来记录某个非终结符后可能出现的第一个终结符。
    在这里插入图片描述
      我们可以给出以下的规则:
    在这里插入图片描述
      求FOLLOW集的时候主要关注产生式右部的符号。比如我们要求A的FOLLOW集,找到所有产生式右部为存在A的产生式,然后找A后面的第一个符号:如果A后第一个符号是终结符,那么把这个终结符加入到A的FOLLOW集中;开始符号的FOLLOW集包含##是终止符,代表一个句子的末尾,可以看做EOF,在有的材料中是$);如果A是最后一个符号,要将该产生式左部非终结符E的FOLLOW集加入A的FOLLOW集;如果A后第一个符号是非终结符B,将该非终结符B的FIRST集(要去除ε)加入A的FOLLOW集中,但需要注意的是,如果B的FIRST集存在ε,要加上下一个符号C的FIRST集(要去除ε),如果FIRST(C)还有ε就继续向后推演,以此类推,如果直到最后一个符号的FIRST集还包含ε,要将该产生式左部非终结符E的FOLLOW集加入A的FOLLOW集
      需要注意的是,我们认为终结符是没有FOLLOW集的

    c. SELECT集的概念以及求解

      引入FIRST集和FOLLOW集之后,我们便可以判断LL(1)文法的条件3(任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同)是否满足了。
      此时我们引入SELECT集(可选集):
    在这里插入图片描述
      如果一个文法满足对相同左部的产生式的SELECT集互不相交,那这个文法便满足任意一个语法变量A的各个候选式所能推导出的第一个终结符必须各不相同(条件3)。
      SELECT集其实也是比较好理解的,也是一个非终结符能推导出的最左终结符的集合但有对空产生式的优化

    d. 判断文法是否是LL(1)文法的步骤

      1.提取左因子;
      2.消除左递归;
      3.求解各个产生式的SELECT集,如果左部相同的产生式的SELECT集没有相交,则为LL(1)文法。

    e. 判断文法是否是LL(1)文法的例子

      这里我们们给出一个例子:
    在这里插入图片描述
      首先,我们遍历产生式,发现没有某一非终结符的候选式存在公共前缀,所以不需要提取左因子
      但我们发现产生式E->E+TT->T*F存在左递归,所以我们需要引入E'T'消除左递归
    在这里插入图片描述
      为了判断相同左部的各个产生式的SELECT集是否相交,我们要先求出各个非终结符的FIRST集:
    在这里插入图片描述
      然后便可以求各个非终结符的FOLLOW集:
    在这里插入图片描述
      然后求各个产生式的SELECT集:
    在这里插入图片描述
      然后判断相同左部的产生式的SELECT集是否相交:
    在这里插入图片描述
      发现相同左部的产生式的SELECT集不相交。此时满足了d部分中的三个条件,此时我们获得了LL(1)文法。

    4、预测分析法

    a. 预测分析法的原理

      经过上面的讲解,我们已经能够判断一个文法是否是LL(1)文法,但光有文法是无法进行语法分析的,需要相应的分析方案才行。预测分析法便是常用的自顶向下的语法分析方法。
      要实现预测分析法,我们要先了解其结构。预测分析器主要由符号栈、预测分析表和输入缓冲区组成。符号栈保存了当前推导出的句型、预测分析表定义了推导的规范、输入缓冲区保存了待推导出的符号序列。
      预测分析表可以使用二维数组表示,行标代表要进行推导的非终结符,列表代表要推导出的最左终结符,单元内的数据表示选用的产生式。Table[A][b]代表:对于非终结符A要想推导出最左终结符为b的短语,要采用Table[A][b]中的产生式进行推导。
      这里给出一个简单的预测分析表:
    在这里插入图片描述
      构造预测分析表的方法也比较简单,先将所有非终结符放在行首,将所有终结符(要带上终止符#)放在列首。然后对于产生式左部为非终结符A的产生式,如果终结符x属于该产生式的SELECT集,则Table[A][x]填上该产生式右部;如果产生式是空产生式(A->ε),则对于该产生式的SELECT集中的终结符x,Table[A][x]填上该空产生式右部(->ε)。
      该预测分析器的总控也比较简单,初始状态将开始符号S压入符号栈,将待读句子放入缓冲区。然后根据符号栈栈顶非终结符A和缓冲区最左符号a查预测分析表,如果Table[A][a]为空,则说明分析错误,该句子不符合语法规范;如果Table[A][a]有多个产生式,就说明该文法不是LL(1)文法;如果只有一个产生式,就利用该产生式进行推导,然后符号栈弹出一个符号(产生式左部),将该产生式右部逆向入栈(因为是最左推导),比较符号栈顶和缓冲区最左符号是否匹配,如果匹配,符号栈和缓冲区弹出相匹配的符号;如果不匹配,继续查预测分析表进行推导,直到结束或接受。

    b. 预测分析法的例子

    在这里插入图片描述
      这里我们扩展了上面判断是否为LL(1)文法的题目,要求给出预测分析表和对于一个句子i+i*i的分析过程。
      为了判断该文法是否为LL(1)文法,我们检查各个非终结符的候选式是否存在公共前缀(是否需要提取左因子)和是否存在左递归。发现不需要提取左因子但需要改造文法消除左递归。
      然后为了判断相同左部的产生式的SELECT集是否相交。我们先后求了各个非终结符的FIRST集、各个非终结符的FOLLOW集、各个产生式右部的FIRST集和各个产生式的SELECT集。
      最后得到了以下SELECT集,并发现我们改造后的文法是LL(1)文法:
    在这里插入图片描述
      到此为止的步骤和上面判断是否是LL(1)文法的题是一样的。之后我们便可以构造预测分析表。实际上,构造预测分析表只需要各个产生式的SELECT集。
      我们先将所有非终结符放在行首,将所有终结符(要带上终止符#)放在列首:
    在这里插入图片描述
      然后对于产生式左部为非终结符A的产生式,如果终结符x属于该产生式的SELECT集,则Table[A][x]填上该产生式右部;如果产生式是空产生式(A->ε),则对于该产生式的SELECT集中的终结符x,Table[A][x]填上该空产生式右部(->ε)。
    在这里插入图片描述
      得到了预测分析表后我们便可以对句子i+i*i进行分析了。首先我们构建分析器的初始状态:
    在这里插入图片描述
      然后开始分析并记录过程:
    在这里插入图片描述
      到此,这道题就解答完成了。

    5、递归下降法

      递归下降法是为每个非终结符设置一个处理子程序。如对非终结符A有产生式:
    在这里插入图片描述
      因此我们可以发现,处理子程序是要求可以递归的。
      现在我们有正则定义式A->aBC,我们用伪代码简单编写其处理子程序:

    procedure A:
    	begin
    		match 'a';  // 匹配终结符 a 并向后移动指针
    		call procedure B;  // 调用 B 的处理子程序
    		call procedure C;  // 调用 C 的处理子程序
    	end
    

      递归下降分析法就是通过递归调用非终结符的处理子程序来进行分析。这种方法简单、直观、可读性好并便于扩充;但同时效率低(使用递归)、处理能力有限而且难以自动生成。
      这里不再过多赘述递归下降分析法,如果之后有时间,我可能会再来补充。

    四、自底向上的语法分析

    1、自底向上的语法分析的介绍

      之前,我们讲解了自顶向下的语法分析的思想和设计思路。之前说过,只有确定的自顶向下语法分析才能彻底消灭回溯问题,带来较为高效的分析过程。然而,确定的自顶向下分析并不适用于所有的文法,所以便出现了自底向上的分析方法。
      与自顶向下的分析方法不同,自底向上的语法分析方法从输入串出发,反复利用产生式进行归约,如果最后能得到文法的开始符号,则输入串是相应文法的一个句子;否则输入串存在语法错误。
      自顶向下分语法分析一般是使用最左推导,而自底向上的语法分析是使用最左归约(最左归约是规范归约;最右推导是规范推导)。在自底向上分析过程中,寻找当前句型最左的和某个产生式的右部相匹配的子串(句柄),用该产生式的左部符号代替该子串(最左归约)。
      大家可能会对某些概念有些模糊,所以在这里进行简单的讲解。
      句型是能从一个文法的开始符号推导出的一个可以包括非终结符的子串,如TYPE VARIABLE = 5;,这是一个声明语句,TYPEVARIABLE都是非终结符;而句子是能从一个文法的开始符号推导出的一个只含终结符的子串,如int a = 5;,这是一个声明语句,只包含终结符。所以不难理解,句子一定是句型,而句型不一定是句子
      短语则是可以进行归约(但这个归约可能并不直接)的一个符号串。在语法树中的体现则是,以一个节点为树根的子树的叶子节点的顺序结合。如果这棵子树只含根叶两层节点(高度为2),则又称直接短语句柄是当前句型的最左直接短语
      不难理解的是,自底向上的语法分析的核心问题便是怎样寻找句柄,所以我们可以说,不同的自底向上语法分析方法实质上便是不同的寻找句柄的方法。
      我们常使用的自底向上的语法分析方法便是移进-归约分析法,该方法的分析程序主要包含了符号栈、输入缓冲区和分析表等,我们从输入缓冲区逐渐将单词移进到符号栈,并利用分析表在符号栈栈顶找到句柄进行归约
      在这里,我们可以将移进-归约分析法再度细分为优先法状态法,而我们对自底向上的语法分析的学习也是以此为基础展开的。

    2、优先法

    a. 优先法的介绍与思想

      优先法的基本思想是根据归约的先后次序为句型中相邻的文法符号规定优先关系,我们可以通过符号间的优先关系来确定句柄。
      比如在简单数学运算的文法中,对a+b*c进行分析。在最简单的最左归约中,我们应该先对句柄a+b进行归约。但很明显,*的优先级要大于+,所以通过终结符的优先关系我们可以得知,实际上应该先对b*c进行归约。
      然而,与确定的自顶向下的语法分析相似的是,优先法也只能对满足一定条件的文法进行分析,简单优先文法算符优先文法便是其二。
      下面简单说明下简单优先文法算符优先文法的概念:
      简单优先文法:如果各文法符号之间的优先关系互不冲突(即至多存在一种优先关系),则可识别任意句型的句柄
      算符优先文法:仅对文法中可能在句型中相邻的终结符定义优先关系,并且各终结符对之间的优先关系互不冲突。
      这里,我们对优先法的讲解只关注基于算符优先文法算符优先分析法

    b. 算符优先分析法

      算符优先分析法在分析表达式的过程中尤为有效。其思想是将文法中的终结符视为算符,借助算符之间的优先关系来决定句柄。
      我们可以如下定义算符间的优先关系:
    在这里插入图片描述
      但需要注意的是,这里的比较是涉及到方向的,可以看做矢量。比如* > ++ > *是不冲突的,前者是说左边的*优先度大于右边的+,而后者是说右侧的*优先度小于左侧的+。这里给个例子,在a*b+c中要先归约a*c,而在a+b*c中要先归约a+b。所以冲突只存在于同向中,如* > +* < +
      在表达式A+B*C中我们要确定运算顺序,只需要比较运算符的优先级和运算对象没有关系,所以这里我们引入算符文法的概念:如果文法 G 中不存在具有相邻非终结符的产生式,则称为算符文法。此时,只存在运算对象和运算符相邻,而不存在运算对象和运算对象相邻,更有利于我们确定运算顺序。
      如下图不存在相邻的非终结符,所以是算符文法
    在这里插入图片描述
      但即使满足了算符文法的条件,我们还是无法对其句子(如:id+id*id)进行有效的分析。因为算符文法本身是没有体现算符间的优先级的。所以我们要定义算符之间的优先关系。
      对于优先关系的确定,我们给定以下规则:
    在这里插入图片描述
      如果一个算符文法的任意两个算符(终结符)在同一方向上只存在一种优先关系,则称该文法为算符优先文法
      我们简单判断下以下文法是不是算符优先文法。
    在这里插入图片描述
      如果我们用产生式E->E-E替换掉E->E+E中右部第一个E,我们可以得到E->E-E+E,此时- > +;如果我们用E->E+E替换掉E->E-E中右部第二个E,我们也可以得到E->E-E+E,但此时- < +。所以对算符+*在同一方向上存在不同的优先级,所以该文法不是算符优先文法。
      回到正题,为了语法分析器的高效运行,我们需要数据结构来存贮不同算符间的优先关系。这里我们通常使用优先矩阵优先函数来记录。

    c. 获取算符间的优先级关系

      在构造优先矩阵优先函数前,我们需要先获取算符间的优先级关系。先前我们已经知道了算符优先级的规则与定义,但并不知道具体地求解方式,为了更好地求解优先级关系,我们要引入FIRSTOPLASTOP的概念。
    在这里插入图片描述
      FIRSTOP又称最左终结符集,是一个非终结符可推导出的最左终结符(不是最左的符号,是最左的终结符)集合;LASTOP又称最右终结符集,是一个非终结符可推导出的最右终结符(不是最右的符号,是最右的终结符)集合。
      下面给出FIRSTOPLASTOP的具体求法:
    在这里插入图片描述
      在这里我们不用考虑ε带来的影响,因为算符优先文法是不存在空产生式的。
      然后我们便可以通过FIRSTOPLASTOP来确定算符间的优先关系:
    在这里插入图片描述

    d. 优先矩阵的构建

      先前我们已经求得了算符之间的优先级关系,现在我们可以通过优先级关系来构建优先矩阵。
      优先矩阵是一个二维矩阵,第一行和第一列是所有的终结符(包括结束符#),Table[x][y]=op的意义是存在Table[x][0] op Table[0][y]的优先关系。
      这里给出一个例子的求解过程,对于以下算符优先文法的产生式集合,求解其优先矩阵:
    在这里插入图片描述
      首先我们要求FIRSTOPLASTOP集合:
    在这里插入图片描述
      然后遍历产生式集合,寻找优先级关系:
    在这里插入图片描述
      然后我们便可以构造优先矩阵:
    在这里插入图片描述
      #的优先关系可以通过增加语法变量S’和产生式S’->#S#来完成;当然我们也可以认为#的优先级小于其它任何算符,在上图中我们便是这样做的,这种做法虽然不是十分严谨,比如#可能和某个算符不存在优先级关系,但我们认为#的优先级更小。但这样一般不会影响求解的结果。

    e. 优先函数的构建

      我们可以发现,如果使用优先矩阵存储算符间的优先关系,会占用较大的空间,为O(n^2);所以我们可以使用优先函数来减少占用的空间资源,优先函数占用的空间为O(2n)
      优先函数的构建遵循以下规则:
    在这里插入图片描述
      在求优先函数之前,我们可以先求出优先矩阵,比较直观但相对麻烦;我们也可以求出FIRSTOP和LASTOP后直接通过优先关系画出有向图,但不直观。现在,我们对以下算符优先文法求优先函数:
    在这里插入图片描述
      这里我们省略具体的求解过程,并且先求出优先矩阵,使过程更加明显。以下是其优先矩阵:
    在这里插入图片描述
      然后通过优先矩阵构建有向图:
    在这里插入图片描述
      然后找到以每个点为起点的最长路径长度,获取优先函数:
    在这里插入图片描述
      优先函数虽然能明显降低存储算符间优先关系的空间消耗,但同时也存在一些问题。比如上题中的idid不能比较,但通过观察优先函数,f(id)=4<g(id)=5,所以优先级id<id。这是因为将偏序关系转化为了全序关系,所以原来无法比较优先级的算符变得可以比较了,这使得程序的检错能力降低,但并不一定会影响分析的进行。

    f. 利用算符优先分析方法进行语法分析

      算符优先分析方法是移进-归约分析法的一种,所以我们通过不断向符号栈移进缓冲区中的符号,并通过优先关系寻找句柄,以归约。我们一般通过<关系寻找句柄头,通过>关系寻找句柄尾。
      我们要知道的是,无论是使用优先矩阵还是优先函数优先关系,其分析过程都不会有太大变化,因为我们只是从存储结构中获取优先关系,,假设我们分析串#a#的优先关系,利用优先矩阵是通过比较Table[#][a]中的符号来比较#a的优先关系,通过比较Table[a][#]中的符号来比较a#的优先关系;利用优先函数则是通过比较f(#)g(a)的大小来比较#a的优先关系,通过比较f(a)g(#)的大小关系来比较a#的优先关系,其中值越大,优先程度越高。此时我们应该可以获得# < a > #的优先关系,此时我们可以发现a是句柄,要对其进行归约。
      这里我们给出一个例子,在以下文法的基础上对id+id进行分析:
    在这里插入图片描述
      这道题在上面已经解答过,所以这里直接沿用之前的结果,以下是优先矩阵:
    在这里插入图片描述
      分析过程如下:
    在这里插入图片描述
      到此,对id+id的分析就结束了。之前我们说的是通过<找句柄头,通过>找句柄尾,但在实际分析过程中是比较直观的,被< >括起来的便是句柄。
      但我们同时也能在分析过程中发现不少问题,比如在第六步中被< >括起来的是+,我们却对F+F进行归约;同样在第六步中,虽然待归约串是F+F,但我们却使用E->E+T进行归约,产生式右部对不上。
      总结一下就是:有时未归约真正的句柄;不是规范归约;归约的符号串有时和相应产生式的右部不同。
      出现以上的问题的原因是算符优先文法未定义非终结符之间的优先关系,不能识别由单非终结符组成的句柄;而在算符优先分析法中的句柄和我们之前所说的句柄不是一个句柄。前面说的句柄是最左直接短语,而在算符优先分析中的句柄是最左素短语最左素短语是至少含有一个终结符,而且不递归含有更小的素短语的短语。这里不再详细展开素短语的求解方法,但其实和求短语是同一种方法,找子树,只不过每求得一个短语后要对该短语进行判断,是否至少含有一个终结符,是否不含有更小的素短语,如果都满足了,那这个短语是一个素短语。

    3、状态法

    a. 状态法的介绍与思想

      在之前的讲解中我们学习了移进-归约方法中的优先法,它可以有效地进行自底向上的语法分析,但同时,它存在着诸多局限,如不能处理所有的文法,算符优先分析无法处理非终结符之间的优先关系,所以如果产生式中存在相邻的非终结符(非算符文法),将难以分析,而且终结符之间也只能有一种优先关系;存在查不到的语法错误;在发现句柄(最左素短语)尾后需要向前搜索找句柄头…所以优先法很难广泛应用在语法分析中,更多的是在表达式分析中使用。
      此时,我们便可以使用状态法进行自底向上的语法分析。该方式是使用确定的有穷状态机(DFA)来进行语法分析,通过当前状态、移进单词和目标动作推进分析。
      LR(k)分析法便是状态法的一种实现。L代表从左向右读入符号、R表示最右推导的逆过程(即规范(最左)归约)、k是归约时超前读入的字符个数以便确定使用的产生式。当k=1时便可以满足绝大多数高级语言编译程序的需要。
      LR分析解决了算符优先分析存在的诸多问题。LR的归约过程是规范归约过程;适用范围广,可识别所有上下文无关文法描述的程序设计语言;分析速度快,准确定位错误。但也存在一点小问题,便是构造分析表的过程较为复杂,所以多采用自动生成的方式(YACC)。
      为了更好地表示当前状态,我们引入项目这个概念。项目在形态上就是产生式加上一个点,而这个点代表了当前识别的程度。如A->.BC,这个项目就代表了还没有读取任何符号,BC是待读符号;而A->B.C,这个项目就代表了已经读入了BC是待读符号;而A->BC.,这个项目就代表了已经读入了BC符号,没有待读符号,可以进行归约了。
      简单来说,项目中的左边便是已经读入的符号,右边是还没有读入的符号,如果在最右边就代表已经读取完,可以进行归约了。
      首先我们先介绍一下LR分析程序的组成部分。LR分析程序由符号栈、状态栈、分析表、缓冲区、总控程序等部分构成。符号栈存储当前分析过的单词、状态栈记录当前状态、分析表记录状态与待读符号决定的动作、缓冲区保存待读符号、总控程序控制整个分析过程。
      符号栈中的符号串是当前句型的活前缀之一。活前缀是不含相应句型的句柄右部的任何符号的前缀。如果已得到待规约的句柄,该活前缀也称为可归前缀。
      所有活前缀构成一个正则语言,对文法的识别就变成利用有穷状态机对规范句型的活前缀的识别的过程。
      有穷状态自动机的状态转移函数包括两个表:动作表(action表)和转移表(goto表),两个表统称为LR分析表:
      1、 ACTION表示当前状态面临输入符号时应采取的动作;action[S,a]=m的意义是对当前状态S(状态栈栈顶状态),当前输入符号为a时进行的语法动作,该动作m包括移进(移进后进行状态的转换(shift),简写是sxs代表转换,x目标状态编号)、归约(归约是reduce,简写为rxr是reduce的简写,x是利用编号为x的产生式进行归约)、接受(acc,分析结束)和出错。
      2、GOTO表示当前状态面临文法符号(非终结符)时应转向的下一个状态。goto[S, X]=x意味着当栈顶状态为S,且分析器刚归约出语法变量X时要转向的下一个状态x
      与优先法相同的是,状态法的关键也是分析表的构建,而分析表是驱动分析的基础。LR分析法在错误检测的强度从低到高是LR(0)->SLR(1)->LR(1),而LALR(1)是对LR(1)的粗化,LR(1)是LALR(1)的细化。它们的总控程序并没有大的差异,只是在分析表的求解过程中有差异。
      总控程序的分析流程如下:
    在这里插入图片描述
      为了使过程更加直观,这里我们给出一个例子来展示总控程序的分析流程。由于我们还没有学习构建分析表的方法,所以这里直接给出对应文法的分析表。
    在这里插入图片描述
      这里我们直接给出该文法的分析表,为了使其尽量直观,err不再填入分析表,用空来替代:
    在这里插入图片描述
      以下便是分析过程:
    在这里插入图片描述
      以上便是总控程序的分析流程,可能在不同材料中,分析过程的细节会有略微不同,但分析规则和分析表的使用是相同的。而在不同的LR分析法中,除了分析表的构建不同,其它步骤都是相同的,所以在介绍不同的LR分析法的时候,只会着重介绍分析表的构建方法,总控程序的流程不再赘述。

    b. LR(0)分析法

      从上面的LR分析法的定义中我们不难理解,LR(0)中的0意味着可以归约的时候不需要超前搜索符号来确定归约使用的产生式,所以可以归约的时候就一定要归约。这句话现在可能不好理解,但看完下面的就很容易理解。
      我们知道,LR分析法是使用确定的有穷状态机(DFA)来构造分析表。所以我们有必要了解一下该DFA的组成。
      之前我们引出了项目的概念,在LR(0)分析法的DFA中,我们要使用到LR(0)项目LR(0)项目的结构和之前说的项目结构是一样的,由产生式和点组成,点左边是识别过的符号,右边是待识别的符号。
      由数个项目组成的集合称为项目集,而项目集便是DFA中的状态。我们称DFA中所有状态的集合为项目集规范簇
      下面是一个DFA的示意图:
    在这里插入图片描述
      了解了LR(0)的DFA的基本概念后,我们就可以对产生式集合求DFA了。这里我们引入闭包的概念。
      现有一个状态中存在项目S->.AB且存在产生式A->ab。该项目点后的第一个符号是A,也就是等待归约出A,而又存在A->ab,也就是ab可以归约出A。我们转化下思维,可以通过等待移进ab,然后用ab归约出A的方式得到A。所以我们要加入新的项目A->.ab
      如此描述可能并不好理解,所以这里直接给出闭包的求取方式:
    在这里插入图片描述
      我们将这个求闭包的函数设为CLOSURE(C)
      DFA包括了一系列的状态和它们之间的转换关系,所以我们需要定义一个获取后继状态的函数GO(C, X),返回项目集(状态)C在识别到符号X后转入的新状态。
      这里直接给出GO(C, X)的规则:
    在这里插入图片描述
      此时我们便得到了状态转换的方法。得到一个DFA的必要条件是确定一个初始状态和已知获取新状态的方法,此时我们已经满足了后者,现在只要确定DFA的初始状态便可以得到该DFA。
      为了使文法有唯一出口,我们要引进拓广文法这一概念。对文法G=(V, T, P, S),添加新的开始符号S',并将产生式S'->S加入产生式集合得到新的产生式集合P',文法G'=(V, T, P', S')便是G的拓广文法。通过构造拓广文法,我们可以使文法有唯一的出口(接受点),也就是在分析表中只有一个单元是acc,可以使分析更加稳定直观。
      而DFA的初始状态I0便是拓广文法新加的产生式S'->S所产生的项目S'->.S的闭包。也就是CLOSURE({S'->.S})
      现在我们已经满足求DFA的条件了,接下来给出其具体过程。需要注意的是,我们可以通过项目集规范簇和GO(C, X)函数来体现DFA,项目集规范簇记录所有的状态,通过GO(C, X)来获取状态间的关系。
    在这里插入图片描述
      此时我们便获取了DFA,可以构建分析表了:
    在这里插入图片描述
      以上是LR(0)分析表生成程序的流程,当我们比着状态转换图填表的时候更为简单。我们先初始化分析表,即上面步骤的1,然后如果有从状态Ix到状态Iy的连线,线上标着M。如果M是终结符,则action[x][M]=sy;如果M是非终结符,则goto[x][M]=y;如果状态Iz中有项目S'->S.,则action[z][#]=acc
      得到分析表后,便可以通过a部分中的总控程序来对句子进行语法分析了。
      下面给出一个球LR(0)分析表的例子:
    在这里插入图片描述
      首先获得其拓广文法:
    在这里插入图片描述
      然后画出其DFA:
    在这里插入图片描述
      最后根据DFA获取LR(0)分析表:
    在这里插入图片描述
      然而LR(0)分析法不能分析所有的文法。因为LR(0)在可以归约的时候并不会前瞻任何符号来确定归约使用的产生式,所以当一个状态存在可以归约的项目(点在最右边)的时候,一定会归约。这就导致了这个状态在分析表action部分中对应的一行全是rx,意思就是无论下一个要读取的符号是什么,我都要先归约,也就是这部分最开始所说的可以归约的时候就一定要归约。这样的性质会导致移进-归约冲突归约-归约冲突,前者表示当一个状态中存在待归约项目和待移进项目的时候无法选择是进行归约还是进行移进,后者表示当一个状态中存在多个待归约项目无法确定先归约哪个。当一个文法的DFA中的每一个状态都不存在移进-归约冲突归约-归约冲突,那这个文法便是LR(0)文法。
      假设一个文法的DFA中的某个状态如下:
    在这里插入图片描述
      后两个项目存在归约-归约冲突,而第一个项目和后两个项目存在移进-归约冲突。此时LR(0)分析法就不足以支持分析该文法,我们需要使用检错能力更高的SLR(1)文法来进行分析。

    c. SLR(1)分析法

      SLR(1)分析法是对LR(0)分析法的优化,同时也是LR(1)分析法的简化,在可以进行归约的时候会前瞻一个符号来判断是否进行归约或选择哪个产生式进行归约。
      SLR(1)分析法构建DFA的方法和LR(0)分析法一模一样,只是在构建分析表的时候略有差别。SLR(1)分析法在某个状态存在项目A->ab.的时候,只有待读符号属于FOLLOW(A)的时候,才用产生式A->ab进行归约
      其实原理也比较简单,假设当前串是ab.cd,目前的状态中存在项目A->ab.,待读符号是c,如果c不在A的FOLLOW集中,那在该文法能产生的所有句型中,c就不可能出现在A的后面,就算我们使用产生式A->ab进行归约得到A.cd,最终也只会得到一个错误报告。所以我们已经可以预测到用这个产生式进行归约是一定行不通的,那我们为什么还要进行无谓的尝试呢,将这个机会让给其它的待归约项目或待移进项目不是更好吗?这便是SLR(1)的思想,缩小了可归约的范围。
      在整个流程中,只有构建分析表的过程SLR(1)与LR(0)稍有不同,而在只存在于有待归约项目的情况下:
    在这里插入图片描述
      只有划红线的地方与LR(0)有区别。所以在SLR(1)的构建分析表前,我们要求所有非终结符的FOLLOW集。
      下面给出一个例题:
    在这里插入图片描述
      首先求文法G的拓广文法,其产生式集合编码过后如下:
    在这里插入图片描述
      然后求每个非终结符的FOLLOW集:
    在这里插入图片描述
      之后画出DFA:
    在这里插入图片描述
      可以发现在状态I1I2I9中存在移进-归约冲突,所以在构建分析表的时候要格外注意:
    在这里插入图片描述
      此时SLR(1)分析表的构建就完成了。SLR(1)分析法已经可以满足分析部分高级语言的语法规则了,但仍然不能满足所有的文法。如对以下产生式集合构建DFA:
    在这里插入图片描述
      可以得到:
    在这里插入图片描述
      我们可以发现状态I2=属于R的FOLLOW集,所以存在移进-归约冲突。原因是SLR(1)分析法在归约的时候没有关注当前的语境。就像上图中的状态I2,判断是否要用R->L进行归约的时候,虽然=属于R的FOLLOW集,但在当前语境(上下文)中,=是不可能出现在R的后面的。这种矛盾在该文法中并不明显。我们通过其它的例子来进行展示。
      假设我们定义以下的语法规则:

    // 有如下的判断语句
    if (a < b) :
    	xxx;
    
    // 有如下的循环语句
    while (a < b) {
    	xxx;
    }
    

      此时我们可以如下简单定义该部分的产生式:
    在这里插入图片描述
      其中1是判断语句的产生式,2是循环语句的产生式,语法变量C代表判断表达式(如a<b)。现在我们不拘泥于这部分产生式的正确与否,单独考虑以下这段代码的语法分析:

    if (a < b):
    	S
    

      代码中判断体中的代码块我们直接用语法变量S表示。假设分析到了IC.:S这个程度,当前语境是判断语句,虽然{属于C的FOLLOW集,但很明显,在当前语境下{是不可能出现在C的后面的,只有在循环语句的语境下{才可能出现在C的后面,而在判断语句的语境下只有:可能出现在C的后面。实际上,FOLLOW集仅仅是针对文法来定义的,对于某个语境来说,某一非终结符后可能出现的终结符集合只能是该非终结符的FOLLOW集的子集。而正是因为SLR(1)分析法没有考虑当前语境,只通过FOLLOW集来判断是否归约,所以会出现这样的问题。为了使归约的范围再度缩小,我们可以使用考虑当前语境(上下文)的LR(1)分析法

    d. LR(1)分析法

      先前我们说过LR(1)分析法是考虑当前所在语境的分析法,所以为了在状态中导入当前语境,我们需要改变项目的结构,改变后的项目我们称之为LR(1)项目
      LR(1)项目LR(0)项目的基础上添加了展望符集合展望符集合包含了可能出现在项目左部非终结符后的终结符集合。正是通过展望符集合来体现当前语境。需要注意的是,展望符集合只在归约的时候发挥作用,在移进等其它情况下没有一点作用
    在这里插入图片描述
      需要注意的是,展望符集合一定是当前项目左部非终结符的FOLLOW集的子集
      在LR(1)项目的作用下,LR(1)分析法构建DFA的方式也会有变化。比如对于初始状态中求闭包前的初始项目S'->.S,我们需要更新为S'->.S , #,因为S'后只可能出现#
      求闭包的方法也略有改变:
    在这里插入图片描述
      也就是在产生新的项目的时候要计算可能出现在项目左部非终结符后的终结符集合。而上面δ属于FIRST(βχ)是因为β有可能是空。
      对应的,获取新状态的方法GO(C, X)也有所改变:
    在这里插入图片描述
      但项目集规范簇的求法几乎没有改变。
    在这里插入图片描述
      而之前说过,在构造分析表的方法上LR(0)、SLR(1)和LR(1)三种方法只在规约时略有不同,而在LR(1)分析法中,对可以归约的项目,只有对待读符号是该项目展望符集合中的终结符才使用该项目对应的产生式进行归约。
    在这里插入图片描述
      这里对c部分中使用SLR(1)分析法出现冲突的文法使用LR(1)文法构建DFA:
    在这里插入图片描述
      得到的DFA如下:
    在这里插入图片描述
      到此LR(1)分析法也就讲完了。虽然LR(1)分析法考虑当前语境,能将归约的范围缩到最小,有最强的检错能力,但相应的会付出相当的代价。对于一个文法,若SLR(1)的项目集规范簇有100个状态,对于LR(1)的项目集规范簇可能会有1000个状态,大大提高了分析表的状态,增大了YACC自动生成分析表的开销和分析的开销。为了尽可能降低分析表的规模,我们可以使用LALR(1)分析法

    e. LALR(1)分析法

      LR(1)分析法产生的DFA状态比较多,我们可以通过合并一些可以合并的状态来降低分析表的规模。在这里我们选择合并同心闭包
      同心闭包是具有相同的LR(0)项目的LR(1)项目闭包。它们在结构上只有展望符集合不同。
      我们可以合并那些不会带来冲突的同心的LR(1)闭包并重构分析表。
      对于具体的例子这里暂时鸽一下,之后有时间的话再更新,大家可以去别的资料查找一下。

    五、总结

      在本篇博客中主要讲解了编译原理中的语法分析,由于最近事情比较多,所以对于一些部分可能讲解得不是很细致(比如LALR(1)分析),但在总体的讲解结构上应该是没有问题的,对于讲解不细致的地方大家可以自行查询或告诉我再补充。最后希望大家能有所收获,谢谢观看!

    展开全文
  • 考试题型填空 24%+简答 4*4=16%+... 编译程序的工作过程 6 个阶段 P4 1词法分析程序 2 语法分析程序 3 语义分析程序 4 中间代码生成 5代码优化程序 6 目标代码生成 不做优化是 4 个阶段 5 6 不要 3. 编译程序的逻辑结构
  • 例如词法分析器对源程序进行第一遍扫描,语法分析器进行第二遍扫描,以此类推,最后生成目标程序。但是一个阶段对应一遍扫描的扫描方式是逻辑上的,编译器往往把若干个阶段结合起来进行一次扫描。原理上希望扫描的遍...
  • 语法分析是编译过程的核心部分,这一章我们主要学习了自上而下的分析方法进行语法分析,上一章已经对句法有了一定的了解,下一步就是要学好语法分析,这样才能够在后面的学习中部吃力,语法分析也是编译原理最基础的...
  • 文法属性的分类: 继承属性 例子,带有继承属性的SDD,这里addtype是副作用。 计算属性的顺序,拓扑序列: 这里的副作用设置一个虚属性 存在环的情况,这样就不能得到一个拓扑排序。......
  • 知识点: 什么是语法分析语法分析就是在词法分析识别出单词符号的基础上,分析并判断程序的语法结构是否符合语法规范。语法分析的方法有两种类型的方法,自上而下推导和自下而上规约,本章主要讲的是自上而下的推...
  • 编译原理知识点总结 目录 第一章 引论 第二章 高级语言及其语法描述 第三章 语法分析自上而下分析 第四章 属性文法和语法制导翻译 第五章 语义分析和中间代码产生 第六章 优化 第一章 引论 一编译程序 (compiler: 把...
  • 1.知识点概括 第四章主要讲了编译程序典型的语法分析方法-自上而下分析法。主要包括这几部分内容:自上而下语法分析出现的问题以及解决的方法、LL(1)分析法、递归下降分析器和预测分析表的构造。语法分析编译过程...
  • 一、学习内容本章我们主要学习以自下而上的方法进行语法分析,首先需要了解移进和规约的基本思想,即用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一...
  • 编译原理》学习总结--第四章 语法分析 自上而下分析知识点 1 移近-规约 用一个寄存符号的先进后出栈,把输入符号一个一个地移进到栈里,当栈顶形成某个产生式的候选式时,即把栈顶的这一部分替换成(归约为)...
  • 1.4 编译过程六个阶段的任务1.5 遍的概念2 词法分析2.1 词法分析器2.2 词法记号与属性2.3 串和语言以及串的运算2.4 正规式、正规定义2.5 小结2.6 有限自动机2.7 不确定的有限自动机2.8 确定的有限自动机2.9 正规式转...
  • 知识总结自下而上分析移进-归约法:句柄为可归纳串算符优先分析法:最左素短语为可归纳串从输入串开始,逐步进行“归约”,直至归约到文法的开始符号。从语法树末端开始,步步向上“归约”,直至根结。基本思想:用...
  • 编译原理期末复习知识点(1)

    千次阅读 2020-05-26 17:38:54
    基础概念 什么是编译程序 一个编译程序简单来说就是一个语言翻译程序, 源语言是高级语言, 目标语言是低级语言, 比如汇编语言和机器语言 什么是"遍" 也称作"趟", 是对源程序或其等价的中间...语法分析 根据语法规则,对
  • 编译原理知识点

    千次阅读 多人点赞 2019-05-16 09:15:52
    1. 编译程序(编译器):先将源程序翻译成汇编语言程序或机器语言程序(称为目标程序),然后再执行它。 2. 解释程序(解释器):按解释方式进行翻译的翻译程序称为解释程序。解释程序的主要优点是便于对源程序进行...
  • 编译原理总结

    2018-06-11 08:53:39
    编译原理是计算机专业的一门重要课程,主要介绍在编译程序构造的一般原理和方法,其中有, 编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析语法...
  • 编译原理重点考点梳理总结[期末总结]

    千次阅读 多人点赞 2020-08-19 20:15:07
    第二章(1)词法分析器的相关概念(2)正规式与正规集正规定义总结:(3)状态转换图(4)有限自动机(5)从正规式到有限自动机第三章(1)上下文无关文法、推导与归约、语法分析树、二义性(2)语法分析器的相关...
  • 自下而上语法分析 本章学习自下而上的语法分析,其分析过程为边输入单词符号,边归约(根据文法的产生式规则,把产生式的右部替换成左部符号)。可采用多种归约方式实现分析过程:(1)移进归约,即用一个寄存符号...
  • 编译原理知识点考点超全总结

    千次阅读 多人点赞 2020-07-22 17:30:07
    T 型图描述自举及移植的过程第二章 词法分析什么是词法分析记号分类正则表达式什么是有穷自动机DFA(确定性有穷自动机)NFA(非确定性有穷自动机)第三章 上下文无关文法上下文无关文法与正则表达式的主要区别:终结...
  • 1、参考书籍:《编译原理》第三版 清华大学出版社 1、本文内容全部来源于开源社区 GitHub和以上博主的贡献,本文也免费开源(可能会存在问题,评论区等待大佬们的指正) 2、本文目的:开源共享 抛砖引玉 一起学习 3...
  • 我用的是LL(1)分析法(又叫预测分析法),开始的时候花了一段时间来理解LL(1)算法,后来到设计、实现、各种测试,可谓经历了一番波折。记得刚开始写的时候想用C++,后来发现竟然忘的差不多了,囧,于是索性挫到底...
  • 程序语言语法——语法规则和词法规则语义——描述语法单位的功能和意义词法规则——合法单词的构成规则(有限状态自动机或正规式描述)语法规则——合法程序的构成规则(用上下文无关文法描述)字母表∑——有限字符...
  • 编译原理概述——基本知识要点汇总,主要对翻译程序、编译程序、解释程序、汇编程序几个概念进行区分和总结,并对编译过程及编译程序的基本结构、编译程序的生成方法做出归纳
  • 编译原理第二章学习总结编译原理是一门独立于其他学科之外的理论性科目,第二章的知识内容首先交代语言程序是一定字符集上的一字符串。如今多数的程序语言可以通过上下文无关文法来作为有效工具描述程序语言的语法...
  • 编译原理知识点复习重点符号表相关语言和文法相关编译和解释相关基本块相关中间代码相关其它其它优化问题推导归约相关LL(1)LR分析法 产生式是用于定义语法范畴的一种书写规则。 程序语言的语句大体分为执行性语句和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,997
精华内容 10,798
关键字:

编译原理语法分析知识点总结