自制深度學(xué)習(xí)推理框架之計(jì)算圖中的表達(dá)式

什么是表達(dá)式

表達(dá)式就是一個計(jì)算過程,類似于如下：

output_mid=input1+input2
output=output_mid*input3

用圖形來表達(dá)就是這樣的.

但是在PNNX的Expession Layer中給出的是一種抽象表達(dá)式,會對計(jì)算過程進(jìn)行折疊,消除中間變量. 并且將具體的輸入張量替換為抽象輸入@0,@1等.對于上面的計(jì)算過程,PNNX生成的抽象表達(dá)式是這樣的.

add(@0,mul(@1,@2))抽象的表達(dá)式重新變回到一個方便后端執(zhí)行的計(jì)算過程（抽象語法樹來表達(dá)，在推理的時候我們會把它轉(zhuǎn)成逆波蘭式）。

其中add和mul表示我們上一節(jié)中說到的RuntimeOperator, @0和@1表示我們上一節(jié)課中說道的RuntimeOperand. 這個抽象表達(dá)式看起來比較簡單,但是實(shí)際上情況會非常復(fù)雜,我們給出一個復(fù)雜的例子：

add(add(mul(@0,@1),mul(@2,add(add(add(@0,@2),@3),@4))),@5)

這就要求我們需要一個魯棒的表達(dá)式解析和語法樹構(gòu)建功能.

我們的工作

詞法解析

