36 def zeroable (r: Rexp) : Boolean = r match { |
36 def zeroable (r: Rexp) : Boolean = r match { |
37 case NULL => true |
37 case NULL => true |
38 case EMPTY => false |
38 case EMPTY => false |
39 case CHAR(_) => false |
39 case CHAR(_) => false |
40 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
40 case ALT(r1, r2) => zeroable(r1) && zeroable(r2) |
41 case SEQ(r1, r2) => zeroable(r1) || zeroable(r2) |
41 case SEQ(r1, r2) => if (nullable(r1)) (zeroable(r1) && zeroable(r2)) else zeroable(r1) |
42 case STAR(_) => false |
42 case STAR(_) => false |
43 case NOT(r) => !(zeroable(r)) |
43 case NOT(r) => !(zeroable(r)) |
44 } |
44 } |
45 |
45 |
46 |
46 |
87 val NONZERODIGITS = RANGE("123456789".toList) |
87 val NONZERODIGITS = RANGE("123456789".toList) |
88 |
88 |
89 val IDENT = SEQ(LETTER, STAR(ALT(LETTER,DIGITS))) |
89 val IDENT = SEQ(LETTER, STAR(ALT(LETTER,DIGITS))) |
90 val NUMBER = ALT(SEQ(NONZERODIGITS, STAR(DIGITS)), "0") |
90 val NUMBER = ALT(SEQ(NONZERODIGITS, STAR(DIGITS)), "0") |
91 val WHITESPACE = RANGE(" \n".toList) |
91 val WHITESPACE = RANGE(" \n".toList) |
|
92 val WHITESPACES = PLUS(WHITESPACE) |
92 |
93 |
93 val ALL = ALT(ALT(LETTER, DIGITS), WHITESPACE) |
94 val ALL = ALT(ALT(LETTER, DIGITS), WHITESPACE) |
94 |
95 |
95 val COMMENT = SEQ(SEQ("/*", NOT(SEQ(SEQ(STAR(ALL), "*/"), STAR(ALL)))), "*/") |
96 val COMMENT = SEQ(SEQ("/*", NOT(SEQ(SEQ(STAR(ALL), "*/"), STAR(ALL)))), "*/") |
96 |
97 |
111 println(matcher(COMMENT, "/* */")) |
112 println(matcher(COMMENT, "/* */")) |
112 println(matcher(COMMENT, "/* foobar comment */")) |
113 println(matcher(COMMENT, "/* foobar comment */")) |
113 println(matcher(COMMENT, "/* test */ test */")) |
114 println(matcher(COMMENT, "/* test */ test */")) |
114 |
115 |
115 // an example list of regular expressions |
116 // an example list of regular expressions |
116 val regs: List[Rexp]= List("if", "then", "else", "+", IDENT, NUMBER, WHITESPACE) |
117 val regs: List[Rexp]= List("if", "then", "else", "+", IDENT, NUMBER, WHITESPACES) |
117 |
118 |
118 def error (s: String) = throw new IllegalArgumentException ("Could not lex " + s) |
119 def error (s: String) = throw new IllegalArgumentException ("Could not lex " + s) |
119 |
120 |
120 def munch(r: Rexp, s: List[Char], t: List[Char]) : Option[(List[Char], List[Char])] = s match { |
121 def munch(r: Rexp, s: List[Char], t: List[Char]) : Option[(List[Char], List[Char])] = s match { |
121 case Nil if (nullable(r)) => Some(Nil, t) |
122 case Nil if (nullable(r)) => Some(Nil, t) |
135 case _ => lex_one(regs, s) match { |
136 case _ => lex_one(regs, s) match { |
136 case (rest, s) => s.mkString :: lex_all(regs, rest) |
137 case (rest, s) => s.mkString :: lex_all(regs, rest) |
137 } |
138 } |
138 } |
139 } |
139 |
140 |
140 println(lex_all(rules, "if true then 42 else +".toList)) |
141 val regs: List[Rexp]= List("if", "then", "else", "+", IDENT, NUMBER, WHITESPACES) |
141 println(lex_all(rules, "ifff if 34 34".toList)) |
|
142 println(lex_all(rules, "ifff $ if 34".toList)) |
|
143 |
142 |
|
143 println(lex_all(regs, "if true then 42 else +".toList)) |
|
144 println(lex_all(regs, "ifff if 34 34".toList)) |
|
145 println(lex_all(regs, "ifff +if+ 34 34".toList)) |
|
146 println(lex_all(regs, "1+x+3+4+foo".toList)) |
|
147 println(lex_all(regs, "ifff $ if 34".toList)) |
|
148 |