## 概念簡述 移動歸約分析法：自底向上的語法分析方法，也稱為***移動歸約分析法***。 - 最易于實現的一種移動歸約分析方法，叫做***算符優先分析法***， - 而更一般的移動歸約分析方法叫做***LR分析法***，LR分析法可以用作許多自動的語法分析器的生成器。 短語：文法G[S]，αβδ是文法G的一個句型，S=>*αAδ且A=>+β則稱β是句型αβδ相對于非終結符A的短語。 直接短語：若有A ?+β則稱β是句型αβδ相對于該規則A→β的直接短語。 句柄：一個句型的最左直接短語稱為該句型的句柄。 **其實作為一個常年和樹打交道的acmer來說，我覺得下面這種定義方法更容易理解….** 短語：一棵子樹的所有葉子自左至右排列起來形成一個相對于子樹根的短語。 直接短語：僅有父子兩代的一棵子樹，它的所有葉子自左至右排列起來所形成的符號串。 句柄：一個句型的分析樹中最左那棵只有父子兩代的子樹的所有葉子的自左至右排列。 算符文法的定義： - 所有產生式的右部都不是ε或兩個相鄰的非終結符 - 設有一個文法G，如果G中沒有形如A→…BC…的產生式，其中B和C為非終結符，則稱G為算符文法(Operator Grammar)也稱OG文法. 算符優先文法的特點： - 一旦我們構造了算符優先語法分析器，就可以忽略原來的文法，棧中的非終結符僅僅作為與這些非終結符相關的屬性的占位符 - 難以處理像減號這樣有不同優先級的符號 - 由于分析的語言的文法和算符優先語法分析器本身的關系不是很緊密，所以不能肯定語法分析器接受的就是所期望的語言 ## 算法優先關系構造算法 ### 一、首先對于優先關系進行如下定義： - a的優先級低于b a < b： 文法中有形如A→…aB…的產生式而B?+b…或B?+Cb… - a的優先級等于b a = b： 文法中有形如A→…ab…或者A→…aBb…的產生式 - a的優先級高于b a > b： 文法中有形如A?…Bb…的產生式,而B?+…a或B?+…aC - 算符的優先關系是有序的 - 如果a > b，不能推出b < a - 如果a > b，有可能b > a - 如果a > b， b > c，不一定a > c 根據這個大小關系的定義，我們知道為了確定兩個終止符的優先關系，我們需要知道它的在所有的產生式中和前后非終止符的關系，那么我們做一個如(二)預處理： ### 二、定義并構造FIRSTVT和LASTVT兩個集合 FIRSTVT(P)={a|P?+a?或P?+Qa?} LASTVT(P)={a|P?+?a或P?+?aQ} FIRSTVT(P)直接根據定義遞歸的構造即可： - a) 若有產生式 P→a??? 或 p→Qa???　 則 a∈FIRSTVT(P) - b) 若有產生式 P→Q??? , 若 a∈FIRSTVT(Q) 則 a∈FIRSTVT(P) LASTVT(P)直接根據定義遞歸的構造即可： - a) 若有產生式 P→???a 或 p→???aQ　 則 a∈LASTVT(P) - b) 若有產生式 P→???Q , 若 a∈LASTVT(Q) 則 a∈LASTVT(P) 代碼實現見代碼部分的make_first和make_last函數，是兩個簡單的遞歸實現。 ### 三、利用FIRSTVT和LASTVT集合構造算法優先關系表 ~~~ FOR 每個產生式 P->X1 X2 ……Xn DO FOR i:=1 TO n-1 DO IF X[i]和X[i+1]均為終結符 THEN 置 X[i]=X[i+1] IF X[i]和X[i+2]均為終結符,X[i+1]為非終結符,i≤n-2, THEN 置 X[i]=X[i+2] IF X[i]為終結符, 但X[i+1]為非終結符 THEN FOR FIRSTVT(X[i+1])中的每個a DO 置 X[i]<a IF Xi為非終結符, 但X i+1 為終結符 THEN FOR LASTVT(X i )中的每個a DO 置 a>X[i+1] ~~~ ## C++代碼實現 ~~~ #include <iostream> #include <cstring> #include <cstdio> #include <vector> #include <stack> #include <map> #include <set> #include <algorithm> #include <string> #include <cstdlib> #include <cctype> #define MAX 507 using namespace std; class WF { public: string left; vector<string> right; WF ( const string& str ) { left = str; } void insert ( char str[] ) { right.push_back(str); } void print ( ) { printf ( "%s->%s" , left.c_str() , right[0].c_str() ); for ( int i = 1 ; i < right.size() ; i++ ) printf ( "|%s" , right[i].c_str() ); puts(""); } }; char relation[MAX][MAX]; vector<char> VT; vector<WF> VN_set; map<string,int> VN_dic; set<char> first[MAX]; set<char> last[MAX]; int used[MAX]; int vis[MAX]; void dfs ( int x ) { if ( vis[x] ) return; vis[x] = 1; string& left = VN_set[x].left; for ( int i = 0 ; i < VN_set[x].right.size() ; i++ ) { string& str = VN_set[x].right[i]; if ( isupper(str[0]) ) { int y = VN_dic[str.substr(0,1)]-1; if ( str.length() > 1 && !isupper(str[1] ) ) first[x].insert ( str[1] ); dfs ( y ); set<char>::iterator it = first[y].begin(); for ( ; it!= first[y].end() ; it++ ) first[x].insert ( *it ); } else first[x].insert ( str[0] ); } } void make_first ( ) { memset ( vis , 0 , sizeof ( vis ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) if ( vis[i] ) continue; else dfs ( i ); #define DEBUG #ifdef DEBUG puts("------------FIRSTVT集-------------------"); for ( int i = 0 ; i < VN_set.size() ; i++ ) { printf ( "%s : " , VN_set[i].left.c_str() ); set<char>::iterator it = first[i].begin(); for ( ; it!= first[i].end() ; it++ ) printf ( "%c " , *it ); puts ("" ); } #endif } void dfs1 ( int x ) { if ( vis[x] ) return; vis[x] = 1; string& left = VN_set[x].left; for ( int i = 0 ; i < VN_set[x].right.size() ; i++ ) { string& str = VN_set[x].right[i]; int n = str.length() -1; if ( isupper(str[n] ) ) { int y = VN_dic[str.substr(n,1)]-1; if ( str.length() > 1 && !isupper(str[n-1]) ) last[x].insert ( str[1] ); dfs1 ( y ); set<char>::iterator it = last[y].begin(); for ( ; it != last[y].end() ; it++ ) last[x].insert ( *it ); } else last[x].insert ( str[n] ); } } void make_last ( ) { memset ( vis , 0 , sizeof ( vis ) ); for ( int i = 0 ; i < VN_set.size() ; i++ ) if ( vis[i] ) continue; else dfs1 ( i ); #define DEBUG #ifdef DEBUG puts("--------------LASTVT集---------------------"); for ( int i = 0 ; i < VN_set.size() ; i++ ) { printf ( "%s : " , VN_set[i].left.c_str() ); set<char>::iterator it = last[i].begin(); for ( ; it!= last[i].end() ; it++ ) printf ( "%c " , *it ); puts ("" ); } #endif } void make_table ( ) { for ( int i = 0 ; i < MAX ; i++ ) for ( int j = 0 ; j < MAX ; j++ ) relation[i][j] = ' '; for ( int i = 0 ; i < VN_set.size() ; i++ ) for ( int j = 0 ; j < VN_set[i].right.size() ; j++ ) { string& str = VN_set[i].right[j]; for ( int k = 0 ; k < str.length()-1 ; k++ ) { if ( !isupper(str[k]) && !isupper(str[k+1]) ) relation[str[k]][str[k+1]] = '='; if ( !isupper(str[k]) && isupper(str[k+1]) ) { int x = VN_dic[str.substr(k+1,1)]-1; set<char>::iterator it = first[x].begin(); for ( ; it != first[x].end() ; it++ ) relation[str[k]][*it] = '<'; } if ( isupper(str[k]) && !isupper(str[k+1]) ) { int x = VN_dic[str.substr(k,1)]-1; set<char>::iterator it = last[x].begin(); for ( ; it != last[x].end() ; it++ ) relation[*it][str[k+1]] = '>'; } if ( k > str.length()-2 ) continue; if ( !isupper(str[k]) && !isupper(str[k+2]) && isupper(str[k+1]) ) relation[str[k]][str[k+2]] = '='; } } #define DEBUG #ifdef DEBUG for ( int i = 0 ; i < VT.size()*5 ; i++ ) printf ("-"); printf ( "算符優先關系表" ); for ( int i = 0 ; i < VT.size()*5 ; i++ ) printf ( "-" ); puts(""); printf ( "|%8s|" , "" ); for ( int i = 0 ; i < VT.size() ; i++ ) printf ( "%5c%5s" , VT[i] , "|" ); puts (""); for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ ) printf ("-"); puts(""); for ( int i = 0 ; i < VT.size() ; i++ ) { printf ( "|%4c%5s" , VT[i] , "|"); for ( int j = 0 ; j < VT.size() ; j++ ) printf ( "%5c%5s" , relation[VT[i]][VT[j]] , "|" ); puts (""); for ( int i = 0 ; i < (VT.size()+1)*10 ; i++ ) printf ("-"); puts(""); } #endif } int main ( ) { int n; char s[MAX]; while ( ~scanf ( "%d" , &n ) ) { memset ( used , 0 , sizeof ( used ) ); 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 ( WF(s) ); VN_dic[s] = VN_set.size(); } int x = VN_dic[s]-1; VN_set[x].insert ( s+j+2 ); for ( int k = 0 ; k < j; k++ ) if ( !isupper(s[k] ) ) { if ( used[s[k]] ) continue; used[s[k]] = 1; VT.push_back ( s[k] ); } for ( int k = j+2 ; k < len; k++ ) if ( !isupper(s[k] ) ) { if ( used[s[k]] ) continue; VT.push_back ( s[k] ); used[s[k]] = VT.size(); } } #define DEBUG #ifdef DEBUG puts ("************VT集*******************"); for ( int i = 0 ; i < VT.size() ; i++ ) printf ( "%c " , VT[i] ); puts (""); puts("*************產生式*****************"); for ( int i = 0 ; i < VN_set.size() ; i++ ) VN_set[i].print(); puts("************************************"); #endif make_first(); make_last(); make_table(); } } ~~~ Input:  Output: