2. LR实现 自底向上分析（方法三）

(1) 构造识别所有活前缀的DFA

构造扩展文法

E' E

E E T|E T|TT T*F|T/F|F F id|(E)|num

FIRST和FOLLOW集如下

(2) 构造LR分析表。

1E E T 4T T*F 2E E T 5T T/F 3E T 6T F

7F id 8F (E) 9F num

(3) 编程实现算法4.3， 构造SLR(1)分析程序。

expression数据结构，content存放表达式字符串，r存放句柄长度 struct expression{ string content; int r; };

按标号顺序存放表达式左边部分string head[10]={"","E","E","E","T","T","T","F","F","F"}; 按标号顺序存放表达式右边部分 expression ex[10]={

{"",0}, {"E+T",3}, {"E-T",3}, {"T",1}, {"T*F",3}, {"T/F",3}, {"F",1}, {"id",1}, {"(E)",3}, {"num",1} };

按分析表从左到右顺序存放终结符string ch[9]={"+","-","*","/","id","num","(",")","$"};

存放分析表action部分 expression action[17][9]={

// + - * / id num ( ) $ /*0*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*1*/{{"s",7}, {"s",8}, {"",-1}, {"",-1}, {"",-1}, {"",-1}, {"",-1}, {"",-1}, {"ac",0}}, /*2*/{{"r",3}, {"r",3}, {"s",9}, {"s",10},{"",-1}, {"",-1}, {"",-1}, {"r",3}, {"r",3}}, /*3*/{{"r",6}, {"r",6}, {"r",6}, {"r",6}, {"",-1}, {"",-1}, {"",-1}, {"r",6}, {"r",6}}, /*4*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*5*/{{"r",7}, {"r",7}, {"r",7}, {"r",7}, {"",-1}, {"",-1}, {"",-1}, {"r",7}, {"r",7}},

/*6*/{{"r",9}, {"r",9}, {"r",9}, {"r",9}, {"",-1}, {"",-1}, {"",-1}, {"r",9}, {"r",9}}, /*7*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*8*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*9*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*10*/{{"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",5}, {"s",6}, {"s",4}, {"",-1}, {"",-1}}, /*11*/{{"s",7}, {"s",8}, {"",-1}, {"",-1}, {"",-1}, {"",-1}, {"",-1}, {"s",16},{"",-1}}, /*12*/{{"r",1}, {"r",1}, {"s",9}, {"s",10},{"",-1}, {"",-1}, {"",-1}, {"r",1}, {"r",1}}, /*13*/{{"r",2}, {"r",2}, {"s",9}, {"s",10},{"",-1}, {"",-1}, {"",-1}, {"r",2}, {"r",2}}, /*14*/{{"r",4}, {"r",4}, {"r",4}, {"r",4}, {"",-1}, {"",-1}, {"",-1}, {"r",4}, {"r",4}}, /*15*/{{"r",5}, {"r",5}, {"r",5}, {"r",5}, {"",-1}, {"",-1}, {"",-1}, {"r",5}, {"r",5}}, /*16*/{{"r",8}, {"r",8}, {"r",8}, {"r",8}, {"",-1}, {"",-1}, {"",-1}, {"r",8}, {"r",8}}, };

存放分析表goto部分 int goTo[17][3]={ // E T F /*0*/{1, 2, 3}, /*1*/{0, 0, 0}, /*2*/{0, 0, 0}, /*3*/{0, 0, 0}, /*4*/{11,2, 3}, /*5*/{0, 0, 0}, /*6*/{0, 0, 0}, /*7*/{0,12, 3}, /*8*/{0,13, 3}, /*9*/{0,0, 14}, /*10*/{0,0, 15}, /*11*/{0, 0, 0}, /*12*/{0, 0, 0}, /*13*/{0, 0, 0}, /*14*/{0, 0, 0}, /*15*/{0, 0, 0}, /*16*/{0, 0, 0}, };

int search(char target)返回分析表中列号 SLR(1)分析主体

void syntax_analyzing(const char * target, int l)