语法分析程序设计

实验目的展开目录

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

实验内容展开目录

某一高级程序设计语言的部分语法规则用扩充的 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 图