passing context on to subsequent parsers

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Is flatMap what you want?

Ishaaq Chandy wrote:
> Hi all, Yet another parser-combinator question:
>
> Is it possible to write a parser combinator (using scala's existing
> parser-combinator library) that passes the result of an earlier
> parser in the combinator chain on to a subsequent parser in the
> same chain?
>
> i.e. if my language was something like:
>
> "foo(x) bar(y)"
>
> ... and I had two parsers fooParser and barParser, fooParser
> returning the value of x while barParser takes the value y and does
> some processing along with the previously retrieved x from
> fooParser and returns a result.
>
> Possible?
>
> Thanks, Ishaaq

- --
Tony Morris
http://tmorris.net/

S, K and I ought to be enough for anybody.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkmiZtkACgkQmnpgrYe6r63pPACfZPLI1rusMCLLAcDOiH7WA1bA
YBQAnjLrFPdNzL2LneHo+DpRkR4M/zz1
=d0K6
-----END PGP SIGNATURE-----

Hi Ishaaq,

The Scala library has "into" that does this (also available as >>).
As Tony Morris suggested in another response, it's just defined as
flatmap.

cheers,
Tony

def into[U](fq : (T) => Parser[U]) : Parser[U]

A parser combinator that parameterises a subsequent parser with the
result of this one
Use this combinator when a parser depends on the result of a previous
parser. `p' should be a function that takes the result from the first
parser and returns the second parser.

`p into fq' (with `fq' typically `{x => q}') first applies `p', and
then, if `p' successfully returned result `r', applies `fq(r)' to the
rest of the input.

From: G. Hutton. Higher-order functions for parsing. J. Funct.
Program., 2(3):323--343, 1992.

Parameters fq - a function that, given the result from this parser,
returns the second parser to be applied

