热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

PYTHON实现算术表达式的词法语法语义分析(编译原理应用)

本学期编译原理的一个大作业,我的选题是算术表达式的词法语法语义分析,当时由于学得比较渣,只用了递归下降的方法进行了分析。首先,

本学期编译原理的一个大作业,我的选题是算术表达式的词法语法语义分析,当时由于学得比较渣,只用了递归下降的方法进行了分析。

 

首先,用户输入算术表达式,其中算术表达式可以包含基本运算符,括号,数字,以及用户自定义变量。

词法分析,检查单词变量是否正确;语法分析,检查算术表达式语法是否正确并输出生成语法树;语义分析,输出四元表达式。

 

最终效果图:

例如输入:

 

词法分析结果:

语法分析结果:

语义分析结果:

 

算术表达式的组成语法如下:

  无符号整数 = 〈数字〉{〈数字〉}          

〈标识符〉= 〈字母〉{〈字母〉|〈数字〉}     

 表达式〉= [+|-]〈项〉{〈加减运算符〉〈项〉}        

〈项〉= 〈因子〉{〈乘除运算符〉〈因子〉}         

〈因子〉= 〈标识符〉|〈无符号整数〉|‘(’〈表达式〉‘)’       

〈加减运算符〉= +|-       

〈乘除运算符〉= *|/

注意:

#标识符以字母开头,仅包含字母和数字

#字母包含大写和小写字母

符号文法表示:

Indentifer: 标识符  digit:数字 M:表达式

项:T    因子:F

M -> +E|-E|E

E -> E+T|E-T|T

T -> T*F|T/F|F

F -> (E)|indentifer|digit

消除左递归,改进文法:

1. M -> +E|-E|E

2. E -> TE~

3. E~ -> +TE~|-TE~|&

4. T -> FT~

5. T~ -> *FT~|/FT~|&

6. F -> (E)|indentifer|digit


1.词法分析


单词类别定义

  运算符:( , ) , + , - , * , /      类别码:3

  标识符:〈字母〉{〈字母〉|〈数字〉}     类别码:1

  无符号整数:〈数字〉{〈数字〉}     类别码:2


设计思路

依次接受所输入的字符串,根据DFA进行判断单词类型,将单词及符号内码存入符号表字典,将单词存入单词栈

1.如若接收到字母说明为标识符,接着一直接受字母和数字,直到出现非数字和非字母符号

2.如若在运算符后接收到数字,则说明为无符号整数,一直接受直到出现非数字符号

3.如若接受到运算符,则继续处理

简单绘制的DFA:


数据结构

符号表:dic={}

单词栈:table=[]输入数据

 

2.语法分析

为文法中的每一个非终结符号设计对应的处理程序,处理程序按照具体的文法接受顺序设计,每当程序选择其中一个文法时,将其保存并打印出来,若单词栈中的所有单词都被接受,则说明语法正确,其他情况,则说明语法错误


数据结构

dic={}   #符号表

table=[]   #单词栈

wenfa=[]   #字符串文法 

 

3.语义分析与中间代码生成


设计思路

这里我运用的依旧是递归下降的思想,我并没有利用语法分析的结果,而是利用词法分析的结果为每一个非终结符号设计相应的程序, 当结果足够生成四元式时,将其输出。将结果赋给给临时变量,传递给父项。


数据结构

table=[]   #单词栈

siyuan=[]  #四元式

 

源码:


 

#-*- coding=utf-8 -*-

 

letter='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

number='0123456789'

operater='+-*/()'

 

dic={}   #符号表

table=[]   #单词栈

wenfa=[]   #字符串文法

siyuan=[]  #四元式

 

 

#####################################        词法分析        ######################################