詞法解析的目的就是將add(@0,mul(@1,@2))拆分為多個token,token依次為add ( @0 , mul等.代碼如下：

enumclassTokenType{
TokenUnknown=-1,
TokenInputNumber=0,
TokenComma=1,
TokenAdd=2,
TokenMul=3,
TokenLeftBracket=4,
TokenRightBracket=5,
};

structToken{
TokenTypetoken_type=TokenType::TokenUnknown;
int32_tstart_pos=0;//詞語開始的位置
int32_tend_pos=0;//詞語結(jié)束的位置
Token(TokenTypetoken_type,int32_tstart_pos,int32_tend_pos):token_type(token_type),start_pos(start_pos),end_pos(end_pos){

}
};

我們在TokenType中規(guī)定了Token的類型,類型有輸入、加法、乘法以及左右括號等.Token類中記錄了類型以及Token在字符串的起始和結(jié)束位置.

如下的代碼是具體的解析過程,我們將輸入存放在statement_中,首先是判斷statement_是否為空, 隨后刪除表達(dá)式中的所有空格和制表符.

if(!need_retoken&&!this->tokens_.empty()){
return;
}

CHECK(!statement_.empty())<

	

	下面的代碼中,我們先遍歷表達(dá)式輸入

	
for(int32_ti=0;i

	

	char c是當(dāng)前的字符,當(dāng)c等于字符a的時候,我們的詞法規(guī)定在token中以a作為開始的情況只有add. 所以我們判斷接下來的兩個字符必須是d和 d.如果不是的話就報(bào)錯,如果是i的話就初始化一個新的token并進(jìn)行保存.

	舉個簡單的例子只有可能是add,沒有可能是axc之類的組合.

	
elseif(c=='m'){
CHECK(i+1

	

	同理當(dāng)c等于字符m的時候,我們的語法規(guī)定token中以m作為開始的情況只有mul. 所以我們判斷接下來的兩個字必須是u和l. 如果不是的話,就報(bào)錯,是的話就初始化一個mul token進(jìn)行保存.

	
}elseif(c=='@'){
CHECK(i+1

	

	當(dāng)輸入為ant時候,我們對ant之后的所有數(shù)字進(jìn)行讀取,如果其之后不是操作數(shù),則報(bào)錯.當(dāng)字符等于(或者,的時候就直接保存為對應(yīng)的token,不需要對往后的字符進(jìn)行探查, 直接保存為對應(yīng)類型的Token.

	語法解析

	當(dāng)?shù)玫絫oken數(shù)組之后,我們對語法進(jìn)行分析,并得到最終產(chǎn)物抽象語法樹（不懂的請自己百度,這是編譯原理中的概念）.語法解析的過程是遞歸向下的,定義在Generate_函數(shù)中.

	
structTokenNode{
int32_tnum_index=-1;
std::shared_ptrleft=nullptr;
std::shared_ptrright=nullptr;
TokenNode(int32_tnum_index,std::shared_ptrleft,std::shared_ptrright);
TokenNode()=default;
};


	

	抽象語法樹由一個二叉樹組成,其中存儲它的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)以及對應(yīng)的操作編號num_index. num_index為正, 則表明是輸入的編號,例如@0,@1中的num_index依次為1和2. 如果num_index為負(fù)數(shù)則表明當(dāng)前的節(jié)點(diǎn)是mul或者add等operator.

	
std::shared_ptrExpressionParser::Generate_(int32_t&index){
CHECK(indextokens_.size());
constautocurrent_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)槭且粋€遞歸函數(shù),所以index指向token數(shù)組中的當(dāng)前處理位置.current_token表示當(dāng)前處理的token,它作為當(dāng)前遞歸層的第一個Token, 必須是以下類型的一種.

	
TokenInputNumber=0,
TokenAdd=2,
TokenMul=3,


	

	如果當(dāng)前token類型是輸入數(shù)字類型, 則直接返回一個操作數(shù)token作為一個葉子節(jié)點(diǎn),不再向下遞歸, 也就是在add(@0,@1)中的@0和@1,它們在前面的詞法分析中被歸類為TokenInputNumber類型.

	
if(current_token.token_type==TokenType::TokenInputNumber){
uint32_tstart_pos=current_token.start_pos+1;
uint32_tend_pos=current_token.end_pos;
CHECK(end_pos>start_pos);
CHECK(end_pos<=?this->statement_.length());
conststd::string&str_number=
std::string(this->statement_.begin()+start_pos,this->statement_.begin()+end_pos);
returnstd::make_shared(std::stoi(str_number),nullptr,nullptr);

}

elseif(current_token.token_type==TokenType::TokenMul||current_token.token_type==TokenType::TokenAdd){
std::shared_ptrcurrent_node=std::make_shared();
current_node->num_index=-int(current_token.token_type);

index+=1;
CHECK(indextokens_.size());
//判斷add之后是否有(leftbracket
CHECK(this->tokens_.at(index).token_type==TokenType::TokenLeftBracket);

index+=1;
CHECK(indextokens_.size());
constautoleft_token=this->tokens_.at(index);
//判斷當(dāng)前需要處理的lefttoken是不是合法類型
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)<

	

	如果當(dāng)前Token類型是mul或者add. 那么我們需要向下遞歸構(gòu)建對應(yīng)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn).

	例如對于add(@1,@2),再遇到add之后,我們需要先判斷是否存在left bracket, 然后再向下遞歸得到@1, 但是@1所代表的 數(shù)字類型,不會再繼續(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)中的逗號
CHECK(indextokens_.size());
//判斷是否是逗號
CHECK(this->tokens_.at(index).token_type==TokenType::TokenComma);

index+=1;
CHECK(indextokens_.size());
//current_node->right=Generate_(index);構(gòu)建右子樹
constautoright_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)<tokens_.size());
CHECK(this->tokens_.at(index).token_type==TokenType::TokenRightBracket);
returncurrent_node;


	

	例如對于add(@1,@2),index當(dāng)前指向逗號的位置,所以我們需要先判斷是否存在comma, 隨后開始構(gòu)建右子樹.右子樹中的向下遞歸分析中得到了@2. 當(dāng)右子樹構(gòu)建完畢后,我們將它(Generate_返回的節(jié)點(diǎn),此處返回的是一個葉子節(jié)點(diǎn),其中的數(shù)據(jù)是@2) 放到current_node的right指針中.

	串聯(lián)起來的例子

	簡單來說，我們復(fù)盤一下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)建左子樹.

	
