编译原理实验1——词法分析器的Java实现

亦凉 2023-10-09 19:37 18阅读 0赞

## ![92f2cfeec04042c2b47fac98df9044d6.png][] ##

## **一、 实验目的** ##

设计并实现一个PL/0语言(或其它语言的子集,如C语言的子集)的词法分析程序，加深对词法分析原理的理解。

## **二、实验原理** ##

词法分析是从左向右扫描每行源程序的符号，拼成单词，换成统一的机内表示形式——TOKEN字，送给语法分析程序。

TOKEN字是一个二元式：（单词种别码，自身值）。PL/0语言单词的种别码用整数表示，可参考教材或自行设定；单词自身值按如下规则给出：

1 标识符的自身值是它在符号表的入口地址。

1.  常数的自身值是常数本身。
2.  关键字和界限符的自身值为本身。

## **三、 实验步骤与要求** ##

1、要求根据状态图，设计实现词法分析器。

2、编制程序,此程序应具有如下功能:

1.  输入:字符串(待进行词法分析的源程序),可从文件读或入从键盘直接输入

输出:由(**种别码,自身值**)所组成的二元组序列，二元组序列可保存到一个文件中，也可直接屏幕显示。

单词的种别码是语法分析需要的信息，可用整数编码表示，例如：标识符的种别码为1，常数为2，保留字为3，运算符为4，界符为5。

单词的自身值是编译其它阶段需要的信息，标识符的自身值是标识符在符号表入口，其他类型单词的自身值是其本身。

可以参考下面的示例:

输入字符串if i>=15 then x := y;

输出：

（3，‘if’）// i的符号表入口为0
    （4，‘>=’）
    （2，‘15’）
    （3，‘then’）
    （1，1） // x的符号表的入口为1
    （4，‘：=’）
    （1，2)   // y的符号表的入口为2
    （5，‘；’）

1.  功能:

1.  滤空格
2.  识别保留字：if then else while do 等
3.  识别标识符：<字母>(<字母>|<数字>)\*
4.  识别整数数：0 | (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)\*
5.  识别典型的运算符和分隔符，例如 + - \* / > >= <= ( ) ；

1.  具有一定的错误处理功能。例如，能检查出程序语言的字符集以外的非法字符。

3、可以使用开发工具，自行设计界面，可以自行确定一些附加功能。

4、请指导教师检查程序和运行结果，评定成绩。

评定级别分优秀、良好、合格、不合格。第一次验收中如果存在问题，老师指出后允许改进，改进后再重新验收。成绩以最后一次的验收为准。

5、撰写并上交实验报告。

必须提交实验报告，通过此环节训练实验总结与分析的能力。最后参考实验报告给出实验成绩。

## **四、上机报告内容** ##

**设计思路：**

本次实验采用 Java 语言编写，词法分析器采用了模块化的设计思路，通过多个正则表达式模式进行词法元素匹配。程序首先定义了一系列正则表达式模式，包括匹配数字、字母和数字、运算符、界符等。此外，还定义了一个关键字集合，用于识别C语言关键字。

词法分析器的主要功能是通过lex方法对输入的源代码字符串进行分析。这个方法采用了迭代的方式，不断从输入字符串中匹配并提取词法元素。为了避免死循环，设置了一个限制循环次数的条件，当匹配次数超过100次仍未找到匹配项时，将其识别为非法字符。分析过程中，根据匹配到的词法元素类型将其封装为Token对象并添加到结果列表中。

程序最后还包括了一个displayTokens方法，用于输出分析结果。这个方法遍历词法元素列表，根据不同类型的Token对象进行格式化输出。

**实验截图：**

测试案例：

if i>=15 then  x := y;

![263c513983e9470ab266aa53e2bcc1e4.png][]

**代码：**

> 仅供参考~

public class Lexer {
        // 存储分析结果的列表
        private static List<Token> tokens = new ArrayList<>();
        private static int count = 0; // 标识符记录器，每次自增 1
        // C 语言关键字集合
        private static Set<String> keywords = Set.of("auto", "break", "case", "char", "const", "continue", "default", "do", "double", "else", "enum", "extern", "float", "for", "goto", "if", "int", "long", "register", "return", "short", "signed", "sizeof", "static", "struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while", "then");
        private static Map<String, Integer> typeCodes = Map.of("标识符", 1, "常数", 2, "保留字", 3, "运算符", 4, "界符", 5, "非法字符", 6);
        // regex 字符串表达式，识别数字
        private static Pattern patternNumber = Pattern.compile("\\d+");
        // regex 字符串表达式，识别字母和数字
        private static Pattern patternLetterNumber = Pattern.compile("^[a-zA-Z_][a-zA-Z0-9_]*");
        // regex 字符串表达式，识别C语言中的所有操作符
        private static Pattern patternSymbol = Pattern.compile("\\{\\}|\\{|\\}|~|==|>=|<=|'|=|\"|&&|\\^|\\(\\)|\\(|\\)|\\|\\||:=|[+\\-*/><]");
        // regex 字符串表达式，识别界符;
        private static Pattern patternDelimiter = Pattern.compile(";");
    
