gmane.comp.lang.scala.user

David Pollak | 15 Jan 23:00

unordered stuff in the parser combinator

Howdy,

I'm working on a grammar using the parser combinator.

One of the challenges that I have is parsing stuff that must be present, but doesn't have to be in a particular order. If I have 'dog', 'cat', 'fish' and 'moose' and my zoo is:

zoo = (dog ~ cat ~ fish ~ moose) | (dog ~ fish ~ cat ~ moose) | (dog ~ fish ~ moose ~ cat) ...

Is there a better way to express this?

Thanks,

David

--
lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us

headers

Matt Hellige | 15 Jan 23:31

Re: unordered stuff in the parser combinator

It's possible to write a permutation parser combinator in Haskell.
Here is the key:
  http://citeseer.ist.psu.edu/451549.html
It's not complex, but I haven't read the paper in depth, so I don't
know if it transfers trivially to Scala.

Matt

On Jan 15, 2008 4:02 PM, David Pollak
<feeder.of.the.bears@...> wrote:
> Howdy,
>
> I'm working on a grammar using the parser combinator.
>
> One of the challenges that I have is parsing stuff that must be present, but
> doesn't have to be in a particular order.  If I have 'dog', 'cat', 'fish'
> and 'moose' and my zoo is:
>
> zoo = (dog ~ cat ~ fish ~ moose) | (dog ~ fish ~ cat ~ moose) | (dog ~ fish
> ~ moose ~ cat) ...
>
> Is there a better way to express this?
>
> Thanks,
>
> David
>
> --
> lift, the secure, simple, powerful web framework http://liftweb.net
> Collaborative Task Management http://much4.us

--

-- 
Matt Hellige / matt@...
http://matt.immute.net

headers

Geoffrey Alan Washburn | 16 Jan 00:02

Re: unordered stuff in the parser combinator

Matt Hellige wrote:
> It's possible to write a permutation parser combinator in Haskell.
> Here is the key:
>   http://citeseer.ist.psu.edu/451549.html
> It's not complex, but I haven't read the paper in depth, so I don't
> know if it transfers trivially to Scala.

Skimming the paper indicates that it requires higher-rank polymorphism 
(which *is not* the same as higher-kinded polymorphism, which Scala does 
provide).  So a trivial translation is out of the question.  It may be 
possible, but it will require some cleverness.

headers

Geoffrey Alan Washburn | 16 Jan 00:10

Re: unordered stuff in the parser combinator

Geoffrey Alan Washburn wrote:
> Matt Hellige wrote:
>> It's possible to write a permutation parser combinator in Haskell.
>> Here is the key:
>>   http://citeseer.ist.psu.edu/451549.html
>> It's not complex, but I haven't read the paper in depth, so I don't
>> know if it transfers trivially to Scala.
> 
> Skimming the paper indicates that it requires higher-rank polymorphism 
> (which *is not* the same as higher-kinded polymorphism, which Scala does 
> provide).  So a trivial translation is out of the question.  It may be 
> possible, but it will require some cleverness.

Nope, I misread it.  They were just using Haskell's forall quantifier 
notation for what is really an existential type.  This should be 
straightforward then.

headers

David Pollak | 16 Jan 00:41

Re: Re: unordered stuff in the parser combinator

I'll have some code in a few minutes

On 1/15/08, Geoffrey Alan Washburn <geoffrey.washburn-p8DiymsW2f8@public.gmane.org > wrote:

Geoffrey Alan Washburn wrote:
> Matt Hellige wrote:
>> It's possible to write a permutation parser combinator in Haskell.
>> Here is the key:
>>   http://citeseer.ist.psu.edu/451549.html
>> It's not complex, but I haven't read the paper in depth, so I don't
>> know if it transfers trivially to Scala.
>
> Skimming the paper indicates that it requires higher-rank polymorphism
> (which *is not* the same as higher-kinded polymorphism, which Scala does
> provide).  So a trivial translation is out of the question.  It may be
> possible, but it will require some cleverness.

Nope, I misread it.  They were just using Haskell's forall quantifier
notation for what is really an existential type.  This should be
straightforward then.

--
lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us

headers

David Pollak | 16 Jan 01:14

Re: Re: unordered stuff in the parser combinator

