《编译与反编译技术实战》——3.2　词法分析器的手工实现

3.2　词法分析器的手工实现

手工构造词法分析器首先需要将描述单词符号的正规文法或者正规式转化为状态转换图，然后再依据状态转换图进行词法分析器的构造。状态转换图是一个有限方向图，结点代表状态，用圆圈表示；状态之间用箭弧连接，箭弧上的标记（字符）代表射出结点状态下可能出现的输入字符或字符类。一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态（用双圈表示）。大多数程序语言的单词符号都可以用状态转换图予以识别。具体过程如下：

1）从初始状态出发。

2）读入一个字符。

3）按当前字符转入下一状态。

4）重复步骤2～3直到无法继续转移为止。

在遇到读入的字符是单词的分界符时，若当前状态是终止状态，说明读入的字符组成了一个单词；否则，说明输入字符串不符合词法规则。

这里我们以一个C语言子集作为例子，说明如何基于状态转换图手工编写词法分析器，该语言子集几乎包含了C语言所有的单词符号。主要步骤是，首先给出描述该子集中各种单词符号的词法规则，其次构造其状态转换图，然后根据状态转换图编写词法分析器。

表3-1列出了这个C语言子集的所有单词符号以及它们的种别编码。该语言子集所包含的单词符号有：

1）标识符：以字母、下划线开头的字母、数字和下划线组成的符号串。

2）关键字：标识符的子集，C语言的关键字共有32个（为了测试加入了输入输出函数，共计34个）。

3）无符号十进制整数：由0到9数字组成的字符串。

4）算符和界符：“{”“}”“[”“]”“（”“）”“.”“->”“～”“++”“--”“!”“&”“*”“/”“%”“+”
“-”“<<”“>>”“>”“>=”“<”“<=”“==”“!=”“^”“|”“&&”“||”“?”“=”“/=”“*=”“%=”“+=”“-=”“&=”“^=”“|=”“,”“#”“;”“:”，共计44个。


下面为产生该C语言子集中所涉及的单词符号的文法的产生式。

1）关键字文法：

keyword→ void | char | int | float | double | short | long | signed | unsigned | struct | union | enum | typedef | sizeof | auto | static | register | extern | const | volatile | return | continue | break | goto | if | else | switch | case | default | for | do | while | scanf | printf

2）标识符文法：

letter→A | … | Z | a | …| z
digit→0 | 1 | … | 9
id→letter rid |- rid
rid→letter rid |- rid |digit rid | ε

3）无符号整数文法：

digit→0 | 1 | … | 9
digits→digit rdigit
rdigit→digit rdigit |ε

4）算符和界符的文法：

op→{ | } | [ | ] | ( | ) | . | -bigger | ~ | +plus | -minus  | ! | & | * |  / | % |  + | - | <less | >bigger | > | >equal | < | <equal | =equal | !equal | ^ | | | &and | |or |? | = | /equal |  equal | %equal | +equal | -equal | &equal | ^equal | |equal | , | # | ; | :
bigger →>
plus→+
minus→-
less→<
equal→=
and→&
or→|

依据上述文法可得到如图3-2所示的状态转换图。其中，终态上的星号（*）表示此时还要把超前读出的字符退回，即搜索指针回调一个字符位置。在状态2时，所识别出的标识符应先与表的前34项逐一比较，若匹配，则该标识符是一个保留字，否则就是标识符。如果是标识符，则返回相应的种别编码和标识符本身。在状态4时，将识别的常数种别编码和常数值返回。在状态7、12、16、19、23时，为了识别相应的算符需进行超前搜索。

状态转换图非常易于实现，最简单的方法是为每个状态编写一段程序。对于不含回路的分支状态来说，可以用一个switch()语句或一组if-else语句实现；对于含回路的状态来说，可以让它对应一个while语句。图3-3给出了整个词法分析器的程序设计流程图。

为便于阅读，对下面程序中所涉及的变量和过程进行以下说明：

1）ch字符变量：存放最新读入的源程序字符。
2）strToken 字符数组：存放构成单词符号的字符串。
3）void initialization()子程序：对单词符号设定种别编码。
4）getNextChar () 子程序过程：把下一个字符读入ch中。
5）getbc()子程序过程：每次调用时，检查ch的字符是否为空白符、回车或者制表符，若是则反复调用getNextChar ()，直至ch中读入一非上述符号。
6）concat()子程序过程：把ch中的字符连接到strToken。
7）isLetter()、isDigital()和isUnderline布尔函数：判断ch中字符是否为字母、数字或下划线。
8）reserve_string() 整型函数：对于strToken中的字符串判断它是否为保留字，若它是保留字则给出它的编码，否则返回0。
9）reserve_operator()整型函数：返回strToken中所识别出的算符和界符编码。
10）retract() 子程序：把搜索指针回调一个字符位置。
11）error()：出现非法字符：显示出错信息。

