编译原理—语义分析（Java）

递归下降语法制导翻译

实现含多条简单赋值语句的简化语言的语义分析和中间代码生成。

测试样例

begin
a:=2; b:=4;
c:=c-1;
area:=3.14*a*a;
s:=2*3.1416*r*(h+r);
end
#

词法分析

public class analyzer {

    public static List<String> llist=new ArrayList<>();
    static  Map<Integer,Integer> map=new HashMap<>();
    final static String ID = "\\p{Alpha}(\\p{Alpha}|\\d)*";
    static  int countLine=1;
    /** 整形常数 NUM >> 正则表达式*/
    final static String NUM = "\\d\\d*";

    /** token 词法单元
     * <词符号， 种别码> */
    /** 关键字 token*/

    static Map<String, Integer> TOKEN_KEYWORDS;
    /** 运算符/界符 token */
    static Map<String, Integer> TOKEN_OPERATOR_BOUNDARY;
    /** 其他单词 token*/
    static Map<String, Integer> TOKEN_ID_SUM;

    /** 文件根目录*/
    static final String ROOT_DIRECTORY = "program.txt";

    /**
     * 初始化 token 单元
     */
    public static void initToken(){//种别码创建
        TOKEN_KEYWORDS = new HashMap<String, Integer>(){//关键字
            {
                put("begin", 1);
                put("if", 2);
                put("then", 3);
                put("while", 4);
                put("do", 5);
                put("end", 6);
            }
        };

        TOKEN_OPERATOR_BOUNDARY= new HashMap<String, Integer>(){//运算符和界符
            {
                put("+", 13);
                put("-", 14);
                put("*", 15);
                put("/", 16);
                put(":", 17);
                put(":=", 18);
                put("<", 20);
                put("<>", 21);
                put("<=", 22);
                put(">", 23);
                put(">=", 24);
                put("=", 25);
                put(";", 26);
                put("(", 27);
                put(")", 28);
                put("#", 0);

            }
        };

        TOKEN_ID_SUM= new HashMap<String, Integer>(){//标识符和整型常数
            {
                put(ID, 10);
                put(NUM, 11);
            }
        };
    }

    /**
     * 读 源程序 文件
     */
    public static void ReadFile1() {
        FileInputStream fis = null;
        InputStreamReader isr = null;
        BufferedReader br = null;
        try {
            fis = new FileInputStream(ROOT_DIRECTORY);
            isr = new InputStreamReader(fis, "UTF-8"); // 转化类
            br = new BufferedReader(isr); // 装饰类
            String line;
            /** 记录 程序 行数 */

            while ((line = br.readLine()) != null) {  // 每次读取一行，分析一行
                boolean answer = lexicalAnalysis(line);
                if(answer == false){
                    System.out.printf("ERROR 编译错误=== 第 %d 行出现 词法错误 \n", countLine);
                    break;
                }
                countLine++;
            }
            System.out.printf("===词法分析完成===\n");
        } catch (Exception ex) {
            ex.printStackTrace();
        } finally {
            try {
                br.close(); // 关闭最后一个类，会将所有的底层流都关闭
            } catch (Exception ex) {
                ex.printStackTrace();
            }
        }
    }

    /** 判断key是否是其他单词*/
    private static boolean isIDOrSUM(String key){
        if (key.matches(ID) ) {
            llist.add(key);
            map.put(llist.size()-1,countLine);
            System.out.printf("(%d, %s)\n", TOKEN_ID_SUM.get(ID), key);
        }else if (key.matches(NUM)) {
            llist.add(key);
            map.put(llist.size()-1,countLine);
            System.out.printf("(%d, %s)\n", TOKEN_ID_SUM.get(NUM), key);
        }else {
            return false;
        }
        return true;
    }

