From 7c574439453b88d328d975845c2e55499b56bf14 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Wed, 18 Jul 2007 21:55:59 +0000 Subject: added another example using the combinator pars... added another example using the combinator parsers, courtesy of Miles Sabin (slightly simplified/adapted to new combinators) --- docs/examples/parsing/lambda/Main.scala | 34 +++++++++++ docs/examples/parsing/lambda/TestParser.scala | 68 +++++++++++++++++++++ docs/examples/parsing/lambda/TestSyntax.scala | 86 +++++++++++++++++++++++++++ docs/examples/parsing/lambda/test/test-01.kwi | 1 + docs/examples/parsing/lambda/test/test-02.kwi | 1 + docs/examples/parsing/lambda/test/test-03.kwi | 1 + docs/examples/parsing/lambda/test/test-04.kwi | 1 + docs/examples/parsing/lambda/test/test-05.kwi | 1 + docs/examples/parsing/lambda/test/test-06.kwi | 1 + docs/examples/parsing/lambda/test/test-07.kwi | 1 + docs/examples/parsing/lambda/test/test-08.kwi | 1 + 11 files changed, 196 insertions(+) create mode 100755 docs/examples/parsing/lambda/Main.scala create mode 100755 docs/examples/parsing/lambda/TestParser.scala create mode 100755 docs/examples/parsing/lambda/TestSyntax.scala create mode 100755 docs/examples/parsing/lambda/test/test-01.kwi create mode 100755 docs/examples/parsing/lambda/test/test-02.kwi create mode 100755 docs/examples/parsing/lambda/test/test-03.kwi create mode 100755 docs/examples/parsing/lambda/test/test-04.kwi create mode 100755 docs/examples/parsing/lambda/test/test-05.kwi create mode 100755 docs/examples/parsing/lambda/test/test-06.kwi create mode 100755 docs/examples/parsing/lambda/test/test-07.kwi create mode 100755 docs/examples/parsing/lambda/test/test-08.kwi (limited to 'docs/examples/parsing/lambda') diff --git a/docs/examples/parsing/lambda/Main.scala b/docs/examples/parsing/lambda/Main.scala new file mode 100755 index 0000000000..c0453e75a8 --- /dev/null +++ b/docs/examples/parsing/lambda/Main.scala @@ -0,0 +1,34 @@ +package examples.parsing.lambda + +import scala.util.parsing.combinator.Parsers +import scala.util.parsing.input.StreamReader + +import java.io.File +import java.io.FileInputStream +import java.io.InputStreamReader + +/** + * Parser for an untyped lambda calculus + * + * Usage: scala examples.parsing.lambda.Main + * + * (example files: see test/*.kwi) + * + * @author Miles Sabin (adapted slightly by Adriaan Moors) + */ +object Main extends Application with TestParser +{ + override def main(args: Array[String]) = + { + val in = StreamReader(new InputStreamReader(new FileInputStream(new File(args(0))), "ISO-8859-1")) + parse(in) match + { + case Success(term, _) => + { + Console.println("Term: \n"+term) + } + case Failure(msg, remainder) => Console.println("Failure: "+msg+"\n"+"Remainder: \n"+remainder.pos.longString) + case Error(msg, remainder) => Console.println("Error: "+msg+"\n"+"Remainder: \n"+remainder.pos.longString) + } + } +} diff --git a/docs/examples/parsing/lambda/TestParser.scala b/docs/examples/parsing/lambda/TestParser.scala new file mode 100755 index 0000000000..92d370c29b --- /dev/null +++ b/docs/examples/parsing/lambda/TestParser.scala @@ -0,0 +1,68 @@ +package examples.parsing.lambda + +import scala.util.parsing.input.Reader +import scala.util.parsing.combinator.lexical.StdLexical +import scala.util.parsing.combinator.syntactical.StdTokenParsers +import scala.util.parsing.combinator.ImplicitConversions + +/** + * Parser for an untyped lambda calculus + * + * @author Miles Sabin (adapted slightly by Adriaan Moors) + */ +trait TestParser extends StdTokenParsers with ImplicitConversions with TestSyntax +{ + type Tokens = StdLexical + val lexical = new StdLexical + lexical.reserved ++= List("unit", "let", "in", "if", "then", "else") + lexical.delimiters ++= List("=>", "->", "==", "(", ")", "=", "\\", "+", "-", "*", "/") + + + def name : Parser[Name] = ident ^^ Name + + // meaning of the argumens to the closure during subsequent iterations + // (...(expr2 op1 expr1) ... op1 expr1) + // ^a^^^ ^o^ ^b^^^ + // ^^^^^^^a^^^^^^^ ^o^ ^^b^^ + def expr1 : Parser[Term] = + chainl1(expr2, expr1, op1 ^^ {o => (a: Term, b: Term) => App(App(o, a), b)}) + + def expr2 : Parser[Term] = + chainl1(expr3, expr2, op2 ^^ {o => (a: Term, b: Term) => App(App(o, a), b)}) + + def expr3 : Parser[Term] = + chainl1(expr4, expr3, op3 ^^ {o => (a: Term, b: Term) => App(App(o, a), b)}) + + def expr4 : Parser[Term] = + ( "\\" ~ lambdas + | "let" ~ name ~ "=" ~ expr1 ~ "in" ~ expr1 ^^ flatten3(Let) + | "if" ~ expr1 ~ "then" ~ expr1 ~ "else" ~ expr1 ^^ flatten3(If) + | chainl1(aexpr, success(App(_: Term, _: Term))) + ) + + def lambdas : Parser[Term] = + name ~ ("->" ~ expr1 | lambdas) ^^ flatten2(Lam) + + def aexpr : Parser[Term] = + ( numericLit ^^ (_.toInt) ^^ Lit + | name ^^ Ref + | "unit" ^^ Unit + | "(" ~ expr1 ~ ")" + ) + + def op1 : Parser[Term] = + "==" ^^ Ref(Name("==")) + + def op2 : Parser[Term] = + ( "+" ^^ Ref(Name("+")) + | "-" ^^ Ref(Name("-")) + ) + + def op3 : Parser[Term] = + ( "*" ^^ Ref(Name("*")) + | "/" ^^ Ref(Name("/")) + ) + + def parse(r: Reader[char]) : ParseResult[Term] = + phrase(expr1)(new lexical.Scanner(r)) +} diff --git a/docs/examples/parsing/lambda/TestSyntax.scala b/docs/examples/parsing/lambda/TestSyntax.scala new file mode 100755 index 0000000000..531ae4bd54 --- /dev/null +++ b/docs/examples/parsing/lambda/TestSyntax.scala @@ -0,0 +1,86 @@ +package examples.parsing.lambda + +/** + * Parser for an untyped lambda calculus: abstract syntax tree + * + * @author Miles Sabin (adapted slightly by Adriaan Moors) + */ +trait TestSyntax +{ + trait Term + + case class Unit extends Term + { + override def toString = "unit" + } + + case class Lit(n: int) extends Term + { + override def toString = n.toString + } + + case class Bool(b: boolean) extends Term + { + override def toString = b.toString + } + + case class Name(name: String) extends Term + { + override def toString = name + } + + case class Ref(n: Name) extends Term + { + def value = n + } + + case class Lam(n: Name, l: Term) extends Term + { + override def toString = "(\\ "+n+" -> "+l+")" + } + + case class App(t1: Term, t2: Term) extends Term + { + override def toString = "("+t1+" "+t2+")" + } + + case class Let(n: Name, t1: Term, t2: Term) extends Term + { + override def toString = "let "+n+" = "+t1+" in "+t2 + } + + case class If(c: Term, t1: Term, t2: Term) extends Term + { + override def toString = "if "+c+" then "+t1+" else "+t2 + } + + trait PrimTerm extends Term + { + def apply(n: Lit) : Term + } + + case class PrimPlus extends PrimTerm + { + def apply(x: Lit) = new PrimTerm { def apply(y: Lit) = Lit(x.n+y.n) } + } + + case class PrimMinus extends PrimTerm + { + def apply(x: Lit) = new PrimTerm { def apply(y: Lit) = Lit(x.n-y.n) } + } + + case class PrimMultiply extends PrimTerm + { + def apply(x: Lit) = new PrimTerm { def apply(y: Lit) = Lit(x.n*y.n) } + } + + case class PrimDivide extends PrimTerm + { + def apply(x: Lit) = new PrimTerm { def apply(y: Lit) = Lit(x.n/y.n) } + } + + case class PrimEquals extends PrimTerm + { + def apply(x: Lit) = new PrimTerm { def apply(y: Lit) = Bool(x.n == y.n) } + } +} diff --git a/docs/examples/parsing/lambda/test/test-01.kwi b/docs/examples/parsing/lambda/test/test-01.kwi new file mode 100755 index 0000000000..9833d10673 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-01.kwi @@ -0,0 +1 @@ +let x = 23 in (\y z -> x+y+z) 1 2 diff --git a/docs/examples/parsing/lambda/test/test-02.kwi b/docs/examples/parsing/lambda/test/test-02.kwi new file mode 100755 index 0000000000..11198c6fc9 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-02.kwi @@ -0,0 +1 @@ +let f = (\x y -> x*y) in f 2 3 diff --git a/docs/examples/parsing/lambda/test/test-03.kwi b/docs/examples/parsing/lambda/test/test-03.kwi new file mode 100755 index 0000000000..d4515d7297 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-03.kwi @@ -0,0 +1 @@ +let f = (\x y -> x*y) in f (f 1 2) 3 diff --git a/docs/examples/parsing/lambda/test/test-04.kwi b/docs/examples/parsing/lambda/test/test-04.kwi new file mode 100755 index 0000000000..e54c45457a --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-04.kwi @@ -0,0 +1 @@ +let fact = \x -> if x == 0 then 1 else x*(fact (x-1)) in unit diff --git a/docs/examples/parsing/lambda/test/test-05.kwi b/docs/examples/parsing/lambda/test/test-05.kwi new file mode 100755 index 0000000000..0b95d67846 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-05.kwi @@ -0,0 +1 @@ +let fact = \x -> if x == 0 then 1 else x*(fact (x-1)) in fact 6 diff --git a/docs/examples/parsing/lambda/test/test-06.kwi b/docs/examples/parsing/lambda/test/test-06.kwi new file mode 100755 index 0000000000..47723dc998 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-06.kwi @@ -0,0 +1 @@ +2*3+4*5 == 26 diff --git a/docs/examples/parsing/lambda/test/test-07.kwi b/docs/examples/parsing/lambda/test/test-07.kwi new file mode 100755 index 0000000000..14fba0d66a --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-07.kwi @@ -0,0 +1 @@ +let fix = \f -> f(fix f) in unit diff --git a/docs/examples/parsing/lambda/test/test-08.kwi b/docs/examples/parsing/lambda/test/test-08.kwi new file mode 100755 index 0000000000..7166d154f0 --- /dev/null +++ b/docs/examples/parsing/lambda/test/test-08.kwi @@ -0,0 +1 @@ +let fix = (\f -> f(fix f)) in (fix (\g n -> if n == 0 then 1 else n*(g(n-1)))) 5 -- cgit v1.2.3