对应于图3-2的词法分析器构造如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<fstream>
using namespace std;
struct symbol
{
    char * str;
    int coding;
};
char *keyword_list[34] = { "void", "char", "int", "float", "double", "short", "long", "signed", "unsigned", "struct", "union", "enum", "typedef", "sizeof", "auto", "static", "register", "extern", "const", "volatile", "return", "continue", "break", "goto", "if", "else", "switch", "case","default","for","do","while","scanf","printf"};
char *operator_list[44] = { "{","}","[","]","(",")",".","->","~","++","--",
"!","&","*","/","%","+","-","<<",">>",">", ">=","<","<=","==","!=","^","|","&&",
"||","?","=","/=","*=","%=","+=","-=","&=","^=","|=",",","#",";",":"};
char ch; //读入的字符
char strToken[20] = "";/ /读入的字符串
int eof_flag = 0;
int num = 1;//编码的数字（为了递增）
int row = 1;
struct symbol keywords[34];
struct symbol identifiers[44];
FILE *fp = NULL;
FILE *fw = NULL;
ofstream out;

//给单词符号设定种别编码
void initialization() {
    //给关键字设定种别编码
    for (int i = 0;i < 34;i++)
    {
        keywords[i].str = keyword_list[i];
        keywords[i].coding = num;
        num++;
    }
   //给算符和界符设定种别编码
    for (i = 0;i < 44;i++) {
        identifiers[i].str = operator_list[i];
        identifiers[i].coding = num;
        num++;
    }
    //数字79，标识符80
}

//把下一个字符读入ch中
void getNextChar(FILE *ffp)
{
    if ((ch = getc(ffp)) == EOF)
    {
        eof_flag = 1;
    }
    if (ch == '\n')
        row++;
}
//检查ch的字符是否为空白符、回车或者制表符，若是，则反复调用getNextChar ()，直至ch中读入一非上述符号
void getbc(FILE * ffp)
{
    while (ch == ' ' || ch == '\n' || ch == '\t')
    {
        getNextChar(ffp);
    }
}

//判断ch是否为字母
bool isLetter(char ch)
{
    return isalpha(ch);
}

//判断ch是否为数字
bool isDigit(char ch)
{
    return isdigit(ch);
}

//判断ch是否为下划线
bool isUnderline(char ch)
{
    if (ch == '_')
        return 1;
    else
        return 0;
}

//将输入的字符ch连接到strToken
void concat()
{
    char * tmp = &ch;
    strcat(strToken, tmp);
}

//把搜索指针回调一个字符位置
void retract(FILE * ffp)
{
    fseek(ffp, -1, SEEK_CUR);
    ch = ' ';
}

//对于strToken中的字符串判断它是否为保留字，若它是保留字则给出它的编码，否则返回0
int reserve_string(char * str) {
    for (int i = 0;i < 34;i++) {
        if ((strcmp(str, keywords[i].str)) == 0)
        {
            return keywords[i].coding;
        }
    }
    return 0;
}

//返回strToken中所识别出的算符和界符编码
int reserve_operator(char* ch)
{

    for (int i = 0;i < 44;i++) {
        if ((strcmp(ch, identifiers[i].str)) == 0)
        {
            return identifiers[i].coding;
        }
    }
    return 0;
}

//出错处理
void error()
{
    printf("\n ********Error*********************\n");
    printf(" row %d  Invaild symbol ! ! ! ",  row);
    printf("\n ********Error*********************\n");
    exit(0);
}

