程序的语法

发表于 | 0 comments | 阅读次数

『我不生产代码，我只是代码的搬运工。』当然了，这是一个玩笑。说到代码，我们要学习各种编程语言，学习如何让编译器能懂我们编写的代码。但是，编译器是如何做到能听懂我们的话的呢？按照我们既定的语句一行行的去执行，最终达到我们的目的。这篇文章，我会讲一个很简单的四则运算解释器，通过使用 Python 实现它来一步步了解一个解释器是如何工作的，它们又是怎么得到我们想要的结果的。

#语法

计算机语言同样也是一种语言，是一种计算机能够理解的语言，我们想要和计算机对话，就要去学习这种语言。和我们人类的语言一样，计算机语言也是有语法的。以汉语为例，我说『我是中国人』，因为汉语的语法，你听到这句话之后会知道『我』是主语，『是』是谓语，『中国人』是宾语，同时你又很清楚每一个成分的含义，最终理解了整句话的意思。

同样，对于计算机语言也是一样，有着程序的语法，一个解释器知道哪个词是操作数，哪个是操作符，哪个是关键字，它们都有着怎样的含义和功能，通过解释器的解释，计算机明白了某行语句的意义，然后进行运算，得到最后的执行结果。

#语法图

语法图就是用来表示一种编程语言语法规则设计的示意图，它很直观的显示出了在一种编程语言中，允许使用的语句和不支持的语句。语法图十分易于阅读：只需跟随箭头指示的路径。一些路径表示选择。另一些路径表示循环。

##一个简单的语法图

这里我们举一个语法图的例子：

image

这个语法图就是一个描述了简单的加减运算的语法图，term 在其中的意思就是一个操作数，一开始输入一个操作数，有三条路径可以选择『+』，『-』和退出，如果进入了『+』、『-』路径，则需要再输入一个操作数，之后的路径包括『+』、『-』和退出，如此循环，就能解释一个简单的加减法解释器。

根据上边的语法图，下面的表达式都是合法的：

  • 4
  • 1 + 1
  • 1 + 4 - 3

下面的表达式不合法：

  • -
  • + -
  • 2 +
  • + 3 - 3

语法图可以帮助我们：

  • 用图的方式表示出一种计算机语言的设计规范
  • 可以帮助理解解释器，将图表表示成代码

##代码实现（Python）

学习一样东西最简单的就是阅读代码（Read the Fucking Code！），因此我们先来看完整代码然后再来分析一下，完整代码在：https://github.com/luoyhang003/Pascal-Interpreter/blob/master/calc3.py

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
# Token Types:
# EOF: End-Of-File

INTEGER, PLUS, MINUS, EOF = 'INTEGER', 'PLUS', 'MINUS', 'EOF'

class Token(object):
    def __init__(self, type, value):
        # Token types: INTEGER, PLUS, MINUS, EOF
        self.type = type
        # Token value: 0,1,2,3,4,5,6,7,8,9,+,None
        self.value = value

    def __str__(self):
        """
        The format of the print infomation
        For examle:
        Token(INTEGER, 3)
        Token(PLUS, '+')
        Token(MINUS, '-')
        """
        return 'Token({type},{value})'.format(
                type = self.type,
                value = repr(self.value)
                )

    def __repr__(self):
        return self.__str__()
    
