MENU

简单的词法分析程序

November 10, 2018 • Read: 594 • 编译原理

实验目的

  • 理解词法分析在编译过程中的作用
  • 初步了解和掌握词法分析程序的实现方法和技术

实验内容

  1. 编写程序,输入一串字符,判断该字符串是否为合法标识符或合法整型常量
  2. 无符号数的算术四则运算中的各类单词的识别

输入:由无符号数、+、-、*、/、(、)构成的算术表达式
输出:对识别出的每一单词均单行输出

样例输入:8*2.5-1.0e2
样例输出
8
*
2.5

1.0e2

题目分析

第一种做法,可以首先写出算术表达式的RE,通过RE构建NFA,然后生成最小化DFA,根据DFA构建一棵Trie树。

第二种做法,直接抽象成简单的字符串处理问题,举个例子,小数点后面能跟的只有数字,如果出现了数字以外的字符,就直接报错退出;乘号后面能跟的有左括号"("、数字,如果出现这两种以外的字符,就报错退出。我用的就是这种办法,所以下面我主要讲述一下算法思路

程序实现

定义说明

首先规定一些定义:

字符:若本文中提到字符,则只是限定在0~9+*/()这些范围内

字符串:仅由0~9+*/()这七种字符任意组合构成的序列串称为字符串

last字符:如果有字符串1+(5/80)-69,now字符是9,那么last字符是6;同理,now字符是/,那么last字符是5

其他说明:本文中会见到很多d,d的含义是0-9的任一数字

last字符与now字符

依据算术表达式的规则,我们能列出last字符确定的情况下,能跟在last字符后面的now字符表。如下图所示(d表示0-9任一数字,e表示科学记数法中的e)。举个例子,假如确定last字符为d,那么除了左括号以外,所有的字符都能跟在d后面;如果确定last字符为e,那么now字符可以为d、+、-,因为可能存在1e9、1e+9、1e-9的情况
ibcbJ1.png

算法思路

以字符串15+6e9/(32*(78.5+3.0))为例,首先看一下程序最终输的结果
ibgEy8.png

输入字符串以后,首先初始化last字符为该字符串的第一个字符last = str.charAt(0),Java语言所有的下标都是从0开始,所以要获取第一个字符'1',就要取其0位置

初始化last字符后,还应该获取输入字符串的长度len = str.length(),方便后面遍历整个字符串

最后一步准备工作是将当前的last字符赋值给字符串curcur的作用后面再讲

然后应该从第2个字符开始,遍历整个字符串,并且利用now字符获取当前遍历到的字符now = str.charAt(i)(i = [1...len-1]),再次强调,下标是从0开始,所以假设一个字符串的长度为5,那么他每个字符的下标分别为0,1,2,3,4

循环体内应该判断last字符属于什么类别,数字?加号?还是减号等等,然后分别进入相应的函数,判断last字符和now字符的组合是否合法,也就是是否符合上面的那张表

还是以上面的字符串15+6e9/(32*(78.5+3.0))为例,last字符为1now字符为d,所以应该将last字符和now字符拼接在一起,很明显,他们都是数字,所以当然要拼在一起而不是拆开,因此我们将cur = cur + now,还记得我们之前初始化的时候给cur赋值为1,所以现在cur就变为了15,不光如此,我们还要更新last字符的类型,将now字符的值赋值给last字符last = now

接下来继续循环,此时now字符变为+last字符类型还是d,遇到加号,此时操作就不一样了,考虑一下,假如是一个156+28字符串,我们应该将156、+、28分别打印出来,所以如果遇到+字符,我们应该将当前的cur的值添加到一个“盒子”里,并且将now字符给cur,注意这里是用新的值将cur的值覆盖,而不是追加到cur后面

下面继续回来说例子,刚才说到遇到+字符,应该将cur的值保存到“盒子”里,然后将now字符赋值给cur,最后还要将last字符更新为now字符,因此,这部分代码就是这样

ans.add(cur);//ans就是上面提到的“盒子”
cur = now;
last = now;

现在last字符为+,所以应该进入相应的函数,因为now字符现在为6,是d类型,所以应该将cur添加到“盒子”中,然后分别更新curlast

ans.add(cur);
cur = now;
last = now