//词法分析
void LexiscalAnalyzer()
{
    int num = 0, val = 0, code = 0;
    strcpy(strToken, "");
    getNextChar(fp);
    getbc(fp);
    switch (ch)
    {
    case 'a':
    case 'b':
    case 'c':
    case 'd':
    case 'e':
    case 'f':
    case 'g':
    case 'h':
    case 'i':
    case 'j':
    case 'k':
    case 'l':
    case 'm':
    case 'n':
    case 'o':
    case 'p':
    case 'q':
    case 'r':
    case 's':
    case 't':
    case 'u':
    case 'v':
    case 'w':
    case 'x':
    case 'y':
    case 'z':
    case 'A':
    case 'B':
    case 'C':
    case 'D':
    case 'E':
    case 'F':
    case 'G':
    case 'H':
    case 'I':
    case 'J':
    case 'K':
    case 'L':
    case 'M':
    case 'N':
    case 'O':
    case 'P':
    case 'Q':
    case 'R':
    case 'S':
    case 'T':
    case 'U':
    case 'V':
    case 'W':
    case 'X':
    case 'Y':
    case 'Z':
    case '_':
        while (isLetter(ch) || isDigit(ch) || isUnderline(ch))
        {
            concat();
            getNextChar(fp);
        }
        retract(fp);
         code = reserve_string(strToken);
        if (code = = 0)
        {
            printf("(%d , %s)\n", 79, strToken);
        }
        else
        {
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case'0':
    case'1':
    case'2':
    case'3':
    case'4':
    case'5':
    case'6':
    case'7':
    case'8':
    case'9':
        while (isdigit(ch))
        {
            concat();
            getNextChar(fp);
        }
        retract(fp);
        printf("(%d , %s)\n",80, strToken);
        break;
    case '{':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '}':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '[':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case ']':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '(':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case ')':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '.':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '-':
        concat();
        getNextChar(fp);
        if (ch == '>')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '-')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '~':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '+':
        concat();
        getNextChar(fp);
        if (ch == '+')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);

        }
        break;
    case '*':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);

        }
        break;
    case '&':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '&')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '!':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '%':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '<':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '<')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '>':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '>')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '=':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '^':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case '|':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '|')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;

    case '?':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '/':
        concat();
        getNextChar(fp);
        if (ch == '=')
        {
            concat();
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        else if (ch == '/') //跳过注释
        {
            getNextChar(fp);
            while (ch != '\n') {
                getNextChar(fp);
            }

            break;
        }
        else if (ch == '*')//跳过注释
        {
            getNextChar(fp);
            while (ch != '*') {
                getNextChar(fp);
            }
            getNextChar(fp);
            if (ch == '/');
            break;
        }
        else
        {
            retract(fp);
            code = reserve_operator(strToken);
            printf("(%d , %s)\n", code, strToken);
        }
        break;
    case ',':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case '#':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case ';':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    case ':':
        concat();
        code = reserve_operator(strToken);
        printf("(%d , %s)\n", code, strToken);
        break;
    default:
        if (ch == EOF)
        {
            eof_flag = 1;
            break;
        }
        error();
    }
}

//主函数
int main()
{
    initialization();
    char name[1024];
    cout<<"从文件读入：";
    cin>>name;
    fp=fopen(name,"r");
    out.open("result.txt");
    while(!feof(fp))
    {    if (eof_flag == 1)
        {
            exit(1);
        }
    LexiscalAnalyzer();
    }
    fclose(fp);
    out.close();
    return 0;
}
时间： 2024-07-29 02:33:44

《编译与反编译技术实战》——3.2　词法分析器的手工实现的相关文章

《编译与反编译技术实战》——导读

前 言 "编译技术"是从事软件开发和信息安全相关工作的技术人员必须掌握的基础性技术,也是高等院校计算机科学与技术和软件专业的一门必修专业课,这是理论与实践结合非常强的领域,对提升开发人员的技术水平和大学生科学思维的养成.解决实际问题能力具有重要作用."反编译技术"则是近几年发展起来的新兴技术,许多计算机软件或信息安全从业者非常关心该技术的发展,但目前这方面的书籍较少,与"编译技术"结合起来讲解的书也很少,从实践角度来剖析的更是少见.本书就是在这种

《编译与反编译技术实战 》一导读

前 言 "编译技术"是从事软件开发和信息安全相关工作的技术人员必须掌握的基础性技术,也是高等院校计算机科学与技术和软件专业的一门必修专业课,这是理论与实践结合非常强的领域,对提升开发人员的技术水平和大学生科学思维的养成.解决实际问题能力具有重要作用."反编译技术"则是近几年发展起来的新兴技术,许多计算机软件或信息安全从业者非常关心该技术的发展,但目前这方面的书籍较少,与"编译技术"结合起来讲解的书也很少,从实践角度来剖析的更是少见.本书就是在这种

