编译原理——语法分析程序的设计

时间:2022-02-27 17:05:37

实验目的

通过设计、编制、调试一个典型的语法分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析,进一步掌握常用的语法分析中预测分析方法。

实验内容

设计一个文法的预测分析程序,判断特定表达式的正确性。

实验要求

1、给出文法如下:
G[E]:
E->T|E+T;
T->F|T*F;
F->i|(E);

2、根据该文法构造相应的LL(1)文法及LL(1)分析表,并为该文法设计预测分析程序,利用C语言或C++语言或Java语言实现;
3、利用预测分析程序完成下列功能:
1)手工将测试的表达式写入文本文件,每个表达式写一行,用“;”表示结束;
2)读入文本文件中的表达式;
3)调用实验一中的词法分析程序搜索单词;
4)把单词送入预测分析程序,判断表达式是否正确(是否是给出文法的语言),若错误,应给出错误信息;
5)完成上述功能,有余力的同学可以进一步完成通过程序实现对非LL(1)文法到LL(1)文法的自动转换(见实验二附加资料1)。

实验环境

PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境或Eclipse集成环境
五、实验步骤
1、分析文法,将给出的文法转化为LL(1)文法;
2、学习预测分析程序的结构,设计合理的预测分析程序;
3、编写测试程序,包括表达式的读入和结果的输出;
4、测试程序运行效果,测试数据可以参考下列给出的数据。

测试数据

输入数据:
编辑一个文本文文件expression.txt,在文件中输入如下内容:

10;
1+2;
(1+2)*3+(5+6*7);
((1+2)*3+4;
1+2+3+(*4+5);
(a+b)*(c+d);
((ab3+de4)**5)+1;

正确结果:
(1)10;
输出:正确
(2)1+2;
输出:正确
(3)(1+2)*3+(5+6*7);
输出:正确
(4)((1+2)*3+4
输出:错误
(5)1+2+3+(*4+5)
输出:错误
(6)(a+b)*(c+d)
输出:正确
(7)((ab3+de4)**5)+1
输出:错误

代码

package com;

import java.util.*;

public class test2 {
    static String[] gram = {"E->TA", "A->+TA", "A->@", "T->FB", "B->*FB", "B->@", "F->P", "F->(E)"};
    static String[] followE = {")", "#"};
    static String[] followEA = {")", "#"};
    static String[] followT = {"+", ")", "#"};
    static String[] followTB = {"+", ")", "#"};
    static String[] followF = {"*", "+", ")", "#"};
    static String[] firstE = {"i", "("};
    static String[] firstEA = {"+", "@"};
    static String[] firstT = {"i", "("};
    static String[] firstTB = {"*", "@"};
    static String[] firstF = {"i", "("};
    static String[][] list = {{"", "i", "+", "*", "(", ")", "#"},
            {"E", "TA", null, null, "TA", null, null},
            {"A", null, "+TA", null, null, "@", "@"},
            {"T", "FB", null, null, "FB", null, null},
            {"B", null, "@", "*FB", null, "@", "@"},
            {"F", "i", null, null, "(E)", null, null}};

    public static void main(String[] args) throws Exception {
        String infile = "E:/expression.txt";
        String outfile = "E:/result2.txt";
        Stack<String>[] tmpword = new Stack[20];
        Stack<String>[] expression = new Stack[20];
        //初始化栈
        for (int i = 0; i < tmpword.length; i++) {
            tmpword[i] = new Stack<String>();
            expression[i] = new Stack<String>();
        }
        main.scan(infile, outfile, tmpword, expression);
        int i = 0;
        //循环输出结果
        while (tmpword[i].size() > 2) {
            String[] tmp = expression[i].toArray(new String[0]);
            printArray(tmp);
            isLL1(tmpword[i]);
            i++;
        }
    }

    //输出表达式
    public static void printArray(String[] s) {
        for (int i = 0; i < s.length; i++) {
            System.out.print(s[i]);
        }
        System.out.println();
    }

    //判断是否为LL1文法,是则输出正确,否则输出错误
    public static void isLL1(Stack<String> tmpword) {
        String[] input = tmpword.toArray(new String[0]);
        int inputCount = 0;
        Stack<String> status = new Stack<String>();
        status.push(input[inputCount++]);
        status.push("E");
        boolean flag = true;
        boolean result = true;
        while (flag) {
            if (isVt(status.peek())) {
                if (status.peek().equals(input[inputCount])) {
                    status.pop();
                    inputCount++;
                } else {
                    flag = false;
                    result = false;
                }
            } else if (status.peek().equals("#")) {
                if (status.peek().equals(input[inputCount])) flag = false;
                else {
                    flag = false;
                    result = false;
                }
            } else if (list[indexInList(status.peek(), input[inputCount])[0]][indexInList(status.peek(), input[inputCount])[1]] != null) {
                int[] a = indexInList(status.peek(), input[inputCount]);
                if (list[a[0]][a[1]].endsWith("@"))
                    status.pop();
                else {
                    status.pop();
                    for (int i = list[a[0]][a[1]].length() - 1; i >= 0; i--) {
                        status.push("" + list[a[0]][a[1]].charAt(i));
                    }
                }
            } else {
                flag = false;
                result = false;
            }
        }
        if (result)
            System.out.println("正确");
        else
            System.out.println("错误");
    }

    public static boolean isVt(String s) {
        for (int i = 1; i < list[0].length - 1; i++) {
            if (s.equals(list[0][i])) {
                return true;
            }
        }
        return false;
    }

    public static int[] indexInList(String m, String a) {
        int i = 0, j = 0;
        for (int c = 1; c < list.length; c++) {
            if (m.equals(list[c][0])) i = c;
        }
        for (int c = 1; c < list[0].length; c++) {
            if (a.equals(list[0][c])) {
                j = c;
            }
        }
        return new int[]{i, j};
    }
}
package com;

import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Stack;

public class main {
    static String[] key_word = {"main", "if", "then", "while", "do", "int", "else"};
    static String[] cal_word = {"+", "-", "*", "/", "<", ">", "{", "}", "(", ")", "[", "]", "==", "!=", "!", "=", ">=", "<=", "+=", "-=", "*=", "/=", ";"};

    public static void main(String[] args) throws Exception {
        String infile = "E:/program.txt";
        String outfile = "E:/result.txt";
        Stack[] word = new Stack[5];
        Stack[] expression = new Stack[word.length];
        for (int i = 0; i < word.length; i++) {
            word[i] = new Stack<String>();
            expression[i] = new Stack<String>();
        }
        scan(infile, outfile, word, expression);
    }

    //对源程序进行扫描
    public static void scan(String infile, String outfile, Stack<String>[] word, Stack<String>[] expression) throws Exception {
        java.io.File file = new java.io.File(infile);
        Scanner input = new Scanner(file);
        java.io.PrintWriter output = new PrintWriter(outfile);
        int count = 0;
        word[count].push("#");
        while (input.hasNext()) {
            String tmp = input.next();
            int i = 0;
            while (i < tmp.length()) {
                if (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '1') {//检查十进制数字
                    String num = "";
                    while (tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') {
                        num += tmp.charAt(i);
                        i++;
                        if (i == tmp.length()) break;
                    }
                    output.println("< " + 1 + ", " + num + ">");
                    word[count].push("i");
                    expression[count].push(num);
                }

                if (i + 2 < tmp.length())// 检查十六进制数字
                    if (tmp.charAt(i) == '0' && tmp.charAt(i + 1) == 'x') {
                        i += 2;
                        String num = "";
                        while ((tmp.charAt(i) <= '9' && tmp.charAt(i) >= '0') || (tmp.charAt(i) <= 'f' && tmp.charAt(i) >= 'a')) {
                            num += tmp.charAt(i);
                            i++;
                            if (i == tmp.length()) break;
                        }
                        output.println("< " + 3 + ", " + num + ">");
                        word[count].push("i");
                        expression[count].push(num);
                    }

                if (i + 1 < tmp.length())// 检查八进制数字
                    if (tmp.charAt(i) == '0') {
                        i++;
                        String num = "";
                        while (tmp.charAt(i) <= '7' && tmp.charAt(i) >= '0') {
                            num += tmp.charAt(i);
                            i++;
                            if (i == tmp.length()) break;
                        }
                        output.println("< " + 2 + ", " + num + ">");
                        word[count].push("i");
                        expression[count].push(num);
                    }

                // 检查关键字和变量
                if (i < tmp.length()) {
                    if (i < tmp.length() && tmp.charAt(i) >= 'a' && tmp.charAt(i) <= 'z') {
                        String tmp_word = "";
                        while (tmp.charAt(i) >= 'a' && tmp.charAt(i) <= 'z') {
                            tmp_word += tmp.charAt(i);
                            i++;
                            if (i == tmp.length()) break;
                        }
                        boolean is_keyword = false;
                        for (int j = 0; j < key_word.length; j++) {
                            if (tmp_word.equals(key_word[j])) {
                                output.println("< " + key_word[j] + ", " + "->");
                                word[count].push(key_word[j]);
                                expression[count].push(key_word[j]);
                                is_keyword = true;
                                break;
                            }
                        }
                        if (!is_keyword) {
                            output.println("< " + 0 + ", " + tmp_word + ">");
                            word[count].push("i");
                            expression[count].push(tmp_word);
                        }
                    }
                }
                // 检查运算符以及';'
                if (i < tmp.length()) {
                    if (i + 1 < tmp.length()) {
                        if (tmp.charAt(i + 1) == '=') {
                            for (int j = 0; j < cal_word.length; j++) {
                                if (cal_word[j].equals("" + tmp.charAt(i) + tmp.charAt(i + 1))) {
                                    output.println("< " + cal_word[j] + " ," + "->");
                                    word[count].push(cal_word[j]);
                                    expression[count].push("-");
                                    if (word[count].peek() == ";") {
                                        word[count].pop();
                                        word[count].push("#");
                                        count++;
                                        word[count].push("#");
                                    }
                                    i += 2;
                                    break;
                                }
                            }
                        }
                    }
                    for (int j = 0; j < cal_word.length; j++) {
                        if (cal_word[j].equals("" + tmp.charAt(i))) {
                            output.println("< " + cal_word[j] + ", " + "->");
                            word[count].push(cal_word[j]);
                            expression[count].push(cal_word[j]);
                            if (word[count].peek() == ";") {
                                word[count].pop();
                                word[count].push("#");
                                count++;
                                word[count].push("#");
                            }
                            i++;
                            break;
                        }
                    }
                }
            }
        }
        input.close();
        output.close();
    }
}

编译原理——语法分析程序的设计