词法分析器

本文最后更新于：2 年前

接下来三篇博客将回顾编译原理课程的大作业（编译一个语义极简的画图语言），分别从词法、语法、语义三部分进行梳理。

绘图语言介绍

<1> 实现简单函数绘图的语句

循环绘图（FOR-DRAW）
比例设置（SCALE）
角度旋转（ROT）
坐标平移（ORIGIN）
注释（– 或 //）

<2> 屏幕（窗口）的坐标系

左上角为原点
x方向从左向右增长
y方向从上到下增长(与一般的坐标系方向相反)

<3> 函数绘图源程序举例
————— 函数f(t)=t的图形 —————
origin is (100, 300); – 设置原点的偏移量
rot is 0; – 设置旋转角度(不旋转)
scale is (1, 1); – 设置横坐标和纵坐标的比例
for T from 0 to 200 step 1 draw (t, 0);
– 横坐标的轨迹（纵坐标为0）
for T from 0 to 150 step 1 draw (0, -t);
– 纵坐标的轨迹（横坐标为0）
for T from 0 to 120 step 1 draw (t, -t);
– 函数f(t)=t的轨迹
//默认值：
// origin is (0, 0)
// rot is 0;
// scale is (1, 1)

FOR T FROM 起点 TO 终点 STEP 步长 DRAW(横坐标, 纵坐标);

令T从起点到终点、每次改变一个步长，绘制出由(横坐标，纵坐标)所规定的点的轨迹。

FOR T FROM 0 TO 2*PI STEP PI/50 DRAW (cos(T), sin(T));

该语句的作用是令T从0到2*PI、步长 PI/50，绘制出各个点的坐标(cos(T)，sin(T))，即一个单位圆。

语句满足下述规定(原则)：
<1>各类语句可以按任意次序书写，且语句以分号结尾。源程序中的语句以它们出现的先后顺序处。
<2>ORIGIN、ROT和SCALE语句只影响其后的绘图语句，且遵循最后出现的语句有效的原则。例如，若有下述ROT语句序列： ROT IS 0.7 ；
ROT IS 1.57 ；
则随后的绘图语句将按1.57而不是0.7弧度旋转。
<3>无论ORIGIN、ROT和SCALE语句的出现顺序如何，图形的变换顺序总是：比例变换→旋转变换→平移变换
<4> 语言对大小写不敏感，例如for、For、FOR等，均被认为是同一个保留字。
<5> 语句中表达式的值均为双精度类型，旋转角度单位为弧度且为逆时针旋转，平移单位为点。

词法分析器的构造

步骤：正规式－NFA－DFA－最小DFA－编写程序－测试

三个任务

滤掉源程序中的无用成分
输出记号供语法分析器使用
识别非法输入，并将其标记为“出错记号”。

记号的组成：记号的类别和属性

本简易编译器使用java来构造
public class Token {
public String type=””; //类别
public String lexeme=””; //词义，这里是输入的字符串
public double value; //如果是常数则为常数的值，否则无意义
}

函数绘图语言中记号的分类与表示

private static final String[] Token_Type = {
“ORIGIN”, “SCALE”, “ROT”, “IS”, // 保留字（一字一码）
“TO”, “STEP”, “DRAW”, “FOR”, “FROM”, //保留字
“T”, // 参数
“SEMICO”, “L_BRACKET”, “R_BRACKET”, “COMMA”,// 分隔符
“PLUS”, “MINUS”, “MUL”, “DIV”, “POWER”, // 运算符
“FUNC”, // 函数（调用）
“CONST_ID”, // 常数
“NONTOKEN”, // 空记号（源程序结束）
“ERRTOKEN” //出错记号（非法符号）
};

正规式

letter = [a-zA-Z]
digit = [0-9]

COMMENT = “//“|”–”
WHITE_SPACE = (“ “|\t|\n)+
SEMICO = “;”
L_BRACKET = “(“
R_BRACKET = “)”
COMMA = “,”
PLUS = “+”
MINUS = “-“
MUL = ““
DIV = “/“
POWER = “**”
CONST_ID = digit+(“.” digit)?
ID = letter+
（去除注释与白空有11个正规式）