    /**
     * 进行 词法分析
     * @param word 要分析的字符串
     * @return 结果
     */
    public static boolean  lexicalAnalysis(String word){

        word = word.trim(); // 去首尾空格
        String[] strings = word.split("\\p{Space}+"); // 分割字符串，保证处理的字符串没有空格
        for (String string : strings) {

            /** 3种情况：
             *      1. 关键字 == end （关键字的后面一定是空格 ）
             *      2. 运算符/ 分界符 == continue
             *      3. 其他单词 == continue
             */
            String key = "";

            for (int i = 0; i < string.length(); i++){
                String indexChar = String.valueOf(string.charAt(i)) ;
                if(i+1<string.length()){
                    if((indexChar+string.charAt(i+1)).equals("//"))
                     return true;
                }



                /** 是 运算符 或者 关键字*/
                if (TOKEN_OPERATOR_BOUNDARY.containsKey(indexChar) ||
                        TOKEN_KEYWORDS.containsKey(string.substring(i, string.length()))){

                    if (key.length() > 0) {
                        if (isIDOrSUM(key) == false) {
                            /** 词法错误 */
                            return false;
                        }
                        key = "";
                    }
                    if(TOKEN_OPERATOR_BOUNDARY.containsKey(indexChar)) {



                        /**  1. 是 运算符/分界符 */
                        key += indexChar;
                        if(i + 1 < string.length() && TOKEN_OPERATOR_BOUNDARY.containsKey(indexChar + string.charAt(i+1))){ // 运算分界符
                            key += string.charAt(++i);
                        }
                       llist.add(key);
                        map.put(llist.size()-1,countLine);
                        System.out.printf("(%d, %s)\n",TOKEN_OPERATOR_BOUNDARY.get(key),key);
                        key = "";
                    }else if(TOKEN_KEYWORDS.containsKey(key = string.substring(i, string.length()))) {
                        /** 2. 是关键字*/
                        llist.add(key);
                        map.put(llist.size()-1,countLine);
                        System.out.printf("(%d, %s)\n",TOKEN_KEYWORDS.get(key),key);
                        key = "";
                        break;
                    }
                }else {
                    /** 是其他单词*/
                    key += indexChar;
                    /** 其他单词后面是 1. 换行，2. 运算符/界符 3. 其他单词
                     */
                    if(i+1 >= string.length()){
                        if (isIDOrSUM(key) == false) {
                            /** 词法错误 */
                            return false;
                        }
                    }
                }
            }


        }

        return true;
    }

    public analyzer() {
    }

    public static void main(String[] args) {

        initToken();
        System.out.println("==词法分析程序==");
        System.out.println("从文件中读取程序");
        System.out.println("==============");

        ReadFile1(); for(String s:llist) System.out.println(s);

        System.out.println();
    }



}

语法分析

public class GrammarAnalysis {

    static char[] s = new char[100];

    static int sing;

    static int i; //用来记录数组s中的下标；
    static int error=0;




    static void P() {



            if(Objects.equals(analyzer.llist.get(i), "begin")) {

                ++i;

                S();
//处理
                if(Objects.equals(analyzer.llist.get(i), "end")) {

                    ++i;

                }else{



                    System.out.println("error!--------不是结尾符号end，"+"程序第"+analyzer.map.get(i)+"行出现语法错误");
                    error++;
                    ++i;

                }

            }else {



                System.out.println("error!--------缺少开头符号begin，"+"程序第"+analyzer.map.get(i)+"行出现语法错误");
                error++;



                S();
//处理
                if(Objects.equals(analyzer.llist.get(i), "end")) {

                    ++i;

                }else{


                    System.out.println("error!--------不是结尾符号end，"+"程序第"+analyzer.map.get(i)+"行出现语法错误");
                    error++;
                    ++i;

                }


            }



    }

    static void S() {



            A();

            if(Objects.equals(analyzer.llist.get(i), ";")) {

                ++i;

// if(s[i]!='e') {

                S1();

// }

            }else {



                System.out.println("error!-----------缺少结尾符号;"+"，程序第"+analyzer.map.get(i)+"行出现语法错误");
                error++;
                ++i;
                S1();

            }



    }

    static void S1() {



            if(!Objects.equals(analyzer.llist.get(i), "end")) {

// ++i;

                S();

            }



    }

    static void A() {



            if(i+1<analyzer.llist.size()&&Objects.equals(analyzer.llist.get(i+1), ":=")) {
                String times=analyzer.llist.get(i),data1;
                SemanticAnalysis.j=i;
                SemanticAnalysis.j+=2;
                data1 =  SemanticAnalysis.expression();//表达式
                SemanticAnalysis.memset(times,data1,"","");

                ++i;

                ++i;

                E();

                if(Objects.equals(analyzer.llist.get(i), ")") || Objects.equals(analyzer.llist.get(i), ";")) {

                    if(Objects.equals(analyzer.llist.get(i), ")")) {

                        ++i;

                    }

                }else {



                    System.out.println("error!--------不是结尾符号；或者）"+"，程序第"+analyzer.map.get(i)+"行出现语法错误");
                    error++;
                    ++i;

                }

            }else {



                System.out.println("error!---------不是赋值语句"+"，程序第"+analyzer.map.get(i)+"行出现语法错误");
                error++;
                ++i;

                ++i;

                E();

                if(Objects.equals(analyzer.llist.get(i), ")") || Objects.equals(analyzer.llist.get(i), ";")) {

                    if(Objects.equals(analyzer.llist.get(i), ")")) {

                        ++i;

                    }

                }else {



                    System.out.println("error!--------不是结尾符号；或者）"+"，程序第"+analyzer.map.get(i)+"行出现语法错误");
                    error++;
                    ++i;

                }
            }



    }

