语法分析程序设计

实验目的

• 理解语法分析在编译程序中的作用
• 在词法分析的基础上进行语法检查和结构分析
• 掌握语法分析程序的实现方法和技术

实验内容

某一高级程序设计语言的部分语法规则用扩充的BNF表示如下：

<程序> -> begin<语句串>end
<语句串> -> <语句>{;<语句>}
<语句> -> <赋值语句>
<赋值语句> -> ID=<表达式>
<表达式> -> <项>{+<项> | -<项>}
<项> -> <因子>{*<因子> | /<因子>}
<因子> -> ID | NUM | (<表达式>)

要求：输入单词串，以“#”结束，如果是文法正确的句子，则输出“success”，否则输出“error”。

样例输入：

begin a=9; x=2*3; b=a+x end #

样例输出：
success！

样例输入：

x=a+b*c end #

样例输出：
error！

题目分析

首先规定一些单词记号

因为语法中存在一些冗余部分，所以首先对语法进行改写，将<赋值语句>直接删除

<程序> -> begin<语句串>end
<语句串> -> <语句>{;<语句>}
<语句> -> ID=<表达式>
<表达式> -> <项>{+<项> | -<项>}
<项> -> <因子>{*<因子> | /<因子>}
<因子> -> ID | NUM | (<表达式>)

说一下算法思路，我主要采用的是递归下降LL(1)分析法，打个比方，假设有语法

S -> aAb
A -> cBd
B -> e

那么我直接将其中所有的非终结符定义为函数，看下面的伪代码

void S() {
    if(开头是a) {
        A()
        if(结尾是b)
            print Success!
    }
}
void A() {
    if(当前字符是c) {
        B()
        if(当前字符不是d)
            print Error!
    }
}
void B() {
    if(当前不是e)
        print Error!
}

假设有一个句子acedb，现在利用上面的伪代码判断是不是语法的句子

首先扫描到a，则进入A()函数，因为当前字符是c，所以进入B()函数，因为当前字符是e，所以不会报错，然后B()函数执行完，就会回到A()函数中判断是不是d的那一行，因为是d，所以不会报错。此时A()函数也执行完了，就会回到S()函数中判断结尾是不是b的那一行，因为结尾是b，所以最终打印Success!

所以之前设置的单词记号表就有用了，比方说遇到+，不需要判断当前单词是不是+，只需要判断当前的符号值syn是不是13即可

对于这道题的语法规则来说，大致代码如下：

void parse() { //程序
    if(syn == 1) { //begin
        scanner(); //扫描当前单词串，后面会用到非常多
        statementString(); //进入语句串函数
        if(syn == 2) {//end
            scanner();
            if(syn == 0) //#
                print Success!
        }
    }
}
void statementString() { //语句串
    statement(); //进入语句函数
    while(syn == 26) {//分号
        scanner();
        statement();
    }
}
void statement() { //语句
    if(syn == 10) { //ID
        scanner();
        if(syn == 18) { //等于号
            scanner();
            expression(); //进入表达式函数
        }
    }
}
void expression() { //表达式
    term(); //进入项函数
    while(syn == 13 || syn == 14) { //+或-
        scanner();
        term();
    }
}
void term() { //项
    factor(); //进入因子函数
    while(syn == 15 || syn == 16) { //*或/
        scanner();
        factor();
    }
}
void factor() { //因子
    if(syn == 10 || syn == 11) //ID或NUM
        scanner();
    else if(syn == 27) { //左括号
        scanner();
        expression(); //进入表达式函数
        if(syn == 28)
            scanner();
        else
            print Error
    } else 
        print Error
}

为了解决出现错误打印Error后继续打印Success的问题，可以设置一个全局变量flag，boolean类型，初始值设为true，如果在执行过程从发现错误，就将其设置为false。在最终判断最后一个字符是不是#的情况下，还要判断flag是不是true，只有同时满足最后一个单词是#，并且flag等于true，才会打印Success。

还有最后一个问题，仔细观察样例2会发现，并不是所有的赋值语句都成立，如果在赋值语句的右边，出现了从来未定义过的变量，也会报错。这一点也很好解决，首先定义一个容器，因为程序总是从前往后扫描的，所以如果一旦出现=左边是ID，就将其放到容器中。如果=右边出现ID，就判断这个ID在不在容器中，如果不在，说明没有定义过，就报错；如果在，就继续执行

