Infinite recursion in -[PGParserGenVisitor lookaheadSetForNode:]

[ghost]

I made a direct translation of the XPath 1.0 EBNF rules to a PEGKit grammar. The issue that I am seeing is that the ParserGenApp is infinitely recursing in -[PGParserGenVisitor lookaheadSetForNode:] when I try to generate the parser.

Here is a reduction of the grammar which causes infinite recursion:

locationPath
    = relativeLocationPath
    ;

relativeLocationPath
    = step
    | relativeLocationPath '/' step
    | relativeLocationPath '//' step
    ;

step
    = '.'
    | '..'
    ;

I noticed that the Panthro XPath grammar has a comment at the top about changing the relativeLocationPath production. This fixes one infinite recursion issue, but there is another, seemingly being triggered by the filterExpr production:

filterExpr
    = primaryExpr
    | filterExpr predicate
    ;

And when I print the PGBaseNodes that reach the default case in the switch block within -[PGParserGenVisitor lookaheadSetForNode:], I get:

...
(. '//' #relativeLocationPath)
($filterExpr (| #primaryExpr (. #filterExpr #predicate)))
($primaryExpr (| #variableReference (. '(' #expr ')') QuotedString Number #functionCall))
($variableReference (. '$' Word))
(. '$' Word)
(. '(' #expr ')')
($functionCall (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')'))
(. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')')
($functionName Word)
(. #filterExpr #predicate)
($filterExpr (| #primaryExpr (. #filterExpr #predicate)))
($primaryExpr (| #variableReference (. '(' #expr ')') QuotedString Number #functionCall))
($variableReference (. '$' Word))
(. '$' Word)
(. '(' #expr ')')
($functionCall (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')'))
(. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')')
($functionName Word)
(. #filterExpr #predicate)
($filterExpr (| #primaryExpr (. #filterExpr #predicate)))
...

[itod]

This is not a bug in PEGKit, but rather a question about left recursion. If that's not enough of a hint, please post a question on StackOverflow and tag it 'PEGKit'. I will answer as soon as possible.

Sent from my iPhone

On Aug 17, 2014, at 6:35, Daniel Trebbien notifications@github.com wrote:

I made a direct translation of the XPath 1.0 EBNF rules to a PEGKit grammar. The issue that I am seeing is that the ParserGenApp is infinitely recursing in -[PGParserGenVisitor lookaheadSetForNode:] when I try to generate the parser.

Here is a reduction of the grammar which causes infinite recursion:

locationPath = relativeLocationPath ;

relativeLocationPath = step | relativeLocationPath '/' step | relativeLocationPath '//' step ;

step = '.' | '..' ; I noticed that the Panthro XPath grammar has a comment at the top about changing the relativeLocationPath production. This fixes one infinite recursion issue, but there is another, seemingly being triggered by the filterExpr production:

filterExpr = primaryExpr | filterExpr predicate ; And when I print the PGBaseNodes that reach the default case in the switch block within -[PGParserGenVisitor lookaheadSetForNode:], I get:

... (. '//' #relativeLocationPath) ($filterExpr (| #primaryExpr (. #filterExpr #predicate))) ($primaryExpr (| #variableReference (. '(' #expr ')') QuotedString Number #functionCall)) ($variableReference (. '$' Word)) (. '$' Word) (. '(' #expr ')') ($functionCall (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')')) (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')') ($functionName Word) (. #filterExpr #predicate) ($filterExpr (| #primaryExpr (. #filterExpr #predicate))) ($primaryExpr (| #variableReference (. '(' #expr ')') QuotedString Number #functionCall)) ($variableReference (. '$' Word)) (. '$' Word) (. '(' #expr ')') ($functionCall (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')')) (. #functionName '(' (? (. #argument (* (. ',' #argument)))) ')') ($functionName Word) (. #filterExpr #predicate) ($filterExpr (| #primaryExpr (. #filterExpr #predicate))) ... — Reply to this email directly or view it on GitHub.