语法分析器的功能是输入源程序输出单词符号(单词种别,单词自身值)。

实现思路:首先构造DFA,然后逐个读取文件中的字符,让该字符作为DFA的输入,让该DFA输出相应的单词符号(Token)。

构造每种单词类型的DFA,然后再将所有类型的DFA结合起来,如下图所示(如果不懂如何构造DFA可以先看正则表达式这篇文章)

再根据转换图构造转换表,值得注意的是,一般来说,上图中各个终止状态也相当于开始状态,例如状态3表示识别标识符,如果其遇到等号,那么就可以进入状态6。但也不是所有的终态都是如此,例如状态1识别0后如果遇上数字1的话,那么就是词法错误了,在词法分析阶段我们只考虑词法错误,不考虑语法错误,例如状态1是可以遇到等号的,虽然等号左边不能是常数,但这是语法错误,不是词法错误,所以在阶段状态1下的数字0是可以遇到等号的。

0 1...9 a...z或A...Z或_ ; : = ¬ + * ( ) < > # ~ \t,\n,空格
0 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
1 Ø Ø Ø {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
2 {2} {2} Ø {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
3 {3} {3} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
4 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
5 Ø Ø Ø Ø Ø {6} Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø {0}
6 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
7 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
8 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
9 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
10 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
11 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
12 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
13 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
14 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
15 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
16 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}
17 Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø Ø {18} {0}
18 {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} Ø {0}

有了转换表就可以根据转换表写对应的代码啦,首先是根据输入的字符确定下一个状态的方法

/**
     * 根据输入的字符获取下一个状态
     *
     * @param symbol 输入的字符
     * @return 状态
     */
    public static int getNextStatus(char symbol) {
        if (symbol == '\n' || symbol == '\t' || symbol == ' ') {
            return 0;
        } else if (symbol == '0') {
            return 1;
        } else if (symbol >= '1' && symbol <= '9') {
            return 2;
        } else if (symbol == '_' || (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) {
            return 3;
        } else if (symbol == ';') {
            return 4;
        } else if (symbol == ':') {
            return 5;
        } else if (symbol == '=') {
            return 6;
        } else if (symbol == '¬') {
            return 7;
        } else if (symbol == '∧') {
            return 8;
        } else if (symbol == '∨') {
            return 9;
        } else if (symbol == '+') {
            return 10;
        } else if (symbol == '*') {
            return 11;
        } else if (symbol == '(') {
            return 12;
        } else if (symbol == ')') {
            return 13;
        } else if (symbol == '<') {
            return 14;
        } else if (symbol == '>') {
            return 15;
        } else if (symbol == '#') {
            return 17;
        } else if (symbol == '~') {
            return 18;
        }
        return -1;
    }

根据当前状态识别token的方法

    /**
     * 根据当前的状态以及value保存识别出来的token
     *
     * @param currentStatus 当前DFA所处的状态
     */
    public static void addToken(int currentStatus) {
        String v = value;
        if (currentStatus == 1) {//匹配整常量0
            //tokens.put(Const.intconst, v);
            System.out.println("<" + Const.intconst + "," + v + ">");
        } else if (currentStatus == 2) {//匹配整数
            //tokens.put(Const.intconst, v);
            System.out.println("<" + Const.intconst + "," + v + ">");
        } else if (currentStatus == 3) {//匹配标识符,如果是关键字则用关键字对应的种别码,否则使用变量种别码,其第二个参数值为value
            boolean flag = false;//表示是否为关键词的标志
            for (String s : Const.keywords) {
                if (s.equals(v)) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                //tokens.put(Const.map.get(v), null);
                System.out.println("<" + Const.map.get(v) + "," + "->");
            } else {
                //tokens.put(Const.ident, v);
                System.out.println("<" + Const.ident + "," + v + ">");
            }
        } else if (currentStatus == 4) {//匹配分号
            //tokens.put(Const.semicolon, null);
            System.out.println("<" + Const.semicolon + "," + "->");
        } else if (currentStatus == 6) {//如果是状态6则有三种情况,:=、<=和>=,只需要通过value值区分
            //tokens.put(Const.rop, v);
            System.out.println("<" + Const.semicolon + "," + v + ">");
        } else if (currentStatus == 7) {//匹配not
            //tokens.put(Const.op_not, null);
            System.out.println("<" + Const.op_not + "," + "->");
        } else if (currentStatus == 8) {//匹配and
            //tokens.put(Const.op_and, null);
            System.out.println("<" + Const.op_and + "," + "->");
        } else if (currentStatus == 9) {//匹配or
            //tokens.put(Const.op_or, null);
            System.out.println("<" + Const.op_or + "," + "->");
        } else if (currentStatus == 10) {//匹配+
            //tokens.put(Const.plus, null);
            System.out.println("<" + Const.plus + "," + "->");
        } else if (currentStatus == 11) {//匹配*
            //tokens.put(Const.times, null);
            System.out.println("<" + Const.times + "," + "->");
        } else if (currentStatus == 12) {//匹配左括号
            //tokens.put(Const.lparent, null);
            System.out.println("<" + Const.lparent + "," + "->");
        } else if (currentStatus == 13) {//匹配右括号
            //tokens.put(Const.rparent, null);
            System.out.println("<" + Const.rparent + "," + "->");
        } else if (currentStatus == 14) {//匹配小于号
            //tokens.put(Const.rop, v);
            System.out.println("<" + Const.rop + "," + "->");
        } else if (currentStatus == 15) {//匹配大于号
            //tokens.put(Const.rop, v);
            System.out.println("<" + Const.rop + "," + "->");
        } else if (currentStatus == 16) {//匹配<>
            System.out.println("<" + Const.rop + "," + "->");
            //tokens.put(Const.rop, v);
        } else if (currentStatus == 18) {//匹配#~
            //tokens.put(Const.jinghao, v);
            System.out.println("<" + Const.jinghao + "," + v + ">");
        }
        setValue("");
    }

这个是主要的方法,根据DFA状态表写条件语句

  /**
     * 根据当前状态以及输入的字符确定下一个状态
     *
     * @param status DFA所处的状态
     * @param symbol 输入的字符
     * @return 下一个状态
     * @throws Exception 如果出现词法错误则抛异常
     */
    public static int move(int status, char symbol) throws Exception {
        int nextStatus = getNextStatus(symbol);
        if (nextStatus == -1) {//非法字符
            throw new Exception("Illegal character!");
        } else if (nextStatus == 18) {//如果下一个符号是~,则需要前一个符号是#,否则词法错误
            if (status != 17) {
                throw new Exception("~ and # need to use together!");
            }
        } else if (nextStatus == 6) {//如果等号前面不是: < >三者之一则表示词法错误
            if (status != 5 && status != 14 && status != 15) {
                throw new Exception("The front of = need to be :,< or >");
            }
        } else if (nextStatus == 0) {//如果下一个状态是0则标明需要将当前value识别为token
            if (status != 0) {
                addToken(status);
                return 0;
            }
        } else if (nextStatus == 4) {//如果下一个是分号,则需要识别当前单词为token
            addToken(status);
            return nextStatus;
        }
        if (status == 0) {
            if (nextStatus != 0) {
                setValue(getValue() + symbol);
            } else {
                setValue("");
            }
        } else if (status == 4) {
            addToken(status);
            setValue(getValue() + symbol);
        } else if (status == 5) {
            if (nextStatus != 6) {//如果下一个字符不是等号则表示词法错误
                throw new Exception(": need to be followed by =");
            }
            setValue(getValue() + symbol);//如果是等于号则设置value值然会nextStatus即可
        } else if (status == 17) {//如果下一个字符不是~则报错
            if (nextStatus != 18) {
                throw new Exception("# need to be followed by ~");
            }
            setValue(getValue() + symbol);
        } else if (status == 1) {//如果是0的话,则下一个输入的不能是字母或者数字,如果是其他符号的话就可以
            if (nextStatus >= 1 && nextStatus <= 3) {
                throw new Exception("0 can't be followed by a number or letter");
            }
            addToken(status);//如果是其他合法符号的话则添加token
            setValue(getValue() + symbol);
        } else if (status == 2) {//表示大于0的数,其后不能跟字母,可以跟数字或者其他符号
            if (nextStatus == 1 || nextStatus == 2) {//数字可以,设置value然后返回状态2
                setValue(getValue() + symbol);
                return 2;
            } else if (nextStatus == 3) {//字母则需要报错
                throw new Exception("Values can't followed by letters");
            } else {//其他符号:需要添加数值到token并且清空value然后跳转到相应的状态
                addToken(status);
                setValue(getValue() + symbol);//添加到token
            }
        } else if (status == 3) {//如果是识别标识符的话那就需要看下一个符号是什么,如果还是数字或者字母或者下划线则只需要设置value即可,如果是其他符号,例如=就需要将当前的value添加到token后将value清空,然后返回下一个状态
            if (nextStatus >= 1 && nextStatus <= 3) {//数字或者字母,将当前值保存,并返回状态3
                setValue(getValue() + symbol);
                return 3;
            } else {//添加token
                addToken(status);
                setValue(getValue() + symbol);
            }
        } else if (status >= 6 && status <= 13) {//设置value,添加到token
            addToken(status);
            setValue(getValue() + symbol);
        } else if (status == 14) {//最长匹配原则,如果小于号后面跟着等于号或者大于号就继续匹配
            if (nextStatus == 15) {//由于大于号对应状态15,而<>对应状态16,所以需要返回状态16,为什么这样做呢?因为这番子方便,不然如果输入<>=的话根据最长匹配原则就会三个都匹配,也就是有错
                setValue(getValue() + symbol);
                return 16;
            } else if (nextStatus == 6) {
                setValue(getValue() + symbol);
                return nextStatus;
            } else {
                addToken(status);
                setValue(getValue() + symbol);
            }
        } else if (status == 15) {//如果是大于号,根据最长匹配原则,如果其后跟着等于号则需要匹配成>=,其他符号的话则添加token
            if (nextStatus != 6) {
                addToken(status);
            }
            setValue(getValue() + symbol);
        } else if (status == 16) {//匹配<>,其后可以跟任何符号
            addToken(status);
            setValue(getValue() + symbol);
        }
        return nextStatus;
    }

实验指导书上已经列出了单词内部定义,我们需要将这些定义写成代码形式:

/**
 * @Author HyLee
 * @Date 2020/5/12 22:27
 * @Description
 */
public class Const {
    //定义种别码
    public static int sy_if = 0;
    public static int sy_then = 1;
    public static int sy_else = 2;
    public static int sy_while = 3;
    public static int sy_begin = 4;
    public static int sy_do = 5;
    public static int sy_end = 6;
    public static int a = 7;
    public static int semicolon = 8;
    public static int e = 9;
    public static int jinghao = 10;
    public static int S = 11;
    public static int L = 12;
    public static int tempsy = 13;
    public static int EA = 14;
    public static int EO = 19;
    public static int plus = 34;
    public static int times = 36;
    public static int becomes = 38;
    public static int op_and = 39;
    public static int op_or = 40;
    public static int op_not = 41;
    public static int rop = 42;
    public static int lparent = 48;
    public static int rparent = 49;
    public static int ident = 56;
    public static int intconst = 57;
    public static List<String> keywords = new ArrayList<>();
    public static Map<String, Integer> map = new HashMap<>();//存放符号-种别码映射关系的集合

    public static void init() {
        keywords.add("if");
        keywords.add("then");
        keywords.add("else");
        keywords.add("while");
        keywords.add("begin");
        keywords.add("do");
        keywords.add("end");
        map.put("if", sy_if);
        map.put("then", sy_then);
        map.put("else", sy_else);
        map.put("while", sy_while);
        map.put("begin", sy_begin);
        map.put("do", sy_do);
        map.put("end", sy_end);
        map.put("A", a);
        map.put(":", semicolon);
        map.put("E", e);
        map.put("#", jinghao);
        map.put("S", S);
        map.put("L", L);
        map.put("tempsy", tempsy);
        map.put("∧", EA);
        map.put("∨", EO);
        map.put("+", plus);
        map.put("*", times);
        map.put(":=", becomes);
        map.put("and", op_and);
        map.put("or", op_or);
        map.put("not", op_not);
        map.put("rop", rop);
        map.put("lparent", lparent);
        map.put("rparent", rparent);
        map.put("ident", ident);
        map.put("intconst", intconst);
    }
}

最后在主类中调用读入文件然后输入初始状态以及字符即可

package com.hylee.lexical;

import java.io.BufferedReader;
import java.io.FileReader;

/**
 * @Author HyLee
 * @Date 2020/5/12 18:25
 * @Description
 */
public class Main {
    public static void main(String args[]) throws Exception {
        Const.init();
        BufferedReader reader = new BufferedReader(new FileReader("F:\\Documents\\develop\\java experiment\\Lexical Analysis\\src\\com\\hylee\\lexical\\source.hylee"));
        String temp = null;
        int status = 0;
        StringBuilder content = new StringBuilder();
        while ((temp = reader.readLine()) != null) {
            content.append(temp);
        }
        temp = content.toString();
        int length = temp.length();
        for (int i = 0; i < length; i++) {
            status = DFA.move(status, temp.charAt(i));
        }
    }
}

实验结果:

完整代码可以关注微信公众号小海电脑回复词法分析实验获取。

最后修改日期:2020年5月23日

留言

撰写回覆或留言