def _rotate[T](in: List[T]): List[List[T]] = {
    def doIt(in: List[T], cnt: Int): List[List[T]] = (in, cnt) match {
      case (_, 0) => Nil
      case (x :: xs, cnt) => in :: doIt(xs ::: List(x), cnt - 1)
    }
    doIt(in, in.length)
}

def _permute[T](in: List[T]): List[List[T]] = in match {
    case Nil => Nil
    case x :: Nil => List(List(x))
    case xs => _rotate(xs).flatMap{case x :: xs => _permute(xs).map(x :: _) case _ => Nil}
}

def permute[T](p: (=> Parser[T])*): Parser[List[T]] = if (p.isEmpty ) success(Nil)
else {
    def doLine(in: List[(=> Parser[T])]): Parser[List[T]] = in match {
      case Nil => success(Nil)
      case x :: xs => x ~ doLine(xs) ^^ {case ~(x, xs) => x :: xs}
    }

    def doAll(in: List[List[(=> Parser[T])]]): Parser[List[T]] = in match {
      case x :: Nil => doLine(x)
      case x :: xs => doLine(x) | doAll(xs)
    }

    doAll(_permute(p.toList))
}

On 1/15/08, David Pollak <feeder.of.the.bears-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org> wrote:

I'll have some code in a few minutes

On 1/15/08, Geoffrey Alan Washburn < geoffrey.washburn-p8DiymsW2f8@public.gmane.org > wrote:
Geoffrey Alan Washburn wrote:
> Matt Hellige wrote:
>> It's possible to write a permutation parser combinator in Haskell.
>> Here is the key:
>>   http://citeseer.ist.psu.edu/451549.html
>> It's not complex, but I haven't read the paper in depth, so I don't
>> know if it transfers trivially to Scala.
>
> Skimming the paper indicates that it requires higher-rank polymorphism
> (which *is not* the same as higher-kinded polymorphism, which Scala does
> provide).  So a trivial translation is out of the question.  It may be
> possible, but it will require some cleverness.

Nope, I misread it.  They were just using Haskell's forall quantifier
notation for what is really an existential type.  This should be
straightforward then.

--

lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us

--
lift, the secure, simple, powerful web framework http://liftweb.net
Collaborative Task Management http://much4.us

headers

James Iry | 15 Jan 23:34

Re: unordered stuff in the parser combinator

The library more or less follows EBNF style (with some extra goodies) and permutations aren't part of EBNF. 
I can't see any reason why they can't be added, though.  Let me think about that for awhile.

---- David Pollak <feeder.of.the.bears@...> wrote: 
> Howdy,
> 
> I'm working on a grammar using the parser combinator.
> 
> One of the challenges that I have is parsing stuff that must be present, but
> doesn't have to be in a particular order.  If I have 'dog', 'cat', 'fish'
> and 'moose' and my zoo is:
> 
> zoo = (dog ~ cat ~ fish ~ moose) | (dog ~ fish ~ cat ~ moose) | (dog ~ fish
> ~ moose ~ cat) ...
> 
> Is there a better way to express this?
> 
> Thanks,
> 
> David
> 
> -- 
> lift, the secure, simple, powerful web framework http://liftweb.net
> Collaborative Task Management http://much4.us

headers

Andrew Foggin (h | 16 Jan 01:32

Re: unordered stuff in the parser combinator


David Pollak-4 wrote:
> 
> Howdy,
> 
> I'm working on a grammar using the parser combinator.
> 
> One of the challenges that I have is parsing stuff that must be present,
> but
> doesn't have to be in a particular order.  If I have 'dog', 'cat', 'fish'
> and 'moose' and my zoo is:
> 
> zoo = (dog ~ cat ~ fish ~ moose) | (dog ~ fish ~ cat ~ moose) | (dog ~
> fish
> ~ moose ~ cat) ...
> 
> Is there a better way to express this?
> 
> Thanks,
> 
> David
> 
> -- 
> lift, the secure, simple, powerful web framework http://liftweb.net
> Collaborative Task Management http://much4.us
> 
> 

Don't have time to knock up a proper solution right now, but here's a quick
pointer.  You'll need to define a method that takes a set of (remaining)
choices and returns a parser for those choices.  The method will call itself
recursively with the '>>' operator.

Hope that is enough to get you going!

Regards,

Andrew

Hope this is enough to get you going

--

-- 
View this message in context: http://www.nabble.com/unordered-stuff-in-the-parser-combinator-tp14854455p14854980.html
Sent from the Scala - User mailing list archive at Nabble.com.