开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 多国语言处理 > 词法分析 > 查看源码
grammerLR.java
资源名称：SLR.rar　[点击查看]
上传用户：jzksjx
上传日期：2022-07-12
资源大小：14k
文件大小：19k
源码类别：

词法分析

开发平台：

Java

grammerLR.java：源码内容
  1. import java.util.*;
  2. import java.io.*;
  4. class pair{
  5. public int x, y;
  6. pair(int a, int b){
  7. x = a;
  8. y = b;
  9. }
  10. }
  12. public class grammerLR {
  13. String[][] syntax;//保存文法
  14. String[][] syntax2;//消除左递归的文法
  15. LinkedList<String> term;//终结符
  16. LinkedList<String> nonterm;//非终结符
  17. LinkedList<String> term2;//副本，求first, follow用
  18. LinkedList<String> nonterm2;//副本，求first, follow用
  20. LinkedList<HashSet<String>> nontermFirst;//记录first
  21. LinkedList<HashSet<String>> nontermFollow;//记录follow
  22. boolean[] hasFirst;//记录first 是否求完
  23. boolean[] hasFollow;//记录follow 是否求完
  25. LinkedList<HashSet<pair>> state;//项集族
  26. int[][][] table1;// ACTION表  // table1 第一层操作类型：1=s, 2=r,3=accept,0=error=默认;
  27. int[][] table2;//GOTO表
  28. String path;
  29. Scanner in;
  30. String[] inExpr;//保存输入的需要判断的表达式
  31. int pindex;
  32. int exprIndex;
  34. String readLine(){
  35. return in.nextLine();
  36. }
  37. void readExpr(){//读入表达式
  38. inExpr = readLine().trim().split("[ ]+");
  39. pindex = 0;
  40. }
  41. String readNext(){//每次读入一个词 
  42. exprIndex++;
  43. if(pindex < inExpr.length){
  44. return inExpr[pindex++];
  45. }else if(pindex == inExpr.length){
  46. pindex++;
  47. return "$";
  48. }else{
  49. return null;
  50. }
  51. }
  52. void scanS() throws IOException{//读入文法 ，并处理文法 
  53. File source = new File(path);
  54. BufferedReader in = new BufferedReader(new FileReader(source));
  55. String s;
  56. while((s = in.readLine()) != null){
  57. if(s.equals("%%1")){
  58. int i = 0;
  59. LinkedList<String> list = new LinkedList<String>();
  60. while((s = in.readLine()) != null && !s.equals("%%")){
  61. String[] st = s.trim().split("[ ]+");
  62. for(String one : st){
  63. list.add(one);
  64. i++;
  65. }
  66. }
  67. term = list;
  68. }else if(s.equals("%%2")){
  69. int i = 0;
  70. LinkedList<String> list = new LinkedList<String>();
  71. while((s = in.readLine()) != null && !s.equals("%%")){
  72. String[] st = s.trim().split("[ ]+");
  73. for(String one : st){
  74. list.add(one);
  75. i++;
  76. }
  77. }
  78. nonterm =  list;  
  79. }else if(s.equals("%%3")){
  80. LinkedList<String[]> list = new LinkedList<String[]>();
  81. while((s = in.readLine()) != null && !s.equals("%%")){
  82. String[] st = s.trim().split("[ ]+");
  83. list.add(st);
  84. }
  85. syntax = list.toArray(new String[0][0]);
  86. }
  87. }
  88. in.close();
  89. }
  90. grammerLR(){
  91. in = new Scanner(System.in);
  92. System.out.println("Enter the path of syntax : ");
  93. path = readLine();
  94. try{//读取文法文件 
  95. scanS();
  96. }catch(IOException e){
  97. System.out.println("IOExcpetion error");
  98. }
  99. exprIndex = 0;
  100. //removeLeftRecursion();//消除左递归等
  101. removeLeftRecursion2();//只是简单的复制,term2, nonterm2, syntax2
  102. extendSyntax();//扩展文法
  104. table1 = new int[50][term.size()+1][2];//-----------------------分析表-第一维 行的大小无法确定，只能尽量合适--------------------------
  105. table2 = new int[50][nonterm.size()];
  106. //table1初始化
  107. for(int i = 0; i < table1.length; i++){
  108. for(int j = 0; j < table1[i].length; j++){
  109. table1[i][j][0] = 0;
  110. table1[i][j][1] = -1;
  111. }
  112. }
  113. //table2初始化
  114. for(int i = 0; i < table2.length; i++){
  115. for(int j = 0 ; j < table2[i].length; j++){
  116. table2[i][j] = -1;
  117. }
  118. }
  120. term.add("$");
  121. items();
  122. firstAll();
  123. followAll();
  124. makeTable();
  125. }
  127. void extendSyntax(){//扩展文法
  128. LinkedList<String[]> syntax0 = new LinkedList<String[]>();
  129. String s = "E_` "+"::= " + syntax[0][0];
  130. String[] st = s.trim().split("[ ]+");
  131. syntax0.add(st);
  132. for(String[] one : syntax){//用syntax填充syntax0
  133. syntax0.add(one);
  134. }
  136. syntax = new String[syntax0.size()][];
  137. for(int i = 0; i < syntax0.size(); i++){
  138. syntax[i] = syntax0.get(i).clone();
  139. }
  140. }
  141. void removeLeftRecursion2(){//只是简单的复制
  142. term2 = new LinkedList<String>(term);
  143. nonterm2 = new LinkedList<String>(nonterm);
  144. LinkedList<LinkedList<String>> syntax1 = new LinkedList<LinkedList<String>>();
  145. for(String[] one : syntax){//用syntax填充syntax1
  146. LinkedList<String> temp1 = new LinkedList<String>();
  147. for(String two : one){
  148. temp1.add(two);
  149. }
  150. syntax1.add(temp1);
  151. }
  153. syntax2 = new String[syntax1.size()][];
  154. for(int i = 0; i < syntax1.size(); i++){
  155. syntax2[i] = syntax1.get(i).toArray(new String[0]);
  156. }
  157. }
  158. void removeLeftRecursion(){//消除左递归
  159. term2 = new LinkedList<String>(term);
  160. nonterm2 = new LinkedList<String>(nonterm);
  161. LinkedList<LinkedList<String>> syntax1 = new LinkedList<LinkedList<String>>();
  162. for(String[] one : syntax){//用syntax填充syntax1
  163. LinkedList<String> temp1 = new LinkedList<String>();
  164. for(String two : one){
  165. temp1.add(two);
  166. }
  167. syntax1.add(temp1);
  168. }
  170. for(int i = 0; i < nonterm.size(); i++){
  171. for(int j = 0; j < i; j++){
  172. for(int k = 0; k < syntax1.size(); k++){
  173. if(nonterm.get(i).equals(syntax1.get(k).get(0)) && nonterm.get(j).equals(syntax1.get(k).get(2)) ){
  174. for(int m = 0; m < syntax1.size(); m++){
  175. if(nonterm.get(j).equals(syntax1.get(m).get(0))){//找到所有非终结符j的产生式
  176. syntax1.get(k).addAll(2+1, syntax1.get(m));
  177. syntax1.get(k).remove(2);
  178. }
  179. }
  180. }
  181. }
  182. }
  184. //消除立即左递归
  185. String newMark = nonterm.get(i) + "`";//创造新符号
  186. for(int j = 0; j < syntax1.size(); j++){
  187. if(syntax1.get(j).get(0).equals(nonterm.get(i))){
  188. if(syntax1.get(j).get(0).equals(syntax1.get(j).get(2))){//有左递归
  189. nonterm2.add(newMark);
  190. syntax1.get(j).add(0+1, newMark);
  191. syntax1.get(j).remove(0);
  192. syntax1.get(j).remove(2);
  193. syntax1.get(j).add(newMark);
  194. for(int k = 0; k < syntax1.size(); k++){
  195. if(syntax1.get(k).get(0).equals(nonterm.get(i))){
  196. if(!syntax1.get(k).get(0).equals(syntax1.get(k).get(2))){
  197. syntax1.get(k).add((newMark));
  198. //移动到前面去
  199. LinkedList<String> temp3 = new LinkedList<String>(syntax1.get(k));
  200. syntax1.remove(k);
  201. syntax1.add(k-1, temp3);
  202. }
  203. }
  204. }
  205. LinkedList<String> temp2 = new LinkedList<String>();
  206. temp2.add(newMark);
  207. temp2.add("::=");
  208. temp2.add("ε");
  209. syntax1.add(j+2, temp2);
  210. if(!term2.contains("ε")){
  211. term2.add("ε");
  212. }
  213. }
  214. }
  215. }
  217. }
  218. syntax2 = new String[syntax1.size()][];
  219. for(int i = 0; i < syntax1.size(); i++){
  220. syntax2[i] = syntax1.get(i).toArray(new String[0]);
  221. }
  222. }
  224. HashSet<pair> closure(HashSet<pair> one){
  225. LinkedList<pair> list = new LinkedList<pair>(one);
  226. for(int i = 0; i < list.size(); i++){
  227. pair two = list.get(i);
  228. if(two.y < syntax[two.x].length && nonterm.contains((syntax[two.x][two.y])) && !syntax[two.x][0].equals(syntax[two.x][two.y])){//点后紧跟非终结符，不在末尾,需要被扩展 , 
  229. String signal = new String(syntax[two.x][two.y]);
  230. int index = 0;
  231. for(String three[] : syntax){
  232. if(three[0].equals(signal) && !list.contains(new pair(index, 2))){//找到其产生式，并且未包含
  233. list.add(new pair(index, 2));
  234. }
  235. index++;
  236. }
  237. }
  238. }
  239. one = new HashSet<pair>(list);
  240. return one;
  241. }
  243. void items(){
  244. state = new LinkedList<HashSet<pair>>();
  245. HashSet<pair> i0 = new HashSet<pair>();
  246. i0.add(new pair(0,2));
  247. i0 = closure(i0);
  248. state.add(i0);
  249. int index = 0;
  250. while(true){
  251. LinkedList<HashSet<pair>> other = new LinkedList<HashSet<pair>>(state);
  252. int num = 0;
  253. for(ListIterator<HashSet<pair>> it = other.listIterator(index); it.hasNext(); ){
  254. HashSet<pair> one = it.next();
  255. HashSet<String> signal = new HashSet<String>();//保存 只能接受的那些输入
  256. for(pair pattern : one){
  257. if(syntax[pattern.x].length > pattern.y){
  258. signal.add(syntax[pattern.x][pattern.y]);
  259. }
  260. }
  261. for(String mark : signal){
  262. HashSet<pair> temp = new HashSet<pair>();
  263. for(pair pattern : one){//对于项集的每个项
  264. if(syntax[pattern.x].length > pattern.y && syntax[pattern.x][pattern.y].equals(mark)){
  265. temp.add(new pair(pattern.x, pattern.y+1));
  266. }
  267. }
  268. temp = closure(temp);
  269. boolean isContain = false;
  270. int stateIndex = -1;
  271. for(HashSet<pair> four : state){//判断是否已经包含此项集
  272. boolean isThere = true;
  273. for(pair five : four){
  274. boolean isFind = false;
  275. for(pair six : temp){
  276. if(five.x == six.x  && five.y == six.y){
  277. isFind = true;
  278. break;
  279. }
  280. }
  281. if(!isFind){
  282. isThere = false;
  283. break;
  284. }
  285. }
  286. if(isThere){
  287. isContain = true;
  288. stateIndex = state.indexOf(four);
  289. break;
  290. }
  291. }
  292. if(!isContain){//判断是否已经包含此项集
  293. state.add(temp);
  294. if(term.contains(mark)){//生成分析表的 规则 2-1
  295. int row = state.indexOf(one);
  296. int cell = term.indexOf(mark);
  297. int value = state.indexOf(temp);
  298. table1[row][cell][0] = 1;//操作为 s，即移入
  299. table1[row][cell][1] = value;
  300. }
  301. if(nonterm.contains(mark)){//生成分析表的 规则 3
  302. int row = state.indexOf(one);
  303. int cell = nonterm.indexOf(mark);
  304. int value = state.indexOf(temp);
  305. table2[row][cell] = value;
  306. }
  307. }else{
  308. if(term.contains(mark)){//生成分析表的 规则 2-1
  309. int row = state.indexOf(one);
  310. int cell = term.indexOf(mark);
  311. int value = stateIndex;;
  312. table1[row][cell][0] = 1;//操作为 s，即移入
  313. table1[row][cell][1] = value;
  314. }
  315. if(nonterm.contains(mark)){//生成分析表的 规则 3
  316. int row = state.indexOf(one);
  317. int cell = nonterm.indexOf(mark);
  318. int value = stateIndex;
  319. table2[row][cell] = value;
  320. }
  321. }
  322. }
  323. num++;
  324. }
  326. index++;
  327. if(state.size() <= other.size()){
  328. break;
  329. }
  330. }
  332. }
  333. void appendFirst(HashSet<String> a, HashSet<String> b){
  334. HashSet<String> temp = new HashSet<String>(b);
  335. temp.remove("ε");
  336. a.addAll(temp);
  337. }
  338. HashSet<String> makeFirst(String token){//求token的first 集合 ，递归 
  339. if(term2.contains(token)){//是终结符 
  340. HashSet<String> temp = new HashSet<String>();
  341. temp.add(token);
  342. return temp;
  343. }else if(nonterm2.contains(token)){//是非终结符 
  344. int index = nonterm2.indexOf(token);
  345. if(!hasFirst[index]){//还没生成first，现在生成
  346. for(String[] one : syntax2){
  347. if(one[0].equals(token)){
  348. if(one[0].equals(one[2])){//对于会左递归的文法
  349. continue;
  350. }
  351. boolean isZero = false;
  352. for(int i = 2; i < one.length; i++){
  353. appendFirst(nontermFirst.get(index), makeFirst(one[i]));
  354. if(term2.contains(one[i]) && !one[i].equals("ε") ){
  355. isZero = true;
  356. break;
  357. }else if(nonterm2.contains(one[i]) && !nontermFirst.get(nonterm2.indexOf(one[i])).contains("ε")){
  358. isZero = true;
  359. break;
  360. }
  361. }
  362. if(!isZero){//每个都有 ε  ,则最后加入 ε 到 集合里 
  363. nontermFirst.get(index).add("ε");
  364. }
  365. }
  366. }
  367. hasFirst[index] = true;//标记 此 符号 的 first 已经找完了
  368. }
  369. return nontermFirst.get(index);
  370.  
  371. }else{//基本不会到这里面
  372. System.out.println(token + " : " + "Error! 没有这个符号");
  373. System.exit(0);
  374. return null;
  375. }
  376. }
  377. void firstAll(){//first集合生成 主程序
  378. hasFirst = new boolean[nonterm2.size()];
  379. nontermFirst = new LinkedList<HashSet<String>>();
  380. for(int i = 0; i < nonterm2.size(); i++){
  381. hasFirst[i] = false;
  382. HashSet<String> temp0 = new HashSet<String>();
  383. nontermFirst.add(temp0);
  384. }
  385.  
  386. for(String one : nonterm2){//生成 非终结符 的 first
  387. makeFirst(one);// makeFirst里已经计算完了 吧
  388. }
  389. }
  390.  
  391.  
  392. void appendFollow(HashSet<String> a, HashSet<String> b){
  393. HashSet<String> temp = new HashSet<String>(b);
  394. temp.remove("ε");
  395. a.addAll(temp);
  396. }
  397. Map<String, Integer> cicle;//防止 文法里出现循环递归
  398. HashSet<String> makeFollow(String token){//生成token 的 follow集合 
  399. if(cicle.get(token) != null){//已经存在这个符号， 说明 出现递归 环 了
  400. return nontermFollow.get(nonterm2.indexOf(token));
  401. }
  402. cicle.put(token, 1);
  403. if(hasFollow[nonterm2.indexOf(token)]){
  404. return nontermFollow.get(nonterm2.indexOf(token));
  405. }
  406. for(String[] one : syntax2){//计算 follow
  407. for(int i = 2; i < one.length; i++){
  408. if(one[i].equals(token)){
  409. boolean allZero = true;
  410. for(int j = i+1; j < one.length; j++){//规则2
  411. if(nonterm2.contains(one[j])){//非终结符
  412. appendFollow(nontermFollow.get(nonterm2.indexOf(token)), nontermFirst.get(nonterm2.indexOf(one[j])));
  413. if(!nontermFirst.get(nonterm2.indexOf(one[j])).contains("ε")){
  414. allZero = false;
  415. break;
  416. }
  417. }else if(term2.contains(one[j])){//终结符
  418. HashSet<String> temp  = new HashSet<String>();
  419. temp.add(one[j]);
  420. appendFollow(nontermFollow.get(nonterm2.indexOf(token)), temp);
  421. if(!one[j].equals("ε")){
  422. allZero = false;
  423. break;
  424. }
  425. }
  426.  
  427. }
  428. if(allZero){//规则3
  429. appendFollow(nontermFollow.get(nonterm2.indexOf(one[i])), makeFollow(one[0]));
  430. }
  432. }
  433. }
  434. }
  435. hasFollow[nonterm2.indexOf(token)] = true;
  436. return nontermFollow.get(nonterm2.indexOf(token));
  437. }
  438. void followAll(){//follow集合生成 主程序
  439. hasFollow = new boolean[nonterm2.size()];
  440. nontermFollow = new LinkedList<HashSet<String>>();
  441. for(int i = 0; i < nonterm2.size(); i++){
  442. hasFollow[i] = false;
  443. HashSet<String> temp0 = new HashSet<String>();
  444. nontermFollow.add(temp0);
  445. }
  446. //把 $ 加入到 开始符号 里
  447. HashSet<String> temps = new HashSet<String>();
  448. temps.add("$");
  449. appendFollow(nontermFollow.get(0), temps);// 开始符号
  450. for(String one : nonterm2){
  451. cicle = new HashMap<String, Integer>();
  452. makeFollow(one);
  453. }
  454. }
  455.  
  456. void makeTable(){
  457. // table1 第一层操作类型：1=s, 2=r,3=accept,0=error=默认;
  458. int index = 0;
  459. for(HashSet<pair> one : state){
  460. for(pair two : one){
  461. if(two.y == syntax[two.x].length){//
  462. if(two.x == 0){//规则 2-3
  463. table1[index][term.indexOf("$")][0] = 3;
  464. table1[index][term.indexOf("$")][1] = -3;
  465. }else{//规则 2-2
  466. for(String token : nontermFollow.get(nonterm.indexOf(syntax[two.x][0]))){
  467. table1[index][term.indexOf(token)][0] = 2;
  468. table1[index][term.indexOf(token)][1] = two.x;
  469. }
  470. }
  471. }
  472. }
  473. index++;
  474. }
  475. }
  478. void analysisDriver(){
  479. Stack<Integer> stateStack = new Stack<Integer>();
  480. Stack<String> signalStack = new Stack<String>();
  481. exprIndex = 0;
  482. stateStack.push(0);
  483. String mark = readNext();
  484. int now;
  486. // table1 第一层操作类型：1=s, 2=r,3=accept,0=error=默认;
  487. System.out.println("n**************************");
  488. while(true){
  489. now = stateStack.peek();
  490. //System.out.println("now = " + now + "," + term.indexOf(mark));
  491. //打印分析栈
  493. for(int i : stateStack){
  494. System.out.print(i + ",");
  495. }
  496. if(stateStack.size() > 3){
  497. System.out.print("t");
  498. }else{
  499. System.out.print("tt");
  500. }
  502. for(String one : signalStack){
  503. System.out.print(one + ",");
  504. }
  505. if(signalStack.size() > 3){
  506. System.out.print("t");
  507. }else{
  508. System.out.print("tt");
  509. }
  510. System.out.print(mark + " ");
  511. for(int i = exprIndex; i < inExpr.length; i++){
  512. System.out.print(inExpr[i] + " ");
  513. }
  514. System.out.println();
  515. if(table1[now][term.indexOf(mark)][0] == 1){
  516. stateStack.push(table1[now][term.indexOf(mark)][1]);
  517. signalStack.push(mark);
  518. mark = readNext();
  519. }else if(table1[now][term.indexOf(mark)][0] == 2){
  520. int syntaxIndex = table1[now][term.indexOf(mark)][1];
  521. for(int i = 2; i < syntax[syntaxIndex].length; i++){
  522. signalStack.pop();
  523. stateStack.pop();
  524. }
  525. signalStack.push(syntax[syntaxIndex][0]);
  526. now = stateStack.peek();
  527. stateStack.push(table2[now][nonterm.indexOf(signalStack.peek())]);
  528. }else if(table1[now][term.indexOf(mark)][0] == 3){
  529. System.out.println("***  Accept  ***");
  530. break;
  531. }else{
  532. System.out.println("*** UnAccept ***");
  533. break;
  534. }
  536. }
  538. }
  539. void printAll(){//输入中间产生的各种信息
  540. int index = 0;
  541. System.out.println("n********************    syntax   ********************");
  542. for(String[] one : syntax){
  543. System.out.print("" + index++ + ":t");
  544. for(String two : one){
  545. System.out.print(two + "t");
  546. }
  547. System.out.println();
  548. }
  550. index = 0;
  551. System.out.println("n********************   syntax2   ********************");
  552. for(String[] one : syntax2){
  553. System.out.print("" + index++ + ":t");
  554. for(String two : one){
  555. System.out.print(two + "t");
  556. }
  557. System.out.println();
  558. }
  559. System.out.println("n********************    term     ********************");
  560. for(String one : term){
  561. System.out.print(one + "t");
  562. }
  563. System.out.println();
  564. System.out.println("n********************   nonterm   ********************");
  565. for(String one : nonterm){
  566. System.out.print(one + "t");
  567. }
  568. System.out.println();
  569. System.out.println("n********************    term2    ********************");
  570. for(String one : term2){
  571. System.out.print(one + "t");
  572. }
  573. System.out.println();
  574. System.out.println("n********************  nonterm2   ********************");
  575. for(String one : nonterm2){
  576. System.out.print(one + "t");
  577. }
  578. System.out.println();
  580. index = 0;
  581. System.out.println("n********************nontermFirst ********************");
  582. for(HashSet<String> one : nontermFirst){
  583. System.out.print("" + index++ + ":t");
  584. for(String two : one){
  585. System.out.print(two + "t");
  586. }
  587. System.out.println();
  588. }
  590. index = 0;
  591. System.out.println("n********************nontermFollow********************");
  592. for(HashSet<String> one : nontermFollow){
  593. System.out.print("" + index++ + ":t");
  594. for(String two : one){
  595. System.out.print(two + "t");
  596. }
  597. System.out.println();
  598. }
  600. index = 0;
  601. System.out.println("n********************    state    ********************");
  602. for(HashSet<pair> one : state){
  603. System.out.print("" + index++ + ":t");
  604. for(pair two : one){
  605. System.out.print("(" + two.x + "," + two.y + ")t");
  606. }
  607. System.out.println();
  608. }
  610. index = 0;
  611. System.out.println("n********************    table    ********************");
  612. System.out.print("t");
  613. for(String one : term){
  614. System.out.print(one + "t");
  615. }
  616. System.out.println();
  617. for(int i = 0; i < state.size(); i++){
  618. System.out.print("" + index++ + ":t");
  619. for(int j = 0; j < table1[i].length; j++){
  620. if(table1[i][j][0] != 0){
  621. System.out.print(table1[i][j][0] + ",");
  622. System.out.print(table1[i][j][1] + "t");
  623. }else{
  624. System.out.print("---t");
  625. }
  626. }
  627. System.out.println();
  628. }
  630. index = 0;
  631. System.out.println("--------------------");
  632. System.out.print("t");
  633. for(String one : nonterm){
  634. System.out.print(one + "t");
  635. }
  636. System.out.println();
  637. for(int i = 0; i < state.size(); i++){
  638. System.out.print("" + index++ + ":t");
  639. for(int j = 0; j < table2[i].length; j++){
  640. if(table2[i][j] != -1){
  641. System.out.print(table2[i][j] + "t");
  642. }else{
  643. System.out.print("-t");
  644. }
  645. }
  646. System.out.println();
  647. }
  649. }
  650. public static void main(String[] args){
  651. grammerLR myLR = new grammerLR();
  652. myLR.printAll();
  653. while(true){
  654. System.out.println("n*****************************************************");
  655. System.out.print("Enter expr:");
  656. myLR.readExpr();
  657. myLR.analysisDriver();
  658. }
  660. }
  662. }