一个基于约束传播的微型计算语言的设计和实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
变量is-a表达式
数值is-a表达式
故有如下继承关系

通过env的符号表可以查到Expr的实例
"""
__all__ = ['Expr','Var','Number']

class Expr(object):
    op=""               #a function
    parameters=[]       #Expr list
    desc=""

    def __init__(self,op,paras,desc=""):
        self.op=op
        self.parameters=paras
        self.desc=desc

    def get_value(self):
        pl=[p.get_value() for p in self.parameters]
        return self.op(*pl)

    def set_desc(self,d):
        self.desc=d

    def dump(self):
        pas=[]
        if len(self.parameters):
            pas=[s.dump() for s in self.parameters]
        pas.insert(0, '('+self.op.__name__)
        return ' '.join(pas) + ')'


class Number(Expr):
    value=0.0
    def __init__(self,v):
        self.value=v

    def get_value(self):
        return self.value

    def dump(self):
        return str(self.value)

    def update(self):
        pass

class Var(Expr):
    name=""
    desc=""
    expr=None
    value=0.0
    subscribers=[]
    state="invaild"

    def __init__(self,name,desc=""):
        self.name=name
        self.desc=desc
        self.state="invaild"

    def broadcast(self):
        for s in self.subscribers:
            s.update()

    def update(self):
        self.state="normal"
        new_value=self.expr.get_value()
        if new_value == self.value:
            return
        self.value=new_value
        self.broadcast()

    def set_expr(self,exp):
        self.expr=exp
        if isinstance(exp,Number):
            self.update()

    def set_value(self,v):
        self.value=v
        self.state="normal"
        self.broadcast()

    def get_value(self):
        if self.state=="invaild":
            self.update()
        assert self.state=="normal"
        return self.value

    def subscribe(self,subs):
        for sub in subs:
            self.subscribers.append(sub)

    def dump(self):
        expr_d=""
        if self.expr:
            expr_d=' '+self.expr.dump()
        return str(self.name) +"="+str(self.value)+expr_d#+" "+self.desc


def test():
    a=Var("a","变量a")
    b=Var("b","变量b")

if __name__=="__main__":
    test()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import operator
from expr import Var,Number,Expr
from parser import Parser

class CmdFilter(object):
    def __init__(self,env,input_file):
        self.env=env
        self.input_file=input_file

    def readline(self):
        while True:
            s=self.input_file.readline()
            if not s:
                return s
            if self.env.filter_cmd(s):
                return s

class Env(object):
    """
    求值环境，提供变量符号表和函数符号表
    """
    symbol_table={} #存放变量
    expr_table=[]   #存放自由表达式
    function_table={}#存放函数，对外只读
    cmds=['dump','run']    #env先于parser处理掉一些命令,如dump
    parser=None

    def __init__(self):
        self.fill_function_table()
        self.fill_symbol_table()
        self.parser=Parser(self)

    def dump(self):
        print "-"*70,"\ndump all variables and expressions:"
        for k,v in self.symbol_table.items():
            print k+":",v.get_value()
        print "\nall checkings:"
        for e in self.expr_table:
            print e.get_value(),"=",e.dump()
        print "-"*70

    def run(self):
        for k,v in self.symbol_table.items():
            v.update()

    def fill_function_table(self):
        #算术运算符
        #1.+,-,*,/,^,=,(,)   算术运算符
        self.function_table['+']=operator.add
        self.function_table['-']=operator.sub
        self.function_table['*']=operator.mul
        self.function_table['/']=operator.div
        self.function_table['^']=operator.pow
        #逻辑运算符
        #2.==,>=,>,<=,<,!=   逻辑运算符
        self.function_table['==']=operator.eq
        self.function_table['>=']=operator.ge
        self.function_table['>']=operator.gt
        self.function_table['<=']=operator.le
        self.function_table['<']=operator.lt
        self.function_table['!=']=operator.ne
        self.function_table['sqrt']=math.sqrt
        self.function_table['sin']=math.sin
        self.function_table['cos']=math.cos
        self.function_table['tan']=math.tan
        self.function_table['asin']=math.asin
        self.function_table['acos']=math.acos
        self.function_table['atan']=math.atan
        self.function_table['exp']=math.exp
        self.function_table['pow']=math.pow
        self.function_table['factorial']=math.factorial
        self.function_table['fabs']=math.fabs
        self.function_table['ln']=math.log
        self.function_table['log10']=math.log10


    def fill_symbol_table(self):
        self.symbol_table['pi']=Number(math.pi)
        self.symbol_table['e'] =Number(math.e)

    def add_expr(self,e):
        if e:
            self.expr_table.append(e)

    def get_function(self,name):
        if self.function_table.has_key(name):
            return self.function_table[name]
        else:
            return None

    def get_variable(self,name):
        if self.symbol_table.has_key(name):
            return self.symbol_table[name]
        else:
            return None

    def set_variable(self,name,var):
        self.symbol_table[name]=var

    def filter_cmd(self,s):
        s=s.strip()
        if s in self.cmds:
            fun=getattr(self,s)
            fun()
            return None
        return s

    def exec_stream(self,in_file):
        input_file=CmdFilter(self,in_file)
        self.parser.parse(input_file)

import sys
def test():
    env=Env()
    env.exec_stream(sys.stdin)

if __name__=="__main__":
    test()

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from math import *
from operator import *
import re
from expr import Var,Number,Expr

""" 把
a=1+b+c^2
c=2
b=c+2
这样的一行一行，分成
ID ASSIGN ADD ID ADD EQ POW 2 EOL
ID ASSIGN 2 EOL
ID ASSIGN ID ADD 2 EOL
这样的一行一行token,
输出是一行一个token list的形式