class Interpreter(object):
    def __init__(self, text):
        # Process the whole input
        # e.g. 3+5
        self.text = text
        self.pos = 0
        self.current_token = None
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Error Parsing Error!')

    def advance(self):
        # Advance the pos and set current_char
        self.pos += 1

        if self.pos > len(self.text)-1:
            self.current_char = None
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):
        # Skip space
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):
        # Support mutidigit integer
        result = ''
        
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        
        return int(result)

    def get_next_token(self):
        """
        Lexical Analyzer:
        Parsing the input into tokens.
        Strategy:
        1. is pos past the end of the text?
        2. if so, return EOF
        3. get a character at pos, and decide its type depends on the single char
        4. if it is a space, advance the pos
        5. if it is a digit, then convert it to integer and return INTEGER token
        6. if it is a '+', then return PLUS token
        7. if it is a '-', then return MINUS token
        """

        while self.current_char is not None:

            if self.pos > len(self.text) - 1:
                return Token(EOF, None)

            current_char = self.text[self.pos]

            if current_char.isspace():
                self.skip_whitespace()
                continue

            if current_char.isdigit():
                return Token(INTEGER, self.integer())

            if current_char == '+':
                self.advance()
                return Token(PLUS, '+')

            if current_char == '-':
                self.advance()
                return Token(MINUS, '-')
            
        
            self.error()

        return Token(EOF, None)

    def eat(self, token_type):
        # compare the current token with the passed token type
        # if they match then eat the current token and assign next token to the self.current_token
        # otherwise raise an Exception

        if self.current_token.type == token_type:
            self.current_token = self.get_next_token()
        else:
            self.error()

    def term(self):
        # return an Integer Token's value
        token = self.current_token
        self.eat(INTEGER)
        return token.value

    

    
    
    def expr(self):
        # expr -> INTEGER PLUS INTEGER
        # expr -> INTEGER MINUS INTEGER
        
        self.current_token = self.get_next_token()

        result = self.term()

        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            if token.type == PLUS:
                self.eat(PLUS)
                result += self.term()
            if token.type == MINUS:
                self.eat(MINUS)
                result -= self.term()

        return result
    
def main():
    while True:
        try:
            text = raw_input('cal> ')
        except EOFError:
            break
        if not text:
            continue

        interpreter = Interpreter(text)
        result = interpreter.expr()
        print(result)

if __name__ == '__main__':
    main()

在代码中，我们首先定义了四种 Token：整数（Integer）、加法（+）、减法（-）、终止符（EOF）

代码中主要分为几个主要部分：

  • term 方法，在表达式中解析出一个整数
1
2
3
4
5
def term(self):
    # return an Integer Token's value
    token = self.current_token
    self.eat(INTEGER)
    return token.value
  • expr 方法，根据语法图的流程来解析语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def expr(self):
    # expr -> INTEGER PLUS INTEGER
    # expr -> INTEGER MINUS INTEGER
    
    self.current_token = self.get_next_token()

    result = self.term()

    while self.current_token.type in (PLUS, MINUS):
        token = self.current_token
        if token.type == PLUS:
            self.eat(PLUS)
            result += self.term()
        if token.type == MINUS:
            self.eat(MINUS)
            result -= self.term()

    return result

expr 方法，首先调用 term 方法获取一个整数，然后判断后边的 Token 是加法还是减法，之后再获取一个整数，然后进行运算，然后判断之后还有没有运算符，如果没有就返回结果，如果还有就重复以上步骤。我们看到 expr 方法是严格按照语法图进行解释的。

##执行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cal> 1+2
3
cal> 1+4-3
2
cal> 1+ 5 -6
0
cal> 1 +
Traceback (most recent call last):
  File "calc3.py", line 176, in <module>
    main()
  File "calc3.py", line 172, in main
    result = interpreter.expr()
  File "calc3.py", line 155, in expr
    result += self.term()
  File "calc3.py", line 136, in term
    self.eat(INTEGER)
  File "calc3.py", line 131, in eat
    self.error()
  File "calc3.py", line 54, in error
    raise Exception('Error Parsing Error!')
Exception: Error Parsing Error!

#文法

文法是另一种被广泛使用的、用于指定一种程序设计语言语法的表示法，它叫做『上下文无关文法』，简称文法。

为什么要使用文法？

  • 文法以更简明的方式说明一种程序设计语言的语法。比起来语法图，文法十分简洁。
  • 文法可以用作很好的文档
  • 文法可以非常方便的转换成代码（非常方便~）

##文法原理

我们以『3 4 / 5 2』这样的算数乘除表达式为例，它对应的文法表达式为：

expr: factor ((MUL | DIV) factor)*

factor: INTEGER

一段文法由一系列的规则（rule）组成，在上述文法中，我们有两条规则：expr: factor ((MUL | DIV) factor)* 和factor: INTEGER

一条规则由由一个非终结符（称规则的头或者左边）、一个冒号：、一系列终结符非终结符（称规则的主体或者右边）组成

