什么是表達(dá)式

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

output_mid=input1+input2
output=output_mid*input3

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

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

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

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

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

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

我們的工作

詞法解析

詞法解析的目的就是將add(@0,mul(@1,@2))拆分為多個(gè)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;//詞語(yǔ)開(kāi)始的位置
int32_tend_pos=0;//詞語(yǔ)結(jié)束的位置
Token(TokenTypetoken_type,int32_tstart_pos,int32_tend_pos):token_type(token_type),start_pos(start_pos),end_pos(end_pos){

}
};

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

如下的代碼是具體的解析過(guò)程,我們將輸入存放在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的時(shí)候,我們的詞法規(guī)定在token中以a作為開(kāi)始的情況只有add. 所以我們判斷接下來(lái)的兩個(gè)字符必須是d和 d.如果不是的話就報(bào)錯(cuò),如果是i的話就初始化一個(gè)新的token并進(jìn)行保存.

	舉個(gè)簡(jiǎn)單的例子只有可能是add,沒(méi)有可能是axc之類的組合.

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

	

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

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

	

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

	語(yǔ)法解析

	當(dāng)?shù)玫絫oken數(shù)組之后,我們對(duì)語(yǔ)法進(jìn)行分析,并得到最終產(chǎn)物抽象語(yǔ)法樹(shù)（不懂的請(qǐng)自己百度,這是編譯原理中的概念）.語(yǔ)法解析的過(guò)程是遞歸向下的,定義在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;
};


	

	抽象語(yǔ)法樹(shù)由一個(gè)二叉樹(shù)組成,其中存儲(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_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)槭且粋€(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_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)建對(duì)應(yīng)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn).

	例如對(duì)于add(@1,@2),再遇到add之后,我們需要先判斷是否存在left bracket, 然后再向下遞歸得到@1, 但是@1所代表的 數(shù)字類型,不會(huì)再繼續(xù)向下遞歸.

	當(dāng)左子樹(shù)構(gòu)建完畢之后,我們將左子樹(shù)連接到current_node的left指針中,隨后我們開(kāi)始構(gòu)建右子樹(shù).此處描繪的過(guò)程體現(xiàn)在current_node->left = Generate_(index);中.

	
index+=1;
//當(dāng)前的index指向add(@1,@2)中的逗號(hào)
CHECK(indextokens_.size());
//判斷是否是逗號(hào)
CHECK(this->tokens_.at(index).token_type==TokenType::TokenComma);

index+=1;
CHECK(indextokens_.size());
//current_node->right=Generate_(index);構(gòu)建右子樹(shù)
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;


	

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

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

	簡(jiǎn)單來(lái)說(shuō)，我們復(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來(lái)判斷合法性, 如果合法則構(gòu)建左子樹(shù).

	
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);
}


	

	處理下一個(gè)token, 構(gòu)建左子樹(shù).

	
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)入左子樹(shù)后，判斷是TokenType::TokenInputNumber則返回一個(gè)新的TokenNode到add token成為左子樹(shù).

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

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

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


	

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

	
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)中的右子樹(shù)


	

	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語(yǔ)句的抽象語(yǔ)法樹(shù)構(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).

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

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

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

	例子中的詞法分析

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

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

	例子中的語(yǔ)法分析

	在ExpressionParser::Generate_函數(shù)對(duì)例子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)錯(cuò). 調(diào)用層為1

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

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

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

	開(kāi)始遞歸調(diào)用用來(lái)構(gòu)建mul token的左子樹(shù).

	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, 我們希望遇到一個(gè)逗號(hào),否則就報(bào)錯(cuò)mul(@0,@1)中中間的逗號(hào).調(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, 我們希望遇到一個(gè)右括號(hào),就是mul(@1,@2)中的右括號(hào).調(diào)用層為2.

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

	...

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

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

	

	實(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);
}



	

	最后會(huì)打印抽象語(yǔ)法樹(shù)的中序遍歷：

	
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


	

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

	

	

	我們的單元測(cè)試輸出為:

	
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


	

	




	審核編輯：劉清