首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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

作者：清风2602939017 | 来源：互联网 | 2023-09-09 17:40
本学期编译原理的一个大作业，我的选题是算术表达式的词法语法语义分析，当时由于学得比较渣，只用了递归下降的方法进行了分析。首先，

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

 

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

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

 

最终效果图&＃xff1a;

例如输入&＃xff1a;

 

词法分析结果&＃xff1a;

语法分析结果&＃xff1a;

语义分析结果&＃xff1a;

 

算术表达式的组成语法如下&＃xff1a;

  无符号整数 &＃xff1d; 〈数字〉{〈数字〉}          

〈标识符〉&＃xff1d; 〈字母〉{〈字母〉&＃xff5c;〈数字〉}     

 表达式〉&＃xff1d; [&＃xff0b;&＃xff5c;&＃xff0d;]〈项〉{〈加减运算符〉〈项〉}        

〈项〉&＃xff1d; 〈因子〉{〈乘除运算符〉〈因子〉}         

〈因子〉&＃xff1d; 〈标识符〉&＃xff5c;〈无符号整数〉&＃xff5c;‘&＃xff08;’〈表达式〉‘&＃xff09;’       

〈加减运算符〉&＃xff1d; &＃xff0b;&＃xff5c;&＃xff0d;       

〈乘除运算符〉&＃xff1d; &＃xff0a;&＃xff5c;&＃xff0f;

注意&＃xff1a;

#标识符以字母开头&＃xff0c;仅包含字母和数字

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

符号文法表示&＃xff1a;

Indentifer&＃xff1a; 标识符  digit&＃xff1a;数字 M&＃xff1a;表达式

项&＃xff1a;T    因子&＃xff1a;F

M -> &＃43;E|-E|E

E -> E&＃43;T|E-T|T

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

F -> (E)|indentifer|digit

消除左递归&＃xff0c;改进文法&＃xff1a;

1. M -> &＃43;E|-E|E

2. E -> TE~

3. E~ -> &＃43;TE~|-TE~|&

4. T -> FT~

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

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


1.词法分析


单词类别定义

  运算符&＃xff1a;( , ) , &＃43; , - , * , /      类别码&＃xff1a;3

  标识符&＃xff1a;〈字母〉{〈字母〉&＃xff5c;〈数字〉}     类别码&＃xff1a;1

  无符号整数&＃xff1a;〈数字〉{〈数字〉}     类别码&＃xff1a;2


设计思路

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

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

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

3.如若接受到运算符&＃xff0c;则继续处理

简单绘制的DFA:


数据结构

符号表&＃xff1a;dic&＃61;{}

单词栈&＃xff1a;table&＃61;[]输入数据

 

2.语法分析

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


数据结构

dic&＃61;{}   #符号表

table&＃61;[]   #单词栈

wenfa&＃61;[]   #字符串文法 

 

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


设计思路

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


数据结构

table&＃61;[]   #单词栈

siyuan&＃61;[]  #四元式

 

源码&＃xff1a;


 

#-*- coding&＃61;utf-8 -*-

 

letter&＃61;&＃39;abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ&＃39;

number&＃61;&＃39;0123456789&＃39;

operater&＃61;&＃39;&＃43;-*/()&＃39;

 

dic&＃61;{}   #符号表

table&＃61;[]   #单词栈

wenfa&＃61;[]   #字符串文法

siyuan&＃61;[]  #四元式

 

 

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

