從零自制深度學習推理框架: 計算圖中的表達式講解（2）
加入技術交流群
當?shù)玫?/span>token數(shù)組之后,我們對語法進行分析,并得到最終產(chǎn)物抽象語法樹（不懂的請自己百度,這是編譯原理中的概念）.語法解析的過程是遞歸向下的,定義在Generate_函數(shù)中.
struct TokenNode {
int32_t num_index = -1;
std::shared_ptr<TokenNode> left = nullptr;
std::shared_ptr<TokenNode> right = nullptr;
TokenNode(int32_t num_index, std::shared_ptr<TokenNode> left, std::shared_ptr<TokenNode> right);
TokenNode() = default;
};
抽象語法樹由一個二叉樹組成,其中存儲它的左子節(jié)點和右子節(jié)點以及對應的操作編號num_index. num_index為正, 則表明是輸入的編號,例如@0,@1中的num_index依次為1和2. 如果num_index為負數(shù)則表明當前的節(jié)點是mul或者add等operator.
std::shared_ptr<TokenNode> ExpressionParser::Generate_(int32_t &index) {
CHECK(index < this->tokens_.size());
const auto current_token = this->tokens_.at(index);
CHECK(current_token.token_type == TokenType::TokenInputNumber
|| current_token.token_type == TokenType::TokenAdd || current_token.token_type == TokenType::TokenMul);
因為是一個遞歸函數(shù),所以index指向token數(shù)組中的當前處理位置.current_token表示當前處理的token,它作為當前遞歸層的第一個Token, 必須是以下類型的一種.
TokenInputNumber = 0,
TokenAdd = 2,
TokenMul = 3,
如果當前token類型是輸入數(shù)字類型, 則直接返回一個操作數(shù)token作為一個葉子節(jié)點,不再向下遞歸, 也就是在add(@0,@1)中的@0和@1,它們在前面的詞法分析中被歸類為TokenInputNumber類型.
if (current_token.token_type == TokenType::TokenInputNumber) {
uint32_t start_pos = current_token.start_pos + 1;
uint32_t end_pos = current_token.end_pos;
CHECK(end_pos > start_pos);
CHECK(end_pos <= this->statement_.length());
const std::string &str_number =
std::string(this->statement_.begin() + start_pos, this->statement_.begin() + end_pos);
return std::make_shared<TokenNode>(std::stoi(str_number), nullptr, nullptr);
}
else if (current_token.token_type == TokenType::TokenMul || current_token.token_type == TokenType::TokenAdd) {
std::shared_ptr<TokenNode> current_node = std::make_shared<TokenNode>();
current_node->num_index = -int(current_token.token_type);
index += 1;
CHECK(index < this->tokens_.size());
// 判斷add之后是否有( left bracket
CHECK(this->tokens_.at(index).token_type == TokenType::TokenLeftBracket);
index += 1;
CHECK(index < this->tokens_.size());
const auto left_token = this->tokens_.at(index);
// 判斷當前需要處理的left token是不是合法類型
if (left_token.token_type == TokenType::TokenInputNumber
|| left_token.token_type == TokenType::TokenAdd || left_token.token_type == TokenType::TokenMul) {
// (之后進行向下遞歸得到@0
current_node->left = Generate_(index);
} else {
LOG(FATAL) << "Unknown token type: " << int(left_token.token_type);
}
}
如果當前Token類型是mul或者add. 那么我們需要向下遞歸構(gòu)建對應的左子節(jié)點和右子節(jié)點.
例如對于add(@1,@2),再遇到add之后,我們需要先判斷是否存在left bracket, 然后再向下遞歸得到@1, 但是@1所代表的 數(shù)字類型,不會再繼續(xù)向下遞歸.
當左子樹構(gòu)建完畢之后,我們將左子樹連接到current_node的left指針中,隨后我們開始構(gòu)建右子樹.此處描繪的過程體現(xiàn)在current_node->left = Generate_(index);中.
index += 1;
// 當前的index指向add(@1,@2)中的逗號
CHECK(index < this->tokens_.size());
// 判斷是否是逗號
CHECK(this->tokens_.at(index).token_type == TokenType::TokenComma);
index += 1;
CHECK(index < this->tokens_.size());
// current_node->right = Generate_(index);構(gòu)建右子樹
const auto right_token = this->tokens_.at(index);
if (right_token.token_type == TokenType::TokenInputNumber
|| right_token.token_type == TokenType::TokenAdd || right_token.token_type == TokenType::TokenMul) {
current_node->right = Generate_(index);
} else {
LOG(FATAL) << "Unknown token type: " << int(left_token.token_type);
}
index += 1;
CHECK(index < this->tokens_.size());
CHECK(this->tokens_.at(index).token_type == TokenType::TokenRightBracket);
return current_node;
例如對于add(@1,@2),index當前指向逗號的位置,所以我們需要先判斷是否存在comma, 隨后開始構(gòu)建右子樹.右子樹中的向下遞歸分析中得到了@2. 當右子樹構(gòu)建完畢后,我們將它(Generate_返回的節(jié)點,此處返回的是一個葉子節(jié)點,其中的數(shù)據(jù)是@2) 放到current_node的right指針中.
串聯(lián)起來的例子簡單來說，我們復盤一下add(@0,@1)這個例子.輸入到Generate_函數(shù)中, 是一個token數(shù)組.
- add
- (
- @0
- ,
- @1
- )
Generate_數(shù)組首先檢查第一個輸入是否為add,mul或者是input number中的一種.
CHECK(current_token.token_type == TokenType::TokenInputNumber||
current_token.token_type == TokenType::TokenAdd || current_token.token_type == TokenType::TokenMul);
第一個輸入add,所以我們需要判斷其后是否是left bracket來判斷合法性, 如果合法則構(gòu)建左子樹.
else if (current_token.token_type == TokenType::TokenMul || current_token.token_type == TokenType::TokenAdd) {
std::shared_ptr<TokenNode> current_node = std::make_shared<TokenNode>();
current_node->num_index = -int(current_token.token_type);
index += 1;
CHECK(index < this->tokens_.size());
CHECK(this->tokens_.at(index).token_type == TokenType::TokenLeftBracket);
index += 1;
CHECK(index < this->tokens_.size());
const auto left_token = this->tokens_.at(index);
if (left_token.token_type == TokenType::TokenInputNumber
|| left_token.token_type == TokenType::TokenAdd || left_token.token_type == TokenType::TokenMul) {
current_node->left = Generate_(index);
}
處理下一個token, 構(gòu)建左子樹.
if (current_token.token_type == TokenType::TokenInputNumber) {
uint32_t start_pos = current_token.start_pos + 1;
uint32_t end_pos = current_token.end_pos;
CHECK(end_pos > start_pos);
CHECK(end_pos <= this->statement_.length());
const std::string &str_number =
std::string(this->statement_.begin() + start_pos, this->statement_.begin() + end_pos);
return std::make_shared<TokenNode>(std::stoi(str_number), nullptr, nullptr);
}
遞歸進入左子樹后，判斷是TokenType::TokenInputNumber則返回一個新的TokenNode到add token成為左子樹.
檢查下一個token是否為逗號，也就是在add(@0,@1)的@0是否為,
CHECK(this->tokens_.at(index).token_type == TokenType::TokenComma);
index += 1;
CHECK(index < this->tokens_.size());
下一步是構(gòu)建add token的右子樹
index += 1;
CHECK(index < this->tokens_.size());
const auto right_token = this->tokens_.at(index);
if (right_token.token_type == TokenType::TokenInputNumber
|| right_token.token_type == TokenType::TokenAdd || right_token.token_type == TokenType::TokenMul) {
current_node->right = Generate_(index);
} else {
LOG(FATAL) << "Unknown token type: " << int(left_token.token_type);
}
index += 1;
CHECK(index < this->tokens_.size());
CHECK(this->tokens_.at(index).token_type == TokenType::TokenRightBracket);
return current_node;
current_node->right = Generate_(index); /// 構(gòu)建add(@0,@1)中的右子樹
Generate_(index)遞歸進入后遇到的token是@1 token,因為是Input Number類型所在構(gòu)造TokenNode后返回.
if (current_token.token_type == TokenType::TokenInputNumber) {
uint32_t start_pos = current_token.start_pos + 1;
uint32_t end_pos = current_token.end_pos;
CHECK(end_pos > start_pos);
CHECK(end_pos <= this->statement_.length());
const std::string &str_number =
std::string(this->statement_.begin() + start_pos, this->statement_.begin() + end_pos);
return std::make_shared<TokenNode>(std::stoi(str_number), nullptr, nullptr);
}
至此, add語句的抽象語法樹構(gòu)建完成.
struct TokenNode {
int32_t num_index = -1;
std::shared_ptr<TokenNode> left = nullptr;
std::shared_ptr<TokenNode> right = nullptr;
TokenNode(int32_t num_index, std::shared_ptr<TokenNode> left, std::shared_ptr<TokenNode> right);
TokenNode() = default;
};
在上述結(jié)構(gòu)中, left存放的是@0表示的節(jié)點, right存放的是@1表示的節(jié)點.
*博客內(nèi)容為網(wǎng)友個人發(fā)布，僅代表博主個人觀點，如有侵權請聯(lián)系工作人員刪除。
