如果你會編譯原理，對其中的詞法分析算法，語法分析算法足夠了解，那么用什么語言來做這樣的一件事情都是可以的，之所以使用Python只是因為本人會的編程語言中, Python的使用時間最長，也最得心應(yīng)手。所謂性能什么的不在本文的考慮范圍內(nèi), 本文主要重點是語法分析的表達(dá)式的解析，語法解析使用的是普拉特分析法，一種自頂向下的語法解析方法。
成都創(chuàng)新互聯(lián)長期為上千客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊從業(yè)經(jīng)驗10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為晉源企業(yè)提供專業(yè)的成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)，晉源網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗和眾多成功案例,為您定制開發(fā)。
文章目錄如下:
怎么解決讓代碼算出以下解決結(jié)果?(假設(shè)問題代碼保存文1.txt)
重慶分公司
重慶分公司
1 + 2 * 3 - 4 / 5 不用語法分析, 最簡答的解決辦法就是
with open("1.txt") as rf:
print(eval(rf.read()))
# 輸出結(jié)果 6.2那么如果是以下面的代碼呢?(假設(shè)問題代碼保存文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))
# 輸出結(jié)果
4 {'add': } 如果要求加法的優(yōu)先級大于乘法呢？就是說先加后乘,比如1+2*3=9而不是正常情況下的準(zhǔn)確答案7。理論上可以通過重載python的加減乘除來解決這個問題，但是這里就不研究這個方法了，這個問題就留在文章的末尾解決吧。
PS: 怎么可能會有這么坑爹的需求？作為程序猿遇到的坑爹需求還少么？
總的來說上面的解決辦法總是差點意思，我們沒有更深入的研究它的語法結(jié)構(gòu)，也就沒辦法獲得更多的控制權(quán)。
詞法分析就是講文本里面的代碼分成一個個最小的組成部分, 這個最小的組成部分大家稱之為Token.
什么是token呢？首先看下面的python代碼。
1+2*3如果通過詞法分析處理，那么上面的代碼大概是這樣的表示
Token("整型數(shù)字", "1") Token("運算符", "+") Token("整型數(shù)字", 2) Token("運算符", "*") Token("整型數(shù)字", "3")所以1,2,3分別是一個Token, +,*分別也是一個Token。
PS: 一個抽象的東西總喜歡用抽象的名詞來解釋。
這里主要分析一種語法的結(jié)構(gòu)。
四則表達(dá)式雖然看起來很簡單，但是應(yīng)該算的上是編譯原理中一個比較難的部分了吧，主要是算數(shù)優(yōu)先級的問題。
首先定義基本組成元素:
四則運算的表達(dá)式定義如下:
1. 數(shù)字
2. 數(shù)字(加減乘除 數(shù)字)*
# 加減乘除代表+-*/中的任意一個算術(shù)符, （加減乘除 數(shù)字)+代表+ 1或者 * 2 這樣的結(jié)構(gòu)能夠重復(fù)一到無數(shù)次
# 比如: 1 或者 1 + 2 或者 1+2+3PS: 對于這種語法的定義有一種專門的語法來表示，叫做BNF, 如果本文用BNF來說明就是兩個問題了，所以這里就用中文來表示了。畢竟本文是從無到有系列，如果我的解釋，定義看不懂可以學(xué)習(xí)一下BNF，在回來看應(yīng)該就明白了。
所以本文中以下語法是合法的:
1+2-3*412/53
12
1-4以下語法是不合法的:
1 +
* 1
1+2+以下面代碼為例。
1 + 2 - 3 * 4 / 5通過對上面的語法定義，以及對代碼的觀察，我們可以總結(jié)出以下兩點:
# -*- 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):
# 所有整型數(shù)字
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 表示文本終結(jié)的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是為了標(biāo)識整段代碼已經(jīng)到盡頭
self.tokens.append(self.EOF)
return self.tokens
def next(self):
"""使當(dāng)前字符的位置不斷的向右移動"""
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.
上面我們將要執(zhí)行的代碼分成了一個一個的Token,這一節(jié)要將這一個個的Token組成一顆語法樹。以下面代碼為例。
1 + 2 - 3 * 4代碼生成的語法樹是這樣的。
為什么要用一棵樹來表示呢？因為樹這樣的結(jié)構(gòu)可以將優(yōu)先級的問題解決.
我們只要自下而上的依次執(zhí)行，那么獲得結(jié)果就是正確的優(yōu)先級執(zhí)行的結(jié)果。根據(jù)圖中的樹我們可以這樣計算，先計算[Token(type='Integer', value='1'), Token(type='Integer', value='2'), 這兩個Token的計算結(jié)果分別是1和2，然后將其與父節(jié)點，即Token(type='operator', value='+')結(jié)合，那么結(jié)果是下圖
然后同理計算右邊，得到結(jié)果如下
最后計算3 - 12，得到結(jié)果如下。
繪圖軟件來源: https://online.visual-paradigm.com/
import operator
class Node(object):
"""表示語法樹中的一個節(jié)點"""
def eval(self):
"""子類應(yīng)該實現(xiàn)的方法, 計算自身節(jié)點的方式"""
# 不想寫這句話用abc模塊
raise "需要子類實現(xiàn)"
def repr(self):
"""子類應(yīng)該實現(xiàn)的方法，用于數(shù)據(jù)展示"""
raise "需要子類實現(xiàn)"
def __str__(self):
return self.repr()
def __repr__(self):
return self.repr()
class Interger(Node):
"""代表一個整數(shù)節(jié)點"""
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):
"""代表一個算數(shù)表達(dá)式, 比如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，所以會遞歸調(diào)用
return self.op(self.left.eval(), self.right.eval())
def repr(self):
# 注意這里的left, right也可以是一個OperatorExpression，所以會遞歸調(diào)用
return "(" + self.left.repr() + self.token.value + self.right.repr() + ")"
class Parser(object):
# 定義每個操作符的優(yōu)先級，默認(rèn)+-小于*/
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):
"""
解析中序表達(dá)式
中序表達(dá)式是指操作符在兩個對象之間, 比如+-*/, 有中序自然還有前序及后續(xù)，但是這里不涉及
"""
precedence = self.operator_precedence_map[token.value]
# 這里會遞歸調(diào)用parse_expression,但是傳入的precedence最2，所以不會進(jìn)入while循環(huán)
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)
# 默認(rèn)的precedence是0，所以當(dāng)下一個token是+-*/的時候都會進(jìn)入while循環(huán)，將表達(dá)式進(jìn)行左結(jié)合，不斷的遞歸
# 而最后到EOF的時候，EOF的優(yōu)先級是0, 所以導(dǎo)致while循環(huán)終止，返回最終的表達(dá)式
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現(xiàn)在讓我們回到文章開始的問題，如果+-的優(yōu)先級大于*/怎么讓其實現(xiàn)，
我們只需要傳入一個我們自定義的優(yōu)先級字典。代碼如下
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))
輸出結(jié)果如下
((((1+2)-3)*4)/5)
0.0"1 + 2 - 3 * 4 / 5"正確答案的是0.6, 但是將優(yōu)先級調(diào)換后，結(jié)果變成了0，符合預(yù)期。
主要的用處集中在特定語法組成的代碼分析及轉(zhuǎn)換，語法可能是特定編程語言的語法，也可能是某個工具的DSL(領(lǐng)域特定語言).我暫時能想到的就下面兩個，用到的只有第二個，第三個。
表達(dá)式的解析應(yīng)該是最難的部分了。
后面可能會完成這個系列吧，定義一套完整的語法，然后完成該語法的詞法分析，語法分析，語法執(zhí)行。
一套完整的語法應(yīng)該包括賦值語句，控制結(jié)構(gòu)，如if，while，函數(shù)定義及調(diào)用，如果需要面向?qū)ο髣t還需要類。
其實除了解釋執(zhí)行還可以將代碼通過繼承編譯工具編譯成二進(jìn)制執(zhí)行文件，這樣子就像一個編譯語言了，不過這是后話了
其實通過學(xué)習(xí)編譯原理，可以增加一種看待編程語法的角度，在各個編程語言之間游刃有余，應(yīng)該會更快的學(xué)會一門之前沒接觸過的編程語言吧。
https://github.com/youerning/blog/tree/master/new_program
如果期待后續(xù)文章可以關(guān)注我的微信公眾號(又耳筆記)，頭條號(又耳筆記)，github。