def cifa(string):     #词法分析

    print &＃39;&＃39;

    m&＃61;0

    state&＃61;0      #1&＃xff1a;为标识符 2&＃xff1a;为数字串 3&＃xff1a;为运算符

    for i in range(len(string)):

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

            if state&＃61;&＃61;1:        #state&＃61;1表明其前面的为标识符

                print string[m:i],&＃39;是标识符,类型码&＃xff1a;1&＃39;

                dic[string[m:i]]&＃61;1

                table.append(string[m:i])

            elif state&＃61;&＃61;2:      #state&＃61;2表明其前面的为数字

                print string[m:i],&＃39;是数字&＃xff0c;类型码&＃xff1a;2&＃39;

                dic[string[m:i]]&＃61;2

                table.append(string[m:i])

            m&＃61;i&＃43;1

            state&＃61;3

            print string[i],&＃39;是运算符&＃xff0c;类型码&＃xff1a;3&＃39;

            dic[string[i]]&＃61;3

            table.append(string[i])

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

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

                state&＃61;2

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

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

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

                exit(0)

            if i&＃61;&＃61;m:        #判断此时的字母是否为标识符的第一个字母&＃xff0c;若是则改变状态为标识符

                state&＃61;1

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

            print &＃39;词法分析检测到非法字符&＃39;

            exit(0)

    if state&＃61;&＃61;1:        #当字符串检查完后&＃xff0c;若字符串最后部分为标识符&＃xff0c;应将其print出来

        print string[m:],&＃39;是标识符&＃xff0c;类型码&＃xff1a;3&＃39;

        dic[string[m:]]&＃61;1

        table.append(string[m:])

    elif state&＃61;&＃61;2:      #若字符串最后部分为无符号整数&＃xff0c;应将其print出来

        print string[m:],&＃39;是无符号整数&＃xff0c;类型码&＃xff1a;2&＃39;

        dic[string[m:]]&＃61;2

        table.append(string[m:])

    table.append(&＃39;#&＃39;)

    print &＃39;字符栈:&＃39;,table,&＃39;\n词法正确&＃39;

 

 

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

&＃39;&＃39;&＃39;

基本文法&＃xff1a;

M -> &＃43;E|-E|E

E -> TE~

E~ -> &＃43;TE~|-TE~|&

T -> FT~

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

F -> (E)|indentifer|digit

&＃39;&＃39;&＃39;

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

    def __init__(self):

        self.i&＃61;0  #栈指针

        try:            #用异常处理程序捕获程序的错误&＃xff0c;出现异常则报错

            self.m()

        except:

            print &＃39;\n语法分析程序检查到错误&＃39;

            exit(0)

    def m(self):    #PM程序

        if(table[self.i]&＃61;&＃61;&＃39;&＃43;&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;M -> &＃43;E&＃39;)

            self.e()

        elif(table[self.i]&＃61;&＃61;&＃39;-&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;M -> -E&＃39;)

            self.e()

        else:

            wenfa.append(&＃39;M -> E&＃39;)

            self.e()

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

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

            exit(0)

        else:

            print &＃39;\n字符串语法是&＃xff1a;&＃39;       #若一切正确&＃xff0c;则输出语法树文法

            for i in wenfa:

                print i

            print &＃39;语法正确&＃39;

    def e(self):     #PE程序

        wenfa.append(&＃39;E -> TE1&＃39;)

        self.t()

        self.e1()

    def e1(self):    #PE1程序

        if(table[self.i]&＃61;&＃61;&＃39;&＃43;&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;E1 -> &＃43;TE1&＃39;)

            self.t()

            self.e1()

        elif(table[self.i]&＃61;&＃61;&＃39;-&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;E1 -> -TE1&＃39;)

            self.t()

            self.e1()

        else:

            wenfa.append(&＃39;E1 -> &&＃39;)

    def t(self):      #PT程序

        wenfa.append(&＃39;T -> FT1&＃39;)

        self.f()

        self.t1()

    def t1(self):     #PT1程序

        if(table[self.i]&＃61;&＃61;&＃39;*&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;T1 -> *FT1&＃39;)

            self.f()

            self.t1()

        elif(table[self.i]&＃61;&＃61;&＃39;/&＃39;):

            self.i&＃43;&＃61;1

            wenfa.append(&＃39;T1 -> /FT1&＃39;)

            self.f()

            self.t1()

        else:

            wenfa.append(&＃39;T1 -> &&＃39;)

    def f(self):      #PF程序

        if(table[self.i]&＃61;&＃61;&＃39;(&＃39;):

            wenfa.append(&＃39;F -> (E)&＃39;)

            self.i&＃43;&＃61;1

            self.e()

            if(table[self.i]!&＃61;&＃39;)&＃39;):

                raise Exception

            self.i&＃43;&＃61;1

        elif(dic[table[self.i]]&＃61;&＃61;1):

            wenfa.append(&＃39;F -> Indentifer &＃39;&＃43;str(table[self.i]))

            self.i&＃43;&＃61;1

        elif(dic[table[self.i]]&＃61;&＃61;2):

            wenfa.append(&＃39;F -> Digit &＃39;&＃43;str(table[self.i]))

            self.i&＃43;&＃61;1

        else:

            raise Exception          #若均不符合&＃xff0c;则引出异常

 

 

 

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

 

class yuyi:

    def __init__(self):

        print &＃39;\n语义分析结果(四元式):&＃39;

        self.i&＃61;0    #栈指针

        self.flag&＃61;0    #记录临时变量T数目

        self.m()

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

            print i

    def m(self):        #PM程序

        if(table[self.i]&＃61;&＃61;&＃39;&＃43;&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.e()

            siyuan.append(&＃39;(&＃43;,0,&＃39;&＃43;ret1&＃43;&＃39;,out)&＃39;)

            self.flag&＃43;&＃61;1

        elif(table[self.i]&＃61;&＃61;&＃39;-&＃39;):

            self.i&＃43;&＃61;1

            ret2&＃61;self.e()

            siyuan.append(&＃39;(-,0,&＃39;&＃43;ret2&＃43;&＃39;,out)&＃39;)

            self.flag&＃43;&＃61;1

        else:

            ret3&＃61;self.e()

            siyuan.append(&＃39;(&＃61;,&＃39;&＃43;ret3&＃43;&＃39;,0,out)&＃39;)

    def e(self):        #PE程序

        ret1&＃61;self.t()

        ret2,ret3&＃61;self.e1()

        if(ret2!&＃61;&＃39;&&＃39;):      #若ret2不为&&＃xff0c;则可以产生四元式&＃xff0c;否则将变量传递给父项

            self.flag&＃43;&＃61;1

            siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

            return &＃39;T&＃39;&＃43;str(self.flag)

        else:

            return ret1

    def e1(self):           #PE1程序

        if(table[self.i]&＃61;&＃61;&＃39;&＃43;&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.t()

            ret2,ret3&＃61;self.e1()

            if(ret2&＃61;&＃61;&＃39;&&＃39;):

                return &＃39;&＃43;&＃39;,ret1

            else:

                self.flag&＃43;&＃61;1

                siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

                return &＃39;&＃43;&＃39;,&＃39;T&＃39;&＃43;str(self.flag)

        elif(table[self.i]&＃61;&＃61;&＃39;-&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.t()

            ret2,ret3&＃61;self.e1()

            if(ret2&＃61;&＃61;&＃39;&&＃39;):

                return &＃39;-&＃39;,ret1

            else:

                self.flag&＃43;&＃61;1

                siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

                return &＃39;-&＃39;,&＃39;T&＃39;&＃43;str(self.flag)

        else:

            return &＃39;&&＃39;,&＃39;&&＃39;

    def t(self):        #PT程序

        ret1&＃61;self.f()

        ret2,ret3&＃61;self.t1()

        if(ret2!&＃61;&＃39;&&＃39;):

            self.flag&＃43;&＃61;1

            siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

            return &＃39;T&＃39;&＃43;str(self.flag)

        else:

            return ret1

    def t1(self):       #PT1程序

        if(table[self.i]&＃61;&＃61;&＃39;*&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.f()

            ret2,ret3&＃61;self.t1()

            if(ret2&＃61;&＃61;&＃39;&&＃39;):

                return &＃39;*&＃39;,ret1

            else:

                self.flag&＃43;&＃61;1

                siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

                return &＃39;*&＃39;,&＃39;T&＃39;&＃43;str(self.flag)

        elif(table[self.i]&＃61;&＃61;&＃39;/&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.f()

            ret2,ret3&＃61;self.t1()

            if(ret2&＃61;&＃61;&＃39;&&＃39;):           #若ret2不为&&＃xff0c;则可以产生四元式&＃xff0c;否则将变量传递给父项

                return &＃39;/&＃39;,ret1

            else:

                self.flag&＃43;&＃61;1

                siyuan.append(&＃39;(&＃39;&＃43;ret2&＃43;&＃39;,&＃39;&＃43;ret1&＃43;&＃39;,&＃39;&＃43;ret3&＃43;&＃39;,T&＃39;&＃43;str(self.flag)&＃43;&＃39;)&＃39;)

                return &＃39;/&＃39;,&＃39;T&＃39;&＃43;str(self.flag)

        else:

            return &＃39;&&＃39;,&＃39;&&＃39;

    def f(self):        #PF程序

        if(table[self.i]&＃61;&＃61;&＃39;(&＃39;):

            self.i&＃43;&＃61;1

            ret1&＃61;self.e()

            self.i&＃43;&＃61;1

            return str(ret1)

        elif(dic[table[self.i]]&＃61;&＃61;1):        #当为标识符时&＃xff0c;传递给父项

            temp&＃61;self.i

            self.i&＃43;&＃61;1

            return table[temp]

        elif(dic[table[self.i]]&＃61;&＃61;2):        #当为整数时&＃xff0c;传递给父项

            temp&＃61;self.i

            self.i&＃43;&＃61;1

            return table[temp]

 

 

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

if __name__&＃61;&＃61;&＃39;__main__&＃39;:

    string&＃61;raw_input(&＃39;请输入表达式&＃xff1a;&＃39;)

    cifa(string)

    yufa()

    yuyi()

　　


推荐阅读
  • input

    扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

    扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]
    学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]
  • cpython

    Python 2022年面试题总结

    2022年Python面试题一.Python基础二.企业面试题结束语🥇🥇🥇✅作者简介：大家好我是编程IDὌ ... [详细]
  • copy

    编写有趣的VBScript恶作剧脚本

    本文将介绍如何编写一些有趣的VBScript脚本，这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例，帮助您了解VBScript的基本语法和功能。 ... [详细]
  • input

    技术分享：从动态网站提取站点密钥的解决方案

    技术分享：从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]
  • python

    Python 的 10 个开发技巧！太实用了

    1.如何在运行状态查看源代码？查看函数的源代码，我们通常会使用IDE来完成。比如在PyCharm中，你可以Ctrl+鼠标点击进入函数的源代码。那如果没有IDE呢？当我们想使用一个函 ... [详细]
  • input

    JQuery基础：省市联动与表单验证

    本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先，通过change事件监听用户选择的省份，并动态加载对应的城市列表。其次，详细讲解了使用Validation插件进行表单验证的方法，包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • input

    数据库内核开发入门 | 搭建研发环境的初步指南

    数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始，逐步掌握数据库内核开发的基础知识和实践技能，重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • split

    深入理解Python的os和sys模块

    本文详细解析了Python中的os和sys模块，介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]
  • python

    寻找满足特定条件的整数N的最大和(a+b)

    本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]
  • split

    解析Java中Text.splitText()方法及其应用场景

    本文详细介绍了Java中org.w3c.dom.Text类的splitText()方法，通过多个代码示例展示了其实际应用。该方法用于将文本节点在指定位置拆分为两个节点，并保持在文档树中。 ... [详细]
  • const

    Weight the Tree（树形dp）

    题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]
  • install

    基于KVM的SRIOV直通配置及性能测试

    基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置，以及包转发率性能测试小慢哥的原创文章，欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • install

    在Python 3环境中实现离线模块安装的方法与技巧

    在Python 3环境中，当无法连接互联网时，可以通过下载离线模块包来实现模块的安装。具体步骤包括：首先从PyPI网站下载所需的模块包，然后将其传输到目标环境，并使用`pip install`命令进行本地安装。此方法不仅适用于单个模块，还支持依赖项的批量安装，确保开发环境的完整性和一致性。 ... [详细]
  • cpython

    利用 PythonOCC 实现等间距周长分割的曲线分析与应用

    基于PythonOCC库，本文探讨了如何实现对曲线边（TopoDS_Edge）进行等间距周长分割的分析方法及其应用。通过使用BRepGProp模块中的线性属性计算功能，我们能够精确地将曲线分割成多个等长段，从而为后续的几何建模和工程应用提供基础支持。该方法不仅提高了曲线处理的效率，还增强了模型的准确性和可靠性。 ... [详细]
  • cpython

    PyTorch 2.0来了！100%向后兼容，一行代码将训练提速76%！

    PyTorch 2.0来了！100%向后兼容，一行代码将训练提速76%！
    点击下方卡片，关注“CVer”公众号AICV重磅干货，第一时间送达点击进入—CV微信技术交流群转载自：机器之心PyTorch官方 ... [详细]
author-avatar
清风2602939017
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有