編譯原理(五) LL(1)文法分析法(預測分析表的構造算法C++實現) · 編譯原理算法實現

## 基本定義 - FIRST(α): - 令Ｇ是一個不含左遞歸的文法，對G的所有非終結符的每個候選α定義它的終結首符集FIRST(α)為： FIRST(α)={a | α=>*a…, a∈VT} - 若α=>*ε，則規定ε∈FIRST(α) - FIRST(α)是α的所有可能推導的開頭終結符或可能的ε - 如果非終結符Ａ的所有候選首符集兩兩不相交，即Ａ的任何兩個不同候選αi和αｊ FIRST(αi) ∩FIRST(αj)=Φ - 那么當要求Ａ匹配輸入串時，Ａ就能根據它所面臨的第一個輸入符號ａ，準確的指派某一個候選前去執行任務。這個候選就是那個終結首符集含ａ的α。 - FOLLOW(A): - 假定S是文法G的開始符號，對于G的任何非終結符A，我們定義 FOLLOW(A)={a | S=>*…Aa…，a∈VT} - FOLLOW(A)是所有句型中出現在緊接A之后的終結符或“#”。開始符號的FOLLOW集初始化時加入“#”。 - 當非終結符A面臨輸入符號a，且a不屬于A的任意候選首符集但A的某個候選首符集包含ε時，只有當a∈FOLLOW(A)時，才可能允許A自動匹配。 - LL(1)文法: - 文法不含左遞歸 - 對于文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若A→α1 |α2 | … |αn，則FIRST(αi)∩FIRST(αj)=Φ (i≠j) - 對文法中的每個非終結符A，若它存在某個候選首符集包含ε，則，FIRST(A)∩FOLLOW(A)=Φ 如果一個文法G滿足以上條件，則稱該文法G為***LL(1)文法***。 - LL(1)文法是***不帶回溯***的***自頂向下***的文法 - 預測分析表： - 預測分析表示一個M[A,a]形式的矩陣。其中A為非終結符，a是終結符或‘#’ 。 - 矩陣元素M[A,a]中存放著一條關于A的產生式，指出當A面臨輸入符號a時所應采用的候選。 M[A,a]中也可能存放一個“出錯標志”，指出A根本不該面臨輸入符號a。 ## 預測分析表的構造 ### FIRST(α)的構造算法要構造FIRST(α)，根據定義： α=X1?Xn 那么對于從前到后的Xi我們進行分類討論： - 如果Xi∈Vt,那么FIRST(α)=FIRST(Xi)={Xi} - 如果Xi∈Vn,因為不存在左遞歸，所以Xi=a.......|?,那么FIRST(Xi)={a,?,FIRST(Xi+1)} - 只要Xi?1不包含?,那么Xi不可能影響FIRST(α) - 那么我們通過記錄每個a∈V,然后進行深度優先記憶化搜索,將所有的狀態填滿，因為LL(1)文法使不會回溯的，所以能夠保證在O(n)的時間完成，采取遞歸的形式實現 ### FIRST(α)的構造實現代碼 ~~~ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <string> #include <cctype> #include <map> #include <set> #define MAX 507 using namespace std; //大寫字母為非終止符(可以多一個'的標號做區分)，小寫字母為終止符,用~代替epsilon class WF { public: string left; set<string> right; WF ( char s[] ) { left = s; } void print ( ) { printf ( "%s->" , left.c_str() ); set<string>::iterator it = right.begin(); if ( right.begin()!= right.end() ) { printf ( "%s" , it->c_str() ); it++; } for(; it != right.end() ; it++ ) printf ( "|%s" , it->c_str() ); puts(""); } void insert ( char s[] ) { right.insert ( s ); } }; map<string,set<char> > first; map<string,set<char> > follow; map<string,int> VN_dic; vector<WF> VN_set; bool used[MAX]; void dfs ( int x ) { if ( used[x] ) return; used[x] = 1; string& left = VN_set[x].left; set<string>& right = VN_set[x].right; set<string>::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) for ( int i = 0 ; i < it->length() ; i++ ) { if ( !isupper( it->at(i) ) && it->at(i) != '\'' ) { first[left].insert ( it->at(i) ); break; } if ( isupper( it->at(i) ) ) { int y; if ( i != it->length()-1 && it->at(i+1) == '\'' ) y = VN_dic[it->substr(i,2)]-1; else y = VN_dic[it->substr(i,1)]-1; string& tleft = VN_set[y].left; dfs ( y ); set<char>& temp = first[tleft]; set<char>::iterator it1 = temp.begin(); bool flag = true; for ( ; it1 != temp.end() ; it1++ ) { if ( *it1 == '~' ) flag = false; first[left].insert( *it1 ); } if ( flag ) break; } else continue; } } void make_first ( ) { memset ( used , 0 , sizeof ( used ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) dfs ( i ); #define DEBUG #ifdef DEBUG map<string,set<char> >::iterator it = first.begin(); for ( ; it != first.end() ; it++ ) { printf ( "FIRST(%s)={" , it->first.c_str() ); set<char> & temp = it->second; set<char>::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } int main ( ) { int n; char s[MAX]; while ( ~scanf ( "%d" , &n ) ) { for ( int i = 0 ; i < n ; i++ ) { scanf ( "%s" , s ); int len = strlen ( s ),j; for ( j = 0 ; j < len ; j++ ) if ( s[j] == '-' ) break; s[j] = 0; if ( !VN_dic[s] ) { VN_set.push_back ( s ); VN_dic[s] = VN_set.size(); } int x = VN_dic[s]-1; VN_set[x].insert ( s+j+2 ); } make_first(); } } ~~~ **Input:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171faa9d383.jpg "") **Output:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171faab07e4.jpg "") ### FOLLOW(A)的構造算法設S,A,B∈Vn,那么連續使用如下規則，直至follow集不再發生變化： - （1） S為標識符，那么FOLLOW(S)包含“#” - （2）若A::=αBβ,那么FOLLOW(B)+=FIRST(B)?{?} - （3）若A::=αB或者A::=αBβ,且β???，那么FOLLOW(B)+=FOLLOW(A) ### FOLLOW(A)的構造實現代碼 ~~~ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <string> #include <cctype> #include <map> #include <set> #define MAX 507 using namespace std; //大寫字母為非終止符(可以多一個'的標號做區分)，小寫字母為終止符,用~代替epsilon class WF { public: string left; set<string> right; WF ( char s[] ) { left = s; } void print ( ) { printf ( "%s->" , left.c_str() ); set<string>::iterator it = right.begin(); if ( right.begin()!= right.end() ) { printf ( "%s" , it->c_str() ); it++; } for(; it != right.end() ; it++ ) printf ( "|%s" , it->c_str() ); puts(""); } void insert ( char s[] ) { right.insert ( s ); } }; map<string,set<char> > first; map<string,set<char> > follow; map<string,int> VN_dic; vector<WF> VN_set; bool used[MAX]; void dfs ( int x ) { if ( used[x] ) return; used[x] = 1; string& left = VN_set[x].left; set<string>& right = VN_set[x].right; set<string>::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) for ( int i = 0 ; i < it->length() ; i++ ) { if ( !isupper( it->at(i) ) && it->at(i) != '\'' ) { first[left].insert ( it->at(i) ); break; } if ( isupper( it->at(i) ) ) { int y; if ( i != it->length()-1 && it->at(i+1) == '\'' ) y = VN_dic[it->substr(i,2)]-1; else y = VN_dic[it->substr(i,1)]-1; string& tleft = VN_set[y].left; dfs ( y ); set<char>& temp = first[tleft]; set<char>::iterator it1 = temp.begin(); bool flag = true; for ( ; it1 != temp.end() ; it1++ ) { if ( *it1 == '~' ) flag = false; first[left].insert( *it1 ); } if ( flag ) break; } else continue; } } void make_first ( ) { memset ( used , 0 , sizeof ( used ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) dfs ( i ); #define DEBUG #ifdef DEBUG puts ("***************FIRST集***********************"); map<string,set<char> >::iterator it = first.begin(); for ( ; it != first.end() ; it++ ) { printf ( "FIRST(%s)={" , it->first.c_str() ); set<char> & temp = it->second; set<char>::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } void append ( const string& str1 , const string& str2 ) { set<char>& from = follow[str1]; set<char>& to = follow[str2]; set<char>::iterator it = from.begin(); for ( ; it != from.end() ; it++ ) to.insert ( *it ); } void make_follow ( ) { while ( true ) { bool goon = false; for ( int i = 0 ; i < VN_set.size() ; i++ ) { string& left = VN_set[i].left; set<string>& right = VN_set[i].right; set<string>::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) { bool flag = true; const string& str = *it; for ( int j = it->length()-1 ; j >= 0 ; j-- ) { if ( str[j] == '\'' ) { int x = VN_dic[it->substr(j-1,2)]-1; if ( flag ) { int tt = follow[it->substr(j-1,2)].size(); append ( left , it->substr(j-1,2) ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[x].right.count("~" ) ) flag = false; } for ( int k = j+1 ; k < it->length() ; k++ ) { if ( isupper(str[k]) ) { string id; if ( k != it->length()-1 && str[k+1] == '\'' ) id = it->substr(k,2); else id = it->substr(k,1); set<char>& from = first[id]; set<char>& to = follow[it->substr(j-1,2)]; int tt = to.size(); set<char>::iterator it1 = from.begin(); for ( ; it1 != from.end() ; it1++ ) if ( *it1 != '~' ) to.insert ( *it1 ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[VN_dic[id]-1].right.count("~") ) break; } else if ( str[k] != '\'' ) { int tt = follow[it->substr(j-1,2)].size(); follow[it->substr(j-1,2)].insert ( str[k] ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; break; } else continue; } j--; } else if ( isupper(str[j] ) ) { int x = VN_dic[it->substr(j,1)]-1; if ( flag ) { int tt = follow[it->substr(j,1)].size(); append ( left , it->substr(j,1) ); if ( !VN_set[x].right.count("~") ) flag = false; int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; } for ( int k = j+1 ; k < it->length() ; k++ ) { if ( isupper( str[k] ) ) { string id; if ( k != it->length()-1 && str[k+1] == '\'' ) id = it->substr(k,2); else id = it->substr(k,1); set<char>& from = first[id]; set<char>& to = follow[it->substr(j,1)]; set<char>::iterator it1 = from.begin(); int tt = follow[it->substr(j,1)].size(); for ( ; it1 != from.end() ; it1++ ) if ( *it1 != '~' ) to.insert( *it1 ); int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[VN_dic[id]-1].right.count("~") ) break; } else if ( str[k] != '\'' ) { int tt = follow[it->substr(j,1)].size(); follow[it->substr(j,1)].insert ( str[k] ); int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; break; } else continue; } } else flag = false; } } } if ( !goon ) break; } #define DEBUG #ifdef DEBUG puts ("****************FOLLOW集**********************" ); map<string,set<char> >::iterator it = follow.begin(); for ( ; it != follow.end() ; it++ ) { printf ( "FOLLOW(%s)={" , it->first.c_str() ); set<char> & temp = it->second; temp.insert('#'); set<char>::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } int main ( ) { int n; char s[MAX]; while ( ~scanf ( "%d" , &n ) ) { for ( int i = 0 ; i < n ; i++ ) { scanf ( "%s" , s ); int len = strlen ( s ),j; for ( j = 0 ; j < len ; j++ ) if ( s[j] == '-' ) break; s[j] = 0; if ( !VN_dic[s] ) { VN_set.push_back ( s ); VN_dic[s] = VN_set.size(); } int x = VN_dic[s]-1; VN_set[x].insert ( s+j+2 ); } make_first(); make_follow(); } } ~~~ **Input:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171faac4093.jpg "") **Output:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171faad3248.jpg "") ### 預測分析表的構造算法 ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171faaedc8e.jpg "") ### 預測分析表的構造實現代碼 ~~~ #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cstdlib> #include <vector> #include <string> #include <cctype> #include <map> #include <set> #define MAX 507 using namespace std; //大寫字母為非終止符(可以多一個'的標號做區分)，小寫字母為終止符,用~代替epsilon class WF { public: string left; set<string> right; WF ( char s[] ) { left = s; } void print ( ) { printf ( "%s->" , left.c_str() ); set<string>::iterator it = right.begin(); if ( right.begin()!= right.end() ) { printf ( "%s" , it->c_str() ); it++; } for(; it != right.end() ; it++ ) printf ( "|%s" , it->c_str() ); puts(""); } void insert ( char s[] ) { right.insert ( s ); } }; map<string,set<char> > first; map<string,set<char> > follow; map<string,int> VN_dic; vector<WF> VN_set; bool used[MAX]; void dfs ( int x ) { if ( used[x] ) return; used[x] = 1; string& left = VN_set[x].left; set<string>& right = VN_set[x].right; set<string>::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) for ( int i = 0 ; i < it->length() ; i++ ) { if ( !isupper( it->at(i) ) && it->at(i) != '\'' ) { first[left].insert ( it->at(i) ); break; } if ( isupper( it->at(i) ) ) { int y; if ( i != it->length()-1 && it->at(i+1) == '\'' ) y = VN_dic[it->substr(i,2)]-1; else y = VN_dic[it->substr(i,1)]-1; string& tleft = VN_set[y].left; dfs ( y ); set<char>& temp = first[tleft]; set<char>::iterator it1 = temp.begin(); bool flag = true; for ( ; it1 != temp.end() ; it1++ ) { if ( *it1 == '~' ) flag = false; first[left].insert( *it1 ); } if ( flag ) break; } else continue; } } void make_first ( ) { memset ( used , 0 , sizeof ( used ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) dfs ( i ); #define DEBUG #ifdef DEBUG puts ("***************FIRST集***********************"); map<string,set<char> >::iterator it = first.begin(); for ( ; it != first.end() ; it++ ) { printf ( "FIRST(%s)={" , it->first.c_str() ); set<char> & temp = it->second; set<char>::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } void append ( const string& str1 , const string& str2 ) { set<char>& from = follow[str1]; set<char>& to = follow[str2]; set<char>::iterator it = from.begin(); for ( ; it != from.end() ; it++ ) to.insert ( *it ); } void make_follow ( ) { while ( true ) { bool goon = false; for ( int i = 0 ; i < VN_set.size() ; i++ ) { string& left = VN_set[i].left; set<string>& right = VN_set[i].right; set<string>::iterator it = right.begin(); for ( ; it!= right.end() ; it++ ) { bool flag = true; const string& str = *it; for ( int j = it->length()-1 ; j >= 0 ; j-- ) { if ( str[j] == '\'' ) { int x = VN_dic[it->substr(j-1,2)]-1; if ( flag ) { int tt = follow[it->substr(j-1,2)].size(); append ( left , it->substr(j-1,2) ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[x].right.count("~" ) ) flag = false; } for ( int k = j+1 ; k < it->length() ; k++ ) { if ( isupper(str[k]) ) { string id; if ( k != it->length()-1 && str[k+1] == '\'' ) id = it->substr(k,2); else id = it->substr(k,1); set<char>& from = first[id]; set<char>& to = follow[it->substr(j-1,2)]; int tt = to.size(); set<char>::iterator it1 = from.begin(); for ( ; it1 != from.end() ; it1++ ) if ( *it1 != '~' ) to.insert ( *it1 ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[VN_dic[id]-1].right.count("~") ) break; } else if ( str[k] != '\'' ) { int tt = follow[it->substr(j-1,2)].size(); follow[it->substr(j-1,2)].insert ( str[k] ); int tt1 = follow[it->substr(j-1,2)].size(); if ( tt1 > tt ) goon = true; break; } else continue; } j--; } else if ( isupper(str[j] ) ) { int x = VN_dic[it->substr(j,1)]-1; if ( flag ) { int tt = follow[it->substr(j,1)].size(); append ( left , it->substr(j,1) ); if ( !VN_set[x].right.count("~") ) flag = false; int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; } for ( int k = j+1 ; k < it->length() ; k++ ) { if ( isupper( str[k] ) ) { string id; if ( k != it->length()-1 && str[k+1] == '\'' ) id = it->substr(k,2); else id = it->substr(k,1); set<char>& from = first[id]; set<char>& to = follow[it->substr(j,1)]; set<char>::iterator it1 = from.begin(); int tt = follow[it->substr(j,1)].size(); for ( ; it1 != from.end() ; it1++ ) if ( *it1 != '~' ) to.insert( *it1 ); int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; if ( !VN_set[VN_dic[id]-1].right.count("~") ) break; } else if ( str[k] != '\'' ) { int tt = follow[it->substr(j,1)].size(); follow[it->substr(j,1)].insert ( str[k] ); int tt1 = follow[it->substr(j,1)].size(); if ( tt1 > tt ) goon = true; break; } else continue; } } else flag = false; } } } if ( !goon ) break; } #define DEBUG #ifdef DEBUG puts ("****************FOLLOW集**********************" ); map<string,set<char> >::iterator it = follow.begin(); for ( ; it != follow.end() ; it++ ) { printf ( "FOLLOW(%s)={" , it->first.c_str() ); set<char> & temp = it->second; temp.insert('#'); set<char>::iterator it1 = temp.begin(); bool flag = false; for ( ; it1 != temp.end() ; it1++ ) { if ( flag ) printf ( "," ); printf ( "%c" , *it1 ); flag = true; } puts ("}"); } #endif } vector<map<char,string> > predict_table; //檢查一個字符是否屬于一個字符串的FIRST集合 bool check_first ( const string& text , char ch ) { for ( int i = 0 ; i < text.length() ; i++ ) { bool hasEmpty = false; if ( !isupper(text[i]) && text[i] != '\'' ) { if ( text[i] != ch ) return false; else return true; } else if ( isupper(text[i] ) ) { string temp; if ( i != text.length()-1 && text[i+1] == '\'' ) temp = text.substr(i,2); else temp = text.substr(i,1); set<char>& dic = first[temp]; set<char>::iterator it = dic.begin(); for ( ; it != dic.end() ; it++ ) { if ( *it == '~' ) hasEmpty = true; if ( *it == ch ) return true; } if ( !hasEmpty) break; } else continue; } return false; } //檢查一個字符是否屬于一個字符串的FOLLOW集合 bool check_follow ( const string& text , char ch ) { set<char>& dic = follow[text]; set<char>::iterator it = dic.begin(); for ( ; it != dic.end() ; it++ ) if ( *it == ch ) return true; return false; } void make_table () { map<char,string> temp; vector<char> letter; bool vis[500]; memset ( vis , 0 , sizeof ( vis ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) { set<string>& right = VN_set[i].right; set<string>::iterator it = right.begin(); for ( ; it != right.end() ; it++ ) for ( int j = 0 ; j < it->length() ; j++ ) if ( !isupper(it->at(j)) && it->at(j) != '\'' ) { if ( vis[it->at(j)] ) continue; vis[it->at(j)] = true; letter.push_back ( it->at(j) ); } } for ( int i = 0 ; i < VN_set.size() ; i++ ) { temp.clear(); string& left = VN_set[i].left; set<string>& right = VN_set[i].right; set<string>::iterator it = right.begin(); for ( ; it != right.end() ; it++ ) for ( int j = 0 ; j < letter.size() ; j++ ) { //cout << *it << " " << letter[j] << endl; if ( check_first ( *it , letter[j] ) ) { //cout << "YES" << endl; temp[letter[j]] = *it; } if ( it->at(0) == '~' && check_follow ( left, letter[j] )) temp[letter[j]] = *it; } predict_table.push_back ( temp ); } #define DEBUG #ifdef DEBUG for ( int i = 0 ; i <= (letter.size()+1)*10 ; i++ ) printf ( "-" ); puts (""); printf ( "|%9s" , "|" ); for ( int i = 0 ; i < letter.size() ; i++ ) printf ( "%5c%5s" , letter[i] , "|" ); puts(""); for ( int i = 0 ; i <= (letter.size()+1)*10 ; i++ ) printf ( "-" ); puts(""); for ( int i = 0 ; i < VN_set.size() ; i++ ) { printf ( "|%5s%4s" , VN_set[i].left.c_str() , "|" ); for ( int j = 0 ; j < letter.size() ; j ++ ) if ( predict_table[i].count(letter[j] ) ) printf ( "%7s%3s" , predict_table[i][letter[j]].c_str() , "|" ); else printf ( "%10s" , "|" ); puts(""); for ( int i = 0 ; i <= (letter.size()+1)*10 ; i++ ) printf ( "-" ); puts (""); } #endif } int main ( ) { int n; char s[MAX]; while ( ~scanf ( "%d" , &n ) ) { for ( int i = 0 ; i < n ; i++ ) { scanf ( "%s" , s ); int len = strlen ( s ),j; for ( j = 0 ; j < len ; j++ ) if ( s[j] == '-' ) break; s[j] = 0; if ( !VN_dic[s] ) { VN_set.push_back ( s ); VN_dic[s] = VN_set.size(); } int x = VN_dic[s]-1; VN_set[x].insert ( s+j+2 ); } make_first(); make_follow(); make_table(); } } ~~~ **Input:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171fab0fd79.jpg "") **Output:** ![這里寫圖片描述](https://box.kancloud.cn/2016-04-20_57171fab228be.jpg "")