def cifa(string):     #词法分析

    print ''

    m=0

    state=0      #1:为标识符 2:为数字串 3:为运算符

    for in range(len(string)):

        if string[i] in operater :  #如果是运算符

            if state==1:        #state=1表明其前面的为标识符

                print string[m:i],'是标识符,类型码:1'

                dic[string[m:i]]=1

                table.append(string[m:i])

            elif state==2:      #state=2表明其前面的为数字

                print string[m:i],'是数字,类型码:2'

                dic[string[m:i]]=2

                table.append(string[m:i])

            m=i+1

            state=3

            print string[i],'是运算符,类型码:3'

            dic[string[i]]=3

            table.append(string[i])

        elif string[i] in number:    #如果是数字

            if i==m:        #判断此时的数字是否为整数的第一个数字,若是则改变状态为无符号整数

                state=2

        elif string[i] in letter: #如果是字母

            if state==2:    #判断此时的状态,若state=2表明状态为无符号整数,而整数内不能包含字母,故报错

                print '词法分析检测到错误,数字串中不能包含字母'

                exit(0)

            if i==m:        #判断此时的字母是否为标识符的第一个字母,若是则改变状态为标识符

                state=1

        else:               #当输入的字符均不符合以上判断,则说明为非法字符,故报错

            print '词法分析检测到非法字符'

            exit(0)

    if state==1:        #当字符串检查完后,若字符串最后部分为标识符,应将其print出来

        print string[m:],'是标识符,类型码:3'

        dic[string[m:]]=1

        table.append(string[m:])

    elif state==2:      #若字符串最后部分为无符号整数,应将其print出来

        print string[m:],'是无符号整数,类型码:2'

        dic[string[m:]]=2

        table.append(string[m:])

    table.append('#')

    print '字符栈:',table,'\n词法正确'

 

 

###################################        语法分析         #####################################

'''

基本文法:

M -> +E|-E|E

E -> TE~

E~ -> +TE~|-TE~|&

T -> FT~

T~ -> *FT~|/FT~|&

F -> (E)|indentifer|digit

'''

class yufa():       #语法分析程序

    def __init__(self):

        self.i=0  #栈指针

        try:            #用异常处理程序捕获程序的错误,出现异常则报错

            self.m()

        except:

            print '\n语法分析程序检查到错误'

            exit(0)

    def m(self):    #PM程序

        if(table[self.i]=='+'):

            self.i+=1

            wenfa.append('M -> +E')

            self.e()

        elif(table[self.i]=='-'):

            self.i+=1

            wenfa.append('M -> -E')

            self.e()

        else:

            wenfa.append('M -> E')

            self.e()

        if(self.i is not len(table)-1):   #语法分析结束时,若单词栈指针与单词表长度不相等,报错

            print "\n语法分析程序检查到错误,'('前应该有运算符"

            exit(0)

        else:

            print '\n字符串语法是:'       #若一切正确,则输出语法树文法

            for in wenfa:

                print i

            print '语法正确'

    def e(self):     #PE程序

        wenfa.append('E -> TE1')

        self.t()

        self.e1()

    def e1(self):    #PE1程序

        if(table[self.i]=='+'):

            self.i+=1

            wenfa.append('E1 -> +TE1')

            self.t()

            self.e1()

        elif(table[self.i]=='-'):

            self.i+=1

            wenfa.append('E1 -> -TE1')

            self.t()

            self.e1()

        else:

            wenfa.append('E1 -> &')

    def t(self):      #PT程序

        wenfa.append('T -> FT1')

        self.f()

        self.t1()

    def t1(self):     #PT1程序

        if(table[self.i]=='*'):

            self.i+=1

            wenfa.append('T1 -> *FT1')

            self.f()

            self.t1()

        elif(table[self.i]=='/'):

            self.i+=1

            wenfa.append('T1 -> /FT1')

            self.f()

            self.t1()

        else:

            wenfa.append('T1 -> &')

    def f(self):      #PF程序

        if(table[self.i]=='('):

            wenfa.append('F -> (E)')

            self.i+=1

            self.e()

            if(table[self.i]!=')'):

                raise Exception

            self.i+=1

        elif(dic[table[self.i]]==1):

            wenfa.append('F -> Indentifer '+str(table[self.i]))

            self.i+=1

        elif(dic[table[self.i]]==2):

            wenfa.append('F -> Digit '+str(table[self.i]))

            self.i+=1

        else:

            raise Exception          #若均不符合,则引出异常

 

 

 

