從無到有用Python創造一門屬于自己的編程語言1

前言

如果你會編譯原理，對其中的詞法分析算法，語法分析算法足夠了解，那么用什么語言來做這樣的一件事情都是可以的，之所以使用Python只是因為本人會的編程語言中, Python的使用時間最長，也最得心應手。所謂性能什么的不在本文的考慮范圍內, 本文主要重點是語法分析的表達式的解析，語法解析使用的是普拉特分析法，一種自頂向下的語法解析方法。

文章目錄如下:

• 四則運算的問題
• 詞法分析
• 語法分析與解釋執行
• 參考鏈接
• 這有什么用
• 后記
• 源代碼

四則運算的問題

怎么解決讓代碼算出以下解決結果?(假設問題代碼保存文1.txt)

1 + 2 * 3 - 4 / 5 

不用語法分析, 最簡答的解決辦法就是

with open("1.txt") as rf:
    print(eval(rf.read()))
# 輸出結果 6.2

那么如果是以下面的代碼呢?(假設問題代碼保存文2.txt)

add(1, add(1,2))

不用語法分析, 最簡單的解決辦法是

def add(a, b):
    return a + b

with open("2.txt") as rf:
    print(eval(rf.read()), dict(add=add))
# 輸出結果
4 {'add': <function add at 0x0000013E8033AD90>}

如果要求加法的優先級大于乘法呢？就是說先加后乘,比如1+2*3=9而不是正常情況下的準確答案7。理論上可以通過重載python的加減乘除來解決這個問題，但是這里就不研究這個方法了，這個問題就留在文章的末尾解決吧。

PS: 怎么可能會有這么坑爹的需求？作為程序猿遇到的坑爹需求還少么？

總的來說上面的解決辦法總是差點意思，我們沒有更深入的研究它的語法結構，也就沒辦法獲得更多的控制權。

詞法分析

詞法分析就是講文本里面的代碼分成一個個最小的組成部分, 這個最小的組成部分大家稱之為Token.

什么是token呢？首先看下面的python代碼。

1+2*3

如果通過詞法分析處理，那么上面的代碼大概是這樣的表示

Token("整型數字", "1") Token("運算符", "+") Token("整型數字", 2) Token("運算符", "*") Token("整型數字", "3")

所以1,2,3分別是一個Token, +,*分別也是一個Token。

PS: 一個抽象的東西總喜歡用抽象的名詞來解釋。

語法定義

這里主要分析一種語法的結構。

1. 四則運算的表達式

四則表達式雖然看起來很簡單，但是應該算的上是編譯原理中一個比較難的部分了吧，主要是算數優先級的問題。

首先定義基本組成元素:

1. 數字: 只能由整型組成, 比如: 111, 123123
2. 加減乘除: 分別對于符號 + - * /

四則運算的表達式定義如下:

1. 數字
2. 數字(加減乘除 數字)*

# 加減乘除代表+-*/中的任意一個算術符, （加減乘除 數字)+代表+ 1或者 * 2 這樣的結構能夠重復一到無數次
# 比如: 1 或者 1 + 2 或者 1+2+3

PS: 對于這種語法的定義有一種專門的語法來表示，叫做BNF, 如果本文用BNF來說明就是兩個問題了，所以這里就用中文來表示了。畢竟本文是從無到有系列，如果我的解釋，定義看不懂可以學習一下BNF，在回來看應該就明白了。

所以本文中以下語法是合法的:

1+2-3*412/53
12
1-4

以下語法是不合法的:

1 +
* 1
1+2+

實現原理

以下面代碼為例。

1 + 2 - 3 *  4  /     5

通過對上面的語法定義，以及對代碼的觀察，我們可以總結出以下兩點:

1. 代碼里面的空格對語法沒有沒有任何意義，所以我們應該忽略代碼中的空格。
2. 數字可能是單個或者多個整數組成，這意味著我們需要判斷下一個字符是不也是數字。

代碼實現

# -*- coding: utf-8 -*-
from __future__ import print_function
import string
from collections import namedtuple

# 定義一個namedtuple類型的Token類型用于表示Token
Token = namedtuple("Token", ["type", "value"])

