|
1 import scala.language.implicitConversions |
|
2 import scala.language.reflectiveCalls |
|
3 import scala.annotation.tailrec |
|
4 import scala.io.Source |
|
5 import scala.util.parsing.combinator._ |
|
6 |
|
7 abstract class Rexp |
|
8 case object ZERO extends Rexp |
|
9 case object ONE extends Rexp |
|
10 case class CHAR(c: Char) extends Rexp { |
|
11 override def toString = c.toString |
|
12 } |
|
13 case class ALT(r1: Rexp, r2: Rexp) extends Rexp { |
|
14 override def toString = "(" + r1.toString + "|" + r2.toString + ")" |
|
15 } |
|
16 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp { |
|
17 override def toString = "(" + r1.toString + r2.toString +")" |
|
18 } |
|
19 case class STAR(r: Rexp) extends Rexp |
|
20 case class RECD(x: String, r: Rexp) extends Rexp |
|
21 |
|
22 case class Parser(s: String) { |
|
23 var i = 0 |
|
24 |
|
25 def peek() = s(i) |
|
26 def eat(c: Char) = |
|
27 if (c == s(i)) i = i + 1 else throw new Exception("Expected " + c + " got " + s(i)) |
|
28 def next() = { i = i + 1; s(i - 1) } |
|
29 def more() = s.length - i > 0 |
|
30 |
|
31 def Regex() : Rexp = { |
|
32 val t = Term(); |
|
33 if (more() && peek() == '|') { |
|
34 eat ('|') ; |
|
35 val r = Regex(); |
|
36 ALT(t, r) |
|
37 } |
|
38 else t |
|
39 } |
|
40 |
|
41 def Term() : Rexp = { |
|
42 var f : Rexp = if (more() && peek() != ')' && peek() != '|') Factor() else ZERO; |
|
43 while (more() && peek() != ')' && peek() != '|') { |
|
44 var nextf = Factor(); |
|
45 f = SEQ(f, nextf) ; |
|
46 } |
|
47 |
|
48 f |
|
49 } |
|
50 |
|
51 def Factor() : Rexp = { |
|
52 var b = Base(); |
|
53 while (more() && peek() == '*') { |
|
54 eat('*') ; |
|
55 b = STAR(b) ; |
|
56 } |
|
57 |
|
58 b |
|
59 } |
|
60 |
|
61 def Base() : Rexp = { |
|
62 peek() match { |
|
63 case '(' => { eat('(') ; val r = Regex(); eat(')') ; r } |
|
64 case _ => CHAR(next()) |
|
65 } |
|
66 } |
|
67 } |
|
68 |
|
69 println(Parser("a|(bc)*").Regex()) |
|
70 |
|
71 |
|
72 def process(line: String) : String = { |
|
73 val s = line.split("\\t+")(1) |
|
74 s + ": " + Parser(s).Regex().toString |
|
75 } |
|
76 |
|
77 |
|
78 val filename = "../tests/forced-assoc.txt" |
|
79 val filelines : List[String] = Source.fromFile(filename).getLines.toList |
|
80 |
|
81 |
|
82 filelines.foreach((s: String) => println(process(s))) |
|
83 |