    static void E() {


            T();

            if(Objects.equals(analyzer.llist.get(i), "+") || Objects.equals(analyzer.llist.get(i), "-") || Objects.equals(analyzer.llist.get(i), ";") || Objects.equals(analyzer.llist.get(i), ")")) {

                E1();

            }else {



                System.out.println("error!-----------不是结尾符号+或者-或者；或者）"+"，程序第"+analyzer.map.get(i)+"行出现语法错误"); error++;

                E1();

            }



    }

    static void T() {



            F();

            if(Objects.equals(analyzer.llist.get(i), "+") || Objects.equals(analyzer.llist.get(i), "-") || Objects.equals(analyzer.llist.get(i), ";") || Objects.equals(analyzer.llist.get(i), ")") || Objects.equals(analyzer.llist.get(i), "*") || Objects.equals(analyzer.llist.get(i), "/")) {

                T1();

            }



    }

    static void F() {



            if(Objects.equals(analyzer.llist.get(i), "(")) {

                ++i;

                E();

            }else {


                ++i;

            }



    }

    static void T1() {



            if(Objects.equals(analyzer.llist.get(i), "*")) {

                ++i;

                F();

                T1();

            }else if(Objects.equals(analyzer.llist.get(i), "/")){

                ++i;

                F();

                T1();

            }



    }

    static void E1() {



            if(Objects.equals(analyzer.llist.get(i), "+")) {

                ++i;

                T();

                E1();

            }else if(Objects.equals(analyzer.llist.get(i), "-")){

                ++i;

                T();

                E1();

            }

        }



    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);

        System.out.println("==词法分析程序==");
        System.out.println("从文件中读取程序");
        System.out.println("==============");

        analyzer.initToken();
        analyzer.ReadFile1();


        System.out.println("语法分析中....,请稍候");

        i=0;

        sing=0;

        if(Objects.equals(analyzer.llist.get(0), "#")) System.exit(-1);




        P();

        if(Objects.equals(analyzer.llist.get(i), "#")) {



        }else {

            System.out.println("error!-------不是结尾符号#"+analyzer.llist.get(i)+i);

            error++;

        }

        System.out.println("===词法分析完成===");
        System.out.println("共检查出"+error+"个语法错误");
        System.out.println("\n===中间代码生成结果===");
        for(int i = 0;i <  SemanticAnalysis.elements.size();i++) {
            Element e =  SemanticAnalysis.elements.get(i);
            System.out.println(e.times + " = " + e.data1 + " " + e.op + " " + e.data2);
        }
    }

}

语义分析

public class SemanticAnalysis {
    static  int j=0,t=1;
    static List<Element> elements = new ArrayList<Element>();
    static void memset(String times,String data1,String op,String data2) {
        Element e = new Element(times,data1,op,data2);
        elements.add(e);
    }
    public static String expression() { // 表达式
        String times,data1,op,data2;
        data1 = term();
        while(analyzer.llist.get(j).equals("+") || analyzer.llist.get(j).equals("-")) {// 当前单词为+、－
            if(analyzer.llist.get(j).equals("+")) // +
                op = "+";
            else // -
                op = "-";
            j++;
            data2 = term();
            times = "t" + (t++);
            memset(times,data1,op,data2);
            data1 = times;
        }
        return data1;
    }

    private static String term() { // 项
        String times,data1,op,data2;
        data1 = factor();
        while(analyzer.llist.get(j).equals("*") || analyzer.llist.get(j).equals("/") ) { // 当前单词为*、/
            if(analyzer.llist.get(j).equals("*")) // *
                op = "*";
            else // /
                op = "/";
            j++;
            data2 = factor();
            times = "t" + (t++);
            memset(times,data1,op,data2);
            data1 = times;
        }
        return data1;
    }

    private static String factor() { // 因子
        String data = "";
        if(analyzer.map2.get(analyzer.llist.get(j)) == 10) { // ID

            data = analyzer.llist.get(j);
            j++;

        } else if(analyzer.map2.get(analyzer.llist.get(j)) == 11) { // NUM
            data = analyzer.llist.get(j);
            j++;
        }
        else if(analyzer.llist.get(j).equals("(")) { // 左括号
            j++;
            data = expression();
            if(analyzer.llist.get(j).equals(")"))
                j++;

        } else {
            System.out.println("Error,表达式错误");

        }
        return data;
    }

}

public class Element {
    String times;
    String data1;
    String op;
    String data2;
    Element(String times,String data1,String op,String data2) {
        this.times = times;
        this.data1 = data1;
        this.op = op;
        this.data2 = data2;
    }
}