完成了形式上的消除左递归，但是还存在bug，不能直接用于求解实际问题，但过实验指导书的样例是没问题的。先上几组测试数据。
test.data（指导书上的样例）：
1 E->TG
2 G->+TG|-TG
3 G->ε
4 T->FS
5 S->*FS|/FS
6 S->ε
7 F->(E)
8 F->itest2.data：
1 E->E+T|T
2 T->T-T|F
3 T->T+T|x
4 F->(E)|itest3.data：
1 E->TG
2 G->+TG|-TG
3 G->ε
4 S->*FS|/FS
5 S->ε
6 F->(E)
7 F->i
8 T->α
9 α->Sα|εtest4.data：
1 E->EG|HR
2 G->+TG|-TG
3 G->ε
4 T->FS
5 E->ES|HR
6 S->*FS|/FS
7 S->ε
8 F->(E)
9 F->itest5.data（书上的例子）：
1 E->E+T|T
2 T->T*F|F
3 F->(E)|i下面直接上代码，如果后面有时间而且心情好的话再修修补补下。老师要求有个界面，我因为对Scala的GUI编程不熟悉，没有弄；虽说Scala的GUI编程与Java的一脉相承，但差别还是有的，如果直接把Java的代码放在Scala里面跑铁定是一堆error和warnning。
1 import scala.collection.mutable
2 import scala.collection.mutable.{ArrayBuffer, Map}
3 import scala.util.matching.Regex
4
5
6
7
8 object LL1_try_GUI {
9 private final var allCharacters = new String()
10 private final var relations = new ArrayBuffer[ (String, String, String) ]()
11 private final var VN = new String()
12 private final var VT = new String()
13 private final var LL1_G = new ArrayBuffer[ (String, String) ]()
14 //private val allCandidateLetters = "αΑβΒγΓδΔεΕζΖηΗθΘιΙκΚλΛμΜνΝξΞοΟπΠρΡσΣτΤυΥφΦχΧψΨωΩ" + "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ"
15 private val allCandidateLetters = "ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩABCDEFGHIJKLMNOPQRSTUVWXYZ"
16 private final var usedCharacters = ""
17 // private val LL1_G = ArrayBuffer( ("E", "TG"), ("G", "+TG|-TG"), ("G", "ε"), ("T", "FS"), ("S", "*FS|/FS"),
18 // ("S", "ε"), ("F", "(E)"), ("F", "i") )//, ("Y", "*FS|/FS"), ("Y", "+TG|-TG"), ("Y", "x"), ("Y", "M"), ("M", "i"), ("M", "ε") )
19 // test data 1:
20 // ( ("E", "TG"), ("G", "+TG|-TG"), ("G", "ε"), ("T", "FS"), ("S", "*FS|/FS"),
21 // ("S", "ε"), ("F", "(E)"), ("F", "i"), ("Y", "S"), ("Y", "Gx"), ("Y", "x"), ("Y", "M"), ("M", "i"), ("M", "ε") )
22 // test data 2:
23 // ( ("D", "*FD"), ("D", "ε"), ("T", "FD"), ("E", "TC"), ("F", "(E)"), ("F", "i"), ("C", "+TC"), ("C", "ε") )
24 // test data 3:
25 // ( ("E", "E+T|T"), ("T", "T*F|T"), ("F", "(E)|i") )
26 // stand test data:
27 // ( ("E", "TG"), ("G", "+TG|-TG"), ("G", "ε"), ("T", "FS"), ("S", "*FS|/FS"), ("S", "ε"), ("F", "(E)"), ("F", "i") )
28
29 def main(args: Array[String]): Unit = {
30
31 //test countLines
32 //println( "cnt = " + countLines( readFromTxtByLine("/home/hadoop001/Desktop/test.data") ) )
33 //test parseFile
34 val result = parseFile("/home/hadoop001/Desktop/test.data")
35 println( "the original language rules:" )
36 for( rs <- result ) {
37 println( rs._1 + "->" + rs._2 )
38 }
39 initiate("/home/hadoop001/Desktop/test.data")
40 println( "after eliminating the all the left recursion in the language rules:" )
41 displayRelations()
42
43 println( "VT = " + VT )
44 println( "VN = " + VN )
45 println( "allCharacters = " + allCharacters )
46
47 println("*************")
48
49 val testMatrix1 = initiateMatrix()
50 for( i <- 0 to (testMatrix1.length - 1) ) {
51 for( j <- 0 to (testMatrix1(0).length - 1) ) {
52 print(testMatrix1(i)(j) + " ")
53 }
54 println()
55 }
56
57 println("*************")
58
59 // test FIRST
60 val tx = FIRST(LL1_G)
61 println( "FIRST: " )
62 for( t <- tx ) {
63 if( allCharacters.contains( t._1 ) ) {
64 println(t)
65 }
66 }
67 // test FOLLOW
68 val ex = FOLLOW(LL1_G)
69 println( "FOLLOW: " )
70 for( t <- ex ) {
71 if( VN.contains( t._1 ) ) {
72 println(t)
73 }
74 }
75
76
77
78 println("*************")
79
80 val testMatrix2 = createMatrix()
81 for( i <- 0 to (testMatrix2.length - 1) ) {
82 for( j <- 0 to (testMatrix2(0).length - 1) ) {
83 print(testMatrix2(i)(j) + " ")
84 }
85 println()
86 }
87
88 println("*************")
89
90 for( i <- 0 to (testMatrix1.length - 1) ) {
91 for( j <- 0 to (testMatrix1(0).length - 1) ) {
92 if( i == 0 && j == 0 ) {
93 testMatrix1(i)(j) = " "
94 }
95 }
96 }
97 println()
98 for( i <- 0 to (testMatrix1.length - 1) ) {
99 for( j <- 0 to (testMatrix1(0).length - 1) ) {
100 if( testMatrix1(i)(j) == null && i != 0 && j != 0 ) {
101 print(" ")
102 }
103 else {
104 print(testMatrix1(i)(j) + " ")
105 }
106 }
107 println()
108 }
109
110 analyse("i+i*i#")
111 }
112
113 /*
114 * Function name: initiate
115 * Function description: 初始化全局变量
116 * Input parameters: the absolute path of the language-rule source file
117 * Return value: 无
118 * Exception: 未处理
119 * Author: 来自高山
120 * Created date: Sat Oct 19 2019 +0800
121 * Editor: 来自高山
122 * Edited Date: Sat Oct 19 2019 +0800
123 */
124 def initiate( filePath: String ): Unit = {
125 LL1_G = parseFile(filePath)
126 allCharacters = getWholeCharacters(LL1_G)
127 usedCharacters = allCharacters
128 relations = getRelation(LL1_G)
129 VN = getVN(allCharacters)
130 VT = getVT(allCharacters)
131 eliminateLeftRecursion // eliminate all the left recursion at first
132 }
133
134 /*
135 * Function name: displayRelations
136 * Function description: display all he language rules
137 * Input parameters: 无
138 * Return value: 无
139 * Exception: 未处理
140 * Author: 来自高山
141 * Created date: Sat Oct 19 2019 +0800
142 * Editor: 来自高山
143 * Edited Date: Sat Oct 19 2019 +0800
144 */
145 def displayRelations(): Unit = {
146 for( ex <- relations ) {
147 if( ex._3 != "א" ) {
148 println( ex._1 + "->" + ex._2 + "|" + ex._3 )
149 }
150 else {
151 println( ex._1 + "->" + ex._2 )
152 }
153 }
154 }
155
156 /*
157 * Function name: parseFile
158 * Function description: 解析文本文件，保存在数组中
159 * Input parameters: 文本绝对路径
160 * Return value: -ArrayBuffer[ ( String, String ) ]（String类型的元组ArrayBuffer数组）
161 * Exception: 未处理
162 * Author: 来自高山
163 * Created date: Fri Oct 18 2019 +0800
164 * Editor: 来自高山
165 * Edited Date: Fri Oct 18 2019 +0800
166 */
167 def parseFile( filePath: String ): ArrayBuffer[ ( String, String ) ] = {
168 val result = new ArrayBuffer[ ( String, String ) ]( countLines( readFromTxtByLine(filePath) ) )
169 val sourceFile = readFromTxtByLine(filePath) //filePath
170 for( line <- sourceFile ) {
171 val tmp = line.split( "->", 2 )
172 result += ( ( tmp.head, tmp.last ) )
173 }
174 result
175 }
176
177 /*
178 * Function name: countLines
179 * Function description: 计算文本行数，用于创建接收数组时开辟相应空间
180 * Input parameters: -Array[String]（文本文件数据构成的数组）
181 * Return value: -Int（文本行数）
182 * Exception: 未处理
183 * Author: 来自高山
184 * Created date: Fri Oct 18 2019 +0800
185 * Editor: 来自高山
186 * Edited Date: Sat Oct 19 2019 +0800
187 */
188 def countLines( sourceFile: Array[String] ): Int = {
189 var cnt = 0
190 for( line <- sourceFile ) {
191 cnt += 1
192 }
193 cnt
194 }
195
196 /*
197 * Function name: readFromTxtByLine
198 * Function description: 读取文本文件
199 * Input parameters: -String（文本文件绝对路径）
200 * Return value: -Array[String]（文本文件构成的数组，每行数据占一个数组元素）
201 * Exception: -未处理
202 * Author: 来自高山
203 * Created date: Fri Oct 18 2019 +0800
204 * Editor: 来自高山
205 * Edited Date: Fri Oct 18 2019 +0800
206 */
207 def readFromTxtByLine(filePath: String): Array[String] = {
208 import scala.io.Source
209 val source = Source.fromFile(filePath, "UTF-8")
210 //val lineIterator = source.getLines()
211 //lineIterator.foreach()
212 val lines = source.getLines().toArray
213 source.close()
214 //println(lines.size)
215 lines
216 }
217
218 /*
219 * Function name: getWholeCharacters
220 * Function description: 获取文法的除“|”之外的所有字符
221 * Input parameters: -ArrayBuffer[ (String, String) ]（由文法左右两部分字符构成一个元组的数组，筛掉“|”）
222 * Return value: -String（文法的除“|”之外的所有字符）
223 * Exception: 未处理（有出错提示）
224 * Author: 来自高山
225 * Created date: Fri Oct 11 2019 +0800
226 * Editor: 来自高山
227 * Edited Date: Fri Oct 11 2019 +0800
228 */
229 def getWholeCharacters( string: ArrayBuffer[ (String, String) ] ): String = {
230 var wholeCharacters = ""
231 for( expression <- string ) {
232 wholeCharacters += expression._1 + expression._2
233 }
234 val pattern = new Regex("\\|")
235 val result = pattern replaceAllIn( wholeCharacters, "" )
236 if( result.isEmpty )
237 "function getWholeCharacters failed"
238 else
239 result.distinct
240 }
241 /*
242 * Function name: getVN
243 * Function description: 获取文法的所有非终结符（non-terminal character），默认大写字母为非终结符，使用正则表达式匹配
244 * Input parameters: -String（函数getWholeCharacters传来的文法的所有字符）
245 * Return value: -String（文法的所有非终结符）
246 * Exception: 未处理（有出错提示）
247 * Author: 来自高山
248 * Created date: Fri Oct 11 2019 +0800
249 * Editor: 来自高山
250 * Edited Date: Fri Oct 11 2019 +0800
251 */
252 def getVN( string: String ): String = {
253 //match big letter:
254 //^[A-Z]+$
255 val pattern = new Regex("[A-Z]")//("^[A-Z]+$")
256 if( (pattern findAllIn string) != null )
257 (pattern findAllIn string).mkString("")
258 else
259 "function getVN failed"
260 }
261
262 /*
263 * Function name: getVT
264 * Function description: 获取文法的所有非终结符（terminal character），默认大写字母外的字符为终结符，使用正则表达式匹配
265 * Input parameters: -String（函数getWholeCharacters传来的文法的所有字符）
266 * Return value: -String（文法的所有终结符）
267 * Exception: 未处理（有出错提示）
268 * Author: 来自高山
269 * Created date: Fri Oct 11 2019 +0800
270 * Editor: 来自高山
271 * Edited Date: Fri Oct 11 2019 +0800
272 */
273 def getVT( string: String ): String = {
274 val pattern1 = new Regex("[A-Z]")
275 val pattern2 = new Regex("\\|")
276 val firstFilter = pattern1 replaceAllIn( string, "" )
277 val result = pattern2 replaceAllIn( firstFilter, "" )
278 if( result.isEmpty == false )
279 result
280 else
281 return "function getVT failed"
282 }
283 /*
284 * Function name: getRelation
285 * Function description: 获取文法每一行对应的推导关系，若文法只推出了1项（即没有符号“|”），则返回元组的第三个用希伯来字母“א”示空
286 * Input parameters: -ArrayBuffer[ (String, String)（已经分割好的文法左右部分构成的数组）
287 * Return value: -ArrayBuffer[ (String, String, String) ]（元组第一个元素为推导式左边符号，第二为右边第二个符号串，第三为右边（若有）第三个符号串）
288 * Exception: 未处理
289 * Author: 来自高山
290 * Created date: Fri Oct 11 2019 +0800
291 * Editor: 来自高山
292 * Edited Date: Fri Oct 11 2019 +0800
293 */
294 def getRelation( string: ArrayBuffer[ (String, String) ] ): ArrayBuffer[ (String, String, String) ] = {
295 val relation = new ArrayBuffer[ (String, String, String) ]()
296 for( expression <- string ) {
297 if( expression._2.contains("|") == false ) {
298 relation += ( ( expression._1, expression._2, "א" ) )
299 }
300 else {
301 val tmp = expression._2.split("\\|", 2 )
302 relation += ( ( expression._1, tmp.head, tmp.last ) )
303 }
304 }
305 relation
306 }
307
308 /*
309 * Function name: findFirst
310 * Function description: 获取指定字符的右边两个（可能是一个）导出字符串的首个非 ε 组成的字符串
311 * Input parameters: -String（指定字符）
312 * Return value: -String（指定字符的右边两个（可能是一个）导出字符串的首个非 ε 组成的字符串）
313 * Exception: 未处理
314 * Author: 来自高山
315 * Created date: Fri Oct 11 2019 +0800
316 * Editor: 来自高山
317 * Edited Date: Fri Oct 11 2019 +0800
318 */
319 def findFirst( ch: String ): String = {
320
321 val localRelations = relations
322 var result = ""
323 for( ex <- localRelations ) {
324 if( ch == ex._1 ) {
325 if( ex._3 != "א" ) {
326 if( VT.contains( ex._2(0) ) && ex._2(0) != 'ε' ) {
327 result += ex._2(0).toString
328 }
329 if( VT.contains( ex._3(0) ) && ex._3(0) != 'ε' ) {
330 result += ex._3(0).toString
331 }
332 }
333 else {
334 if( VT.contains( ex._2(0) ) && ex._2(0) != 'ε' ) {
335 result += ex._2(0).toString
336 }
337 }
338 }
339 }
340 result
341 }
342
343 /*
344 * Function name: judgeOnlyOneVoidSuccession
345 * Function description: 判断指定字符是否可推出唯一的字符ε
346 * Input parameters: -String（指定字符串）
347 * Return value: -Boolean（存在则true，否则false）
348 * Exception: 未处理
349 * Author: 来自高山
350 * Created date: Fri Oct 11 2019 +0800
351 * Editor: 来自高山
352 * Edited Date: Fri Oct 11 2019 +0800
353 */
354 def judgeOnlyOneVoidSuccession( ch: String ): Boolean = {
355 val localRelations = relations
356 var result = 1
357 for( ex <- localRelations ) {
358 if( ch == ex._1 ) {
359 if( ex._3 != "א" ) {
360 if( ( ex._2.length == 1 && ex._2(0) == 'ε' ) || (ex._3.length == 1 && ex._3(0) == 'ε') ) {
361 result = 1
362 }
363 else {
364 result = 0
365 }
366 }
367 else {
368 if( ( ex._2.length == 1 && ex._2(0) == 'ε' ) ) {
369 result = 1
370 }
371 else {
372 result = 0
373 }
374 }
375 }
376 }
377 if( result == 1 ) true else false
378 }
379
380 /*
381 * Function name: judgeCaseXY
382 * Function description: 判断构造FIRST集时可能的第3种情况的（1），即若X->Y...是一个产生式且Y∈VN（省略若干描述）
383 * Input parameters: -Char（指定字符，即可能满足条件的产生式的左边字符）
384 * Return value: -Boolean（满足则true，否则false）
385 * Exception: 未处理
386 * Author: 来自高山
387 * Created date: Sat Oct 12 2019 +0800
388 * Editor: 来自高山
389 * Edited Date: Sat Oct 12 2019 +0800
390 */
391 def judgeCaseXY( ch: Char ): Boolean = {
392 val localVN = VN
393 val localRelations = relations
394 var result = 0
395 if( localVN.contains(ch) == true ) {
396 for( ex <- localRelations ) {
397 if( ex._1(0) == ch ) {
398 if( localVN.contains( ex._2(0) ) || localVN.contains( ex._3(0) ) ) {
399 result += 1
400 }
401 }
402 }
403 }
404 if( result > 0 )
405 true
406 else
407 false
408 }
409
410 /*
411 * Function name: findCase_Y_In_XY
412 * Function description: 获取构造FIRST集时可能的第3种情况的（1），即若X->Y...是一个产生式且Y∈VN（省略若干描述）时的Y
413 * Input parameters: -Char（指定字符，即可能满足条件的产生式的左边字符）
414 * Return value: -String（Y构成的String字符串，无则为空）
415 * Exception: 未处理
416 * Author: 来自高山
417 * Created date: Sat Oct 12 2019 +0800
418 * Editor: 来自高山
419 * Edited Date: Sat Oct 12 2019 +0800
420 */
421 def findCase_Y_In_XY( ch: Char ): String = {
422 val localVN = VN
423 val localRelations = relations
424 var result = ""
425 if( localVN.contains(ch) == true ) {
426 for( ex <- localRelations ) {
427 if( ex._1(0) == ch ) {
428 if( ex._3 != "א" ) {
429 if( localVN.contains( ex._2(0) ) == true ) {
430 result += ex._2(0).toString
431 }
432 if( localVN.contains( ex._3(0) ) == true ) {
433 result += ex._3(0).toString
434 }
435 }
436 else {
437 if( localVN.contains( ex._2(0) ) == true ) {
438 result += ex._2(0).toString
439 }
440 }
441 }
442 }
443 }
444 result
445 }
446
447 /*
448 * Function name: findCase_Y_In_nY
449 * Function description: 获取构造FIRST集时可能的第3种情况的（2）时的FIRST(Yi)中所有的非ε-元素（省略描述若干字）
450 * Input parameters: -Char（指定字符，即可能满足条件的产生式的左边字符）
451 * Return value: -String（FIRST(Yi)中所有的非ε-元素构成的String字符串，无则为空）
452 * Exception: 未处理
453 * Author: 来自高山
454 * Created date: Sat Oct 12 2019 +0800
455 * Editor: 来自高山
456 * Edited Date: Sat Oct 12 2019 +0800
457 */
458 def findCase_Y_In_nY( ch: Char ): String = {
459 val localVN = VN
460 val localRelations = relations
461 var result = ""
462 for( ex <- localRelations ) {
463 if (ex._1 == ch.toString) {
464 var tmp = ""
465
466 if (ex._3 != 'א') {
467 var cnt = 0
468 for (tx <- ex._2) {
469 // add the element belongs to tmp
470 if (localVN.contains(tx)) {
471 tmp += tx.toString
472 cnt += 1
473 }
474 // otherwise, reset tmp as empty string
475 else {
476 tmp = ""
477 }
478 }
479 if (cnt == ex._2.length) {
480 result += tmp
481 }
482
483 // reset
484 cnt = 0
485 tmp = ""
486 for (tx <- ex._3) {
487 // add the element belongs to tmp
488 if (localVN.contains(tx)) {
489 tmp += tx.toString
490 cnt += 1
491 }
492 // otherwise, reset result as empty string
493 else {
494 tmp = ""
495 }
496 }
497 if (cnt == ex._3.length) {
498 result += tmp
499 }
500 }
501 else {
502 tmp = ""
503 var cnt = 0
504 for (tx <- ex._2) {
505 // add the element belongs to tmp
506 if (localVN.contains(tx)) {
507 tmp += tx.toString
508 cnt += 1
509 }
510 // otherwise, reset tmp as empty string
511 else {
512 tmp = ""
513 }
514 }
515 if (cnt == ex._2.length) {
516 result += tmp
517 }
518 }
519 }
520 }
521 result = result.distinct
522 result
523 }
524
525 /*
526 * Function name: FIRST
527 * Function description: 按照教材P78左下角的算法描述实现求解指定文法FIRST集；因用的是循环迭代求解，因此代码较长
528 * Input parameters: -ArrayBuffer[ (String, String) ]（产生式左右两部分分别构成元组的第1个和第2个元素）
529 * Return value: -Map[ String, String ]（Map的key是非终结符，value是其FIRST元素）
530 * Exception: 未处理
531 * Author: 来自高山
532 * Created date: Mon Oct 14 2019 +0800
533 * Editor: 来自高山
534 * Edited Date: Sat Oct 19 2019 +0800
535 */
536 def FIRST( string: ArrayBuffer[ (String, String) ] ): Map[ String, String ] = {
537 val FIRST_Group = Map[ String, String ]()
538
539 val wholeCharacters = allCharacters
540 val localVT = VT
541 val localVN = VN
542
543 for( character <- wholeCharacters ) {
544 // case 1
545 if( localVT.contains(character) ) {
546 //if there exist the original key that equals the current one
547 if( FIRST_Group.contains(character.toString) == true ) {
548 val tmp = character.toString + FIRST_Group(character.toString)
549 FIRST_Group(character.toString) = tmp.distinct
550 }
551 //otherwise
552 else {
553 FIRST_Group(character.toString) = character.toString
554 }
555 }
556
557 // case 2
558 if( localVN.contains(character.toString) == true ) {
559 // case 2.1
560 val value = findFirst(character.toString)
561 if ( value.length != 0 ) {
562 if ( FIRST_Group.contains(character.toString) == true ) {
563 for( ch <- value ) {
564 val tmp = ch + FIRST_Group(character.toString)
565 FIRST_Group(character.toString) = tmp.distinct
566 }
567 }
568 else {
569 FIRST_Group(character.toString) = value.toString
570 }
571 }
572
573 // case 2.2
574 if( judgeOnlyOneVoidSuccession(character.toString) == true ) {
575 if ( FIRST_Group.contains(character.toString) == true ) {
576 val tmp = "ε" + FIRST_Group(character.toString)
577 FIRST_Group(character.toString) = tmp.distinct
578 }
579 else {
580 FIRST_Group(character.toString) = "ε"
581 }
582 }
583 }
584
585 for( character <- wholeCharacters ) {
586 // case 3
587 // case 3.1
588 if( judgeCaseXY(character) == true ) {
589 val tmpReply = findCase_Y_In_XY(character)
590 for( eachTmpReply <- tmpReply ) {
591 if( FIRST_Group.contains(eachTmpReply.toString) == true ) {
592 for (ex <- FIRST_Group(eachTmpReply.toString)) {
593 if (ex != 'ε') {
594 if (FIRST_Group.contains(character.toString) == true) {
595 val tmp = ex.toString + FIRST_Group(character.toString)
596 FIRST_Group(character.toString) = tmp.distinct
597 }
598 else {
599 FIRST_Group(character.toString) = ex.toString
600 }
601 }
602 }
603 }
604 }
605 }
606
607 // case 3.2
608 if( findCase_Y_In_nY(character).length > 0 ) {
609 var flag = true
610 val tmpReply = findCase_Y_In_nY(character)
611
612 for( ex <- tmpReply ) {
613 if( localVN.contains(ex.toString) && FIRST_Group.contains(ex.toString) == true ) {
614 if( FIRST_Group(ex.toString).contains("ε") == false ) {
615 flag = false
616 }
617 }
618 else {
619 flag = false
620 }
621 if( flag == true ) {
622 if (FIRST_Group.contains(character.toString) == true) {
623 val tmp = FIRST_Group(ex.toString).replace( "ε", "" ) + FIRST_Group(character.toString)
624 FIRST_Group(character.toString) = tmp.distinct
625 }
626 else {
627 FIRST_Group(character.toString) = FIRST_Group(ex.toString).replace( "ε", "" )
628 }
629
630 }
631 }
632 }
633 // case 3.3
634 if( findCase_Y_In_nY(character).length > 0 ) {
635 var flag = true
636 val tmpReply = findCase_Y_In_nY(character)
637 for( ex <- tmpReply ) {
638 if( localVN.contains(ex.toString) && FIRST_Group.contains(ex.toString) == true ) {
639 if( FIRST_Group(ex.toString).contains("ε") == false ) {
640 flag = false
641 }
642 }
643 else {
644 flag = false
645 }
646 if( flag == true ) {
647
648 if (FIRST_Group.contains(character.toString) == true) {
649 val tmp = "ε" + FIRST_Group(character.toString)
650 FIRST_Group(character.toString) = tmp.distinct
651 }
652 else {
653 FIRST_Group(character.toString) = "ε"
654 }
655 }
656 }
657 }
658 }
659 }
660 FIRST_Group
661 }
662
663 /*
664 * Function name: FOLLOW
665 * Function description: 根据dfsFOLLOW函数，获取各个非终结符的FOLLOW集元素
666 * Input parameters: -ArrayBuffer[ (String, String) ]（产生式左右两部分分别构成元组的第1个和第2个元素）
667 * Return value: -Map[ String, String ]（Map的key是非终结符，value是其FOLLOW集元素）
668 * Exception: 未处理
669 * Author: 来自高山
670 * Created date: Sat Oct 19 2019 +0800
671 * Editor: 来自高山
672 * Edited Date: Sat Oct 19 2019 +0800
673 */
674 def FOLLOW( string: ArrayBuffer[ (String, String) ] ): Map[ String, String ] = {
675 val localVN = VN
676 val FOLLOW_Group = Map[ String, String ]()
677 for( ch <- localVN ) {
678 FOLLOW_Group(ch.toString) = dfsFOLLOW(ch.toString)
679 }
680 FOLLOW_Group
681 }
682
683 /*
684 * Function name: dfsFOLLOW
685 * Function description: 使用深度优先搜索（DFS）寻找各个非终结符的FOLLOW集元素
686 * Input parameters: -String（指定的非终结符）
687 * Return value: -String（指定终结符的FOLLOW集元素）
688 * Exception: 未处理
689 * Author: 来自高山
690 * Created date: Sat Oct 19 2019 +0800
691 * Editor: 来自高山
692 * Edited Date: Sat Oct 19 2019 +0800
693 */
694 def dfsFOLLOW( ch: String ): String = {
695 val FOLLOWPositions = Map[ String, String ]()
696 val FOLLOW_Group = Map[ String, String ]()
697 val localLL1_G = LL1_G
698 val FIRST_Group = FIRST(localLL1_G)
699 val localVN = VN
700 for( ch <- localVN ) {
701 FOLLOWPositions(ch.toString) = findGivenValueFOLLOWPosition(ch.toString)
702 FOLLOW_Group(ch.toString) = "#"
703 }
704 var result = ""
705
706 if( FOLLOWPositions(ch).length == 4 ) {
707 if( FOLLOWPositions(ch)(1).toString == "T" ) {
708 result += FIRST_Group( FOLLOWPositions(ch)(0).toString )
709 FOLLOW_Group(ch) += result.distinct
710 }
711 else if( FOLLOWPositions(ch)(3).toString == "T" ) {
712 result += FIRST_Group( FOLLOWPositions(ch)(2).toString )
713 FOLLOW_Group(ch) += result.distinct
714 }
715 if( FOLLOWPositions(ch)(1).toString == "W" ) {
716 result += dfsFOLLOW( FOLLOWPositions(ch)(0).toString )
717 FOLLOW_Group(ch) = result.distinct
718 }
719 else if( FOLLOWPositions(ch)(3).toString == "W" ) {
720 result += dfsFOLLOW( FOLLOWPositions(ch)(2).toString )
721 FOLLOW_Group(ch) = result.distinct
722 }
723 }
724
725 if( FOLLOWPositions(ch).length == 2 ) {
726 if( FOLLOWPositions(ch)(1).toString == "T" ) {
727 result += FIRST_Group( FOLLOWPositions(ch)(0).toString )
728 FOLLOW_Group(ch) = result.distinct
729 }
730 else if( FOLLOWPositions(ch)(1).toString == "W" ) {
731 result += dfsFOLLOW( FOLLOWPositions(ch)(0).toString )
732 FOLLOW_Group(ch) = result.distinct
733 }
734 }
735 FOLLOW_Group(ch).replace("ε", "")
736 }
737
738 /*
739 * Function name: findGivenValueFOLLOWPosition
740 * Function description: 按照教材P79右上角的算法描述，求解构成每个非终结符的FOLLOW集的“依赖”（因为实现了这个函数，节省了我原先用循环叠加求解FOLLOW集的700+代码）
741 * Input parameters: -String（指定终结符）
742 * Return value: -String（指定终结符的FOLLOW集元素，无则为空）
743 * Exception: 未处理
744 * Author: 来自高山
745 * Created date: Sat Oct 19 2019 +0800
746 * Editor: 来自高山
747 * Edited Date: Sat Oct 19 2019 +0800
748 */
749 def findGivenValueFOLLOWPosition( ch: String ): String = {
750 var result = ""
751 val cnt = new ArrayBuffer[String]()
752 val localRelations = relations
753
754 for( ex <- localRelations ) {
755 if( ex._3 != "א" ) {
756 if( ex._2.contains(ch) ) {
757 // מ
758 if( ex._2.length == 3 ) {
759 // B A α B β
760 if( ex._2(1).toString == ch && judgeCase2( ex._1, ex._2(0).toString, ch, ex._2(2).toString ) ) {
761 val value = ex._2(2).toString + "T"
762 if( cnt.contains(value) == false ) {
763 cnt += value
764 result += value
765 }
766 }
767 // B A α B β
768 if( ex._2(1).toString == ch && judgeCase3( ex._1, ex._2(0).toString, ch, ex._2(2).toString ) ) {
769 val value = ex._1.toString + "W"
770 if( cnt.contains(value) == false ) {
771 cnt += value
772 result += value
773 }
774 }
775 }
776 if( ex._2.length == 2 ) {
777 // B A α B
778 if( ex._2(1).toString == ch && judgeCase3( ex._1, ex._2(0).toString, ch, "" ) ) {
779 val value = ex._1 + "W"
780 if( cnt.contains(value) == false ) {
781 cnt += value
782 result += value
783 }
784 }
785 }
786 }
787 if( ex._3.contains(ch) ) {
788 if( ex._3.length == 3 ) {
789 // B A α B β
790 if( ex._3(1).toString == ch && judgeCase2( ex._1, ex._3(0).toString, ch, ex._3(2).toString ) ) {
791 val value = ex._3(2).toString + "T"
792 if( cnt.contains(value) == false ) {
793 cnt += value
794 result += value
795 }
796 }
797 if( ex._3(1).toString == ch && judgeCase3( ex._1, ex._3(0).toString, ch, ex._3(2).toString ) ) {
798 val value = ex._1 + "W"
799 if( cnt.contains(value) == false ) {
800 cnt += value
801 result += value
802 }
803 }
804 }
805 if( ex._3.length == 2 ) {
806 // B A α B
807 if( ex._3(1).toString == ch && judgeCase3( ex._1, ex._3(0).toString, ch, "" ) ) {
808 val value = ex._1 + "W"
809 if( cnt.contains(value) == false ) {
810 cnt += value
811 result += value
812 }
813 }
814 }
815 }
816 }
817 else {
818 if( ex._2.contains(ch) ) {
819 if( ex._2.length == 3 ) {
820 // B A α B β
821 if( ex._2(1).toString == ch && judgeCase2( ex._1, ex._2(0).toString, ch, ex._2(2).toString ) ) {
822 val value = ex._2(2).toString + "T"
823 if( cnt.contains(value) == false ) {
824 cnt += value
825 result += value
826 }
827 }
828 if( ex._2(1).toString == ch && judgeCase3( ex._1, ex._2(0).toString, ch, ex._2(2).toString ) ) {
829 val value = ex._1 + "T"
830 if( cnt.contains(value) == false ) {
831 cnt += value
832 result += value
833 }
834 }
835 }
836 if( ex._2.length == 2 ) {
837 // B A α B
838 if( ex._2(1).toString == ch && judgeCase3( ex._1, ex._2(0).toString, ch, "" ) ) {
839 val value = ex._1 + "W"
840 if( cnt.contains(value) == false ) {
841 cnt += value
842 result += value
843 }
844 }
845 }
846 }
847 }
848 }
849 result
850 }
851
852 /*
853 * Function name: judgeCase2
854 * Function description: 按照教材P79右下角的算法描述，判断是否填充满足条件（2）的矩阵元素
855 * Input parameters: -String, String, String, String[分别代表条件（2）的四个字符]
856 * Return value: -Boolean（满足条件（2）则返回true，否则返回false）
857 * Exception: 未处理
858 * Author: 来自高山
859 * Created date: Tue Oct 15 2019 +0800
860 * Editor: 来自高山
861 * Edited Date: Tue Oct 15 2019 +0800
862 */
863 def judgeCase2( A: String, α: String, B: String, β: String ): Boolean = {
864 val localVN = VN
865 val wholeCharacters = allCharacters
866 val localLL1_G = LL1_G
867 val localFIRST = FIRST(localLL1_G)
868 if( localVN.contains(A) == true && wholeCharacters.contains(α) == true && localVN.contains(B) == true &&
869 wholeCharacters.contains(β) && localFIRST.contains(β) == true ) {
870 true
871 }
872 else {
873 false
874 }
875 }
876
877 /*
878 * Function name: judgeCase3
879 * Function description: 按照教材P79右下角的算法描述，判断是否填充满足条件（3）的矩阵元素
880 * Input parameters: -String, String, String, String[分别代表条件（3）的四个字符]
881 * Return value: -Boolean（满足条件（3）则返回true，否则返回false）
882 * Exception: 未处理
883 * Author: 来自高山
884 * Created date: Wed Oct 16 2019 +0800
885 * Editor: 来自高山
886 * Edited Date: Wed Oct 16 2019 +0800
887 */
888 def judgeCase3( A: String, α: String, B: String, β: String ): Boolean = {
889 val localVN = VN
890 val wholeCharacters = allCharacters
891 val localLL1_G = LL1_G
892 val localFIRST = FIRST(localLL1_G)
893 if( ( localVN.contains(A) == true && wholeCharacters.contains(α) == true && localVN.contains(B) == true ) ||
894 ( localVN.contains(A) == true && wholeCharacters.contains(α) == true && localVN.contains(B) == true && localFIRST(β).contains("ε") == true ) ) {
895 true
896 }
897 else {
898 false
899 }
900 }
901
902 /*
903 * Function name: initiateMatrix
904 * Function description: 初始化分析表（为了在控制台打印方便，表长为非终结符个数加一，表宽为终结符个数加一）
905 * Input parameters: 无
906 * Return value: -Array[ Array[ String] ]（分析表矩阵元素构成的二维数组，除了第0行和第0列，其它列与行的元素均为null）
907 * Exception: 未处理
908 * Author: 来自高山
909 * Created date: Wed Oct 16 2019 +0800
910 * Editor: 来自高山
911 * Edited Date: Wed Oct 16 2019 +0800
912 */
913 def initiateMatrix(): Array[ Array[ String] ] = {
914 val localVN = VN
915 val localVT = VT
916 val result = Array.ofDim[String](localVN.length + 1, localVT.length + 1)
917 for( i <- 1 to localVN.length ) {
918 result(i)(0) = localVN(i - 1).toString
919 }
920 for( j <- 1 to localVT.length ) {
921 if( localVT(j - 1).toString == "ε" ) {
922 result(0)(j) = "#"
923 }
924 else {
925 result(0)(j) = localVT(j - 1).toString
926 }
927 }
928 result
929 }
930
931 /*
932 * Function name: createMatrix
933 * Function description: 按照教材P79右下角的算法描述，构造分析表
934 * Input parameters: 无
935 * Return value: -Array[ Array[String] ]（分析表矩阵元素构成的二维数组）
936 * Exception: 未处理
937 * Author: 来自高山
938 * Created date: Wed Oct 16 2019 +0800
939 * Editor: 来自高山
940 * Edited Date: Wed Oct 16 2019 +0800
941 */
942 def createMatrix(): Array[ Array[String] ] = {
943 val result = initiateMatrix()
944 val localVT = VT
945 val localRelations = relations
946 val localLL1_G = LL1_G
947 val localFIRST = FIRST(localLL1_G)
948 val localFOLLOW = FOLLOW(localLL1_G)
949
950 for( ex <- localRelations ) {
951
952 if( ex._3 != "א" ) {
953 for( a <- localVT ) {
954 val ex2Length = ex._2.length
955 var range = ""
956 var α = ""
957 var flag = false
958 for( x <- 0 to (ex2Length - 1) ) {
959 if( localFIRST( ex._2(x).toString ).contains("ε") == false && flag == false ) {
960 α = ex._2(x).toString
961 range = localFIRST( α )
962 flag = true
963 }
964 }
965 if( range.contains(a) == true && flag == true ) {
966 result(getRow(ex._1))(getColumn(a.toString)) = ex._1 + "->" + ex._2
967 }
968 if( flag == false ) {
969 range = "ε"
970 result( getRow(ex._1) )( getColumn("ε") ) = ex._1 + "->" + "ε"
971 }
972
973 // case 3
974 if( range.contains("ε") == true && flag == false ) {
975 for( b <- localFOLLOW(α) ) {
976 result( getRow(ex._1.toString) )( getColumn(b.toString) ) = ex._1 + "->" + ex._2 // t --> tx
977 }
978 }
979
980 val ex3Length = ex._3.length
981 range = ""
982 flag = false
983 for( x <- 0 to (ex3Length - 1) ) {
984 if( localFIRST( ex._3(x).toString ).contains("ε") == false && flag == false ) {
985 α = ex._3(x).toString
986 range = localFIRST( α )
987 flag = true
988 }
989 }
990 if( range.contains(a) == true && flag == true ) {
991 result( getRow(ex._1) )( getColumn(a.toString) ) = ex._1 + "->" + ex._3
992 }
993 if( flag == false ) {
994 range = "ε"
995 result(getRow(ex._1))(getColumn("ε")) = ex._1 + "->" + "ε"
996 }
997
998 // case 3
999 if( range.contains("ε") == true && flag == false ) {
1000 for( b <- localFOLLOW(ex._1) ) {
1001 result( getRow(ex._1.toString) )( getColumn(b.toString) ) = ex._1 + "->" + ex._3 // t --> tx
1002 }
1003 }
1004 }
1005 }
1006
1007 else {
1008 for( a <- localVT ) {
1009 val ex2Length = ex._2.length
1010 var range = ""
1011 var α = ""
1012 var flag = false
1013 for( x <- 0 to (ex2Length - 1) ) {
1014 if( localFIRST( ex._2(x).toString ).contains("ε") == false && flag == false ) {
1015 α = ex._2(x).toString
1016 range = localFIRST(α)
1017 flag = true
1018 }
1019 }
1020 if( range.contains(a) == true && flag == true ) {
1021 result( getRow(ex._1) )( getColumn(a.toString) ) = ex._1 + "->" + ex._2
1022 }
1023 if( flag == false ) {
1024 range = "ε"
1025 result( getRow(ex._1) )( getColumn("ε") ) = ex._1 + "->" + "ε"
1026 }
1027
1028 // case 3
1029 if( range.contains("ε") == true && flag == false ) {
1030 for( b <- localFOLLOW(ex._1) ) {
1031 result( getRow(ex._1.toString) )( getColumn(b.toString) ) = ex._1 + "->" + ex._2
1032 }
1033 }
1034 }
1035 }
1036 }
1037 result
1038 }
1039
1040 /*
1041 * Function name: getRow
1042 * Function description: 获取指定字符在分析表中的行数
1043 * Input parameters: -String（指定字符）
1044 * Return value: -Int（指定字符所在的行数）
1045 * Exception: 未处理
1046 * Author: 来自高山
1047 * Created date: Wed Oct 16 2019 +0800
1048 * Editor: 来自高山
1049 * Edited Date: Wed Oct 16 2019 +0800
1050 */
1051 def getRow( ch: String ): Int = {
1052 val matrix = initiateMatrix()
1053 var result = -1
1054 if( ch == "α" ) {
1055 println( "1 --- getRow, ch == " + ch )
1056 }
1057 for( i <- 0 to (matrix.length - 1) ) {
1058 if( matrix(i)(0) == ch ) {
1059 result = i
1060 }
1061 }
1062 result
1063 }
1064
1065 /*
1066 * Function name: getColumn
1067 * Function description: 获取指定字符在分析表中的列数
1068 * Input parameters: -String（指定字符）
1069 * Return value: -Int（指定字符所在的列数）
1070 * Exception: 未处理
1071 * Author: 来自高山
1072 * Created date: Wed Oct 16 2019 +0800
1073 * Editor: 来自高山
1074 * Edited Date: Wed Oct 16 2019 +0800
1075 */
1076 def getColumn( ch: String ): Int = {
1077 val matrix = initiateMatrix()
1078 var result = -1
1079 for( i <- 0 to (matrix.length - 1) ) {
1080 for( j <- 0 to (matrix(i).length - 1) ) {
1081 if( matrix(0)(j) == ch ) {
1082 result = j
1083 }
1084 if( matrix(0)(j) == "#" && ch == "ε" ) {
1085 result = j
1086 }
1087 }
1088 }
1089 result
1090 }
1091
1092 /*
1093 * Function name: analyse
1094 * Function description: 对指定的字符串进行LL(1)分析
1095 * Input parameters: -String（输入的指定字符串）
1096 * Return value: -Boolean（分析成功则返回true，否则false）
1097 * Exception: 未处理（有出错提示）
1098 * Author: 来自高山
1099 * Created date: Wed Oct 16 2019 +0800
1100 * Editor: 来自高山
1101 * Edited Date: Wed Oct 16 2019 +0800
1102 */
1103 def analyse( expression: String ): Boolean = {
1104 val stack = new mutable.Stack[String]()
1105 var localExpression = expression
1106 val table = createMatrix()
1107 val localVT = VT
1108 val localVN = VN
1109 val localRelations = relations
1110
1111 stack.push("#")
1112 stack.push( localRelations(0)._1 )
1113
1114 var cnt = 0
1115 println( cnt + " " + " stack = " + stack + ", expression = " + localExpression + " initiate" )
1116
1117 while( stack.isEmpty == false ) {
1118 val stackTop = stack.top
1119 stack.pop()
1120 // 栈顶符号属于 非终结符
1121 if( localVN.contains(stackTop) == true ) {
1122 // 栈顶符号与表达式左端首字符 存在 关系
1123 if( table( getRow(stackTop) )( getColumn( localExpression(0).toString ) ) != null ) {
1124 val lastHalf = table( getRow(stackTop) )( getColumn( localExpression(0).toString ) ).split( "->", 2 ).last
1125 val length = lastHalf.length
1126 for( i <- 0 to (length - 1) ) {
1127 if( lastHalf != "ε" ) {
1128 stack.push(lastHalf(length - 1 - i).toString)
1129 }
1130 }
1131 cnt += 1
1132 println( cnt + " " + " stack = " + stack + ", expression = " + localExpression +
1133 ", analyse expression = " + table( getRow(stackTop) )( getColumn( localExpression(0).toString ) ) + ", POP, PUSH(" + lastHalf.reverse + ")")
1134 }
1135 // 栈顶符号与表达式左端首字符 不存在 关系
1136 else {
1137 // 栈顶符号 等于 表达式左端首字符
1138 if( stackTop == "#" && localExpression(0).toString == "#" ) {
1139 println("11111")
1140 return true
1141 }
1142 // 栈顶符号 不等于 表达式左端首字符
1143 else {
1144 println("1 - error")
1145 //stack.push( localExpression(0).toString )
1146 println( cnt + " " + " stack = " + stack + ", expression = " + localExpression )
1147 return false
1148 }
1149 }
1150 }
1151 // 栈顶符号属于 终结符
1152 if( localVT.contains(stackTop) == true ) {
1153 // 栈顶符号 等于 表达式左端首字符
1154 if( stackTop == localExpression(0).toString ) {
1155 if( stackTop == localExpression(0).toString ) {
1156 //stack.pop()
1157 localExpression = localExpression.drop(1)
1158 cnt += 1
1159 println( cnt + " " + " stack = " + stack + ", expression = " + localExpression + ", GETNEXT(" + stackTop + ")" )
1160 }
1161 // 栈顶符号 不等于 表达式左端首字符
1162 else {
1163 println("2 - error")
1164 return false
1165 }
1166 }
1167 }
1168 }
1169 true
1170 }
1171
1172 /*
1173 * Function name: judgeLeftRecursion
1174 * Function description: 判断是否存在形式上的左递归
1175 * Input parameters: -(String, String, String)（产生式的左端与右端的两个（或为1个）元素）
1176 * Return value: -Int（0表示无，1表示右端第1个元素存在形式上的左递归，2表示右端第2个元素）
1177 * Exception: 未处理
1178 * Author: 来自高山
1179 * Created date: Sat Oct 19 2019 +0800
1180 * Editor: 来自高山
1181 * Edited Date: Sat Oct 19 2019 +0800
1182 */
1183 def judgeLeftRecursion( expression: (String, String, String) ): Int = {
1184 var ans = 0 // ans = 0 means the current expression is not involved left-recursion
1185 if( expression._2.length >= 2 && expression._1 == expression._2(0).toString && expression._2.drop(1) != "ε" ) {
1186 ans += 1 // ans = 1 means the left recursion involves the expression._2
1187 }
1188 if( expression._3.length >= 2 && expression._1 == expression._3(0).toString && expression._3.drop(1) != "ε" ) {
1189 ans += 2 // ans = 2 means the left recursion involves the expression._3
1190 }
1191 ans // ans = 3 means the given expression is false since both exp(2) and exp(3) involved
1192 }
1193
1194 /*
1195 * Function name: eliminateLeftRecursion
1196 * Function description: 消除形式上的左递归
1197 * Input parameters: 无
1198 * Return value: -ArrayBuffer[ (String, String, String) ]（消除左递归后的新文法）
1199 * Exception: 未处理
1200 * Author: 来自高山
1201 * Created date: Sat Oct 19 2019 +0800
1202 * Editor: 来自高山
1203 * Edited Date: Sat Oct 19 2019 +0800
1204 */
1205 def eliminateLeftRecursion(): ArrayBuffer[ (String, String, String) ] = {
1206 var localRelations = relations
1207 var invalidRelations = new ArrayBuffer[ (String, String, String) ]()
1208 val localCandidateLetters = allCandidateLetters
1209 val VN1 = "ΑΒΓΔΕΖΗΘΙΚΛΜΝΞΟΠΡΣΤΥΦΧΨΩABCDEFGHIJKLMNOPQRSTUVWXYZ"
1210 val VT1 = "αβγδεζηθικλμνξοπρστυφχψωabcdefghijklmnopqrstuvwxyz"
1211 for( ex <- localRelations ) {
1212 if( ex._3 != "א" ) {
1213 if( judgeLeftRecursion( ex._1, ex._2, ex._3 ) == 1 ) {
1214 // P = ex._1, α = ex._2 - ex._1, β = ex._3, P' = newValue
1215 invalidRelations += ( ( ex._1, ex._2, ex._3 ) )
1216 val newValue = subString( usedCharacters, localCandidateLetters )(0)
1217 usedCharacters += newValue
1218 if( VN1.contains(newValue) && !VN.contains(newValue) ) {
1219 VN += newValue.toString
1220 allCharacters += newValue.toString
1221 }
1222 if( VT1.contains(newValue) && !VT.contains(newValue) ) {
1223 VT += newValue.toString
1224 allCharacters += newValue.toString
1225 }
1226 val α = ex._2.drop(1)
1227 val exp1 = ( ex._1, ex._3 + newValue.toString, "א" )
1228 val exp2 = ( newValue.toString, α.toString + newValue.toString, "ε" )
1229 // println( "1 -- exp1._1 = " + exp1._1 + ", exp1._2 = " + exp1._2 + ", exp1._3 = " + exp1._3 )
1230 // println( "1 -- exp2._1 = " + exp2._1 + ", exp2._2 = " + exp2._2 + ", exp2._3 = " + exp2._3 )
1231 localRelations += exp1
1232 localRelations += exp2
1233 }
1234 else if( judgeLeftRecursion( ex._1, ex._2, ex._3 ) == 2 ) {
1235 // P = ex._1, α = ex._3 - ex._1, β = ex._3, P' = newValue
1236 invalidRelations += ( ( ex._1, ex._2, ex._3 ) )
1237 val newValue = subString( usedCharacters, localCandidateLetters )(0)
1238 if( VN1.contains(newValue) && !VN.contains(newValue) ) {
1239 VN += newValue.toString
1240 allCharacters += newValue.toString
1241 }
1242 if( VT1.contains(newValue) && !VT.contains(newValue) ) {
1243 VT += newValue.toString
1244 allCharacters += newValue.toString
1245 }
1246 usedCharacters += newValue
1247 val α = ex._3.drop(1)
1248 val exp1 = ( ex._1, ex._3 + newValue.toString, "א" )
1249 val exp2 = ( newValue.toString, α.toString + newValue.toString, "ε" )
1250 // println( "2 -- exp1._1 = " + exp1._1 + ", exp1._2 = " + exp1._2 + ", exp1._3 = " + exp1._3 )
1251 // println( "2 -- exp2._1 = " + exp2._1 + ", exp2._2 = " + exp2._2 + ", exp2._3 = " + exp2._3 )
1252 localRelations += exp1
1253 localRelations += exp2
1254 }
1255 else if( judgeLeftRecursion( ex._1, ex._2, ex._3 ) == 3 ){
1256 println( "error in the function eliminateLeftRecursion" )
1257 }
1258 }
1259 else {
1260 if( judgeLeftRecursion( ex._1, ex._2, ex._3 ) == 1 ) {
1261 // P = ex._1, α = ex._2 - ex._1, β = ex._3, P' = newValue
1262 invalidRelations += ( ( ex._1, ex._2, ex._3 ) )
1263 val newValue = subString( usedCharacters, localCandidateLetters )(0)
1264 if( VN1.contains(newValue) && !VN.contains(newValue) ) {
1265 VN += newValue.toString
1266 allCharacters += newValue.toString
1267 }
1268 if( VT1.contains(newValue) && !VT.contains(newValue) ) {
1269 VT += newValue.toString
1270 allCharacters += newValue.toString
1271 }
1272 usedCharacters += newValue
1273 val α = ex._2.drop(1)
1274 val exp1 = ( ex._1, newValue.toString, "א" )
1275 val exp2 = ( newValue.toString, α.toString + newValue.toString, "ε" )
1276 // println( "3 -- exp1._1 = " + exp1._1 + ", exp1._2 = " + exp1._2 + ", exp1._3 = " + exp1._3 )
1277 // println( "3 -- exp2._1 = " + exp2._1 + ", exp2._2 = " + exp2._2 + ", exp2._3 = " + exp2._3 )
1278 localRelations += exp1
1279 localRelations += exp2
1280 }
1281 }
1282 }
1283 for( ex <- invalidRelations ) {
1284 localRelations = localRelations.-(ex)
1285 }
1286 relations = localRelations
1287 localRelations
1288 }
1289
1290 /*
1291 * Function name: subString
1292 * Function description: 获取两输入字符串的差集（要求两者均非空）
1293 * Input parameters: 无
1294 * Return value: -String（两输入字符串的差集）
1295 * Exception: 未处理
1296 * Author: 来自高山
1297 * Created date: Sat Oct 19 2019 +0800
1298 * Editor: 来自高山
1299 * Edited Date: Sat Oct 19 2019 +0800
1300 */
1301 def subString( usedCharacters: String, localCandidateLetters: String ): String = {
1302 require( usedCharacters.length != 0 && localCandidateLetters.length != 0 )
1303 var ans = ""
1304 var A = usedCharacters
1305 var B = localCandidateLetters
1306 if( A.length < B.length ) {
1307 val tmp = A
1308 A = B
1309 B = tmp
1310 }
1311 for( i <- 0 to (A.length - 1) ) {
1312 var j = 0
1313 while( j < B.length && B(j) != A(i) ) {
1314 j += 1
1315 }
1316 if( j == B.length ) {
1317 ans += A(i)
1318 }
1319 }
1320 ans
1321 }
1322 }