        public static void main(String[] args) {
            String  input   = "if i>=15 then  x := y;";
            Scanner scanner = new Scanner(input).useDelimiter("\\s+");
            // 拆分空格，对每一项进行词法分析
            while (scanner.hasNext()) {
                String next = scanner.next();
                lex(next);
            }
            displayTokens(); // 输出结果
        }
    
        /**
         * 词法分析，结果存入 tokens
         *
         * @param msg 输入字符串
         */
        public static void lex(String msg) {
            StringBuilder sb    = new StringBuilder(msg);
            int           times = 0;
            // 当输入字符串非空时，持续运行
            while (sb.length() > 0) {
                matchAndAddToken(sb, patternLetterNumber, typeCodes.get("标识符"));
                matchAndAddToken(sb, patternSymbol, typeCodes.get("运算符"));
                matchAndAddToken(sb, patternNumber, typeCodes.get("常数"));
                matchAndAddToken(sb, patternDelimiter, typeCodes.get("界符"));
                // 100 次循环还没匹配到，说明有非法字符
                if (times++ > 100) {
                    String match = sb.substring(0, 1);
                    sb.delete(0, 1);
                    tokens.add(new Token(typeCodes.get("非法字符"), match));
                }
            }
        }
    
        /**
         * 尝试匹配给定的正则表达式，如果匹配成功，添加到 tokens 列表并返回 true，否则返回 false
         *
         * @param sb       输入字符串
         * @param pattern  正则表达式
         * @param typeCode 类型码
         * @return 是否匹配成功
         */
        private static boolean matchAndAddToken(StringBuilder sb, Pattern pattern, int typeCode) {
            Matcher matcher = pattern.matcher(sb.toString());
            if (matcher.find()) {
                String match = matcher.group();
                sb.delete(0, match.length());
                // 判断是不是关键字
                if (typeCode == typeCodes.get("标识符") && keywords.contains(match)) {
                    tokens.add(new Token(typeCodes.get("保留字"), match));
                } else if (typeCode == typeCodes.get("标识符")) {
                    tokens.add(new Token(typeCodes.get("标识符"), count, "//" + match + "符号表的入口为" + count++));
                }else {
                        tokens.add(new Token(typeCode, match));
                    }
                return true;
            }
            return false;
        }
    
        // 输出结果
        public static void displayTokens() {
            for (Token token : tokens) {
                if (token.msg != null) {
                    System.out.println("(" + token.typeCode + ", " + token.value + ")  " + token.msg);
                } else {
                    System.out.println("(" + token.typeCode + ", '" + token.value + "')");
                }
            }
        }
    
        /**
         * Token 类
         * typeCode: 类型码
         * value: 值
         */
        static class Token {
            int typeCode;
            Object value;
            String msg;
    
            public Token(int typeCode, Object value) {
                this.typeCode = typeCode;
                this.value = value;
            }
            public Token(int typeCode, Object value, String msg) {
                this.typeCode = typeCode;
                this.value = value;
                this.msg = msg;
            }
        }
    }

## **五****、实验总结与收获** ##

本次实验主要目的是设计并实现一个PL/0语言（或其它语言的子集）的词法分析程序，以加深对词法分析原理的理解。实验采用Java语言编写，通过多个正则表达式模式进行词法元素匹配，实现了识别保留字、标识符、常数、运算符、界符等功能，并具有一定的错误处理功能。

通过本次实验，我们不仅深入理解了词法分析原理，还学习了Java语言的正则表达式和模块化设计思路。通过对源程序的扫描和分析，词法分析器可以为后续的语法分析和代码生成提供基础支持，为编译器的整个过程打下坚实的基础。

在实验中，我们发现了一些需要注意的问题，如需要考虑不同语言的差异，合理处理各种异常情况等。通过克服这些问题，我们不仅更加熟悉了词法分析的实现过程，还提高了自己的编程能力和代码质量。

总的来说，本次实验不仅加深了我们对词法分析原理的理解，还提高了我们的编程能力和代码质量。我们将继续努力学习编译原理相关知识，为以后的软件开发工作打下更加坚实的基础。

[92f2cfeec04042c2b47fac98df9044d6.png]: https://img-blog.csdnimg.cn/92f2cfeec04042c2b47fac98df9044d6.png
[263c513983e9470ab266aa53e2bcc1e4.png]: https://img-blog.csdnimg.cn/263c513983e9470ab266aa53e2bcc1e4.png