精华内容
下载资源
问答
  • 编译原理语法分析3-LR分析器

    千次阅读 2018-11-02 15:54:55
    #语法分析LR分析器 import pandas as pd data={'id':['s5',' ',' ',' ','s5',' ','s5','s5',' ',' ',' ',' '], '+':[' ','s6','r2','r4',' ','r6',' ',' ','s6','r1','r3','r5'], '*':[' ',' ','s7','...

    要求

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

    代码

    #语法分析,LR分析器
    import pandas as pd
    data={'id':['s5',' ',' ',' ','s5',' ','s5','s5',' ',' ',' ',' '],
          '+':[' ','s6','r2','r4',' ','r6',' ',' ','s6','r1','r3','r5'],
          '*':[' ',' ','s7','r4',' ','r6',' ',' ',' ','s7','r3','r5'],
          '(':['s4',' ',' ',' ','s4',' ','s4','s4',' ',' ',' ',' ',],
          ')':[' ',' ','r2','r4',' ','r6',' ',' ','s11','r1','r3','r5'],
          '$':[' ','acc','r2','r4',' ','r6',' ',' ',' ','r1','r3','r5'],
          'E':['1',' ',' ',' ','8',' ',' ',' ',' ',' ',' ',' '],
          'T':['2',' ',' ',' ','2',' ','9',' ',' ',' ',' ',' ',],
          'F':['3',' ',' ',' ','3',' ','3','10',' ',' ',' ',' ']}
    SLR=pd.DataFrame(data,index=['0','1','2','3','4','5','6','7','8','9','10','11'])#SLR分析表
    grammer=[' ','E→E+T','E→T','T→T*F','T→F','F→(E)','F→id']#文法的各个产生式
    stk='0'#用字符串模拟栈
    sub=""   #当前待处理记号被处理后的输入
    def nextToken():#获取下一个词法记号
        global sub
        if(sub[0:2]=="id"):
             sub=sub[2:]
             return "id"
        else:
            s=sub[0:1]
            sub=sub[1:]
            return s
    def showNextToken():#查看下一个词法记号
        global sub
        if (sub[0:2] == "id"):
            return "id"
        else:
            s = sub[0:1]
            return s
    def top():#获取栈顶元素
        global stk
        if(stk[-2:]=='10'or stk[-2:]=='id' or stk[-2:]=='11'):
            return stk[-2:]
        else:
            return stk[-1:]
    def pop():#弹出栈顶元素
        global stk
        if(stk[-2:]=='id'or stk[-2:]=='10'or stk[-2:]=='11'):
            stk=stk[:-2];
        else:
            stk=stk[:-1]
    def push(s):#产生式→右边的逆序入栈
        global stk
        stk=stk+s
    def rightlenth(s):#计算产生式→右边的长度
        index=s.find('→')
        ss=s[index+1:]
        if ss=='id':
            return 1
        else:
            return len(s[index+1:])
    def leftPro(s):#计算产生式→左边的非终结符
        index = s.find('→')
        return s[:index]
    def handle(t,head):#分析程序
        global SLR
        global stk
        action=SLR[head][t]
        #print("head=",head,'t=',t,"action=",action,end="  ")
        if action=='acc':
            print("%-10s"%stk,"%+9s"%sub,'    接受')
            return True
        else:
            if action[0]=='s':#要移进
                print("%-10s"%stk,"%+9s"%sub,"    移进")
                push(nextToken())
                push(action[1:])
            elif action[0]=='r':#要归约
                production=grammer[ord(action[1:])-ord('0')]
                print("%-10s"%stk,"%+9s"%sub,"    按",production,"归约")
                lenth=rightlenth(production)
                for i in range(lenth*2):
                    pop()
                t=top()
                left=leftPro(production)
                push(left)
                push(SLR[left][t])
            else:#出错
                print("%-10s"%stk,"%+9s"%sub,end='')
                print("     error",end=',  ')
                print('多输入了一个',head)
                head=nextToken()
            return False
    if __name__=='__main__':
        print("---------------------------------------")
        sub=input()
        sub+='$'
        print("---------------------------------------")
        print("%-8s"%"栈","%+8s"%"输入","    动作")
        while(True):
            b=handle(top(),showNextToken())
            if b==True:
                break
        print("---------------------------------------")
    

    输入输出

    在这里插入图片描述

    展开全文
  • 从new.txt文件中读入写好的由正规表达式(a|b)*(aa|bb)(a|b)*所转化的正规文法(右线性),自动构造项目集族,生成LR分析表,并对输入的字符串通过LR分析表进行分析,输出分析过程,指出错误
  • 编译原理语法分析器

    万次阅读 多人点赞 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|ε

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

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

    展开全文
  • 自制编译器语法分析器

    千次阅读 2014-10-06 10:39:14
    感觉语法分析器编译器前端是一个较为庞大的东西,因此打算分两篇博客来描述,第一篇着重描述思想,第二篇具体论述实现。   1、语法分析器要做什么 在编写任何一个东西的的时候,都要先弄明白这个玩意儿...

    感觉语法分析器在编译器前端是一个较为庞大的东西,因此打算分两篇博客来描述,第一篇着重描述思想,第二篇具体论述实现。

     

    1、语法分析器要做什么

    在编写任何一个东西的的时候,都要先弄明白这个玩意儿是做什么的,接受什么输入,产生什么输出。

    一个语法分析器要接受词法分析器所产生的词素作为输入,产生一个抽象语法树给中间代码生成器,然后再由中间代码生成器生成中间代码并递交给编译器后端。当然在某些理解中可以把抽象语法树就当做是一种中间代码的表示形式,直接递交给后端。不管怎么说,总之就是语法分析器是一个生成抽象语法树的东西。

    值得注意的是,语法分析器不仅要生成抽象语法树,而且还要在这个生成过程中找出各种语法错误并生成和维护符号表。

     

    2、符号表

    什么是符号表?符号表有什么用?

    所谓符号表就是一个记录各种标识符(也就是终结符号id,词素id)及其属性的表,比如记录一个int变量x的类型为int,它的作用域,记录一个函数名,记录其函数类型,参数列表等。

    符号表有作用域,比如一段简单的代码:

    [java] view plaincopy
    1. public void function()  
    2. {  
    3.    int i=0;  
    4.    while(true)  
    5.    {  
    6.       int i=1;  
    7.    }  
    8. }  

    因此一个符号表的构造一定是一个树状结构,我们在编译器中用以下结构来描述一个符号表:

    [java] view plaincopy
    1. package ravaComplier.symTable;  
    2. import java.util.*;  
    3. public class SymTable {  
    4.     private SymTable fatherSymTable;  
    5.     private ArrayList<SymTable> blockSymTables;  
    6.     private HashMap<String,Symbol> table;  
    7.     private String blockid;  
    8.     public SymTable(SymTable st,String str)  
    9.     {  
    10.         fatherSymTable=st;  
    11.         blockid=str;  
    12.         blockSymTables=new ArrayList<SymTable>();  
    13.         table=new HashMap<String,Symbol>();  
    14.     }  
    15.     public void addSym(Symbol sym)  
    16.     {  
    17.         table.put(sym.id, sym);  
    18.     }  
    19.     public Symbol getSym(String id)  
    20.     {  
    21.         Symbol result=table.get(id);  
    22.         if(result==null && fatherSymTable!=null)  
    23.         {  
    24.             return fatherSymTable.getSym(id);  
    25.         }  
    26.         return result;  
    27.     }  
    28.     public void addSymTable(SymTable st)  
    29.     {  
    30.         blockSymTables.add(st);  
    31.     }  
    32. }  

    代码很简单以至于注释都懒得写了。

    通过fatherSymTable来记录此符号表的父表,用于不断的向上回溯查找符号(getSym)使用。
    blockid算是给此表一个id,用于打印调试信息时使用。
    addSym在此表增加符号。除此之外还有个addSymTables来加入子表。
    另外此类还重载了toString()方法,用于debug信息,限于篇幅这个方法没贴到博客里,可在我上传的资源里拿到完整的源文件。
    也许在之后的分析描述写代码的过程中我会发现需要给这个类添加新的函数,到那时再对此类进行补充。
    接下来看看简单的Symbol类,也就是表示一个符号的类:

    [java] view plaincopy
    1. package ravaComplier.symTable;  
    2.   
    3. public class Symbol {  
    4.     public String id;  
    5.     public int type;  
    6.     public Object value;  
    7.     public Symbol(String i,int t,Object v)  
    8.     {  
    9.         id=i;  
    10.         type=t;  
    11.         value=v;  
    12.     }  
    13.     public static int TYPE_CLASSNAME=0;  
    14.     public static int TYPE_MEMBERVAR=1;  
    15.     public static int TYPE_LOCALVAR=2;  
    16.     public static int TYPE_FUNCNAME=3;  
    17.     public static int TYPE_CONSFUNC=4;  
    18. }  

    分为3个域,id,也就是标识符,type,枚举值已列出,value,根据不用的枚举值定义了不同的value,之后若用到了再贴代码吧。
    总共分为5类符号:类名、成员变量、局部变量、函数名和构造函数名。
    当然若之后根据需要,或许会使用新的符号也可以灵活的添加。

     

    3、语法树的表示
    一棵语法树不能使用普通的树结构因为每个不同的节点的行为、值太多且不同。语法树中的节点为非终结符号或者终结符号,对于其中的id,我们就让它指向符号表中的符号即可,对于非终结符号,每个非终结符号我们都建立一个新的类来描述其行为,对于非id的终结符号,其信息要么不记录(比如无意义的分好括号等),要么简单记录其类型(比如各种运算符)。
    所以这种情况下每一个节点的建立都比较灵活,下面举两个例子:
    对于产生式:ops --> bitop | logiop | artmop | cprop
    我们建立如下的类来描述ops:

    [java] view plaincopy
    1. package ravaComplier.syntax.nodes;  
    2.   
    3. public class ops {  
    4.     private int type;  
    5.     private Object value; //must be bitop,logiop,artmop,cprop  
    6.     public ops()  
    7.     {  
    8.         //not implements  
    9.     }  
    10.     public static int TYPE_BITOP=0;  
    11.     public static int TYPE_LOGIOP=1;  
    12.     public static int TYPE_ARTMOP=2;  
    13.     public static int TYPE_CPROP=3;  
    14. }  
    int描述运算符类型,然后根据响应的类型让value为具体的运算符类。接着给出cprop的类:
    [java] view plaincopy
    1. package ravaComplier.syntax.nodes;  
    2.   
    3. public class cprop {  
    4.     public cprop()  
    5.     {  
    6.         //not implemets  
    7.     }  
    8.     private int type;  
    9.     public static int  TYPE_GREATER = 0;//>  
    10.     public static int TYPE_GREATEREQUAL=1;//>=;  
    11.     public static int TYPE_LESS=2;//<;  
    12.     public static int TYPE_LESSEQUEAL=3;//<=;  
    13.     public static int TYPE_EQUAL=4;//==  
    14. }  

    这是一个终结符,所以只有一个域来记录运算符的类型。


    接下来讲着重分析语法树的展开过程。

    一、语法制导翻译、LL与LL(X)语法、左递归等其它

    为什么要写一个语法分析器?语法分析器的作用不仅仅是来检查词素列表中的序列是否是一个我们语言的语句,更重要的是只有借助语法分析器得到的抽象语法树,才能够生成中间代码或者具体的目标代码,这个过程叫做语法制导翻译(syntax-directed translation)。在紫龙书(编译原理第二版)的封面上,一个拿盾的骑士正在和一个喷火龙决斗,其中龙的身上写的是Complexity of Complier Design,而骑士的盾上写的则是Syntax Directed Translation,因此把语法制导翻译当作是编译器前端的核心也不为过。


    展开语法树的过程实质上也就是将词素不断地对应到我们语言定义的递推式的过程,换个说法其实也就是不断地展开语言的递推式,使之符合已有词素的过程。这个展开的过程从方法上来讲可分为两种:LL和LR。其中第一个字母代表从左到右读词素序列,第二个字母L代表尝试最先展开最左边的非终结符号,R代表尝试从右边开始将词素归约为非终结符好。换言之,LL是一种自顶向下的展开方法,LR是一种自底向上的归约方法,本文采用的技术为LL,所以以下也以讨论LL为主。


    为了使编译器能高效迅速,一个良好的语法设计必须是一个LL(1)语法,什么是LL(1)语法呢?举个例子,当我们面对如下推导式的时候:

    ids-> id|               ----------1

              id.ids|        -----------2

             ids[expr] |   -----------3

             this

    此时我们读到了一个词素id,是展开成1、2、3中的哪种呢?当然目前我们无法判断,因此需要多读入下一个词素才能进行判断。如果读到的是[,则展开成3。如果读到了.则展开成2,否则展开成1。但问题是有些情况下,多读入一个词素或许还不能进行判断,当一个语言的语法中,只要多读入X个词素就能唯一的确定推导式,则称其为LL(X)文法。很遗憾,我们的语法不是LL(1)语法,虽然有很多推导式的处理技巧可以将一个非LL(1)的语法处理成LL(1)的语法,但这样会失去语法的直观性。考虑再三我在“不是很合理但易于理解的语法” 和 “合理高效的不直观的语法” 之间选择了前者。

    因此既然我们的语法并非LL(1)的,因此在语法分析的过程中,我们只是不断的去尝试展开,如果不成功,则回溯。虽然这是比较低效的,但文法中的大多数推导式并不复杂,所以处理的时间完全可以接受。

    考虑如下 推导式:

    expr -->  (expr)     ------------1

                    ids|       ------------2

                  number|    -----------3

                  literal|      ------------4

                 func-call|   ------------5

                expr  ops expr|

    这个推导式不满足LL(1),假设当前读到了一个id,目前可供选择的有2、4、5,然后又读入了一个“。”,目前可供选择的还是2、4、5,又读入了一个id,可供选择的还是2、4、5,然后读入了一个“(” ,这时候才能确定唯一的展开式func-call。但这个表达式除了不满足LL(1)之外还有其它的问题:左递归。

    假设expr上来就尝试去展开成5的形式,因为是递归展开的过程,5中最左边的expr又会尝试展开成5的形式,然后这个过程就不断递归下去最终导致stack overflow。虽然有很多方法和技巧可以改变推导式的形式来消除左递归,但是依然本着易于理解的原则,我们在语法分析中通过使用朴素的笨办法来避免这种情况的发生。所谓的笨办法就是:

    (1)按优先级先展开1234,然后都失败再展开成5。

    (2)设置最大展开深度为200,超过了直接报错。

    虽然很笨很低效,但勉强够用了。


    二、语法分析器结构

    语法分析器在实现上分以下几个部分,第一部分为SyntaxTreeGenerator,负责读入词素,和词法分析器以及后端程序进行交流,算是语法分析器的对外接口。其次使用GlobalVars来存储各种全局数据,记录分析过程中的各种信息。最后就是各种节点,每个节点在分析的过程中若需要其它信息则通过GlobalVars来解耦。接下来通过几个例子来具体说明这些节点是如何展开语法分析的:


    (1)id

    [java] view plaincopy
    1. package ravaComplier.syntax.nodes;  
    2.   
    3. import ravaComplier.lexer.Lexeme;  
    4. import ravaComplier.symTable.SymTable;  
    5. import ravaComplier.symTable.Symbol;  
    6. import ravaComplier.syntax.GlobalVars;  
    7. import ravaComplier.syntax.SyntaxTreeGenerator;  
    8.   
    9. /* 
    10.  * 该类尝试读入词素并生成id节点 
    11.  */  
    12. public class id {  
    13.     public SymTable curST;//这个节点的符号表  
    14.     public id() throws Exception  
    15.     {  
    16.       
    17.         Lexeme lex=SyntaxTreeGenerator.readLexeme();//读一个词素  
    18.         curST=SyntaxTreeGenerator.getCurTable();//得到当前符号表  
    19.         if(lex.type==Lexeme.ID)  
    20.         {  
    21.             //类型正确  
    22.             symEntry=SyntaxTreeGenerator.getCurTable().getSym(lex.value.toString());//判断符号表中是否已有此id  
    23.             if(symEntry==null)  
    24.             {  
    25.                 firstappear=true;  
    26.                   
    27.             }  
    28.             else  
    29.             {  
    30.                 firstappear=false;  
    31.             }  
    32.             value=lex.value.toString();  
    33.               
    34.             symEntry=new Symbol(value,2,null);//生成一个入口  
    35.         }  
    36.         else  
    37.         {  
    38.             //类型错误抛出异常  
    39.             throw new Exception("ID required!\r\n");  
    40.               
    41.         }  
    42.         GlobalVars.idlist.add(this);//把所有id都添加进idlist里。  
    43.     }  
    44.     public String value;  
    45.     public boolean firstappear;  
    46.     public type tp;//类型,由调用者赋值  
    47.     public Symbol symEntry;//指向符号表的条目  
    48. }  
    这个类代表id节点,首先尝试读入词素,如果不是id则发生语法错误。其次需要判断此id是否是第一次出现,在某些时候这个信息很重要(比如变量定义时),然后最后将已经初始化好的id添加到GlobalVars的list中。值得注意的是,GlobalVars里面有很多的list,主要是用于在生成语法树之后用于一些检查。

    (2)vardeclare

    来个稍微复杂点的,局部变量的定义

    [java] view plaincopy
    1. package ravaComplier.syntax.nodes;  
    2.   
    3. import java.util.ArrayList;  
    4.   
    5. import ravaComplier.lexer.Lexeme;  
    6. import ravaComplier.symTable.SymTable;  
    7. import ravaComplier.symTable.Symbol;  
    8. import ravaComplier.syntax.SyntaxTreeGenerator;  
    9.   
    10. public class vardeclare {  
    11.     /* 
    12.      * var-declare --> type args|type[] args 
    13.      *         
    14.      */  
    15.     public SymTable curST;  
    16.     public vardeclare() throws Exception  
    17.     {  
    18.         curST=SyntaxTreeGenerator.getCurTable();  
    19.         tp=new type();  
    20.         int pos=SyntaxTreeGenerator.savePos();//得到当前分析的位置  
    21.         Lexeme lex=SyntaxTreeGenerator.readLexeme();//读取下一个词素  
    22.         arrayDeclare=false;  
    23.         if(!lex.value.equals("["))  
    24.         {  
    25.             SyntaxTreeGenerator.loadPos(pos);//若不是想要的词素则回溯  
    26.         }  
    27.         else  
    28.         {  
    29.             lex=SyntaxTreeGenerator.readLexeme();  
    30.             if(!lex.value.equals("]"))  
    31.             {  
    32.                 SyntaxTreeGenerator.loadPos(pos);  
    33.                 throw new Exception("] expected!");//发生语法错误,数组定义时括号没有闭合。  
    34.             }  
    35.             else  
    36.             {  
    37.                 arrayDeclare=true;  
    38.                   
    39.             }  
    40.         }  
    41.         ags=new args();  
    42.         ArrayList<ids> al=ags.getidsList();//获取参数列表,若args为   a1,a2,a3则返回的列表中含有a1,a2,a3  
    43.         SymTable st=SyntaxTreeGenerator.getCurTable();  
    44.         for(int i=0;i<=al.size()-1;i++)  
    45.         {  
    46.             id ID=al.get(i).getLastID();//id1.id2.id3则此函数返回id3。  
    47.             if(ID.firstappear==false)  
    48.             {  
    49.                 throw new Exception("id declared duplicated!");//定义的变量名已经出现过了,报错  
    50.             }  
    51.             st.addSym(ID.symEntry);//将id添加进符号表  
    52.             ID.symEntry.value=ID;  
    53.             ID.symEntry.type=Symbol.TYPE_LOCALVAR;  
    54.             ID.tp=tp;//给此id赋予类型  
    55.             if(arrayDeclare)  
    56.             {  
    57.                 ID.tp.isArray=true;  
    58.             }  
    59.         }  
    60.     }  
    61.     public type tp;  
    62.     public args ags;  
    63.     public boolean arrayDeclare;  
    64. }  
    可以看出,id节点中的很多属性都是由其调用者决定的,这点在节点逻辑的编写中体现的尤为明显。


    (3)memberfundeclare

    来个再复杂点的,成员函数定义:

    [java] view plaincopy
    1. package ravaComplier.syntax.nodes;  
    2.   
    3. import ravaComplier.lexer.Lexeme;  
    4. import ravaComplier.symTable.SymTable;  
    5. import ravaComplier.symTable.Symbol;  
    6. import ravaComplier.syntax.SyntaxTreeGenerator;  
    7.   
    8. public class memberfuncdeclare {  
    9.     public SymTable curST;  
    10.     public memberfuncdeclare() throws Exception  
    11.     {  
    12.         /*member-func-declare --> private|public 
    13.                                   NUL|static 
    14.                                   type func-name(  NUL|def-args )  {  func-body  }*/  
    15.         curST=SyntaxTreeGenerator.getCurTable();  
    16.         af=new accessflag();//得到一个accessflag, 即public 或者 private  
    17.         //尝试读取static ,若没有则回溯。  
    18.         int pos=SyntaxTreeGenerator.savePos();  
    19.         Lexeme lex=SyntaxTreeGenerator.readLexeme();  
    20.         if(lex.type!=Lexeme.STATIC)  
    21.         {  
    22.             SyntaxTreeGenerator.loadPos(pos);  
    23.         }  
    24.         else  
    25.         {  
    26.               
    27.             isstatic=true;  
    28.         }  
    29.         tp=new type();//得到type  
    30.         fc=new funcname();//得到函数名。  
    31.         fc.id.symEntry.value=this;  
    32.         if(fc.id.firstappear==false)  
    33.         {  
    34.             //判断函数名是否重复,若重复则报错。  
    35.             throw new Exception("function name must be unique!");  
    36.         }  
    37.         SymTable st=SyntaxTreeGenerator.getCurTable();  
    38.         st.addSym(fc.id.symEntry);//把这个函数添加进符号表  
    39.         fc.id.symEntry.type=Symbol.TYPE_FUNCNAME;  
    40.         SymTable st1=new SymTable(st,fc.id.value+" symtable");//建立一个子表,每个函数都有自己的符号表因为里面变量的作用域和其外不同  
    41.         SyntaxTreeGenerator.setCurTable(st1);//将子表设置为当前符号表,之后该函数体内的一切分析都使用该表  
    42.         lex=SyntaxTreeGenerator.readLexeme();  
    43.         if(!lex.value.toString().equals("("))  
    44.         {  
    45.             throw new Exception("( expected!");//语法检查  
    46.         }  
    47.         try  
    48.         {  
    49.             pos=SyntaxTreeGenerator.savePos();  
    50.         da=new defargs();//尝试搜寻其后的调用参数,若没有参数则根据上一行存储的位置回滚  
    51.           
    52.         }  
    53.         catch(Exception e)  
    54.         {  
    55.             SyntaxTreeGenerator.loadPos(pos);  
    56.             da=null;  
    57.         }  
    58.         lex=SyntaxTreeGenerator.readLexeme();  
    59.         if(!lex.value.toString().equals(")"))  
    60.         {  
    61.             throw new Exception(") expected!");//语法检查  
    62.         }  
    63.         lex=SyntaxTreeGenerator.readLexeme();  
    64.         if(!lex.value.toString().equals("{"))  
    65.         {  
    66.             throw new Exception("{ expected!");//语法检查  
    67.         }  
    68.         fb=new funcbody();//构造函数体  
    69.         lex=SyntaxTreeGenerator.readLexeme();  
    70.         if(!lex.value.toString().equals("}"))  
    71.         {  
    72.             throw new Exception("} expected!");//语法检查  
    73.         }  
    74.         SyntaxTreeGenerator.setCurTable(st);//函数结束,重置符号表  
    75.     }  
    76.     public accessflag af;  
    77.     public type tp;  
    78.     public boolean isstatic;  
    79.     public funcname fc;  
    80.     public defargs da;  
    81.     public funcbody fb;  
    82. }  



    通过以上的分析,我们可以总结出每一个节点的构造规则:

    1、尝试将此节点按一定的顺序展开

    2、其每一个部分当作该节点的成员变量

    3、在展开的时候和符号表进行适当的交互

     

    按照类似的思路,我们当我们完成所有节点后,编译器的前端也已经差不多了,下图是上篇博文中日志里的示例程序得到的语法树,可以看到即便是一个简单的示例程序,其语法树也相当复杂。



    展开全文
  • 这是我用VC6.0(用了MFC类库)编写的一个集词法分析、语法分析为一体的程序,是我编译原理课程设计的拙作!压缩包里包括源代码、测试数据,可执行文件打包,安装文件打包,课程设计文档,程序使用说明和数据规范说明...
  • 自制编译器语法分析器(二)

    万次阅读 2013-05-16 23:13:42
    这篇博文拖了好久才写完,其一是语法分析器本身的难度实在有点超出我的预料,以至于反复重构多次才完成,其二是因为弄了个xbox玩,占用了一部分的课余时间= =!。 本篇博文将分为以下几个部分来描述一下语法分析器...

    这篇博文拖了好久才写完,其一是语法分析器本身的难度实在有点超出我的预料,以至于反复重构多次才完成,其二是因为弄了个xbox玩,占用了一部分的课余时间= =!。

    本篇博文将分为以下几个部分来描述一下语法分析器的具体实现,理论、部分典型节点与结果。


    一、语法制导翻译、LL与LL(X)语法、左递归等其它

    为什么要写一个语法分析器?语法分析器的作用不仅仅是来检查词素列表中的序列是否是一个我们语言的语句,更重要的是只有借助语法分析器得到的抽象语法树,才能够生成中间代码或者具体的目标代码,这个过程叫做语法制导翻译(syntax-directed translation)。在紫龙书(编译原理第二版)的封面上,一个拿盾的骑士正在和一个喷火龙决斗,其中龙的身上写的是Complexity of Complier Design,而骑士的盾上写的则是Syntax Directed Translation,因此把语法制导翻译当作是编译器前端的核心也不为过。


    展开语法树的过程实质上也就是将词素不断地对应到我们语言定义的递推式的过程,换个说法其实也就是不断地展开语言的递推式,使之符合已有词素的过程。这个展开的过程从方法上来讲可分为两种:LL和LR。其中第一个字母代表从左到右读词素序列,第二个字母L代表尝试最先展开最左边的非终结符号,R代表尝试从右边开始将词素归约为非终结符好。换言之,LL是一种自顶向下的展开方法,LR是一种自底向上的归约方法,本文采用的技术为LL,所以以下也以讨论LL为主。


    为了使编译器能高效迅速,一个良好的语法设计必须是一个LL(1)语法,什么是LL(1)语法呢?举个例子,当我们面对如下推导式的时候:

    ids-> id|               ----------1

              id.ids|        -----------2

             ids[expr] |   -----------3

             this

    此时我们读到了一个词素id,是展开成1、2、3中的哪种呢?当然目前我们无法判断,因此需要多读入下一个词素才能进行判断。如果读到的是[,则展开成3。如果读到了.则展开成2,否则展开成1。但问题是有些情况下,多读入一个词素或许还不能进行判断,当一个语言的语法中,只要多读入X个词素就能唯一的确定推导式,则称其为LL(X)文法。很遗憾,我们的语法不是LL(1)语法,虽然有很多推导式的处理技巧可以将一个非LL(1)的语法处理成LL(1)的语法,但这样会失去语法的直观性。考虑再三我在“不是很合理但易于理解的语法” 和 “合理高效的不直观的语法” 之间选择了前者。

    因此既然我们的语法并非LL(1)的,因此在语法分析的过程中,我们只是不断的去尝试展开,如果不成功,则回溯。虽然这是比较低效的,但文法中的大多数推导式并不复杂,所以处理的时间完全可以接受。

    考虑如下 推导式:

    expr -->  (expr)     ------------1

                    ids|       ------------2

                  number|    -----------3

                  literal|      ------------4

                 func-call|   ------------5

                expr  ops expr|

    这个推导式不满足LL(1),假设当前读到了一个id,目前可供选择的有2、4、5,然后又读入了一个“。”,目前可供选择的还是2、4、5,又读入了一个id,可供选择的还是2、4、5,然后读入了一个“(” ,这时候才能确定唯一的展开式func-call。但这个表达式除了不满足LL(1)之外还有其它的问题:左递归。

    假设expr上来就尝试去展开成5的形式,因为是递归展开的过程,5中最左边的expr又会尝试展开成5的形式,然后这个过程就不断递归下去最终导致stack overflow。虽然有很多方法和技巧可以改变推导式的形式来消除左递归,但是依然本着易于理解的原则,我们在语法分析中通过使用朴素的笨办法来避免这种情况的发生。所谓的笨办法就是:

    (1)按优先级先展开1234,然后都失败再展开成5。

    (2)设置最大展开深度为200,超过了直接报错。

    虽然很笨很低效,但勉强够用了。


    二、语法分析器结构

    语法分析器在实现上分以下几个部分,第一部分为SyntaxTreeGenerator,负责读入词素,和词法分析器以及后端程序进行交流,算是语法分析器的对外接口。其次使用GlobalVars来存储各种全局数据,记录分析过程中的各种信息。最后就是各种节点,每个节点在分析的过程中若需要其它信息则通过GlobalVars来解耦。接下来通过几个例子来具体说明这些节点是如何展开语法分析的:


    (1)id

    package ravaComplier.syntax.nodes;
    
    import ravaComplier.lexer.Lexeme;
    import ravaComplier.symTable.SymTable;
    import ravaComplier.symTable.Symbol;
    import ravaComplier.syntax.GlobalVars;
    import ravaComplier.syntax.SyntaxTreeGenerator;
    
    /*
     * 该类尝试读入词素并生成id节点
     */
    public class id {
    	public SymTable curST;//这个节点的符号表
    	public id() throws Exception
    	{
    	
    		Lexeme lex=SyntaxTreeGenerator.readLexeme();//读一个词素
    		curST=SyntaxTreeGenerator.getCurTable();//得到当前符号表
    		if(lex.type==Lexeme.ID)
    		{
    			//类型正确
    			symEntry=SyntaxTreeGenerator.getCurTable().getSym(lex.value.toString());//判断符号表中是否已有此id
    			if(symEntry==null)
    			{
    				firstappear=true;
    				
    			}
    			else
    			{
    				firstappear=false;
    			}
    			value=lex.value.toString();
    			
    			symEntry=new Symbol(value,2,null);//生成一个入口
    		}
    		else
    		{
    			//类型错误抛出异常
    			throw new Exception("ID required!\r\n");
    			
    		}
    		GlobalVars.idlist.add(this);//把所有id都添加进idlist里。
    	}
    	public String value;
    	public boolean firstappear;
    	public type tp;//类型,由调用者赋值
    	public Symbol symEntry;//指向符号表的条目
    }
    这个类代表id节点,首先尝试读入词素,如果不是id则发生语法错误。其次需要判断此id是否是第一次出现,在某些时候这个信息很重要(比如变量定义时),然后最后将已经初始化好的id添加到GlobalVars的list中。值得注意的是,GlobalVars里面有很多的list,主要是用于在生成语法树之后用于一些检查。

    (2)vardeclare

    来个稍微复杂点的,局部变量的定义

    package ravaComplier.syntax.nodes;
    
    import java.util.ArrayList;
    
    import ravaComplier.lexer.Lexeme;
    import ravaComplier.symTable.SymTable;
    import ravaComplier.symTable.Symbol;
    import ravaComplier.syntax.SyntaxTreeGenerator;
    
    public class vardeclare {
    	/*
    	 * var-declare --> type args|type[] args
    	 *        
    	 */
    	public SymTable curST;
    	public vardeclare() throws Exception
    	{
    		curST=SyntaxTreeGenerator.getCurTable();
    		tp=new type();
    		int pos=SyntaxTreeGenerator.savePos();//得到当前分析的位置
    		Lexeme lex=SyntaxTreeGenerator.readLexeme();//读取下一个词素
    		arrayDeclare=false;
    		if(!lex.value.equals("["))
    		{
    			SyntaxTreeGenerator.loadPos(pos);//若不是想要的词素则回溯
    		}
    		else
    		{
    			lex=SyntaxTreeGenerator.readLexeme();
    			if(!lex.value.equals("]"))
    			{
    				SyntaxTreeGenerator.loadPos(pos);
    				throw new Exception("] expected!");//发生语法错误,数组定义时括号没有闭合。
    			}
    			else
    			{
    				arrayDeclare=true;
    				
    			}
    		}
    		ags=new args();
    		ArrayList<ids> al=ags.getidsList();//获取参数列表,若args为   a1,a2,a3则返回的列表中含有a1,a2,a3
    		SymTable st=SyntaxTreeGenerator.getCurTable();
    		for(int i=0;i<=al.size()-1;i++)
    		{
    			id ID=al.get(i).getLastID();//id1.id2.id3则此函数返回id3。
    			if(ID.firstappear==false)
    			{
    				throw new Exception("id declared duplicated!");//定义的变量名已经出现过了,报错
    			}
    			st.addSym(ID.symEntry);//将id添加进符号表
    			ID.symEntry.value=ID;
    			ID.symEntry.type=Symbol.TYPE_LOCALVAR;
    			ID.tp=tp;//给此id赋予类型
    			if(arrayDeclare)
    			{
    				ID.tp.isArray=true;
    			}
    		}
    	}
    	public type tp;
    	public args ags;
    	public boolean arrayDeclare;
    }
    可以看出,id节点中的很多属性都是由其调用者决定的,这点在节点逻辑的编写中体现的尤为明显。


    (3)memberfundeclare

    来个再复杂点的,成员函数定义:

    package ravaComplier.syntax.nodes;
    
    import ravaComplier.lexer.Lexeme;
    import ravaComplier.symTable.SymTable;
    import ravaComplier.symTable.Symbol;
    import ravaComplier.syntax.SyntaxTreeGenerator;
    
    public class memberfuncdeclare {
    	public SymTable curST;
    	public memberfuncdeclare() throws Exception
    	{
    		/*member-func-declare --> private|public
                                      NUL|static
                                      type func-name(  NUL|def-args )  {  func-body  }*/
    		curST=SyntaxTreeGenerator.getCurTable();
    		af=new accessflag();//得到一个accessflag, 即public 或者 private
    		//尝试读取static ,若没有则回溯。
    		int pos=SyntaxTreeGenerator.savePos();
    		Lexeme lex=SyntaxTreeGenerator.readLexeme();
    		if(lex.type!=Lexeme.STATIC)
    		{
    			SyntaxTreeGenerator.loadPos(pos);
    		}
    		else
    		{
    			
    			isstatic=true;
    		}
    		tp=new type();//得到type
    		fc=new funcname();//得到函数名。
    		fc.id.symEntry.value=this;
    		if(fc.id.firstappear==false)
    		{
    			//判断函数名是否重复,若重复则报错。
    			throw new Exception("function name must be unique!");
    		}
    		SymTable st=SyntaxTreeGenerator.getCurTable();
    		st.addSym(fc.id.symEntry);//把这个函数添加进符号表
    		fc.id.symEntry.type=Symbol.TYPE_FUNCNAME;
    		SymTable st1=new SymTable(st,fc.id.value+" symtable");//建立一个子表,每个函数都有自己的符号表因为里面变量的作用域和其外不同
    		SyntaxTreeGenerator.setCurTable(st1);//将子表设置为当前符号表,之后该函数体内的一切分析都使用该表
    		lex=SyntaxTreeGenerator.readLexeme();
    		if(!lex.value.toString().equals("("))
    		{
    			throw new Exception("( expected!");//语法检查
    		}
    		try
    		{
    			pos=SyntaxTreeGenerator.savePos();
    		da=new defargs();//尝试搜寻其后的调用参数,若没有参数则根据上一行存储的位置回滚
    		
    		}
    		catch(Exception e)
    		{
    			SyntaxTreeGenerator.loadPos(pos);
    			da=null;
    		}
    		lex=SyntaxTreeGenerator.readLexeme();
    		if(!lex.value.toString().equals(")"))
    		{
    			throw new Exception(") expected!");//语法检查
    		}
    		lex=SyntaxTreeGenerator.readLexeme();
    		if(!lex.value.toString().equals("{"))
    		{
    			throw new Exception("{ expected!");//语法检查
    		}
    		fb=new funcbody();//构造函数体
    		lex=SyntaxTreeGenerator.readLexeme();
    		if(!lex.value.toString().equals("}"))
    		{
    			throw new Exception("} expected!");//语法检查
    		}
    		SyntaxTreeGenerator.setCurTable(st);//函数结束,重置符号表
    	}
    	public accessflag af;
    	public type tp;
    	public boolean isstatic;
    	public funcname fc;
    	public defargs da;
    	public funcbody fb;
    }



    通过以上的分析,我们可以总结出每一个节点的构造规则:

    1、尝试将此节点按一定的顺序展开

    2、其每一个部分当作该节点的成员变量

    3、在展开的时候和符号表进行适当的交互

     

    按照类似的思路,我们当我们完成所有节点后,编译器的前端也已经差不多了,下图是上篇博文中日志里的示例程序得到的语法树,可以看到即便是一个简单的示例程序,其语法树也相当复杂。


    展开全文
  • 编译原理——语法分析器

    热门讨论 2009-01-05 22:22:01
    语法分析编译程序的核心部分,其主要任务是确定语法结构,检查 语法错误,报告错误的性质和位置,并进行适当的纠错工作.法分析的方法有多种多样,常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL(K)...
  • 实验一的基础上,设计lr(1)分析表,实现lr(1)语法分析器,输出分析过程
  • 语法分析 词法分析:字母是元素,组成字符...语法分析器编译器前端的重要组成部分,中心部件 语法分析器的两个重要作用: 根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树) 检查输入中的语法
  • LR分析器是一种由下而上(bottom-up)的上下文无关语法分析器LR意指由左(Left)至右处理输入字符串,并以最右边优先派生(Right derivation)的推导顺序(相对于LL分析器)建构语法树。能以此方式分析的语法...
  • 今天学习了编译原理中的语法分析-自上而下分析的基本问题这一章节,我参考了国防工业出版社《编译原理》教材1 和中国大学MOOC-国防科技大学《编译原理》的PPT,整理了这一章的内容,希望能够理解这部分的知识。
  • 本章首先简要介绍编译的整体过程,然后对词法分析和语法分析中所采用的主要技术和算法进行论述分析,以便为整个系统的设计和开发提供理论基础。 1.1 编译过程概述 编译程序完成从源程序到目标程序的翻译工作,是一...
  • 编译原理 $2 语法分析

    2020-08-26 12:58:12
    §2 语法分析 C1 语法分析 1)作用:接受词法单元流,检查是否符合文法,翻译出中间代码 2)语法分析方法:自底向上与自顶向下 3)语法错误处理: 错误:词法错误、语法错误、语义错误、逻辑错误 恢复: Panic模式...
  • PS:本次语法分析器实验在我的实验一词法分析器的基础上完成,我把实验一的词法器类稍作修改获得代码的token串以支持语法分析器类LL1,参考了其他博主的first follow集求解代码以及预测分析表的生成代码,注意要修改...
  • 作为编译过程的核心部分,语法分析根据一定的语法规则,通过语法分析程序进行分析,识别出各类语法成分,进行语法检查。 语法分析程序 作用 输入:记号流/记号序列 输出:分析树 功能:将记号组合成语法成分,...
  • C语言实现的编译原理LR(1)文法分析器,VC++6.0开发
  • 编译原理语法分析器

    千次阅读 2016-11-01 19:49:08
    需求分析采用至少一种句法分析技术(LL(1)、SLR(1)、LR(1)或LALR(1))对类高级语言中的基本语句进行句法分析。阐述句法分析系统所要完成的功能。 (1)能识别以下几类语句: 声明语句(包括变量声明、数组声明、...
  • 语法分析(parsing or syntax analysis)最常用于实现编程语言的编译器,它的作用是输入一串词法单元,验证这些词法单元组成句子的语法是否正确,并输出语法分析树。 这就好比假如词法单元是单词,语法分析就是分析...
  • 编译原理 编译器的实现(C语言实现)chap1 词法语法语义的实现绪论 根据输入Context-free Grammar(上下文无关法)构建分析器,实现类似于yacc,lex的功能。 例如输入: S->S S->BB B->bB|a 下面说明,可选择...
  • C语言简化编译器前端 编译原理 LR1

    热门讨论 2010-07-14 20:28:30
    C语言编译器,采用C++实现。 词法分析、语法分析、语法制导翻译全过程。 附上ISO定义的标准C语言文法。 更具体说明见"说明.doc".
  • LR分析法及分析程序自动构造 概述 上下文无关文法的LR分析法 LR:自左至右扫描,最右推导的逆过程(也就是最左归约) LR方法: 在归约的过程中,一方面记住移入和归约的整个符号串,另一...LR分析器: 包括两部
  • 编译原理-语法分析

    2020-03-27 11:26:53
    许多编译器,特别是由自动生成工具构造的编译器,往往其前端的中心部件就是语法分析器 (1)语法分析器的作用 根据词法分析器提供的记号流,为语法正确的输入构造分析树(或语法树) 检查输入中的语法(可能包括词法...
  • 前言 该项目是我在学习编译原理的时候所完成的一个项目,不同于成熟的yacc语法分析器,我的语法检查器通过和一个词法分析器相互配合,启动之前读入由BNF范式和正则表达式所描述的文法与词法,之后根据给定的文法对...
  • 大家在参考本节时,请先阅读以下博文,进行预热: ...  ...代码的理解和运行是吃透编译原理的关键,如果我们看的是爱情动作片,自然选择无码的好,但如果看得是计算机课程,则必须有码,无码的计算机理
  • 编译原理-语法分析详解

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

    千次阅读 2019-01-29 20:59:53
    阅读已有编译器的经典语法分析源程序,并测试语法分析器的输出。 实验内容 (1)选择一个编译器,如:TINY,其它编译器也可(需自备源代码)。 (2)阅读语法分析源程序,加上你自己的理解。尤其要求对相关函数...
  • LR(1)文法也需要构造要给预测分析表,但是LR(1)的的预测分析表有两部分,分别是action表和goto表。 action表的横坐标是不同的状态标号,纵坐标是不同的终结符,goto表的横坐标也是不同状态标号,纵坐标是不同的非...
  • 实验一:词法分析器 词法分析器的思路: 1.首先是对关键词的识别 可以做一个数组存放关键词的所有单词,例如下列程序的 char *rwtab[6]={"begin","if","then","while","do","end"}; 2.然后是主程序的逻辑: * 循环...
  • " Expression |"(" Expression ")" 注意事项 1) EOF 表示的是词法分析器在扫描到文件尾时返回的token 2) 未被引号包裹的()[]{}范式中的符号,而非词法分析中解析的token。 ()表示优先级 []表示可选 {}表示重复至少...
  • 或者调研语法分析器的自动生成工具YACC的功能与工作原理,使用YACC生成一个自底向上的语法分析器。 二、实验内容 (1)已给 PL/0 语言文法,构造表达式部分的语法分析器。 分析对象〈算术表达式〉的 BN

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,312
精华内容 924
关键字:

编译原理编译器lr语法分析器