编译原理 on 子恒的博客

[编译原理]Python实现的语义分析器

Tue, 27 Dec 2016 20:18:40 +0800

语义分析是编译系统的第三部分,负责赋值检查,表达式检查以及代码生成.

基本思想

代码沿用了上一部分的文法表, 利用递归下降算法对每一个非终结符写一个函数. 但是文法多达70多条, 工作量太大, 就只实现了赋值语句, 表达式, 条件语句这几个代表性的文法规则. 其他实现起来也类似, 多写几个函数即可.

函数介绍

需要注意的几个细节:

compare_var_type用于比较类型, 比较失败则raise一个CompileError
在生成代码过程中, 有的传入了其他的变量, 是为了回填
把if回填做成了label的方式, 可以在后阶段再处理
未初始化的变量调用也留给了后阶段处理.

函数表:

成员函数	对应非终结符	备注
init()		初始化
get_register()		分配寄存器
get_label_no()		分配记号
compare_var_type(var_type_1,var_type_2)		比较类型,raise错误
build_table(x)		建立符号表
check_factor(factor)	<因式>	用于检查
check_factors(factor)	<因式递归>	用于检查
check_factor_c(fc)	<因子>	用于检查
check_term(term)	<项>	用于检查
check_exp(x)	<表达式>	用于检查
check_stm(x)	<赋值函数>	用于检查
generate_factor(factor)	<因式>	用于生成
generate_factors(factors,factor)	<因式递归>	用于生成
generate_factor_c(fc)	<因子>	用于生成
generate_term(term,factor)	<项>	用于生成
generate_exp(x)	<表达式>	用于生成
generate_stm(x)	<赋值函数>	用于生成
generate_func_blocks(x)	<函数块闭包>	用于生成
generate_func_block(x)	<函数块>	用于生成
generate_else_block(x)	<否则语句>	用于生成
generate_logical(x)	<逻辑表达式>	用于生成
generate_if(x)	<条件语句>	用于生成
generate_code(tree)	<函数定义>	用于生成
dfs(tree,func)		搜索函数
run(code)		获取生成结果

文法表

<函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}]
<修饰词闭包>-><修饰词><修饰词闭包>
<修饰词闭包>->[@]
<修饰词>->[public]
<修饰词>->[private]
<修饰词>->[protected]
<类型>->[int]<取地址>
<类型>->[char]<取地址>
<类型>->[boolean]<取地址>
<类型>->[void]<取地址>
<取地址>-><星号><取地址>
<取地址>->[@]
<星号>->[*]
<变量>-><标志符><数组下标>
<标志符>->[id]
<数组下标>->[[]<因式>[]]
<数组下标>->[@]
<因式>->[(]<表达式>[)]
<因式>-><变量>
<因式>-><数字>
<数字>->[digit]
<表达式>-><因子><项>
<因子>-><因式><因式递归>
<因式递归>->[*]<因式><因式递归>
<因式递归>->[/]<因式><因式递归>
<因式递归>->[@]
<项>->[+]<因子><项>
<项>->[-]<因子><项>
<项>->[@]
<参数声明>-><声明><声明闭包>
<参数声明>->[@]
<声明>-><修饰词闭包><类型><变量><赋初值>
<赋初值>->[=]<右值>
<赋初值>->[@]
<右值>-><表达式>
<右值>->[{]<多个数据>[}]
<多个数据>-><数字><数字闭包>
<数字闭包>->[,]<数字><数字闭包>
<数字闭包>->[@]
<声明闭包>->[,]<声明><声明闭包>
<声明闭包>->[@]
<函数块>-><声明语句闭包><函数块闭包>
<声明语句闭包>-><声明语句><声明语句闭包>
<声明语句闭包>->[@]
<声明语句>-><声明>[;]
<函数块闭包>-><赋值函数><函数块闭包>
<函数块闭包>-><for循环><函数块闭包>
<函数块闭包>-><条件语句><函数块闭包>
<函数块闭包>-><函数返回><函数块闭包>
<函数块闭包>->[@]
<赋值函数>-><变量><赋值或函数调用>
<赋值或函数调用>->[=]<右值>[;]
<赋值或函数调用>->[(]<参数列表>[)][;]
<参数列表>-><参数><参数闭包>
<参数闭包>->[,]<参数><参数闭包>
<参数闭包>->[@]
<参数>-><标志符>
<参数>-><数字>
<参数>-><字符串>
<字符串>->[string]
<for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}]
<逻辑表达式>-><表达式><逻辑运算符><表达式>
<逻辑运算符>->[<]
<逻辑运算符>->[>]
<逻辑运算符>->[==]
<逻辑运算符>->[!=]
<后缀表达式>-><变量><后缀运算符>
<后缀运算符>->[++]
<后缀运算符>->[--]
<条件语句>->[if][(]<逻辑表达式>[)][{]<函数块>[}]<否则语句>
<否则语句>->[else][{]<函数块>[}]
<否则语句>->[@]
<函数返回>->[return]<因式>[;]