DFA

程序思路及代码

思路非常简单，单个单个读取字符，根据DFA匹配，并赋值给Token，以产生记号流给予语法分析器分析。

import java.io.*;
class Token {
    public String type="";
    public String lexeme="";
    public double value;
}

public class OutputToken {
    static Token[] tokens = new Token[1000];//开辟数组空间
    private static final String[] Token_Type = {
            "ORIGIN", "SCALE", "ROT", "IS",      // 保留字（一字一码）
            "TO", "STEP", "DRAW", "FOR", "FROM", //保留字
            "T",                  // 参数
            "SEMICO", "L_BRACKET", "R_BRACKET", "COMMA",// 分隔符
            "PLUS", "MINUS", "MUL", "DIV", "POWER",        // 运算符
            "FUNC",                  // 函数（调用）
            "CONST_ID",              // 常数
            "NONTOKEN",              // 空记号（源程序结束）
            "ERRTOKEN"              //出错记号（非法符号）
    };



    public int Cifa_Analyzer() throws IOException {

        String pathName = "/Users/leo/Desktop/test.txt";
        FileInputStream fis = new FileInputStream(pathName);
        BufferedReader br = new BufferedReader(new InputStreamReader(fis));
        String temp = "";
        String string2 = "";
        while ((temp = br.readLine()) != null) {
            string2 = string2 + temp + '\n';
        }
        char[] chars = string2.toCharArray();
//        OutputToken test=new OutputToken(string);

        for (int j = 0; j < 1000; j++) //对象需要分别初始化
        {
            tokens[j] = new Token();
        }
        int k = 0;

        for (int i = 0; i < string2.length(); ) {
            if ((chars[i] >= 65 && chars[i] <= 90) || (chars[i] <= 122 && chars[i] >= 97)) {
                tokens[k].type += "ID";
                tokens[k].lexeme = tokens[k].lexeme + chars[i];
                tokens[k].value = 0.0d;
                i++;
                while ((chars[i] >= 65 && chars[i] <= 90) || (chars[i] <= 122 && chars[i] >= 97)) {
                    tokens[k].lexeme = tokens[k].lexeme + chars[i];
                    i++;
                }
                k++;
            }   //letter
            else if (chars[i] >= 48 && chars[i] <= 57) {
                tokens[k].type = "CONST_ID";
                tokens[k].lexeme = tokens[k].lexeme + chars[i];
                i++;
                while (chars[i] >= 48 && chars[i] <= 57) {
                    tokens[k].lexeme = tokens[k].lexeme + chars[i];
                    i++;
                }
                if (chars[i] == '.') {
                    tokens[k].lexeme = tokens[k].lexeme + chars[i];
                    i++;
                } else {
                    tokens[k].value = Double.parseDouble(tokens[k].lexeme);
                    k++;
                    continue;
                }
                if (chars[i] >= 48 && chars[i] <= 57) {
                    while (chars[i] >= 48 && chars[i] <= 57) {
                        tokens[k].lexeme = tokens[k].lexeme + chars[i];
                        i++;
                    }
                    tokens[k].value = Double.parseDouble(tokens[k].lexeme);
                    k++;
                } else {
                    System.out.println(tokens[k].lexeme);
                    return 0;
                }

            }//digit

            else if (chars[i] == '*') {
                if (chars[i + 1] == '*') {
                    tokens[k].type = "POWER";
                    tokens[k].lexeme = "**";
                    tokens[k].value = 0.0d;
                    i = i + 2;
                    k++;

                } else {
                    tokens[k].type = "MUL";
                    tokens[k].lexeme = "*";
                    tokens[k].value = 0.0d;
                    i++;
                    k++;
                }
            }// MUL and POWER

            else if (chars[i] == '/') {
                if (chars[i + 1] == '/') {
                    //tokens[k].type = "COMMENT";
                    //tokens[k].lexeme = "//";
                    //tokens[k].value = 0.0d;
                    i = i + 2;
                    //k++;
                    while (chars[i] != '\n') {   //直接跳到换行符之后
                        i++;
                        if (i == string2.length()) {
                            return k;
                        }
                    }
                    i++;
                } else {
                    tokens[k].type = "DIV";
                    tokens[k].lexeme = "/";
                    tokens[k].value = 0.0d;
                    i++;
                    k++;
                }
            }// 注释或者除

            else if (chars[i] == '-') {
                if (chars[i + 1] == '-') {
                    tokens[k].type = "COMMENT";
                    tokens[k].lexeme = "--";
                    tokens[k].value = 0.0d;
                    i = i + 2;
                    k++;
                    while (chars[i] != '\n') {   //直接跳到换行符之后
                        i++;
                        if (i == string2.length()) {
                            return k;
                        }
                    }
                    i++;
                } else {
                    tokens[k].type = "MINUS";
                    tokens[k].lexeme = "-";
                    tokens[k].value = 0.0d;
                    i++;
                    k++;
                }
            }// 注释或者减

            else if (chars[i] == '+') {
                tokens[k].type = "PLUS";
                tokens[k].lexeme = "+";
                tokens[k].value = 0.0d;
                i++;
                k++;
            } else if (chars[i] == ',') {
                tokens[k].type = "COMMA";
                tokens[k].lexeme = ",";
                tokens[k].value = 0.0d;
                i++;
                k++;
            } else if (chars[i] == ';') {
                tokens[k].type = "SEMICO";
                tokens[k].lexeme = ";";
                tokens[k].value = 0.0d;
                i++;
                k++;
            } else if (chars[i] == '(') {
                tokens[k].type = "L_BRACKET";
                tokens[k].lexeme = "(";
                tokens[k].value = 0.0d;
                i++;
                k++;
            } else if (chars[i] == ')') {
                tokens[k].type = "R_BRACKET";
                tokens[k].lexeme = ")";
                tokens[k].value = 0.0d;
                i++;
                k++;
            } else if (chars[i] == 9 || chars[i] == '\n' || chars[i] == ' ') {
                //tokens[k].type="WHITE_SPACE";
                //tokens[k].lexeme+=chars[i];
                //tokens[k].value=0.0d;
                i++;
                //k++;
            } else {
                System.out.println(chars[i] + " 词法错误 " + "位置：" + k);
                return 0;
            }
        }
        String functions[] = {"SIN", "COS", "TAN", "LN", "EXP", "SQRT"};
        for (int kk = 0; kk < k; kk++) {
            for (int ii = 0; ii < 10; ii++) {
                if (tokens[kk].lexeme.toUpperCase().equals(Token_Type[ii])) {
                    tokens[kk].type = Token_Type[ii];
                    break;
                }
            }
            for (int ii = 0; ii < functions.length; ii++) {
                if (tokens[kk].lexeme.toUpperCase().equals(functions[ii])) {
                    tokens[kk].type = "FUNC";
                }
            }
            if (tokens[kk].lexeme.toUpperCase().equals("PI")) {
                tokens[kk].type = "CONST_ID";
                tokens[kk].value = 3.1415926d;
            }
            if (tokens[kk].lexeme.toUpperCase().equals("E")) {
                tokens[kk].type = "CONST_ID";
                tokens[kk].value = 2.71828d;
            }
        }

        tokens[k].type="NONTOKEN";
        tokens[k].value=0.0d;
        tokens[k].lexeme="NONTOKEN";
        if (k > 0) {
            for (int i = 0; i < k+1; i++) {
                System.out.print(tokens[i].type);
                System.out.print("    ");
                System.out.print(tokens[i].lexeme);
                System.out.print("    ");
                System.out.println(tokens[i].value);
            }
        }
        return k;
    }
}

编译原理

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

语法分析器上一篇

linux3.8.13编译内核的小问题下一篇