token分为如下几类:
1.+,-,*,/,^,=,(,),,   算术运算符
2.==,>=,>,<=,<,!=   逻辑运算符
3.[0-9]+\.[0-9]*[Ee][+-]?[0-9]+  [0-9]+ 字面浮点数和整数
4.[a-zA-Z_]+        变量或函数名称标识符
5.[ \\t\\n]           忽略，或结束

由于使用正则表达式直接匹配，所以和flex不同的是:
无法确保当有多个匹配项时，最长优先,因此，只能利用先后顺序解决冲突，
因而必须把==放在=前面。
"""
logic_op_re=re.compile(r'==|>=|>|<=|<|!=')
number_re  =re.compile(r'[+-]?[0-9]+\.?[0-9]*[Ee]?[+-]?[0-9]?') 
arith_op_re=re.compile(r'\+|-|\*|/|\^|=|\(|\)|,')
int_re     =re.compile(r'[0-9]+')
id_re      =re.compile(r'[a-zA-Z_]+')
blank_re   =re.compile(r'[\ |\t|\r]+')
comment_re =re.compile(r'"([^"]*)"')
other_re   =re.compile(r'.+')

def scanner(line):
    result=[]
    while True:
        line=line.strip()
        if not line:
            return result

        m=re.match(logic_op_re,line)
        if m:
            result.append(('logic_op',m.group()))
            line=line[m.end():]
            continue

        m=re.match(number_re  ,line)
        if m:
            result.append(('number',float(m.group())))
            line=line[m.end():]
            continue

        m=re.match(arith_op_re,line)
        if m:
            result.append(('arith_op',m.group()))
            line=line[m.end():]
            continue

        m=re.match(int_re     ,line)
        if m:
            result.append(('number',float(m.group())))
            line=line[m.end():]
            continue

        m=re.match(id_re      ,line)
        if m:
            result.append(('id',m.group()))
            line=line[m.end():]
            continue

        m=re.match(comment_re ,line)
        if m:
            result.append(('comment',m.group()))
            line=line[m.end():]
            continue

        m=re.match(blank_re   ,line)
        if m:
            line=line[m.end():]
            continue

        m=re.match(other_re,line)
        if m:
            print "亲，看看你都塞了一堆什么进来呀？\""+m.group()+"\" 人家好伤心的呀！" 
            line=line[m.end():]
            return result

class Parser(object):
    """ 文法分析： """
    input_file=None
    env=None

    def __init__(self,env):
        self.env=env

    def parse(self,input_file):
        """
        如入可以是sys.stdin,a file,a string
        要求实现readline()方法
        """
        self.input_file=input_file
        self.run()

    def run(self):
        while True:
            line=self.input_file.readline()
            if not line:
                return
            tokens=scanner(line)

            #把字母名称的函数标示出来
            r=[]
            for t in tokens:
                if t[0]=='id' and self.env.get_function(t[1]):
                    r.append(('function',t[1]))
                else:
                    r.append(t)

            tokens=r

            #把comment提取出来
            comments=map(lambda x:x[1],
                         filter(lambda x:x[0]=="comment",tokens))
            comments=' '.join(comments)
            tokens=filter(lambda x:x[0]!="comment",tokens)

            #含有=的表达式是约束方程，其它的都是expr
            c=tokens.count( ('arith_op', '='))
            if c==0:
                #没有约束到变量的表达式
                e=self.parse_expr(tokens)
                #e.set_desc(comments)
                self.env.add_expr(e)
                continue

            if c>1:
                print "亲，赋值一次就够了，你肿么赋值了"+str(c)+"次涅？"
                continue

            #c=1
            if len(tokens)<3 or tokens[0][0]!='id' or \
               tokens[1]!=('arith_op','='):
                print "亲，你给我的表达式格式有问题偶～:"+line
                continue

            var_name=tokens[0][1]
            var=self.env.get_variable(var_name) 
            if var is None:
                var=Var(var_name,comments)
                self.env.set_variable(var_name,var)

            e=self.parse_expr(tokens[2:])
            var.set_expr(e)

    def parse_expr(self,tokens):
        """
        token分为如下几类:
        1.+,-,*,/,^,=,(,),,   算术运算符
        2.==,>=,>,<=,<,!=   逻辑运算符
        3.[0-9]+\.[0-9]*[Ee][+-]?[0-9]+  [0-9]+ 字面浮点数和整数
        4.[a-zA-Z_]+        变量或函数名称标识符
        5.[ \\t\\n]           忽略，或结束

        BNF:
        expr=expr[==|>=|>|<=|<|!=]expr|expr
        expr=expr+expr | expr-expr
        expr=expr*expr | expr/expr
        expr=expr^expr
        expr=function(expr[,expr])
        expr=(expr)
        expr=<float>|<var>
        """
        if len(tokens):
            expr,rest=self.parse_logic_op(tokens)
            return expr

    #能处理就处理，不能处理原样返回。
    def parse_logic_op(self,tokens):
        left,rest=self.parse_add_sub_op(tokens)
        if not len(rest):
            return left,rest

        logic_op_list=["==",">=",">","<=","<","!="]

        if rest[0][1] not in logic_op_list:
            return left,rest

        op=self.env.get_function(rest[0][1])
        right,rest=self.parse_add_sub_op(rest[1:])
        return Expr(op,[left,right]),rest

    def parse_add_sub_op(self,tokens):
        left,rest=self.parse_mul_div_op(tokens)
        add_sub_op_list=["+","-"]

        while len(rest) and rest[0][1] in add_sub_op_list:
            op=self.env.get_function(rest[0][1])
            right,rest=self.parse_mul_div_op(rest[1:])
            left=Expr(op,[left,right])

        return left,rest

    def parse_mul_div_op(self,tokens):
        left,rest=self.parse_pow_op(tokens)
        mul_div_op_list=["*","/"]

        while len(rest) and rest[0][1] in mul_div_op_list:
            op=self.env.get_function(rest[0][1])
            right,rest=self.parse_pow_op(rest[1:])
            left=Expr(op,[left,right])

        return left,rest

    def parse_pow_op(self,tokens):
        left,rest=self.parse_function_op(tokens)
        pow_op_list=["^"]

        while len(rest) and (rest[0][1] in pow_op_list):
            op=self.env.get_function(rest[0][1])
            right,rest=self.parse_pow_op(rest[1:])
            left=Expr(op,[left,right])
        return left,rest

    def parse_function_op(self,tokens):
        if tokens[0][0] in ['number','id']:
            return self.parse_float_var_op(tokens)
        if tokens[0][1]=='(':
            return self.parse_parentheses_op(tokens)

        if tokens[0][0]!='function':
            return None,tokens

        op=self.env.get_function(tokens[0][1])
        if op and tokens[1][1]=='(':
                paras=[]
                tokens=tokens[2:]
                left,tokens=self.parse_add_sub_op(tokens)
                paras.append(left)
                while tokens[0][1]==',':
                    left,tokens=self.parse_add_sub_op(tokens[1:])
                    paras.append(left)
                if tokens[0][1]==')':
                    tokens=tokens[1:]
                else:
                    print "bad syntax. tokens found ->",tokens

                expr=Expr(op,paras)
                return expr,tokens
        else:
            print "error bad syntax ->",tokens
        return None,tokens

    def parse_parentheses_op(self,tokens):
        if tokens[0][1]=='(':
            left,tokens=self.parse_logic_op(tokens[1:])
            if tokens[0][1]==')':
                return left,tokens[1:]
            return left,tokens
        return None,tokens

    def parse_float_var_op(self,tokens):
        if tokens[0][0] == 'number':
            n=Number(tokens[0][1])
            return n,tokens[1:]
        if tokens[0][0] == 'id':
            var=self.env.get_variable(tokens[0][1]) 
            if not var:
                var_name=tokens[0][1]
                var=Var(var_name,'')
                self.env.set_variable(var_name,var)
                var=self.env.get_variable(tokens[0][1]) 
            return var,tokens[1:]
        return None,tokens


import StringIO
from env import *
def test():
    s=""" a=1+(b+c)^2/23.1e-10 "变量a"
    c=2  "变量c" "c是个好变量"
    b=c+2 "变量b" "b也是个好变量" "这是为它写的第三条注释"
    a>c  "检查a是否大于c"
    a>=c  "检查a是否大于等于c"
    run
    dump
    c=3   "change c again."
    "注释也可以在前面" c^2>=sin(pow(a,b)+b)
    run
    dump
    """
    #for l in s.split('\n'):
    #    scanner(l)
    print "+"*80
    print '*'*70
    print s
    print '*'*70
    e=Env()
    i=StringIO.StringIO(s)
    e.exec_stream(i)
    print "+"*80

if __name__=="__main__":
    test()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys
from env import Env
import StringIO

e=Env()
e.exec_stream(sys.stdin)

s=""" x=-1"""
i=StringIO.StringIO(s)
e.exec_stream(i)