分析以上文法：

  • expr、factor这样的变量叫做非终结符
  • MUL、DIV、Integer这样的标记称为终结符
  • | 表示『或』，多选一。(MUL | DIV)表示要么 MUL（乘）要么 DIV（除）
  • ( ) 一对圆括号表示把终结符非终结符组合起来，就像 (MUL | DIV) 一样
  • ( )* 表示匹配组合里面的内容 0 次或者多次，就像 while 循环

解释一下 expr 规则：
expr 可以是一个 factor 可选地接着一个乘法或者除法运算符，再接着另一个 factor，依次可选地接着一个乘法或者除法运算符，再接着另一个 factor……

现在我们以解释『3 4 / 5 2』这样的算数乘除表达式为例：

1
2
3
4
5
6
7
expr
factor ((MUL | DIV) factor)*
factor MUL factor ((MUL | DIV) factor)*
factor MUL factor DIV factor ((MUL | DIV) factor)*
factor MUL factor DIV factor MUL factor
INTEGER MUL INTEGER DIV INTEGER MUL INTEGER
 3       *   4       /   5       *   2

##将文法映射称为为代码

  • 对于文法中定义的每一条规则 R，都可以在代码中变成同名的方法 R()
  • 对于多个可选项 ( | ) 可以编程为 if-else 语句
  • 可选的 ( )* 集合编程称为 while 语句，表示可以循环 0~n 次

因此，上述文法用代码表示出来就是：

  • factor 方法
1
2
3
4
5
6
def factor(self):
    # return an Integer Token's value
    # factor: Integer
    token = self.current_token
    self.eat(INTEGER)
    return token.value
  • expr 方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def expr(self):
    # Arithmetic expression parser
    # expr: factor( (MUL | DIV) factor)*
    # factor: Integer
    
    result = self.factor()

    while self.current_token.type in (MUL, DIV):
        token = self.current_token

        if token.type == MUL:
            self.eat(MUL)
            result = result * self.factor()
        elif token.type == DIV:
            self.eat(DIV)
            result = result / self.factor()

    return result

##扩充我们的文法

###加入加减运算

因为，我们加入了加减运算，因此现在存在运算优先级问题，很显然乘除运算优先级要高于加减运算

我们得到以下的优先级表格：

操作符 优先级 结合性
+ - 2 左结合
* / 1 左结合

根据优先级表格构建文法：

  • 为每个优先级定义一个非终结符。非终结符所在产生式的主体应该包含同等级的算术运算符和优先级高一级的非终结符
  • 为表达式创建一个额外的非终结符 factor 作为基本单位，在我们的例子中该基本单位是整数。通用的规则是如果你有 N 层优先级，那么你总共需要 N + 1 个非终结符：每层优先级需要一个非终结符，加上一个用作表达式基本单位的非终结符。

更新我们的文法：

expr: term ((PLUS | MINUS) term)*

term: factor ((MUL | DIV) factor)*

factor: INTEGER

###加入括号表达式

在之前，我们的基本单位只有 INTEGER，这次我们加入括号表达式。

更新后的文法为：

expr: term ((PLUS | MINUS) term)*

term: factor ((MUL | DIV) factor)*

factor: INTEGER | LPAREN expr RPAREN

  • LPAREN 表示左括号，RPAREN 表示右括号
  • 括号表达式内的非终结符 expr 表示 expr 规则

下面我们以『 3 * （1 + 5）』为例，来说明该文法是如何工作的：

image

##最终的四则运算解释器

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
# Token Types:
# EOF: End-Of-File
INTEGER, PLUS, MINUS, MUL, DIV, LPAREN, RPAREN, EOF = (
    'INTEGER', 'PLUS', 'MINUS', 'MUL', 'DIV', '(', ')', 'EOF'
)
class Token(object):
    def __init__(self, type, value):
        # Token types: INTEGER, PLUS, MINUS, MUL, DIV, EOF
        self.type = type
        # Token value: 0,1,2,3,4,5,6,7,8,9,,+,-,*,/,None
        self.value = value

    def __str__(self):
        """
        The format of the print infomation
        For examle:
        Token(INTEGER, 3)
        Token(PLUS, '+')
        Token(MINUS, '-')
        TOKEN(MUL, '*')
        TOEKN(LPAREN, ')')
        """
        return 'Token({type},{value})'.format(
                type = self.type,
                value = repr(self.value)
                )

    def __repr__(self):
        return self.__str__()
    