代码实现

知道了思路还是很好读的, 无非是看每个非终结符对应了哪条规则, 再利用分支调用对应的分支.

[编译原理]Python实现的语法分析器

Tue, 27 Dec 2016 01:20:24 +0800

语法分析器是这套编译系统的第二部分,可以直接用上一篇中的词法分析器的结果继续做语法分析.

文法表

= =一直没时间更, 直到考试周格外闲…
借鉴了一个网络上的文法表, 覆盖了一些基础的C文法, 测试后发现该文法是LL(1)文法.
文法如下:

<函数定义>-><修饰词闭包><类型><变量>[(]<参数声明>[)][{]<函数块>[}]
<修饰词闭包>-><修饰词><修饰词闭包>
<修饰词闭包>->[@]
<修饰词>->[public]
<修饰词>->[private]
<修饰词>->[protected]
<类型>->[int]<取地址>
<类型>->[char]<取地址>
<类型>->[boolean]<取地址>
<类型>->[void]<取地址>
<取地址>-><星号><取地址>
<取地址>->[@]
<星号>->[*]
<变量>-><标志符><数组下标>
<标志符>->[id]
<数组下标>->[[]<因式>[]]
<数组下标>->[@]
<因式>->[(]<表达式>[)]
<因式>-><变量>
<因式>-><数字>
<数字>->[digit]
<表达式>-><因子><项>
<因子>-><因式><因式递归>
<因式递归>->[*]<因式><因式递归>
<因式递归>->[/]<因式><因式递归>
<因式递归>->[@]
<项>->[+]<因子><项>
<项>->[-]<因子><项>
<项>->[@]
<参数声明>-><声明><声明闭包>
<参数声明>->[@]
<声明>-><修饰词闭包><类型><变量><赋初值>
<赋初值>->[=]<右值>
<赋初值>->[@]
<右值>-><表达式>
<右值>->[{]<多个数据>[}]
<多个数据>-><数字><数字闭包>
<数字闭包>->[,]<数字><数字闭包>
<数字闭包>->[@]
<声明闭包>->[,]<声明><声明闭包>
<声明闭包>->[@]
<函数块>-><声明语句闭包><函数块闭包>
<声明语句闭包>-><声明语句><声明语句闭包>
<声明语句闭包>->[@]
<声明语句>-><声明>[;]
<函数块闭包>-><赋值函数><函数块闭包>
<函数块闭包>-><for循环><函数块闭包>
<函数块闭包>-><条件语句><函数块闭包>
<函数块闭包>-><函数返回><函数块闭包>
<函数块闭包>->[@]
<赋值函数>-><变量><赋值或函数调用>
<赋值或函数调用>->[=]<右值>[;]
<赋值或函数调用>->[(]<参数列表>[)][;]
<参数列表>-><参数><参数闭包>
<参数闭包>->[,]<参数><参数闭包>
<参数闭包>->[@]
<参数>-><标志符>
<参数>-><数字>
<参数>-><字符串>
<字符串>->[string]
<for循环>->[for][(]<赋值函数><逻辑表达式>[;]<后缀表达式>[)][{]<函数块>[}]
<逻辑表达式>-><表达式><逻辑运算符><表达式>
<逻辑运算符>->[<]
<逻辑运算符>->[>]
<逻辑运算符>->[==]
<逻辑运算符>->[!=]
<后缀表达式>-><变量><后缀运算符>
<后缀运算符>->[++]
<后缀运算符>->[--]
<条件语句>->[if][(]<逻辑表达式>[)][{]<函数块>[}]<否则语句>
<否则语句>->[else][{]<函数块>[}]
<否则语句>->[@]
<函数返回>->[return]<因式>[;]

