從零自制深度學(xué)習(xí)推理框架: 計(jì)算圖中的表達(dá)式講解（2）
加入技術(shù)交流群
掃碼加入
和技術(shù)大咖面對(duì)面交流
海量資料庫查詢
當(dāng)?shù)玫?/span>token數(shù)組之后,我們對(duì)語法進(jìn)行分析,并得到最終產(chǎn)物抽象語法樹（不懂的請(qǐng)自己百度,這是編譯原理中的概念）.語法解析的過程是遞歸向下的,定義在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;
};
抽象語法樹由一個(gè)二叉樹組成,其中存儲(chǔ)它的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)以及對(duì)應(yīng)的操作編號(hào)num_index. num_index為正, 則表明是輸入的編號(hào),例如@0,@1中的num_index依次為1和2. 如果num_index為負(fù)數(shù)則表明當(dāng)前的節(jié)點(diǎn)是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);
因?yàn)槭且粋€(gè)遞歸函數(shù),所以index指向token數(shù)組中的當(dāng)前處理位置.current_token表示當(dāng)前處理的token,它作為當(dāng)前遞歸層的第一個(gè)Token, 必須是以下類型的一種.
TokenInputNumber = 0,
TokenAdd = 2,
TokenMul = 3,
如果當(dāng)前token類型是輸入數(shù)字類型, 則直接返回一個(gè)操作數(shù)token作為一個(gè)葉子節(jié)點(diǎn),不再向下遞歸, 也就是在add(@0,@1)中的@0和@1,它們?cè)谇懊娴脑~法分析中被歸類為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);
// 判斷當(dāng)前需要處理的left token是不是合法類型
if (left_token.token_type == TokenType::TokenInputNumber
|| left_token.token_type == TokenType::TokenAdd || left_token.token_type == TokenType::TokenMul) {
// (之后進(jìn)行向下遞歸得到@0
current_node->left = Generate_(index);
} else {
LOG(FATAL) << "Unknown token type: " << int(left_token.token_type);
}
}
如果當(dāng)前Token類型是mul或者add. 那么我們需要向下遞歸構(gòu)建對(duì)應(yīng)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn).
例如對(duì)于add(@1,@2),再遇到add之后,我們需要先判斷是否存在left bracket, 然后再向下遞歸得到@1, 但是@1所代表的 數(shù)字類型,不會(huì)再繼續(xù)向下遞歸.
當(dāng)左子樹構(gòu)建完畢之后,我們將左子樹連接到current_node的left指針中,隨后我們開始構(gòu)建右子樹.此處描繪的過程體現(xiàn)在current_node->left = Generate_(index);中.
index += 1;
// 當(dāng)前的index指向add(@1,@2)中的逗號(hào)
CHECK(index < this->tokens_.size());
// 判斷是否是逗號(hào)
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;
例如對(duì)于add(@1,@2),index當(dāng)前指向逗號(hào)的位置,所以我們需要先判斷是否存在comma, 隨后開始構(gòu)建右子樹.右子樹中的向下遞歸分析中得到了@2. 當(dāng)右子樹構(gòu)建完畢后,我們將它(Generate_返回的節(jié)點(diǎn),此處返回的是一個(gè)葉子節(jié)點(diǎn),其中的數(shù)據(jù)是@2) 放到current_node的right指針中.
串聯(lián)起來的例子簡(jiǎn)單來說，我們復(fù)盤一下add(@0,@1)這個(gè)例子.輸入到Generate_函數(shù)中, 是一個(gè)token數(shù)組.
- add
- (
- @0
- ,
- @1
- )
Generate_數(shù)組首先檢查第一個(gè)輸入是否為add,mul或者是input number中的一種.
CHECK(current_token.token_type == TokenType::TokenInputNumber||
current_token.token_type == TokenType::TokenAdd || current_token.token_type == TokenType::TokenMul);
第一個(gè)輸入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);
}
處理下一個(gè)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);
}
遞歸進(jìn)入左子樹后，判斷是TokenType::TokenInputNumber則返回一個(gè)新的TokenNode到add token成為左子樹.
檢查下一個(gè)token是否為逗號(hào)，也就是在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)遞歸進(jìn)入后遇到的token是@1 token,因?yàn)槭?/span>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é)點(diǎn), right存放的是@1表示的節(jié)點(diǎn).
*博客內(nèi)容為網(wǎng)友個(gè)人發(fā)布，僅代表博主個(gè)人觀點(diǎn)，如有侵權(quán)請(qǐng)聯(lián)系工作人員刪除。
