equal
deleted
inserted
replaced
1 :load matcher.scala |
1 // Parser combinators including semantic actions |
|
2 // parses lists of tokens |
|
3 // |
|
4 // Needs |
|
5 // :load matcher.scala |
2 |
6 |
3 // some regular expressions |
7 // some regular expressions |
4 val LETTER = RANGE("abcdefghijklmnopqrstuvwxyz".toList) |
8 val LETTER = RANGE("abcdefghijklmnopqrstuvwxyz") |
5 val ID = PLUS(LETTER) |
9 val ID = PLUS(LETTER) |
6 |
10 |
7 val DIGIT = RANGE("0123456789".toList) |
11 val DIGIT = RANGE("0123456789") |
8 val NONZERODIGIT = RANGE("123456789".toList) |
12 val NONZERODIGIT = RANGE("123456789") |
9 val NUMBER = ALT(SEQ(NONZERODIGIT, STAR(DIGIT)), "0") |
13 val NUMBER = ALT(SEQ(NONZERODIGIT, STAR(DIGIT)), "0") |
10 |
14 |
11 val LPAREN = CHAR('(') |
15 val LPAREN = CHAR('(') |
12 val RPAREN = CHAR(')') |
16 val RPAREN = CHAR(')') |
13 |
17 |
14 val WHITESPACE = PLUS(RANGE(" \n".toList)) |
18 val WHITESPACE = PLUS(RANGE(" \n")) |
15 val OPS = RANGE("+-*".toList) |
19 val OPS = RANGE("+-*") |
16 |
20 |
17 // for classifying the strings that have been recognised |
21 // for classifying the strings that have been recognised |
18 abstract class Token |
22 abstract class Token |
19 |
23 |
20 case object T_WHITESPACE extends Token |
24 case object T_WHITESPACE extends Token |
25 case object T_RPAREN extends Token |
29 case object T_RPAREN extends Token |
26 case object T_IF extends Token |
30 case object T_IF extends Token |
27 case object T_THEN extends Token |
31 case object T_THEN extends Token |
28 case object T_ELSE extends Token |
32 case object T_ELSE extends Token |
29 |
33 |
30 def tokenizer(rs: List[Rule[Token]], s: String) : List[Token] = |
|
31 tokenize(rs, s.toList).filterNot(_ match { |
|
32 case T_WHITESPACE => true |
|
33 case _ => false |
|
34 }) |
|
35 |
|
36 |
|
37 // lexing rules for arithmetic expressions |
34 // lexing rules for arithmetic expressions |
38 val lexing_rules: List[Rule[Token]]= |
35 val lexing_rules: List[Rule[Token]]= |
39 List(("if", (s) => T_IF), |
36 List(("if", (s) => T_IF), |
40 ("then", (s) => T_THEN), |
37 ("then", (s) => T_THEN), |
41 ("else", (s) => T_ELSE), |
38 ("else", (s) => T_ELSE), |
44 (WHITESPACE, (s) => T_WHITESPACE), |
41 (WHITESPACE, (s) => T_WHITESPACE), |
45 (LPAREN, (s) => T_LPAREN), |
42 (LPAREN, (s) => T_LPAREN), |
46 (RPAREN, (s) => T_RPAREN), |
43 (RPAREN, (s) => T_RPAREN), |
47 (OPS, (s) => T_OP(s.mkString))) |
44 (OPS, (s) => T_OP(s.mkString))) |
48 |
45 |
|
46 val Tok = Tokenizer(lexing_rules, List(T_WHITESPACE)) |
49 |
47 |
50 // parser combinators with return type T |
48 // parser combinators with return type T |
51 abstract class Parser[T] { |
49 abstract class Parser[T] { |
52 def parse(ts: List[Token]): Set[(T, List[Token])] |
50 def parse(ts: List[Token]): Set[(T, List[Token])] |
53 |
51 |
96 |
94 |
97 lazy val E: Parser[Int] = (T ~ T_OP("+") ~ E) ==> { case ((x, y), z) => x + z } || T |
95 lazy val E: Parser[Int] = (T ~ T_OP("+") ~ E) ==> { case ((x, y), z) => x + z } || T |
98 lazy val T: Parser[Int] = (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => x * z } || F |
96 lazy val T: Parser[Int] = (F ~ T_OP("*") ~ T) ==> { case ((x, y), z) => x * z } || F |
99 lazy val F: Parser[Int] = (T_LPAREN ~> E <~ T_RPAREN) || NumParser |
97 lazy val F: Parser[Int] = (T_LPAREN ~> E <~ T_RPAREN) || NumParser |
100 |
98 |
101 println(E.parse_all(tokenizer(lexing_rules, "1 + 2 + 3"))) |
99 println(E.parse_all(Tok.fromString("1 + 2 + 3"))) |
102 println(E.parse_all(tokenizer(lexing_rules, "1 + 2 * 3"))) |
100 println(E.parse_all(Tok.fromString("1 + 2 * 3"))) |
103 println(E.parse_all(tokenizer(lexing_rules, "(1 + 2) * 3"))) |
101 println(E.parse_all(Tok.fromString("(1 + 2) * 3"))) |
104 |
102 |
105 println(E.parse_all(tokenizer(lexing_rules, "(1 - 2) * 3"))) |
103 // Excercise: implement minus |
106 println(E.parse_all(tokenizer(lexing_rules, "(1 + 2) * - 3"))) |
104 println(E.parse_all(Tok.fromString("(1 - 2) * 3"))) |
|
105 println(E.parse_all(Tok.fromString("(1 + 2) * - 3"))) |