elseif(current_token.token_type==TokenType::TokenMul||current_token.token_type==TokenType::TokenAdd){
std::shared_ptrcurrent_node=std::make_shared();
current_node->num_index=-int(current_token.token_type);

index+=1;
CHECK(indextokens_.size());
CHECK(this->tokens_.at(index).token_type==TokenType::TokenLeftBracket);

index+=1;
CHECK(indextokens_.size());
constautoleft_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_tstart_pos=current_token.start_pos+1;
uint32_tend_pos=current_token.end_pos;
CHECK(end_pos>start_pos);
CHECK(end_pos<=?this->statement_.length());
conststd::string&str_number=
std::string(this->statement_.begin()+start_pos,this->statement_.begin()+end_pos);
returnstd::make_shared(std::stoi(str_number),nullptr,nullptr);

}


	

	遞歸進(jìn)入左子樹后，判斷是TokenType::TokenInputNumber則返回一個新的TokenNode到add token成為左子樹.

	檢查下一個token是否為逗號，也就是在add(@0,@1)的@0是否為,

	
CHECK(this->tokens_.at(index).token_type==TokenType::TokenComma);

index+=1;
CHECK(indextokens_.size());


	

	下一步是構(gòu)建add token的右子樹

	
index+=1;
CHECK(indextokens_.size());
constautoright_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)<tokens_.size());
CHECK(this->tokens_.at(index).token_type==TokenType::TokenRightBracket);
returncurrent_node;

current_node->right=Generate_(index);///構(gòu)建add(@0,@1)中的右子樹


	

	Generate_(index)遞歸進(jìn)入后遇到的token是@1 token,因?yàn)槭荌nput Number類型所在構(gòu)造TokenNode后返回.

	
if(current_token.token_type==TokenType::TokenInputNumber){
uint32_tstart_pos=current_token.start_pos+1;
uint32_tend_pos=current_token.end_pos;
CHECK(end_pos>start_pos);
CHECK(end_pos<=?this->statement_.length());
conststd::string&str_number=
std::string(this->statement_.begin()+start_pos,this->statement_.begin()+end_pos);
returnstd::make_shared(std::stoi(str_number),nullptr,nullptr);

}


	

	至此, add語句的抽象語法樹構(gòu)建完成.

	