class Lexer(object):
    # 所有整型數字
    numbers = set(map(str, range(10)))
    # {'2', '9', '1', '0', '6', '3', '7', '5', '8', '4'}

    # 所有大小寫英文字母
    letters = set(string.ascii_letters)
    # {'W', 'b', 'g', 'a', 'V', 'G', 'h', 'I', 'N', 'X', 'S', 'r', 'e', 'M', 'p', 'F', 'O', 'Z', 't', 'j', 'q', 'L', 'd', 'J', 'R', 'k', 'Y', 'D', 's', 'K', 'o', 'x', 'u', 'A', 'H', 'T', 'i', 'w', 'm', 'n', 'v', 'f', 'C', 'y', 'c', 'E', 'Q', 'P', 'l', 'B', 'z', 'U'}

    # 加減乘除
    ADD = "+"
    SUB = "-"
    MUL = "*"
    DIV = "/"
    operators = set([ADD, SUB, MUL, DIV])

    # END OF FILE 表示文本終結的Token
    EOF = Token("EOF", "")

    def parse(self, text):
        self.tokens = []
        self.text = text
        self.cur_pos = 0
        self.cur_char = self.text[self.cur_pos]

        while self.cur_char is not self.EOF:
            if self.cur_char == " ":
                self.next()
                continue
            elif self.cur_char in self.numbers:
                token = self.read_integer()
            elif self.cur_char in self.operators:
                token = Token("operator", self.cur_char)
                self.next()
            else:
                raise "未知字符: %s" % self.cur_char

            self.tokens.append(token)

        # 加一個EOF是為了標識整段代碼已經到盡頭
        self.tokens.append(self.EOF)
        return self.tokens

    def next(self):
        """使當前字符的位置不斷的向右移動"""
        self.cur_pos += 1
        if self.cur_pos >= len(self.text):
            self.cur_char = self.EOF
        else:
            self.cur_char = self.text[self.cur_pos]

    def read_integer(self):
        integer = self.cur_char
        self.next()
        while self.cur_char in self.numbers:
            integer += self.cur_char
            self.next()

        return Token("Integer", integer)

if __name__ == "__main__":
    text = "1 + 2"
    mylexer = Lexer()
    print("1+2")
    print(mylexer.parse("1+2"))
    print()
    print("3  *4/ 5")
    print(mylexer.parse("3  *4/ 5"))

程序輸出如下:

1+2
[Token(type='Integer', value='1'), Token(type='operator', value='+'), Token(type='Integer', value='2'), Token(type='EOF', value='EOF')]

3  *4/ 5
[Token(type='Integer', value='3'), Token(type='operator', value='*'), Token(type='Integer', value='4'), Token(type='operator', value='/'), Token(type='Integer', value='5'), Token(type='EOF', value='EOF')]

至此，我們將代碼分成了一個一個的Token.

語法分析

上面我們將要執行的代碼分成了一個一個的Token,這一節要將這一個個的Token組成一顆語法樹。以下面代碼為例。

1 + 2 - 3 * 4

代碼生成的語法樹是這樣的。

為什么要用一棵樹來表示呢？因為樹這樣的結構可以將優先級的問題解決.

