parsing incomplete expressions

Hi,
Another question on parser combinators.

So, I am writing an app that runs on the console, interpreting user input and doing stuff accordingly. The user input is defined using a grammar that I've successfully written a parser combinator for.

Now I want to add context-sensitive tab completion to the interpreter. So, the idea is that the user may partially enter in the line, hit the tab key and if possible my app should attempt to insert a tab-completion depending on the context of the point in the input string that the user left  unfinished.

A related problem is that I need to know, when the user hits the enter key, whether the line of input is either:
1. A syntax error and so an error must be thrown
2. Just a case of an incomplete line of user input, i.e. the interpreter should know to wait for the next line of input to attempt to complete the input.

In short, I want my app to act very much like your normal bash shell prompt.

So, my problem of course, is that my parser combinator only knows how to verify a completed sentence, not something left mid-sentence. I need to determine that a given line of input, it is either:
1. a valid sentence to be processed
2. A half-completed sentence that may be possible to auto-complete in the case of a tab key press, or block for further input on an enter key press. i.e. I need to be able to tell the context of the point in the grammar that the user stopped at - to be able to determine the alternatives to present on screen.
3. A sentence that is impossible to be completed in any valid way in which case normal parser error should be displayed.

Is this possible with a parser combinator or not?

Ishaaq

Usually, for auto-completion, you need to have some kind of database which knows what the logical completions are. For example, auto-completion in eclipse is done because the platform has access to the class structure, and to most keywords.
If you want to do auto-completion for keywords (like "while", "for"), you can certainly attempt it.

The basic idea would be :
1) capture the tab , and get what is on the command line
2) process the input, with some auto-completion rules
3) return a result on the command line.

The first and 3rd steps, I don't know how to do it. Hopefully someone else can guide you on that.

Manohar

On Sat, Feb 21, 2009 at 1:13 AM, Ishaaq Chandy <ishaaq@gmail.com> wrote:

Hi,
Another question on parser combinators.

So, I am writing an app that runs on the console, interpreting user input and doing stuff accordingly. The user input is defined using a grammar that I've successfully written a parser combinator for.

Now I want to add context-sensitive tab completion to the interpreter. So, the idea is that the user may partially enter in the line, hit the tab key and if possible my app should attempt to insert a tab-completion depending on the context of the point in the input string that the user left  unfinished.

A related problem is that I need to know, when the user hits the enter key, whether the line of input is either:
1. A syntax error and so an error must be thrown
2. Just a case of an incomplete line of user input, i.e. the interpreter should know to wait for the next line of input to attempt to complete the input.

In short, I want my app to act very much like your normal bash shell prompt.

So, my problem of course, is that my parser combinator only knows how to verify a completed sentence, not something left mid-sentence. I need to determine that a given line of input, it is either:
1. a valid sentence to be processed
2. A half-completed sentence that may be possible to auto-complete in the case of a tab key press, or block for further input on an enter key press. i.e. I need to be able to tell the context of the point in the grammar that the user stopped at - to be able to determine the alternatives to present on screen.
3. A sentence that is impossible to be completed in any valid way in which case normal parser error should be displayed.

Is this possible with a parser combinator or not?

Ishaaq

Ishaaq,

What you say is quite feasible, albeit with a parser combinator library built for that purpose.

I have implemented a parser combinator library in Scala which does this exactly. It's part of a commercial product and not open-source.

If interested, please contact me off-list.

Cheers,
Harshad

Ishaaq Chandy wrote:

> Umm, because I designed the grammar and the parser combinator I know
> exactly what the completions are supposed to be - I could write rules as
> you say - to process the input and generate the completions but since I've
> already written a parser combinator that understands the grammar and the
> context I was wondering if I can take advantage of it to not have to write
> another set of hand-coded rules to generate the completions.
>
> In other words, given a grammar check failure, I want to be able to
> interrogate the parser to work out if the failure was caused due to an
> incomplete sentence that can legitimately be completed or if the sentence
> is impossible to complete in a syntactically correct way. Additionally, if
> it is the former, then I need a way to determine which component parser
> within the combinator failed which would help me determine which
> completions can be applied according to the context.
>
> -Ishaaq
>
>>>
>>> Is this possible with a parser combinator or not?
>>>
>>> Ishaaq

Warning: Wicked, commercial info below.

Ishaaq,

What you say is quite feasible, albeit with a parser combinator library built for that purpose.

I have implemented a parser combinator library in Scala which does this exactly. It's part of a commercial product and not open-source.

If interested, please contact me off-list.

Cheers,
Harshad

Ishaaq Chandy wrote:

> Umm, because I designed the grammar and the parser combinator I know
> exactly what the completions are supposed to be - I could write rules as
> you say - to process the input and generate the completions but since I've
> already written a parser combinator that understands the grammar and the
> context I was wondering if I can take advantage of it to not have to write
> another set of hand-coded rules to generate the completions.
>
> In other words, given a grammar check failure, I want to be able to
> interrogate the parser to work out if the failure was caused due to an
> incomplete sentence that can legitimately be completed or if the sentence
> is impossible to complete in a syntactically correct way. Additionally, if
> it is the former, then I need a way to determine which component parser
> within the combinator failed which would help me determine which
> completions can be applied according to the context.
>
> -Ishaaq
>
>>>
>>> Is this possible with a parser combinator or not?
>>>
>>> Ishaaq

Ishaaq Chandy wrote:

> Thanks but this is a small side-app that I am writing that may or may not
> be used internally by my team if I am successful with it - I'm doing this
> on my own time more for my own enjoyment and self-improvement rather than
> as part of my day job so I can't really justify buying licenses for third
> party dependencies for it at this point.
>
> But your answer does tell me something - this obviously isn't possible
> with the current parser combinator API in scala or you wouldn't have
> rolled your own. Maybe I should read up on parser combinators and write
> something myself - though that may be a bit more than I can chew at this
> point being a newbie to scala.

IMO, writing the parser combinators in Scala is the easy part. See this link
for a nice exposition on the topic:
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW491.abs.html

The challenging part is designing the combinator library to do things you
want it to do.

Cheers,
Harshad

Ishaaq Chandy wrote:

> Thanks but this is a small side-app that I am writing that may or may not
> be used internally by my team if I am successful with it - I'm doing this
> on my own time more for my own enjoyment and self-improvement rather than
> as part of my day job so I can't really justify buying licenses for third
> party dependencies for it at this point.
>
> But your answer does tell me something - this obviously isn't possible
> with the current parser combinator API in scala or you wouldn't have
> rolled your own. Maybe I should read up on parser combinators and write
> something myself - though that may be a bit more than I can chew at this
> point being a newbie to scala.

IMO, writing the parser combinators in Scala is the easy part. See this link
for a nice exposition on the topic:
http://www.cs.kuleuven.be/publicaties/rapporten/cw/CW491.abs.html

The challenging part is designing the combinator library to do things you
want it to do.

Cheers,
Harshad