structTokenNode{
int32_tnum_index=-1;
std::shared_ptrleft=nullptr;
std::shared_ptrright=nullptr;
TokenNode(int32_tnum_index,std::shared_ptrleft,std::shared_ptrright);
TokenNode()=default;
};


	

	在上述結(jié)構(gòu)中, left存放的是@0表示的節(jié)點(diǎn), right存放的是@1表示的節(jié)點(diǎn).

	一個復(fù)雜點(diǎn)的例子

	我們提出這個例子是為了讓同學(xué)更加透徹的理解Expression Layer, 我們舉一個復(fù)雜點(diǎn)的例子：

	add(mul(@0,@1),@2),我們將以人工分析的方式去還原詞法和語法分析的過程.

	例子中的詞法分析

	我們將以上的這個輸入劃分為多個token,多個token分別為

	add | left bracket| |mul|left bracket|@0|comma|@1|right bracket| @2 |right bracket

	例子中的語法分析

	在ExpressionParser::Generate_函數(shù)對例子add(mul(@0,@1),@2),如下的列表為token 數(shù)組.

	add

	(

	mul

	(

	@0

	,

	@1

	)

	,

	@2

	)

	index = 0, 當(dāng)前遇到的token為add, 調(diào)用層為1

	index = 1, 根據(jù)以上的流程,我們期待add token之后的token為left bracket, 否則就報(bào)錯. 調(diào)用層為1

	**開始遞歸調(diào)用,構(gòu)建add的左子樹.**從層1進(jìn)入層2

	index = 2, 遇到了mul token. 調(diào)用層為2.

	index = 3, 根據(jù)以上的流程,我們期待mul token之后的token是第二個left bracket. 調(diào)用層為2.

	開始遞歸調(diào)用用來構(gòu)建mul token的左子樹.

	index = 4, 遇到@0,進(jìn)入遞歸調(diào)用,進(jìn)入層3, 但是因?yàn)椴僮鲾?shù)都是葉子節(jié)點(diǎn),構(gòu)建好之后就直接返回了,得到mul token的左子節(jié)點(diǎn).放在mul token的left 指針上.

	index = 5, 我們希望遇到一個逗號,否則就報(bào)錯mul(@0,@1)中中間的逗號.調(diào)用層為2.

	index = 6, 遇到@2,進(jìn)入遞歸調(diào)用,進(jìn)入層3, 但是因?yàn)椴僮鲾?shù)是葉子節(jié)點(diǎn), 構(gòu)建好之后就直接返回到2,得到mul token的右子節(jié)點(diǎn).

	index = 7, 我們希望遇到一個右括號,就是mul(@1,@2)中的右括號.調(diào)用層為2.

	到現(xiàn)在為止mul token已經(jīng)構(gòu)建完畢,返回形成add token的左子節(jié)點(diǎn),add token的left指針指向構(gòu)建完畢的mul樹. 返回到調(diào)用層1.

	...

	add token開始構(gòu)建right token,但是因?yàn)锧2是一個輸入操作數(shù),所以直接遞歸就返回了,至此得到add的右子樹,并用right指針指向.

	所以構(gòu)建好的抽象語法樹如圖：

	

	實(shí)驗(yàn)部分

	需要完成test/tet_expression.cpp下的expression3函數(shù)

	
TEST(test_expression,expression3){
usingnamespacekuiper_infer;
conststd::string&statement="add(@0,div(@1,@2))";
ExpressionParserparser(statement);
constauto&node_tokens=parser.Generate();
ShowNodes(node_tokens);
}

staticvoidShowNodes(conststd::shared_ptr&node){
if(!node){
return;
}
ShowNodes(node->left);
if(node->num_indexnum_index==-int(kuiper_infer::TokenAdd)){
LOG(INFO)<num_index==-int(kuiper_infer::TokenMul)){
LOG(INFO)<num_index;
}
ShowNodes(node->right);
}

TEST(test_expression,expression1){
usingnamespacekuiper_infer;
conststd::string&statement="add(mul(@0,@1),@2)";
ExpressionParserparser(statement);
constauto&node_tokens=parser.Generate();
ShowNodes(node_tokens);
}



	

	最后會打印抽象語法樹的中序遍歷：

	
Couldnotcreateloggingfile:Nosuchfileordirectory
COULDNOTCREATEALOGGINGFILE20230115-223854.21496!I202301152254.86322621496test_main.cpp:13]Starttest...
I202301152254.86348021496test_expression.cpp:23]NUM:0
I202301152254.86348821496test_expression.cpp:20]MUL
I202301152254.86349221496test_expression.cpp:23]NUM:1
I202301152254.86349721496test_expression.cpp:18]ADD
I202301152254.86350221496test_expression.cpp:23]NUM:2


	

	如果語句是一個更復(fù)雜的表達(dá)式 add(mul(@0,@1),mul(@2,@3))

	

	

	我們的單元測試輸出為:

	
I202301152222.08662723767test_expression.cpp:23]NUM:0
I202301152222.08663523767test_expression.cpp:20]MUL
I202301152222.08663923767test_expression.cpp:23]NUM:1
I202301152222.08664423767test_expression.cpp:18]ADD
I202301152222.08664923767test_expression.cpp:23]NUM:2
I202301152222.08665323767test_expression.cpp:20]MUL
I202301152222.08665823767test_expression.cpp:23]NUM:3


	

	




	審核編輯：劉清