class Lexer(object):
    def __init__(self, text):
        # Process the whole input
        # e.g. 3+ 5 * 2 - 4/2
        self.text = text
        self.pos = 0
        self.current_char = self.text[self.pos]

    def error(self):
        raise Exception('Invalid character!')
    
    def advance(self):
        # Advance the pos and set current_char
        self.pos += 1

        if self.pos > len(self.text)-1:
            self.current_char = None
        else:
            self.current_char = self.text[self.pos]

    def skip_whitespace(self):
        # Skip space
        while self.current_char is not None and self.current_char.isspace():
            self.advance()

    def integer(self):
        # Support mutidigit integer
        result = ''
        
        while self.current_char is not None and self.current_char.isdigit():
            result += self.current_char
            self.advance()
        
        return int(result)

    def get_next_token(self):
        """
        Lexical Analyzer:
        Parsing the input into tokens.
        Strategy:
        1. dictate current char
        2. if it is a space, advance the pos
        3. if it is a digit, then convert it to integer and return INTEGER token
        4. if it is a '+', then return PLUS token
        5. if it is a '-', then return MINUS token
        6. if it is a '*', then return MUL token
        7. if it is a '/', then return DIV token
        8. if it is a '(', then return LPAREN token
        9. if it is a ')', then return RPAREN token
        """

        while self.current_char is not None:

            if self.current_char.isspace():
                self.skip_whitespace()
                continue

            if self.current_char.isdigit():
                return Token(INTEGER, self.integer())

            if self.current_char == '+':
                self.advance()
                return Token(PLUS, '+')

            if self.current_char == '-':
                self.advance()
                return Token(MINUS, '-')

            if self.current_char == '*':
                self.advance()
                return Token(MUL, '*')

            if self.current_char == '/':
                self.advance()
                return Token(DIV, '/')
            
            if self.current_char == '(':
                self.advance()
                return Token(LPAREN, '(')

            if self.current_char == ')':
                self.advance()
                return Token(RPAREN, ')')
        
            self.error()

        return Token(EOF, None)

class Interpreter(object):
    def __init__(self, lexer):
        self.lexer = lexer
        self.current_token = self.lexer.get_next_token()
        
    def error(self):
        raise Exception('Invalid Syntax')

    def eat(self, token_type):
        # compare the current token with the passed token type
        # if they match then eat the current token and assign next token to the self.current_token
        # otherwise raise an Exception

        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            self.error()

    def factor(self):
        # factor: Integer | LPAREN expr RPAREN
        token = self.current_token

        if token.type == INTEGER:
            self.eat(INTEGER)
            return token.value
        
        if token.type == LPAREN:
            self.eat(LPAREN)
            result = self.expr()
            self.eat(RPAREN)
            return result
    
    def term(self):
        # term: factor( (MUL | DIV) factor)*
        # factor: Integer
        result = self.factor()

        while self.current_token.type in (MUL, DIV):
            token = self.current_token

            if token.type == MUL:
                self.eat(MUL)
                result = result * self.factor()
            elif token.type == DIV:
                self.eat(DIV)
                result = result / self.factor()

        return result

    def expr(self):
        # expr: term( (PLUS | MINUS) term)*
        # term: factor( (MUL | DIV) factor)*
        # factor: Integer
        result = self.term()
        
        while self.current_token.type in (PLUS, MINUS):
            token = self.current_token
            
            if token.type == PLUS:
                self.eat(PLUS)
                result = result + self.term()
            elif token.type == MINUS:
                self.eat(MINUS)
                result = result - self.term()

        return result

def main():
    while True:
        try:
            text = raw_input('cal> ')
        except EOFError:
            break
        if not text:
            continue

        lexer = Lexer(text)
        interpreter = Interpreter(lexer)
        result = interpreter.expr()
        print(result)

if __name__ == '__main__':
    main()

##运行结果

1
2
3
4
5
6
7
8
9
10
cal> 1+1
2
cal> 1*3
3
cal> 1+3*3
10
cal> 5*(1+5)
30
cal> (5+6)/(3-1)*2
10

#参考资料

本文的版权归作者 罗远航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！