完整代码

import java.util.*;

public class Main {
    static Map<String, Integer> map = new TreeMap<String, Integer>();
    static List<Character> list = new ArrayList<Character>();
    static List<String> ID = new ArrayList<String>();
    static StringBuffer str;
    static char now;
    static int syn, p;
    static boolean flag = true;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String code = cin.nextLine();
        for(int i = 0;i < code.length();i++)
            list.add(code.charAt(i));
        map.put("begin",1);
        map.put("end", 2);
        scanner();
        parser();
        cin.close();
    }

    private static void scanner() {
        str = new StringBuffer("");
        now = list.get(p++);
        while (now == ' ')
            now = list.get(p++);
        if ((now >= 65 && now <= 90) || (now >= 97 && now <= 122)) { // 字母开头
            while ((now >= 48 && now < 57) || (now >= 65 && now <= 90) || (now >= 97 && now <= 122) || now == 95) { // 字母数字
                str.append(now);
                now = list.get(p++);
                if (map.containsKey(str.toString().trim()) && (now == ' ' || now == '\n')) {
                    syn = map.get(str.toString().trim());
                    return;
                }
            }
            p--;
            syn = 10; // 用户自定义变量
        } else if (now >= 48 && now <= 57) { // 数字开头
            while ((now >= 48 && now <= 57) || now == 46) {
                now = list.get(p++);
            }
            p--;
            syn = 11;//常量
        } else {
            switch (now) {
            case '+': {
                str.replace(0, 0, "" + now);
                syn = 13;
                break;
            }
            case '-': {
                str.replace(0, 0, "" + now);
                syn = 14;
                break;
            }
            case '*': {
                str.replace(0, 0, "" + now);
                syn = 15;
                break;
            }
            case '/': {
                str.replace(0, 0, "" + now);
                syn = 16;
                break;
            }
            case ';': {
                syn = 26;
                str.replace(0, 0, "" + now);
                break;
            }
            case '(': {
                syn = 27;
                str.replace(0, 0, "" + now);
                break;
            }
            case ')': {
                syn = 28;
                str.replace(0, 0, "" + now);
                break;
            }
            case '=': {
                str.append(now);
                syn = 18;
                break;
            }
            case '#': {
                syn = 0;
                str.replace(0, 0, "" + now);
                break;
            }
            default:
                syn = -1;
            }
        }
    }    
    
    private static void parser() {
        if(syn == 1) { // 当前单词为begin
            scanner();
            statementString();
            if(syn == 2) { // 当前单词为end
                scanner();
                if(syn == 0 && flag) // 当前单词为#
                    System.out.println("Success!");
            } else {
                if(flag)
                    System.out.println("Error,Miss end!");
                flag = false;
            }
        } else {
            System.out.println("Error,Miss begin!");
            flag = false;
        }
    }

    private static void statementString() { // 语句串
        statement();
        while(syn == 26) { // 分号
            scanner();
            statement();
        }
    }

    private static void statement() { // 语句
        if(syn == 10) {// ID
            ID.add(str.toString());
            scanner();
            if(syn == 18) { // 等于号
                scanner();
                expression();
            } else {
                System.out.println("Error,赋值符号错误！");
                flag = false;
            }
        } else {
            System.out.println("Error,语句错误！");
            flag = false;
        }
    }

    private static void expression() { // 表达式
        term();
        while(syn == 13 || syn == 14) {// 当前单词为+、－
            scanner();
            term();
        }
    }

    private static void term() { // 项
        factor();
        while(syn == 15 || syn == 16) { // 当前单词为*、/
            scanner();
            factor();
        }
    }

    private static void factor() { // 因子
        if(syn == 10) { // ID
            if(!ID.contains(str.toString())) {
                System.out.println("Error,存在未定义变量" + str.toString());
                flag = false;
            } else
                scanner();
        } else if(syn == 11) // NUM
            scanner();
        else if(syn == 27) { // 左括号
            scanner();
            expression();
            if(syn == 28)
                scanner();
            else {
                System.out.println("Error,')'错误!");
                flag = false;
            }
        } else {
            System.out.println("Error,表达式错误");
            flag = false;
        }
    }
}

下面是程序运行的GIF图