继续往后遍历,last字符为6now字符为e,他俩组合在一起就是6e,说明这是一个科学记数法,是满足算术表达式的规则的,因此cur应该在末尾追加now字符,也就是cur = cur + now,然后将last的值更新为now,也就是last = 'e'

接着继续遍历,last字符为'e',now字符为9,他俩组合组合在一起就是e9,还是一个正确的算术表达式,因此cur应该在末尾追加now字符,然后将last的值更新为now

继续遍历,last字符为9now字符为/,此时规则就和遇到+一样,应该将cur的值保存到“盒子”里,然后令cur = nowlast = now

剩下的我就不多做解释了,总体主要是根据lastnow字符表进行判断,如果满足要求,到底是将cur的值进行更新,还是进行追加这是比较重要的部分。

还有一点就是,如果出现科学记数法1e+9,总体思路还是不变的,但是如果遇到+,上面说到的思路是将前后进行拆分,这样就变成了1e+9,这明显不太对,我们需要的是1e+9这个整体,所以如果now字符是+-,需要进行一次特判,当前位置是i,判断i-2位置是不是e,如果是e,就应该将他们全部连接起来,也就是追加到cur里面,如果不是,说明就是一个普通的加(减)法表达式,并不是科学记数法,那么就将他们拆开

代码

import java.util.*;

public class Main {
    static String str, cur;
    static char last, now;
    static List<String> ans = new ArrayList<String>();

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        str = cin.next();
        cur = "" + str.charAt(0);

        if ("+".equals(cur) || "-".equals(cur) || "*".equals(cur) || "/".equals(cur) || "e".equals(cur)
                || ".".equals(cur)) {
            System.out.println("Error");
            return;
        }

        int LP = 0, RP = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(')
                LP++;
            if (str.charAt(i) == ')')
                RP++;
        }

        if (LP != RP) {
            System.out.println("Error");
            return;
        }

        last = cur.charAt(0);

        for (int i = 1; i < str.length(); i++) {
            now = str.charAt(i);

            if (Character.isDigit(last))
                num(i);
            else if (last == '+' || last == '-' || last == '*' || last == '/')
                opreator(i);
            else if (last == 'e')
                opreator_e(i);
            else if (last == '.')
                opreator_Dian(i);
            else if (last == '(')
                opreator_Left(i);
            else if (last == ')')
                opreator_Right(i);

        }
        if (ans.contains("Error")) {
            System.out.println("Error");
            return;
        }

        ans.add(cur);

        for (int i = 0; i < ans.size(); i++) {
            System.out.println(ans.get(i));
        }
        cin.close();
    }

    static void opreator_Left(int i) {
        if (Character.isDigit(now) || '(' == now) {
            ans.add("(");
            cur = "" + now;
            last = str.charAt(i);
        } else
            ans.add("Error");
    }

    static void opreator_Right(int i) {
        if ('+' == now || '-' == now || '*' == now || '/' == now || ')' == now) {
            ans.add(")");
            cur = "" + now;
            last = now;
        } else
            ans.add("Error");
    }

    static void opreator_Dian(int i) {
        if (Character.isDigit(now)) {
            cur += now;
            last = now;
        } else
            ans.add("Error");
    }

    static void opreator_e(int i) {
        if (Character.isDigit(now) || '+' == now || '-' == now) {
            cur += now;
            last = now;
        } else
            ans.add("Error");
    }

    static void opreator(int i) {
        if (('+' == last || '-' == last) && 'e' == str.charAt(i - 2)) {
            cur += now;
            last = now;
        } else if (Character.isDigit(now) || '(' == now) {
            ans.add("" + last);
            cur = "" + now;
            last = now;
        } else
            ans.add("Error");
    }

    static void num(int i) {
        if (Character.isDigit(now) || 'e' == now || '.' == now) {
            cur += now;
            last = now;
        } else if ('+' == now || '-' == now || '*' == now || '/' == now || ')' == now) {
            ans.add(cur);
            cur = "" + now;
            last = now;
        } else
            ans.add("Error");
    }
}

下面是运行效果GIF,GIF比较大,可能会有点卡
ibOHxO.gif

Archives Tip
QR Code for this page
Tipping QR Code