利用EBNF语法解析实现简单的数学表达式计算

发表于 | 分类于 ，

  当你想根据一组语法规则解析文本并执行命令时，我们可以先以BNF或者EBNF形式指定一个标准语法，再根据正则规则将文本分解为一组令牌流，然后根据(E)BNF语法依次处理令牌流。

1. EBNF简介

  EBNF(Extended Backus–Naur Form,扩展的巴克斯范式)是一种用于描述计算机编程语言等正式语言的与上下文无关语法的元语法(metasyntax)符号表示法。简而言之，它是一种描述语言的语言。

  EBNF一条规则基本书写规范如下：

symbol ::= alternative1 | alternative2 ...

出现在规则左边的符号称为非终端，终端用双引号或单引号包裹起来。
BNF中有一个特殊符号“@”，表示符号可以去掉。如果用@替换符号，只需要将符号去掉。

记号 意义
[…] 可选
{…}* 重复,*表示重复0次或多次，和正则中一致。(?出现0次或1次，+出现至少1次)
(…) 分组
| 并列选项，只能选一个
“…” 终端字符串
‘…’ 终端字符串

例如，用EBNF定义实数：

S := '-' FN | FN 
FN := DL FP 
FP := @ | '.' DL 
DL := D DR 
DR := D DR | @ 
D := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

2. 解析文本为令牌流

2.1 先将文本分割成最小处理单元，同一类单元称为同一个Token，为所有Token定义匹配模式，并使用?P<TOKENNAME>指定模式名称。
例如,对于'foo = 23 + 43 * 10'定义匹配模式如下： 

1
2
3
4
5
6
7
8
import re
NAME = r'(?P<NAME>[a-zA-Z_][a-zA-Z_0-9]*)'
NUM = r'(?P<NUM>\d+)'
PLUS = r'(?P<PLUS>\+)'
TIMES = r'(?P<TIMES>\*)'
EQ = r'(?P<EQ>=)'
WS = r'(?P<WS>\s+)'
master_pat = re.compile('|'.join([NAME, NUM, PLUS, TIMES, EQ, WS]))

2.2 根据上面生成的模式规则，将文本扫描成令牌流

1
2
3
4
5
6
7
8
from collections import namedtuple
Token = namedtuple("Token",["type","value"])

def generate_tokens(text):
    scanner = master_pat.scanner(text)
    for m in iter(scanner.match,None):
        if m.lastgroup != 'WS':
            yield Token(m.lastgroup,m.group())

说明：

  • re.Pattern对象的scanner()方法返回<class '_sre.SRE_Scanner'>类型对象
  • <class '_sre.SRE_Scanner'>类型对象拥有match()方法,该方法类似于可迭代对象中的__next__()方法，每次调用根据匹配顺序依次返回一个匹配到的re.Match对象。直到文本内容结束或者碰到文本中存在不可匹配的内容时，扫描结束，返回None
  • re.Match对象拥有属性lastgroup保存分组组名(即?P<TOKENNAME>...中的TOKENNAME)；拥有方法 group() 返回匹配到的文本内容
  • iter(object[, sentinel])如果没有传入第二个参数，则第一个参数需传入一个序列对象,例如list,str等等; 如果传入第二个参数，则第一个参数需传入可调用对象或方法，且其支持多次调用，直到调用返回值等于sentinel时，调用结束

3. 源码如下：

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
import re
from collections import namedtuple

DECIMAL = r'(?P<DECIMAL>\d+(\.\d+)?)'
PLUS = r'(?P<PLUS>\+)'
MINUS = r'(?P<MINUS>-)'
MULTI = r'(?P<MULTI>\*)'
DIVIDE = r'(?P<DIVIDE>/)'
LPAREN = r'(?P<LPAREN>\()'
RPAREN = r'(?P<RPAREN>\))'
WS = r'(?P<WS>\s+)'

master_pat = re.compile('|'.join([DECIMAL,PLUS,MINUS,MULTI,DIVIDE,LPAREN,RPAREN,WS]))

Token = namedtuple("Token",["type","value"])

def generate_tokens(text):
    scanner = master_pat.scanner(text)
    for m in iter(scanner.match,None):
        if m.lastgroup != 'WS':
            yield Token(m.lastgroup,m.group())

class mathExpressionEvaluator:
    '''
    支持实数范围内的加减乘数表达式计算。
    parse 方法接受表达式字符串，并返回计算结果.
    _accept 方法判断是否存在下一个token,并返回True或者False
    '''

    def parse(self,text):
        self.tokens = generate_tokens(text)
        self.tok = None
        self.nextTok = None
        self._getTok()
        return self.expr()

    def _getTok(self):
        self.tok,self.nextTok = self.nextTok,next(self.tokens,None)

    def _accept(self,toktype):
        if self.nextTok and self.nextTok.type==toktype:
            self._getTok()
            return True
        else:
            return False

    def _expected(self,toktype):
        if not self._accept(toktype):
            raise SyntaxError('Expected '+ toktype)



    """
    加减乘除表达式的 EBNF 语法规则:
        expr ::= term { (+|-)term }*
        term ::= factor { (*|/)factor }*
        factor ::= DECIMAL | (expr) 
    """
    def expr(self):
        expr_val = self.term()
        while self._accept("PLUS") or self._accept("MINUS"):
            op = self.tok.type
            right = self.term()
            if op=="PLUS":
                expr_val += right
            elif op == "MINUS":
                expr_val -= right
        return expr_val

    def term(self):
        term_val = self.factor()
        while self._accept("MULTI") or self._accept("DIVIDE"):
            op = self.tok.type
            right = self.factor()
            if op == "MULTI":
                term_val *= right
            elif op == "DIVIDE":
                term_val /= right
        return term_val

    def factor(self):
        if self._accept("DECIMAL"):
            return float(self.tok.value)
        elif self._accept("LPAREN"):
            factor_val = self.expr()
            self._expected("RPAREN")
            return factor_val
        else:
            raise SyntaxError('Expected DECIMAL or LPAREN')

def descent_parser():
    e = mathExpressionEvaluator()
    expressionList = ['2','2 + 3.5','6 + 1.5 * (3 - 1)','10 / (5 - 3) * (3 + 5)']
    for expression in expressionList:
        print('{} = {}'.format(expression,e.parse(expression)))

if __name__ == '__main__':
    descent_parser()