Quantcast

Newbie recursion problem

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Newbie recursion problem

Darrell Burgan
Hello, I'm brand new to parboiled and am writing my first-ever parser, so please be gentle with me. :-)

I'm trying to create a simple search engine parser that will allow expressions like this:

((a and b) or c)) and not "d d"

I just want to use parboiled to build an AST for this syntax, and then I will afterwards interpret the AST to accomplish the search.

Right now I'm just trying to set up the parboiled rules for this syntax, and no matter what I do I end up with infinite recursion. Here's my simple parser so far:

        public Rule top() {
                return Sequence(anyExpression(), EOI);
        }


        protected Rule anyExpression() {
                return FirstOf(parensExpression(), andExpression(), orExpression(), notExpression(), searchTerm());
        }


        protected Rule parensExpression() {
                return Sequence("(", anyExpression(), ")");
        }


        protected Rule andExpression() {
                return Sequence(anyExpression(), andOperator(), anyExpression());
        }


        protected Rule orExpression() {
                return Sequence(anyExpression(), orOperator(), anyExpression());
        }


        protected Rule notExpression() {
                return Sequence(notOperator(), anyExpression());
        }


        protected Rule searchTerm() {
                return FirstOf(OneOrMore(searchCharacter()), ' ');
        }


        protected Rule searchCharacter() {
                return FirstOf(CharRange('a', 'z'), CharRange('A', 'Z'), CharRange('0', '9'));
        }


        protected Rule andOperator() {
                return IgnoreCase("and");
        }


        protected Rule orOperator() {
                return IgnoreCase("or");
        }


        protected Rule notOperator() {
                return IgnoreCase("not");
        }

What am I doing wrong? How do I get it to stop recursing infinitely?

Thanks for any help!

Darrell
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Newbie recursion problem

binarytemple
I've only played with the Scala API - but there is an 'Optional' construct, whereas you only seem to be using 'Sequence' I can't remember the exact syntax - but it might mean rewriting some of your rules something like this :

protected Rule andExpression() {
                return Sequence(Optional(anyExpression()), andOperator(), Optional(anyExpression()));
        }

http://www.decodified.com/parboiled/api/java/org/parboiled/BaseParser.html

  Rule Optional(java.lang.Object rule, java.lang.Object rule2, java.lang.Object... moreRules)
          Creates a new rule that tries a match on the sequence of the given subrules and always succeeds, independently of the matching success of its sub sequence.

General information upon the category of parsers to which Parboiled belongs can be found here:


On Sun, Sep 8, 2013 at 7:19 PM, Darrell Burgan [via parboiled users] <[hidden email]> wrote:
Hello, I'm brand new to parboiled and am writing my first-ever parser, so please be gentle with me. :-)

I'm trying to create a simple search engine parser that will allow expressions like this:

((a and b) or c)) and not "d d"

I just want to use parboiled to build an AST for this syntax, and then I will afterwards interpret the AST to accomplish the search.

Right now I'm just trying to set up the parboiled rules for this syntax, and no matter what I do I end up with infinite recursion. Here's my simple parser so far:

        public Rule top() {
                return Sequence(anyExpression(), EOI);
        }


        protected Rule anyExpression() {
                return FirstOf(parensExpression(), andExpression(), orExpression(), notExpression(), searchTerm());
        }


        protected Rule parensExpression() {
                return Sequence("(", anyExpression(), ")");
        }


        protected Rule andExpression() {
                return Sequence(anyExpression(), andOperator(), anyExpression());
        }


        protected Rule orExpression() {
                return Sequence(anyExpression(), orOperator(), anyExpression());
        }


        protected Rule notExpression() {
                return Sequence(notOperator(), anyExpression());
        }


        protected Rule searchTerm() {
                return FirstOf(OneOrMore(searchCharacter()), ' ');
        }


        protected Rule searchCharacter() {
                return FirstOf(CharRange('a', 'z'), CharRange('A', 'Z'), CharRange('0', '9'));
        }


        protected Rule andOperator() {
                return IgnoreCase("and");
        }


        protected Rule orOperator() {
                return IgnoreCase("or");
        }


        protected Rule notOperator() {
                return IgnoreCase("not");
        }

What am I doing wrong? How do I get it to stop recursing infinitely?

Thanks for any help!

Darrell



If you reply to this email, your message will be added to the discussion below:
http://users.parboiled.org/Newbie-recursion-problem-tp4024241.html
To start a new topic under parboiled users, email [hidden email]
To unsubscribe from parboiled users, click here.
NAML

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Newbie recursion problem

mathias
Administrator
In reply to this post by Darrell Burgan
Darrell,

you grammar looks ok.
Can you show what exact exception you get, incl. the stack trace?
How do you create your parser?
Note that you cannot simply say `new MyParser`, you'll have to go through the `Parboiled.createParser` method.

Cheers,
Mathias

---
[hidden email]
http://www.parboiled.org

On 08.09.2013, at 20:19, Darrell Burgan [via parboiled users] <[hidden email]> wrote:

>
>
> Hello, I'm brand new to parboiled and am writing my first-ever parser, so
> please be gentle with me. :-)
>
> I'm trying to create a simple search engine parser that will allow
> expressions like this:
>
> ((a and b) or c)) and not "d d"
>
> I just want to use parboiled to build an AST for this syntax, and then I
> will afterwards interpret the AST to accomplish the search.
>
> Right now I'm just trying to set up the parboiled rules for this syntax, and
> no matter what I do I end up with infinite recursion. Here's my simple
> parser so far:
>
> public Rule top() {
> return Sequence(anyExpression(), EOI);
> }
>
>
> protected Rule anyExpression() {
> return FirstOf(parensExpression(), andExpression(), orExpression(),
> notExpression(), searchTerm());
> }
>
>
> protected Rule parensExpression() {
> return Sequence("(", anyExpression(), ")");
> }
>
>
> protected Rule andExpression() {
> return Sequence(anyExpression(), andOperator(), anyExpression());
> }
>
>
> protected Rule orExpression() {
> return Sequence(anyExpression(), orOperator(), anyExpression());
> }
>
>
> protected Rule notExpression() {
> return Sequence(notOperator(), anyExpression());
> }
>
>
> protected Rule searchTerm() {
> return FirstOf(OneOrMore(searchCharacter()), ' ');
> }
>
>
> protected Rule searchCharacter() {
> return FirstOf(CharRange('a', 'z'), CharRange('A', 'Z'), CharRange('0',
> '9'));
> }
>
>
> protected Rule andOperator() {
> return IgnoreCase("and");
> }
>
>
> protected Rule orOperator() {
> return IgnoreCase("or");
> }
>
>
> protected Rule notOperator() {
> return IgnoreCase("not");
> }
>
> What am I doing wrong? How do I get it to stop recursing infinitely?
>
> Thanks for any help!
>
> Darrell
>
>
>
>
> _______________________________________________
> If you reply to this email, your message will be added to the discussion below:
> http://users.parboiled.org/Newbie-recursion-problem-tp4024241.html
> To start a new topic under parboiled users, email [hidden email]
> To unsubscribe from parboiled users, visit class="small">
signature.asc (858 bytes)
Download Attachment
Loading...