Grammar.py

典型的LL(1)的分析过程, 构造NULLABLE集, FIRST集, FOLLOW集, 计算SELECT集,最后画出预测分析表, 生成AST.
其中simplify_tree是用来递归简化树上的节点的.
代码很好读,都是华老师课件上的步骤.

[编译原理]Python实现的词法分析器

Tue, 15 Nov 2016 11:02:42 +0800

最近在上华保健老师的课, 在学习的过程中做了一套编译系统, 外加顺便应付学校的作业. 这个词法分析器是这套编译系统的第一部分.

其中RE到DFA, DFA到NFA的部分都是手工完成, 自己规定token格式(C语言格式), 得到一个NFA.
课程内容详见:
编译原理MOOC

算法都是课程中的算法, 不再详述.伪代码可以在华老师的课件中找到.

state_machine.json

第一部分是手写的DFA, 用类似树状数组的方式存储.

几个Key的含义如下:

SS: 起始状态
FS: 接受状态
I: 接受字符
T: 转换表   //如"8": {"3": 10, "5": 9}表示状态8输入I[3]可以转换到状态10, 状态8输入I[3]可以转换到状态9
S: 状态表    //下标对应的状态的含义

json文件:

state_machine.json

Driver.py

驱动文件,分析结果为三元组**(标识符, 内容, 行数)**的序列.

#!/usr/bin/env python3

import json


class Driver:
    STATE_MACHINE = None
    content_symbols = ['id', 'digit']
    line_no = 0
    NOW_POINT = -1
    PREV_POINT = -1
    STRING = ''
    uncommit = ''
    token_list = []

    def __init__(self, file_name):
        with open(file_name, 'r') as f:
            self.STATE_MACHINE = json.load(f)

    # reset
    def reset(self):
        self.STRING = ''
        self.uncommit = ''
        self.token_list.clear()
        self.NOW_POINT = -1    #当前分析的字符下标
        self.PREV_POINT = -1   #用于获得标识符对应的内容
        self.line_no = 0

    # next char of string
    def next_ch(self):
        self.NOW_POINT += 1
        if self.NOW_POINT < len(self.STRING):
            return self.STRING[self.NOW_POINT]
        else:
            return None

    # rollback
    def rollback(self):
        self.NOW_POINT -= 1

    # drive code
    def next_token(self):
        state = "0"
        stack = []
        # get a token
        while True:
            c = self.next_ch()
            if c is None:
                return False
            # accept state
            if int(state) in self.STATE_MACHINE["FS"]:
                stack.clear()
            stack.append(state)
            # state change or state error
            num = None
            for i in range(0, len(self.STATE_MACHINE["I"])):
                if c in self.STATE_MACHINE["I"][i]:
                    num = i
            if num is None:
                return False
            # not accepted
            try:
                state = str(self.STATE_MACHINE["T"][state][str(num)])
            except KeyError:
                break
        state = stack.pop(-1)
        self.rollback()
        # get idn and token
        idn = self.STATE_MACHINE['S'][int(state)]
        name = self.STRING[self.PREV_POINT + 1:self.NOW_POINT + 1]
        if idn != 'SPACE':
            self.token_list.append({'symbol': idn, 'raw_data': name, 'line_no': self.line_no})

        self.PREV_POINT = self.NOW_POINT
        return True

    # print token to uncommit
    def print_token(self):
        for v in self.token_list:
            self.uncommit += v['raw_data'] + '\t< ' + v['symbol']
            if v['symbol'] in self.content_symbols:
                self.uncommit += ' , ' + v['raw_data'] + '>' + '\n'
            else:
                self.uncommit += ' , - >' + '\n'

    # run a string
    def run(self, string):
        self.reset()
        STRING_ARRAY = string.replace('\t', '').split('\n')
        for v in STRING_ARRAY:
            self.NOW_POINT = -1
            self.PREV_POINT = -1
            self.line_no += 1
            self.STRING = v + ';'
            while True:
                if not self.next_token():
                    break
        self.print_token()


if __name__ == '__main__':
    d = Driver('state_machine.json')
    d.run('while(num!=100)\n{\nnum++;\n}\n')    #简短的示例
    print(d.uncommit)
    print(d.token_list)
    d.run('n++')
    print(d.uncommit)
    print(d.token_list)