编译原理 词法分析实验/课程设计C++实现

简介: 词法分析阶段是编译过程的第一个阶段,是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务

@TOC

一、词法分析简介

词法分析阶段是编译过程的第一个阶段,是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。

词法分析是编译程序的第一个阶段且是必要阶段;词法分析的核心任务是扫描、识别单词且对识别出的单词给出定性、定长的处理;实现词法分析程序的常用途径:自动生成,手工生成。

完成词法分析任务的程序称为词法分析程序或词法分析器或扫描器。

从左至右地对源程序进行扫描,按照语言的词法规则识别各类单词,并产生相应单词的属性字。

二、设计要求

创建一个词法分析程序,它支持对正规文法的分析。必须使用DFA(确定性有限自动机)或NFA(非确定性有限自动机)来实现这一项目。该程序的输入是一个文本文件,包括一组由该正规文法产生的产生式以及待识别源代码字符串。该程序的输出是一个符号表(二元式),它由5种类型符号:关键词,识别符,常量,界符和操作符。

三、开发环境

硬件环境:PC机 windows10 64 位

编程语言:C++

运行环境:codeblocks或vs

四、实现过程

用子集法将NFA转化为DFA。具体实现是:做一个NFA_set类型的栈,新状态不停的进栈,每次从堆栈中弹出一个,计算其转换的结果,是新状态就进栈,重复则丢弃,只记录好dfa的转换,直到栈空。最后成功构造出DFA。

对输入源程序的扫描过程很简单,一次读入一个字符,成串的送入匹配和DFA判断其合法性。给出输出结果。

五、分析过程框架图

在这里插入图片描述

六、运行结果

识别程序的一部分输出结果:

在这里插入图片描述

对应的用于语法分析的部分输入:

在这里插入图片描述

七、部分核心代码

void NFA_to_DFA()
{
    num_new_set=0;
    NFA_set work_set;
    NFA_set worked_set;
    work_set.set[work_set.len++]=start;
    worked_set.len=0;
    stack<NFA_set> s;
    get_closure(work_set);
    s.push(work_set);
    new_set[num_new_set++]=work_set;
    for(int i=0;i<150;++i)
    {
        for(int j=0;j<150;++j)
        {
            dfa[i][j]='-1';
        }
    }
    for(int i=0;i<150;++i)
        is_final[i]=false;
    if(Is_contained_Y(work_set))
        is_final[num_new_set-1]=true;
    while(!s.empty())
    {
        work_set=s.top();
        s.pop();
        for(int i=0;i<len_final;++i)
        {
            for(int j=0;j<work_set.len;++j)
            {
                for(int k=0;k<move[work_set.set[j]][final[i]].len;++k)
                {
                    if(move[work_set.set[j]][final[i]].set[k]!='#' && move[work_set.set[j]][final[i]].set[k]!='Y' && !Is_in_set(move[work_set.set[j]][final[i]].set[k],worked_set))
                    {
                        worked_set.set[worked_set.len++]=move[work_set.set[j]][final[i]].set[k];
                    }
                    if(move[work_set.set[j]][final[i]].set[k]=='Y' && !Is_in_set(move[work_set.set[j]][final[i]].set[k],worked_set))
                    {
                        worked_set.set[worked_set.len++]='Y';    //用Y表示终态
                    }
                }
            }
            get_closure(worked_set);
            if(worked_set.len>0 && Is_in(worked_set)==-1)
            {
                dfa[num_new_set-1][final[i]]=num_new_set;
                s.push(worked_set);
                new_set[num_new_set++]=worked_set;
                if(Is_contained_Y(worked_set))
                {
                    is_final[num_new_set-1]=true;
                }
            }
            if(worked_set.len>0 && Is_in(worked_set)>-1 && final[i]!='@')
            {
                dfa[Is_in(work_set)][final[i]]=Is_in(worked_set);
            }
            worked_set.len=0;
        }
    }
}


相关文章
|
14天前
|
算法 开发工具 计算机视觉
【零代码研发】OpenCV实验大师工作流引擎C++ SDK演示
【零代码研发】OpenCV实验大师工作流引擎C++ SDK演示
19 1
|
14天前
|
存储 搜索推荐 C++
C++课程设计实验杭州电子科技大学ACM题目(中)
C++课程设计实验杭州电子科技大学ACM题目(中)
14 1
|
1月前
|
C++
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P6】大二C++实验作业-模板(4道代码题)【解析,注释】
|
14天前
|
存储 人工智能 测试技术
C++课程设计实验杭州电子科技大学ACM题目(下)
C++课程设计实验杭州电子科技大学ACM题目(下)
10 0
|
14天前
|
存储 C++
C++课程设计实验杭州电子科技大学ACM题目(上)
C++课程设计实验杭州电子科技大学ACM题目(上)
8 0
|
1月前
|
Serverless C++ 容器
【期末不挂科-C++考前速过系列P5】大二C++实验作业-多态性(3道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P5】大二C++实验作业-多态性(3道代码题)【解析,注释】
|
1月前
|
C++ 芯片
【期末不挂科-C++考前速过系列P4】大二C++实验作业-继承和派生(3道代码题)【解析,注释】
【期末不挂科-C++考前速过系列P4】大二C++实验作业-继承和派生(3道代码题)【解析,注释】
|
1月前
|
存储 小程序 机器人
西安石油大学C++上机实验汇总
西安石油大学C++上机实验汇总
121 0
|
1月前
|
C++
深入了解C++:底层编译原理(二)
深入了解C++:底层编译原理(二)
17 2
|
1天前
|
C++
C++一分钟之-类与对象初步
【6月更文挑战第20天】C++的类是对象的蓝图,封装数据和操作。对象是类的实例。关注访问权限、构造析构函数的使用,以及内存管理(深拷贝VS浅拷贝)。示例展示了如何创建和使用`Point`类对象。通过实践和理解原理,掌握面向对象编程基础。
29 2
C++一分钟之-类与对象初步

相关实验场景

更多