《编译与反编译技术实战》——第1章 实践的环境与工具 1.1 实践环境概述

第1章 实践的环境与工具 本书致力于通过实践及案例,从正反向两个角度介绍编译系统的一般构造原理和基本实现技术,本章首先对书中内容涉及的环境与工具进行简单介绍,这些工具都是编译与反编译过程中常用的工具. 1.1 实践环境概述 在编译过程中所涉及的环境主要是编译环境及工具链,常用的工具有词法分析生成器.语法分析生成器.编译器.汇编器.链接器等.在反编译过程中主要涉及反汇编器.静态或动态的调试与分析工具.下面对近年来流行的编译与反编译工具逐一进行简单介绍.

《编译与反编译技术实战 》一 第1章 实践的环境与工具

第1章 实践的环境与工具 本书致力于通过实践及案例,从正反向两个角度介绍编译系统的一般构造原理和基本实现技术,本章首先对书中内容涉及的环境与工具进行简单介绍,这些工具都是编译与反编译过程中常用的工具. 1.1 实践环境概述 在编译过程中所涉及的环境主要是编译环境及工具链,常用的工具有词法分析生成器.语法分析生成器.编译器.汇编器.链接器等.在反编译过程中主要涉及反汇编器.静态或动态的调试与分析工具.下面对近年来流行的编译与反编译工具逐一进行简单介绍.

《编译与反编译技术实战》——第1章实践的环境与工具

第1章实践的环境与工具本书致力于通过实践及案例,从正反向两个角度介绍编译系统的一般构造原理和基本实现技术,本章首先对书中内容涉及的环境与工具进行简单介绍,这些工具都是编译与反编译过程中常用的工具.

《编译与反编译技术实战》——1.1节实践环境概述

1.1 实践环境概述在编译过程中所涉及的环境主要是编译环境及工具链,常用的工具有词法分析生成器.语法分析生成器.编译器.汇编器.链接器等.在反编译过程中主要涉及反汇编器.静态或动态的调试与分析工具.下面对近年来流行的编译与反编译工具逐一进行简单介绍.

《编译与反编译技术》—第2章2.1节词法分析器的需求分析

本节书摘来自华章出版社<编译与反编译技术>一书中的第2章,第2.1节词法分析器的需求分析,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问"华章计算机"公众号查看. 第2章 词法分析的理论与实践 词法分析是编译过程的第一步,也是编译过程必不可少的步骤.编译过程中执行词法分析的程序称为词法分析器.本章主要介绍词法分析器的手动构造和自动构造的原理. 2.1 词法分析器的需求分析 本节首先介绍词法分析器的功能及其输出的单词符号的表示方式,然后研究将词法分析独立出来的原因.

《编译与反编译技术》—第1章1.5节高级语言及其分类

本节书摘来自华章出版社<编译与反编译技术>一书中的第1章,第1.5节高级语言及其分类,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问"华章计算机"公众号查看. 1.5 高级语言及其分类 根据应用类型的不同,涌现了多种多样的面向人类的高级语言,其中典型的有如下几类形式. 1.过程式语言 过程式语言也称为强制式语言(Imperative Language).这类语言的特点是面向语句,命令驱动.一个用过程式语言编写的程序由一系列语句组成,语句的执行会引起若干存储单元中的值

《编译与反编译技术》—第1章1.8节UNIX/Linux环境中的make和makefile

本节书摘来自华章出版社<编译与反编译技术>一书中的第1章,第1.8节UNIX/Linux环境中的make和makefile ,作者庞建民,陶红伟,刘晓楠,岳峰,更多章节内容可以访问"华章计算机"公众号查看. 1.8 UNIX/Linux环境中的make和makefile 在UNIX或Linux环境中,make是一个非常重要和经常使用的编译工具.无论是自己进行项目开发还是安装应用软件,都会经常用到make或make install.使用make工具,可以将大型的开发项目分解成

《编译与反编译技术》目录—导读

前言"编译原理"是高等院校计算机科学与技术和软件工程专业的必修专业课之一,是一门理论与实践相结合的课程,对大学生科学思维的养成和解决实际问题能力的提高具有重要作用."编译技术"是"编译原理"课程中介绍的关键技术,已经被广大计算机软件从业者所掌握和熟悉."反编译技术"则是近几年得以迅速发展的新兴技术,许多计算机软件或信息安全从业者非常关心该项技术,但目前这方面的书籍较少,与"编译技术"结合起来讲解的更少.本书