在完成编译原理实验第二部分----语法分析的时候,需要对自定义语言的文法进行处理求分析表,我采用了LR分析算法.下面是我的LR(1)分析表构造过程:
可以在这里找到最新版本:https://github.com/luofei2011/jslr
第一部分:html
1 <!DOCTYPE HTML> 2 <html lang="en"> 3 <head> 4 <meta charset="UTF-8"> 5 <title>语法分析</title> 6 <script type="text/javascript" src="js/analysis.table.js"></script> 7 <link rel="stylesheet" href="css/main.css" type="text/css"> 8 </head> 9 <body> 10 <div class="wrapper"> 11 <div class="header"> 12 <input type="button" value="创建分析表" onclick="getValue();"> 13 </div> 14 <div class="content"> 15 <div class="left"> 16 <textarea id="input"></textarea> 17 </div> 18 <div class="right"> 19 <div id="display"> 20 </div> 21 </div> 22 </div> 23 </div> 24 </body> 25 </html>
第二部分:Css
1 .wrapper{ 2 width: calc(100% - 20px); 3 width: -moz-calc(100% - 20px); 4 width: -webkit-calc(100% - 20px); 5 margin: 0 auto; 6 } 7 .content{ 8 width: 100%; 9 margin: 0; 10 padding: 0; 11 height: calc(60% - 10px); 12 } 13 .left{ 14 float: left; 15 width: 48%; 16 } 17 .right{ 18 float: right; 19 width: 48%; 20 } 21 #input, 22 #display{ 23 height: 400px; 24 width: 100%; 25 } 26 #display{ 27 border: 1px solid #000; 28 overflow: auto; 29 }
第三部分:Javascript
1 /* 2 * @author:Poised_flw 3 * @email:luofeihit2010@gmail.com 4 * @github:https://github.com/luofei2011/jslr 5 * @blog:www.cnblogs.com/Poised_flw 6 * 7 * README: 8 * 1.通过文法的输入(只能如下的格式:).用LR(1)算法构建分析表 9 V={S,E,T} 10 T={i,-,(,)} 11 S->E 12 E->T 13 E->E-T 14 T->i 15 T->(E) 16 * *(1)文法目前只能支持单独的字母,后期会加入映射转换的功能如(if->con | I->C); 17 * *(2)你不需要在刚输入的时候就使用拓广文法,后期程序会自动添加 18 * *(3)最好按照给定的格式,第一行是非终结符集合,第二行是终结符集合 19 * 2.给analysis_alo()函数传入一个string的参数(必须以'#')结尾.该函数能分析出 20 * 此字符串是否能通过该文法分析,返回状态'acc'或则出错. 21 * 3.该程序目前还没有操作本地文件的功能,因此若想保存数据是能手动copy 22 * 4.函数式编程过程...没想好如何用面向对象来体现. 23 * EXAMPLE: 24 * V={S,E,T} 25 * T->{i,-,(,)} 26 * S->E 27 * E->T 28 * E->E-T 29 * T->i 30 * T->(E) 31 * 测试串:i-(i)-i# 32 * 33 * */ 34 35 var $ = function(selector) { 36 return document.getElementById(selector); 37 } 38 39 /*用到的全局变量*/ 40 var pro = []; //产生式的数组形式存储 41 var I = []; //存储项目集范族 42 var vt_arr = [];//终结符和非终结符集合 43 var V = []; //非终结符集合 44 var T = []; //终结符集合 45 var pro_G = []; //存储拓广文法产生式 46 47 /*判断元素是否在数组中*/ 48 /* 49 * @param array value 待比较的目标数组 50 * @param string arr 待比较的值 51 * @return int|bool 若找到则返回位置下标,否则返回false 52 * */ 53 function is_inArray(value,arr) { 54 for(var i in arr) 55 if(arr[i] == value) return i; 56 return false; 57 } 58 59 /*找出所有的V+T*/ 60 function get_v_t(value) { 61 var vt = value.join('') 62 .replace(/\$|(->)/g,'').split(''); 63 for(var i in vt){ 64 if(!is_inArray(vt[i],vt_arr)) 65 vt_arr.push(vt[i]); 66 } 67 } 68 69 /* 70 * 以数组方式存储产生式的左右项 71 * @param array value 待处理的产生式数组 72 * @example: 73 * S->R处理后为: 74 * pro['S'] = 'R'; 75 * 76 * */ 77 function storePro(value) { 78 var left = []; 79 for(var i in value){ 80 var str_L = value[i].slice(0,1); 81 var str_R = value[i].slice(3,value[i].length); 82 if(!is_inArray(str_L,left)){ 83 left.push(str_L); 84 pro[str_L] = []; 85 } 86 pro[str_L].push(str_R); 87 } 88 } 89 90 /*处理输入产生式中的空格*/ 91 function rmvNull(value) { 92 var newArr = []; 93 for(var i in value){ 94 if(value[i].length){ 95 newArr.push(value[i] 96 .replace(/ /g,'')); //去除空格 97 } 98 } 99 /*拓广文法*/ 100 newArr.unshift('$->S'); 101 return newArr; 102 } 103 104 /*获得所有的非终结符*/ 105 function setV(value) { 106 return value.replace(/(V={)|}$/g,'').split(','); 107 } 108 109 /*获得所有的终结符*/ 110 function setT(value) { 111 return value.replace(/(T={)|}$/g,'').split(','); 112 } 113 114 /*右边栏显示项目集范族*/ 115 function r_dis(value){ 116 var str =''; 117 for(var i in value){ 118 str += 'I['+i+']={'+value[i]+'}</br>'; 119 } 120 $("display").innerHTML = str; 121 } 122 123 /*显示分析表函数*/ 124 function my_dis() { 125 var str = ''; 126 str += 'the action table:</br>'; 127 for(var i in action){ 128 for(var j in action[i]){ 129 if(action[i][j].length) 130 str += 'action['+i+','+j+']='+action[i][j] + '</br>'; 131 } 132 } 133 str += 'the goto table:</br>'; 134 for(var i in _goto){ 135 for(var j in _goto[i]){ 136 if(_goto[i][j].length) 137 str += 'goto['+i+','+j+']='+_goto[i][j] + '</br>'; 138 } 139 } 140 $("display").innerHTML = str; 141 } 142 143 /*获取页面中文本框的输入值,并进行相应的处理*/ 144 function getValue() { 145 var value = $("input").value.split(/\n/g); 146 V = setV(value.shift()); //获得所有的非终结符 147 T = setT(value.shift()); //获得所有的终结符 148 value = pro_G = rmvNull(value); //去除空格并且拓广文法 149 get_v_t(value); //获取到所有的V+T 150 storePro(value); //存储拓广文法产生式 151 getLR_I(); //递归产生项目集范族 152 //r_dis(I); //显示产生的项目集范族 153 action_goto(); //产生action和goto表 154 //my_dis(); //打印action和goto表 155 156 /*清空不再需要的全局变量*/ 157 pro = []; 158 I = []; 159 vt_arr = []; 160 V = []; 161 T = []; 162 /************************/ 163 164 analysis_alo('i-(i)-i#'); 165 } 166 167 /* 168 * 求FIRST集合 169 * T->T*F 170 * T->T/F会产生死循环 171 * */ 172 function getFirstByOne(value) { 173 var first = []; 174 if(is_inArray(value,T) || value == '#') 175 first.push(value); 176 if(is_inArray(value,V)){ 177 //找出所有的X->a/X->Y型产生式 178 var all_x = []; 179 for(var item in pro_G){ 180 //产生式的右部 181 if(pro_G[item][0] == value){ 182 //右侧是终结符并且没有加入first集合的情况下 183 if(is_inArray(pro_G[item][3],T) && !is_inArray(pro_G[item][3],first)) 184 first.push(pro_G[item][3]); 185 //右侧第一个是非终结符 186 /*像这种T->T/F的产生式会发生死递归. 187 能想到的有两种方法能解决: 188 1.循环的过程中,像遍历二叉树一样弄一个hash表记录是否被访问过 189 2.强制规定不能有这种类型的产生式出现,若出现则忽略其FIRST集合 190 本实验我采取第二种方法,牺牲精确度,提高效率. 191 */ 192 else if(is_inArray(pro_G[item][3],V) && pro_G[item][3] != pro_G[item][0]){ 193 var all_v = getFirstByOne(pro_G[item][3]); 194 if(!is_inArray(all_v,first)) 195 for(var j in all_v) 196 first.push(all_v[j]); 197 } 198 } 199 } 200 } 201 return first; 202 } 203 204 /*符号串的FIRST集合*/ 205 function getFirstAll(str){ 206 var first = []; 207 /*for(var i=0; i<str.length; i++){ 208 var _val = getFirstByOne(str[i]); 209 for(var j in _val) 210 if(!is_inArray(_val[j],first)) 211 first.push(_val[j]); 212 if(is_inArray(str[0],T)) 213 break; 214 }*/ 215 //感觉这里只能这样写,不知是FIRST集求错还是怎么.循环会有更多的FIRST集合 216 var _val = getFirstByOne(str[0]); 217 for(var j in _val) 218 if(!is_inArray(_val[j],first)) 219 first.push(_val[j]); 220 return first; 221 } 222 223 224 /* 225 * 闭包函数 226 * 是非递归实现 227 * @param array I 传递的需要求闭包的项目 228 * @param array C 记录产生的闭包集合 229 * @return array C 最终的闭包集合 230 * 231 * */ 232 function closure(I) { 233 //初始化闭包 234 var C = I || []; 235 /*记录闭包中的项目数*/ 236 var len = C.length; 237 while(1){ 238 for(var item in C) { 239 var str = C[item].slice(C[item].indexOf('.')+1,C[item].indexOf('.')+2); 240 /*满足这种产生式:A->a.Bp,a*/ 241 if(str.length && str != ','){ 242 /*'.'后面是终结符则停止*/ 243 if(is_inArray(str,T)) 244 continue; 245 var first_arr = C[item].slice(C[item].indexOf('.')+2,C[item].length).replace(/,/g,''); 246 var first = getFirstAll(first_arr); 247 /*遍历拓广文法G'中产生式的左部*/ 248 for(var i in pro){ 249 /*找到以B开始的项目*/ 250 if(str == i){ 251 /*遍历出以B开始的产生式,并把他们加'.'以后加入闭包中*/ 252 for(var j in pro[i]){ 253 /*还得对当前产生式的FIRST集合遍历一次*/ 254 for(var n in first){ 255 var yeta = i + '->.' + pro[i][j] + ',' + first[n]; 256 /*循环处理C中的每项,去重.直到C的大小不再改变*/ 257 if(!is_inArray(yeta,C)) 258 C.push(yeta); 259 } 260 } 261 } 262 } 263 } 264 } 265 /*大小不再改变则停止寻找闭包*/ 266 if(C.length > len){ 267 len = C.length; 268 }else{ 269 break; 270 } 271 } 272 return C; 273 } 274 275 /* 276 * 交换string中两个元素的位置 277 * @function 交换'.'和其后面一个元素的位置 278 * */ 279 function changeIndex(str){ 280 var indx = str.indexOf('.'); 281 if(indx != -1){ 282 var str_arr = str.split(''); 283 var ex_str = str_arr[indx]; 284 str_arr[indx] = str_arr[indx+1]; 285 str_arr[indx+1] = ex_str; 286 str = str_arr.join(''); 287 } 288 return str; 289 } 290 291 /* 292 * GOTO函数 293 * @param array I 闭包集合 294 * @param string X 标志元素 295 * @param array J 记录可以求闭包的项目 296 * @return array 返回项目J的闭包 297 * 298 * */ 299 function GO(I,X) { 300 var J = []; 301 for(var item in I){ 302 var str = I[item].slice(I[item].indexOf('.')+1,I[item].indexOf('.')+2); 303 if(str == X){ 304 var copy_item = I[item]; 305 J.push(changeIndex(copy_item)); 306 } 307 } 308 return closure(J); 309 } 310 311 /* 312 * 判断两个数组是否相等,可以不同顺序 313 * @example: 314 * a = [1,3,5]; b = [3,5,1] 315 * a和b是相等的 316 * 317 * */ 318 function is_eql_arr(arr_1,arr_2) { 319 /*第一步就判断长度是否相等*/ 320 if(arr_1.length != arr_2.length) 321 return false; 322 /*设置标志位*/ 323 var flag = false; 324 for(var i in arr_1){ 325 for(var j in arr_2){ 326 if(arr_1[i] == arr_2[j]){ 327 flag = true; 328 break; 329 } 330 } 331 if(!flag) 332 return false; 333 flag = false; 334 } 335 return true; 336 } 337 338 /* 339 * 非递归实现 340 * 利用closure()和GO计算LR(1)项目集范族 341 * @param boolean flag 已经产生状态的标志 342 * @param int num 当前递归的数组I项目 343 * @param int len 当到I最后一项时,判断I是否还能增加 344 * @param now_item array 目前正在递归的项目I 345 * 346 * */ 347 function getLR_I() { 348 /*设置一个标志*/ 349 var flag = false; 350 var num = 0; 351 var len = 0; //while结束的标志 352 /*初始化项目*/ 353 var now_item = closure(['$->.S,#']); 354 I.push(now_item); //I[0] 355 356 /*递归求解项目集*/ 357 while(1){ 358 for(var vt in vt_arr){ 359 var _t = GO(now_item,vt_arr[vt]); 360 if(_t.length){ 361 /*循环遍历I中的所有项,若存在则不做处理*/ 362 for(var all in I){ 363 if(is_eql_arr(_t,I[all])){ 364 flag = true; 365 break; 366 } 367 } 368 if(!flag) I.push(_t); 369 /*清除状态标志位*/ 370 flag = false; 371 } 372 } 373 now_item = I[++num]; 374 len = I.length; 375 /*到最后一项后需要判断是结束递归还是继续递归*/ 376 if(num > I.length){ 377 if(I.length > len){ 378 /*递归处理I中的每项,给他们求闭包*/ 379 continue; 380 } 381 break; 382 } 383 } 384 } 385 386 /*维护两张表*/ 387 var action = []; 388 var _goto = []; 389 390 /*返回相同的项目集下标*/ 391 function get_pos(arr) { 392 for(var i in I){ 393 if(is_eql_arr(arr,I[i])) 394 return i; 395 } 396 return -1; 397 } 398 399 /* 400 * 分析表的构造 401 * @param array action 构造的action表 402 * @param array _goto 构造的goto表 403 * */ 404 function action_goto() { 405 for(var i in I){ 406 //需要初始化一下两张表 407 action[i] = ['']; 408 _goto[i] = ['']; 409 if(is_inArray('$->S.,#',I[i])){ 410 action[i]['#'] = 'acc'; 411 continue; 412 } 413 for(var j in I[i]){ 414 var item = I[i][j]; 415 var a = item.slice(item.indexOf('.')+1,item.indexOf('.')+2); 416 //移入项目 417 if(is_inArray(a,T)){ 418 var s = get_pos(GO(I[i],a)); 419 if(s > -1) 420 action[i][a] = 'S'+s; 421 } 422 //记录能归约的项 423 if(a == ','){ 424 var J = is_inArray(item.slice(0,item.indexOf('.')),pro_G); 425 if(J) 426 action[i][item[item.length-1]] = 'r'+J; 427 } 428 } 429 //归约后的状态改变 430 for(var k in V){ 431 var go = get_pos(GO(I[i],V[k])) 432 if(go > -1) 433 _goto[i][V[k]] = go; 434 } 435 } 436 } 437 438 /* 439 * LR分析算法 440 * 非递归实现 441 * 通过判断栈顶状态和输入串确定当前是移入还是归约等等... 442 * @param string w_str 需要匹配的串 443 * @param array S_stack 当前栈状态数组 444 * @param array X_stack 符号栈 445 * @param string ip 输入串指针 446 * @return state 'acc'表示接受,其它则出错 447 * 448 * */ 449 function analysis_alo(w_str) { 450 var w_str = w_str.split(''); 451 var S_stack = []; //栈顶状态 452 var X_stack = []; //输入符号栈 453 /*初始化两个栈*/ 454 S_stack.push('0'); 455 X_stack.push('#'); 456 /*将输入串放入输入缓冲区中,指针ip指向第一个符号*/ 457 var ip = w_str.shift(); 458 /*显示信息*/ 459 var str_dis = '<table>'; 460 var step =0; 461 while(1){ 462 str_dis += '<tr><td>步骤'+ (++step) + 463 '</td><td>' + S_stack + X_stack + 464 '</td><td>' +ip+w_str + '</td>'; 465 var status = action[parseInt(S_stack[S_stack.length-1])][ip] || ''; 466 str_dis += '<td>action['+S_stack[S_stack.length-1]+','+ip+']='+status; 467 /*移入*/ 468 if(status.indexOf('S') != -1){ 469 S_stack.push(parseInt(status.replace(/S/g,''))); 470 X_stack.push(ip); 471 ip = w_str.shift(); 472 str_dis += ',移进状态'+status.replace(/S/g,'')+'和输入符号'+ip+'</td>'; 473 /*归约,并判断下一步状态*/ 474 }else if(status.indexOf('r') != -1){ 475 /*第k个产生式A->a*/ 476 var str = pro_G[parseInt(status.replace(/r/g,''))]; 477 /*从栈顶弹出2*|a|个符号*/ 478 for(var j=0; j<str.slice(str.indexOf('>')+1,str.length).length; j++){ 479 X_stack.pop(); 480 S_stack.pop(); 481 } 482 /*把A压入栈中*/ 483 X_stack.push(str[0]); 484 str_dis += ',按第'+status.replace(/r/g,'')+'个产生式'+str+'归约</td></tr>'; 485 486 //下一步的状态 487 str_dis += '<tr><td>步骤'+ (++step) + '</td>' + 488 '<td>' + S_stack + X_stack + '</td>' + 489 '<td>' + ip+w_str + '</td>'; 490 /*令S'为当前栈顶状态,把goto[S',A]压入栈中*/ 491 var _s = _goto[parseInt(S_stack[S_stack.length-1])][X_stack[X_stack.length-1]]; 492 S_stack.push(_s); 493 str_dis += '<td>goto['+S_stack[S_stack.length-2]+','+str[0]+']='+_s+ 494 ',将状态'+_s+'压入栈中</td></tr>'; 495 /*接受,暂停处理*/ 496 }else if(status == 'acc'){ 497 str_dis += ',接受</tr>'; 498 break; 499 /*出错,同样暂停处理*/ 500 }else{ 501 str_dis += ',无此状态转换,出错!</tr>'; 502 break; 503 } 504 str_dis += '</tr>'; 505 } 506 str_dis += '</table>'; 507 $("display").innerHTML = str_dis; 508 } 509 510 window.onload = function() { 511 /*初始化文本框中的值*/ 512 (function() { 513 var init = 'V={S,L,R}\nT={*,i,=}\nS->L=R\nS->R\nL->*R\nL->i\nR->L\n'; 514 $("input").value = init; 515 })(); 516 };
所有评论(0)