#######################################       语义分析        #######################################

 

class yuyi:

    def __init__(self):

        print '\n语义分析结果(四元式):'

        self.i=0    #栈指针

        self.flag=0    #记录临时变量T数目

        self.m()

        for in siyuan:        #输出四元式结果

            print i

    def m(self):        #PM程序

        if(table[self.i]=='+'):

            self.i+=1

            ret1=self.e()

            siyuan.append('(+,0,'+ret1+',out)')

            self.flag+=1

        elif(table[self.i]=='-'):

            self.i+=1

            ret2=self.e()

            siyuan.append('(-,0,'+ret2+',out)')

            self.flag+=1

        else:

            ret3=self.e()

            siyuan.append('(=,'+ret3+',0,out)')

    def e(self):        #PE程序

        ret1=self.t()

        ret2,ret3=self.e1()

        if(ret2!='&'):      #若ret2不为&,则可以产生四元式,否则将变量传递给父项

            self.flag+=1

            siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

            return 'T'+str(self.flag)

        else:

            return ret1

    def e1(self):           #PE1程序

        if(table[self.i]=='+'):

            self.i+=1

            ret1=self.t()

            ret2,ret3=self.e1()

            if(ret2=='&'):

                return '+',ret1

            else:

                self.flag+=1

                siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

                return '+','T'+str(self.flag)

        elif(table[self.i]=='-'):

            self.i+=1

            ret1=self.t()

            ret2,ret3=self.e1()

            if(ret2=='&'):

                return '-',ret1

            else:

                self.flag+=1

                siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

                return '-','T'+str(self.flag)

        else:

            return '&','&'

    def t(self):        #PT程序

        ret1=self.f()

        ret2,ret3=self.t1()

        if(ret2!='&'):

            self.flag+=1

            siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

            return 'T'+str(self.flag)

        else:

            return ret1

    def t1(self):       #PT1程序

        if(table[self.i]=='*'):

            self.i+=1

            ret1=self.f()

            ret2,ret3=self.t1()

            if(ret2=='&'):

                return '*',ret1

            else:

                self.flag+=1

                siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

                return '*','T'+str(self.flag)

        elif(table[self.i]=='/'):

            self.i+=1

            ret1=self.f()

            ret2,ret3=self.t1()

            if(ret2=='&'):           #若ret2不为&,则可以产生四元式,否则将变量传递给父项

                return '/',ret1

            else:

                self.flag+=1

                siyuan.append('('+ret2+','+ret1+','+ret3+',T'+str(self.flag)+')')

                return '/','T'+str(self.flag)

        else:

            return '&','&'

    def f(self):        #PF程序

        if(table[self.i]=='('):

            self.i+=1

            ret1=self.e()

            self.i+=1

            return str(ret1)

        elif(dic[table[self.i]]==1):        #当为标识符时,传递给父项

            temp=self.i

            self.i+=1

            return table[temp]

        elif(dic[table[self.i]]==2):        #当为整数时,传递给父项

            temp=self.i

            self.i+=1

            return table[temp]

 

 

#######################################        主程序         #######################################

if __name__=='__main__':

    string=raw_input('请输入表达式:')

    cifa(string)

    yufa()

    yuyi()

  