我們只要自下而上的依次執行，那么獲得結果就是正確的優先級執行的結果。根據圖中的樹我們可以這樣計算，先計算[Token(type='Integer', value='1'), Token(type='Integer', value='2'), 這兩個Token的計算結果分別是1和2，然后將其與父節點，即Token(type='operator', value='+')結合，那么結果是下圖

然后同理計算右邊，得到結果如下

最后計算3 - 12，得到結果如下。

繪圖軟件來源: https://online.visual-paradigm.com/

代碼實現

import operator

class Node(object):
    """表示語法樹中的一個節點"""

    def eval(self):
        """子類應該實現的方法, 計算自身節點的方式"""
        # 不想寫這句話用abc模塊
        raise "需要子類實現"

    def repr(self):
        """子類應該實現的方法，用于數據展示"""
        raise "需要子類實現"

    def __str__(self):
        return self.repr()

    def __repr__(self):
        return self.repr()

class Interger(Node):
    """代表一個整數節點"""

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

    def eval(self):
        return int(self.token.value)

    def repr(self):
        return self.token.value

class OperatorExpression(Node):
    """代表一個算數表達式, 比如1+2"""
    operator_map = {
        "+": operator.add,
        "-": operator.sub,
        "*": operator.mul,
        "/": operator.truediv
    }

    def __init__(self, token, left, right):
        self.token = token
        self.op = self.operator_map[self.token.value]
        self.left = left
        self.right = right

    def eval(self):
        # 注意這里的left, right也可以是一個OperatorExpression，所以會遞歸調用
        return self.op(self.left.eval(), self.right.eval())

    def repr(self):
        # 注意這里的left, right也可以是一個OperatorExpression，所以會遞歸調用
        return "(" + self.left.repr() + self.token.value + self.right.repr() + ")"

class Parser(object):
    # 定義每個操作符的優先級，默認+-小于*/
    operator_precedence_map = {
        "EOF": 0,
        "+": 1,
        "-": 1,
        "*": 2,
        "/": 2,
    }

    def __init__(self, precedences=None):
        if precedences:
            self.operator_precedence_map = precedences

    def parse_infix_expression(self, token, left):
        """
        解析中序表達式

        中序表達式是指操作符在兩個對象之間, 比如+-*/, 有中序自然還有前序及后續，但是這里不涉及
        """
        precedence = self.operator_precedence_map[token.value]
        # 這里會遞歸調用parse_expression,但是傳入的precedence最2，所以不會進入while循環
        right = self.parse_expression(precedence)
        expr = OperatorExpression(token, left, right)

        return expr

    def parse_integer(self, token):
        return Interger(token)

    def parse_expression(self, precedence=0):
        current_token = self.next_token
        self.next_token = self.next()
        left_expr = self.parse_integer(current_token)

        # 默認的precedence是0，所以當下一個token是+-*/的時候都會進入while循環，將表達式進行左結合，不斷的遞歸
        # 而最后到EOF的時候，EOF的優先級是0, 所以導致while循環終止，返回最終的表達式
        while precedence < self.operator_precedence_map[self.next_token.value]:
            current_token = self.next_token
            self.next_token = self.next()

            left_expr = self.parse_infix_expression(current_token, left_expr)
        return left_expr

    def next(self):
        return next(self.iter_tokens)

    def parse(self, tokens):
        self.tokens = tokens
        self.iter_tokens = iter(tokens)
        self.next_token = self.next()
        return self.parse_expression()

    def eval(self, expression):
        return expression.eval()

if __name__ == "__main__":
    from xlexer import Lexer
    text = "1 + 2 - 3 * 4 / 5"
    mylexer = Lexer()
    myparser = Parser()
    tokens = mylexer.parse(text)
    expr = myparser.parse(tokens)
    print(expr)
    print(myparser.eval(expr))

輸出如下:

((1+2)-((3*4)/5))
0.6000000000000001

現在讓我們回到文章開始的問題，如果+-的優先級大于*/怎么讓其實現，

我們只需要傳入一個我們自定義的優先級字典。代碼如下

custom_precedences = {
        "+": 2,
        "-": 2,
        "*": 1,
        "/": 1,
    }

if __name__ == "__main__":
    from xlexer import Lexer
    from xparser import Parser

    text = "1 + 2 - 3 * 4 / 5"
    mylexer = Lexer()
    myparser = Parser(custom_precedences)
    tokens = mylexer.parse(text)
    expr = myparser.parse(tokens)
    print(expr)
    print(myparser.eval(expr))

輸出結果如下

((((1+2)-3)*4)/5)
0.0

"1 + 2 - 3 * 4 / 5"正確答案的是0.6, 但是將優先級調換后，結果變成了0，符合預期。

參考鏈接

1. https://study.163.com/course/courseMain.htm?courseId=1004632002
   這個不是我的課程, 該課程的作者是使用的JavaScript完成詞法分析，語法分析，語法解析運行的。我是學了這個教程才有的這篇文章。
2. https://github.com/cameronp98/pratt
   一個普拉特解析法的Python實現，該作者實在是惜字如金，寫得太短小精悍了。

這有什么用?

主要的用處集中在特定語法組成的代碼分析及轉換，語法可能是特定編程語言的語法，也可能是某個工具的DSL(領域特定語言).我暫時能想到的就下面兩個，用到的只有第二個，第三個。

1. 編程語言的翻譯
   通過構造指定編程語言的語法分析器，進行編程語言之間的轉換，翻譯, 雖然整套語言的翻譯或者說完全的兼容很難，但是代碼的片段不會太難。
2. 代碼片段的生成
   和翻譯大體相同，不過側重于生成代碼片段，比如一些DSL，jenkins的pipeline語法。
3. 代碼片段的格式化
   將代碼片段按照一定的標準進行縮進
4. 代碼的語法檢查
5. 創造自己的DSL
6. 創造自己的編程語言

后記

表達式的解析應該是最難的部分了。

后面可能會完成這個系列吧，定義一套完整的語法，然后完成該語法的詞法分析，語法分析，語法執行。

一套完整的語法應該包括賦值語句，控制結構，如if，while，函數定義及調用，如果需要面向對象則還需要類。

其實除了解釋執行還可以將代碼通過繼承編譯工具編譯成二進制執行文件，這樣子就像一個編譯語言了，不過這是后話了

其實通過學習編譯原理，可以增加一種看待編程語法的角度，在各個編程語言之間游刃有余，應該會更快的學會一門之前沒接觸過的編程語言吧。

源代碼

https://github.com/youerning/blog/tree/master/new_program

如果期待后續文章可以關注我的微信公眾號(又耳筆記)，頭條號(又耳筆記)，github。