Returns a parser that succeeds if this parser succeeds (with result
`x') and if then `fq(x)' succeeds

On 23/02/2009, at 7:45 PM, Ishaaq Chandy wrote:

> Hi all,
> Yet another parser-combinator question:
>
> Is it possible to write a parser combinator (using scala's existing
> parser-combinator library) that passes the result of an earlier
> parser in the combinator chain on to a subsequent parser in the same
> chain?
>
> i.e. if my language was something like:
>
> "foo(x) bar(y)"
>
> ... and I had two parsers fooParser and barParser, fooParser
> returning the value of x while barParser takes the value y and does
> some processing along with the previously retrieved x from fooParser
> and returns a result.
>
> Possible?
>
> Thanks,
> Ishaaq

Thanks, but sorry, I must be dense - that is about as clear as mud to me :(

can you please give me an example? Note that in the combinator I am trying to implement the two parsers in question are not adjacent to each other. In other words with a string something like this:

"fooExpression something-else-here barExpression"

my combinator should be something like this:

rootParser= fooParser ~ somethingElseParser ~ barParser

and somehow I need to pass the results of fooParser into barParser, the documentation of the method you pointed to seems to indicate that it does what I want but I have no idea how I construct the combinator out of it.

Ishaaq

2009/2/23 Tony Sloane <inkytonik@gmail.com>

Hi Ishaaq,

The Scala library has "into" that does this (also available as >>).  As Tony Morris suggested in another response, it's just defined as flatmap.

cheers,
Tony

def into[U](fq : (T) => Parser[U]) : Parser[U]

A parser combinator that parameterises a subsequent parser with the result of this one
Use this combinator when a parser depends on the result of a previous parser. `p' should be a function that takes the result from the first parser and returns the second parser.

`p into fq' (with `fq' typically `{x => q}') first applies `p', and then, if `p' successfully returned result `r', applies `fq(r)' to the rest of the input.

From: G. Hutton. Higher-order functions for parsing. J. Funct. Program., 2(3):323--343, 1992.

Parameters fq - a function that, given the result from this parser, returns the second parser to be applied

Returns a parser that succeeds if this parser succeeds (with result `x') and if then `fq(x)' succeeds

On 23/02/2009, at 7:45 PM, Ishaaq Chandy wrote:

Hi all,
Yet another parser-combinator question:

Is it possible to write a parser combinator (using scala's existing parser-combinator library) that passes the result of an earlier parser in the combinator chain on to a subsequent parser in the same chain?

i.e. if my language was something like:

"foo(x) bar(y)"

... and I had two parsers fooParser and barParser, fooParser returning the value of x while barParser takes the value y and does some processing along with the previously retrieved x from fooParser and returns a result.

Possible?

Thanks,
Ishaaq

Ishaaq Chandy writes:

> Thanks, but sorry, I must be dense - that is about as clear as mud to me :(can
you please give me an example?

I have attached an example (see below). The parser there accepts the following
kind of input

"test n some xyz m"

where n and m are numeric literals. The parser succeeds only if n == m

Hope it helps. If you need any more clarification, feel free to ask.

Hints:
1. What you are trying to do is context-sensitive parsing. Usually context-free
grammars are the preferred approach, in which you do this
kind of analysis in a separate "semantic" pass. It is architecturally the right
thing to do, though may have overheads in implementation.
Context-sensitive parsing is fine for small projects.

2. I have used the ^? combinator to check whether n == m.

3. The ^? combinator requires a partial function as input which is nothing but a
case clause. Eg,
{case x if (x == 5) => x }
is a partial function defined only at x==5

cheers,
Harshad

import scala.util.parsing.combinator.lexical.StdLexical
import scala.util.parsing.combinator.syntactical.StdTokenParsers
import scala.util.parsing.input.StreamReader

object smParser extends StdTokenParsers {
type Tokens = StdLexical ; val lexical = new StdLexical
lexical.delimiters ++= List("(", ")", "=", "->", ",", "{", "}", ";")

lexical.reserved ++= List("test", "some", "xyz")

val testPrsr = ("test" ~> numericLit) ^^ {case x => x.toInt}
val somePrsr = keyword("some")
val xyzPrsr = {a:Int => ("xyz" ~> numericLit) ^? {case x if (x.toInt == a) =>
x.toInt}}
val fullPrsr = phrase (testPrsr >> {n => somePrsr ~ xyzPrsr(n) })

}

val res1 = smParser.fullPrsr(new smParser.lexical.Scanner("test 1 some xyz 1"))
val res2 = smParser.fullPrsr(new smParser.lexical.Scanner("test 1 some xyz 2"))

println(res1)
println(res2)

On Mon, Feb 23, 2009 at 6:06 AM, Ishaaq Chandy wrote:
> Thanks, but sorry, I must be dense - that is about as clear as mud to me :(
>
> can you please give me an example? Note that in the combinator I am trying
> to implement the two parsers in question are not adjacent to each other. In
> other words with a string something like this:
>
> "fooExpression something-else-here barExpression"
>
> my combinator should be something like this:
>
> rootParser= fooParser ~ somethingElseParser ~ barParser
>
> and somehow I need to pass the results of fooParser into barParser, the
> documentation of the method you pointed to seems to indicate that it does
> what I want but I have no idea how I construct the combinator out of it.
>

Short answer, and probably needs tweaking:
rootParser = fooParser >> { foo => somethingElseParser ~ barParser(foo) }

Also, this changes the result from "foo ~ somethingElse ~ bar" to just
"somethingElse ~ bar". If you also want to return the parsed foo, you
need to do a bit more work, maybe something like:
rootParser = fooParser >> { foo => new ~(foo, somethignElseParser ~
barParser(foo)) }

I haven't checked this code, though, so I'm sure there are some problems.

Matt

Thanks guys,
I'll give that a shot.

@Harshad: I do understand that this is not a context-free grammar and having just listened to a podcast this weekend about parser generation I do understand the advantages of context-free grammars. However what I am doing is pretty small - I don't expect to be parsing expressions much longer than say 50 tokens (50 being a stretch already).

Regards,
Ishaaq

2009/2/24 Matt Hellige <matt@immute.net>

On Mon, Feb 23, 2009 at 6:06 AM, Ishaaq Chandy <ishaaq@gmail.com> wrote:
> Thanks, but sorry, I must be dense - that is about as clear as mud to me :(
>
> can you please give me an example? Note that in the combinator I am trying
> to implement the two parsers in question are not adjacent to each other. In
> other words with a string something like this:
>
> "fooExpression something-else-here barExpression"
>
> my combinator should be something like this:
>
> rootParser= fooParser ~ somethingElseParser ~ barParser
>
> and somehow I need to pass the results of fooParser into barParser, the
> documentation of the method you pointed to seems to indicate that it does
> what I want but I have no idea how I construct the combinator out of it.
>

Short answer, and probably needs tweaking:
 rootParser = fooParser >> { foo => somethingElseParser ~ barParser(foo) }

Also, this changes the result from "foo ~ somethingElse ~ bar" to just
"somethingElse ~ bar". If you also want to return the parsed foo, you
need to do a bit more work, maybe something like:
 rootParser = fooParser >> { foo => new ~(foo, somethignElseParser ~
barParser(foo)) }

I haven't checked this code, though, so I'm sure there are some problems.

Matt