推荐阅读
  • 电话号码的字母组合解题思路和代码示例
    本文介绍了力扣题目《电话号码的字母组合》的解题思路和代码示例。通过使用哈希表和递归求解的方法,可以将给定的电话号码转换为对应的字母组合。详细的解题思路和代码示例可以帮助读者更好地理解和实现该题目。 ... [详细]
  • XML介绍与使用的概述及标签规则
    本文介绍了XML的基本概念和用途,包括XML的可扩展性和标签的自定义特性。同时还详细解释了XML标签的规则,包括标签的尖括号和合法标识符的组成,标签必须成对出现的原则以及特殊标签的使用方法。通过本文的阅读,读者可以对XML的基本知识有一个全面的了解。 ... [详细]
  • CF:3D City Model(小思维)问题解析和代码实现
    本文通过解析CF:3D City Model问题,介绍了问题的背景和要求,并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景,每个网格单元可以作为建筑的基础,建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路,并给出了相应的代码实现供读者参考。 ... [详细]
  • 本文介绍了南邮ctf-web的writeup,包括签到题和md5 collision。在CTF比赛和渗透测试中,可以通过查看源代码、代码注释、页面隐藏元素、超链接和HTTP响应头部来寻找flag或提示信息。利用PHP弱类型,可以发现md5('QNKCDZO')='0e830400451993494058024219903391'和md5('240610708')='0e462097431906509019562988736854'。 ... [详细]
  • Python爬虫中使用正则表达式的方法和注意事项
    本文介绍了在Python爬虫中使用正则表达式的方法和注意事项。首先解释了爬虫的四个主要步骤,并强调了正则表达式在数据处理中的重要性。然后详细介绍了正则表达式的概念和用法,包括检索、替换和过滤文本的功能。同时提到了re模块是Python内置的用于处理正则表达式的模块,并给出了使用正则表达式时需要注意的特殊字符转义和原始字符串的用法。通过本文的学习,读者可以掌握在Python爬虫中使用正则表达式的技巧和方法。 ... [详细]
  • 本文介绍了在iOS开发中使用UITextField实现字符限制的方法,包括利用代理方法和使用BNTextField-Limit库的实现策略。通过这些方法,开发者可以方便地限制UITextField的字符个数和输入规则。 ... [详细]
  • 基于Socket的多个客户端之间的聊天功能实现方法
    本文介绍了基于Socket的多个客户端之间实现聊天功能的方法,包括服务器端的实现和客户端的实现。服务器端通过每个用户的输出流向特定用户发送消息,而客户端通过输入流接收消息。同时,还介绍了相关的实体类和Socket的基本概念。 ... [详细]
  • 微软头条实习生分享深度学习自学指南
    本文介绍了一位微软头条实习生自学深度学习的经验分享,包括学习资源推荐、重要基础知识的学习要点等。作者强调了学好Python和数学基础的重要性,并提供了一些建议。 ... [详细]
  • 本文介绍了如何在给定的有序字符序列中插入新字符,并保持序列的有序性。通过示例代码演示了插入过程,以及插入后的字符序列。 ... [详细]
  • springmvc学习笔记(十):控制器业务方法中通过注解实现封装Javabean接收表单提交的数据
    本文介绍了在springmvc学习笔记系列的第十篇中,控制器的业务方法中如何通过注解实现封装Javabean来接收表单提交的数据。同时还讨论了当有多个注册表单且字段完全相同时,如何将其交给同一个控制器处理。 ... [详细]
  • 猜字母游戏
    猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]
  • [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程,同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率,并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
  • 这是一个愚蠢的问题,但我只是对此感到好奇.假设我在Pythonshell,我有一些我查询的数据库对象.我做:db.query(的queryString)该查询在0xffdf842c ... [详细]
  • 欢乐的票圈重构之旅——RecyclerView的头尾布局增加
    项目重构的Git地址:https:github.comrazerdpFriendCircletreemain-dev项目同步更新的文集:http:www.jianshu.comno ... [详细]
  • 本文介绍了一种在PHP中对二维数组根据某个字段进行排序的方法,以年龄字段为例,按照倒序的方式进行排序,并给出了具体的代码实现。 ... [详细]
author-avatar
清风2602939017
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有