Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

#

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Jump to bottom

Failed to eliminate direct left recursion from this production #4

Open
fabriciofx opened this issue Jun 30, 2020 · 2 comments
Open

Failed to eliminate direct left recursion from this production #4

fabriciofx opened this issue Jun 30, 2020 · 2 comments
Assignees
@GuntherRademacher

Comments

@fabriciofx
Copy link

Using the RR site to plot a graph, this recursive grammar (which I don't know if is valid input):

whitespace ::= ('space')+ | ('linefeed')+ | ('carriage return')+ | ('horizontal tab')+ | (whitespace)+

generates an exception:

HTTP Status 500 – Internal Server Error
Type Exception Report

Message failed to eliminate direct left recursion from this production:

Description The server encountered an unexpected condition that prevented it from fulfilling the request.

Exception

java.lang.RuntimeException: failed to eliminate direct left recursion from this production:
  whitespace
           ::= 'space'+
             | 'linefeed'+
             | 'carriage return'+
             | 'horizontal tab'+
             | whitespace+
result was:
whitespace
           ::= ( 'space'+ | 'linefeed'+ | 'carriage return'+ | 'horizontal tab'+ | whitespace+ ) ( )*
	de.bottlecaps.railroad.webapp.RailroadWebApp.doRequest(RailroadWebApp.java:185)
	de.bottlecaps.railroad.webapp.RailroadServlet.doPost(RailroadServlet.java:31)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:661)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:742)
	org.apache.tomcat.websocket.server.WsFilter.doFilter(WsFilter.java:52)
Root Cause

net.sf.saxon.s9api.SaxonApiException: failed to eliminate direct left recursion from this production:
  whitespace
           ::= 'space'+
             | 'linefeed'+
             | 'carriage return'+
             | 'horizontal tab'+
             | whitespace+
result was:
whitespace
           ::= ( 'space'+ | 'linefeed'+ | 'carriage return'+ | 'horizontal tab'+ | whitespace+ ) ( )*
	net.sf.saxon.s9api.XQueryEvaluator.evaluate(XQueryEvaluator.java:433)
	de.bottlecaps.railroad.webapp.RailroadWebApp.doRequest(RailroadWebApp.java:147)
	de.bottlecaps.railroad.webapp.RailroadServlet.doPost(RailroadServlet.java:31)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:661)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:742)
	org.apache.tomcat.websocket.server.WsFilter.doFilter(WsFilter.java:52)
Root Cause

net.sf.saxon.functions.Error$UserDefinedXPathException: failed to eliminate direct left recursion from this production:
  whitespace
           ::= 'space'+
             | 'linefeed'+
             | 'carriage return'+
             | 'horizontal tab'+
             | whitespace+
result was:
whitespace
           ::= ( 'space'+ | 'linefeed'+ | 'carriage return'+ | 'horizontal tab'+ | whitespace+ ) ( )*
	net.sf.saxon.functions.Error.error(Error.java:66)
	net.sf.saxon.functions.Error.call(Error.java:111)
	net.sf.saxon.expr.FunctionCall.iterate(FunctionCall.java:543)
	net.sf.saxon.expr.Expression.process(Expression.java:948)
	net.sf.saxon.expr.SystemFunctionCall.process(SystemFunctionCall.java:476)
	net.sf.saxon.expr.instruct.Choose.processLeavingTail(Choose.java:910)
	net.sf.saxon.expr.LetExpression.processLeavingTail(LetExpression.java:729)
	net.sf.saxon.expr.instruct.Choose.processLeavingTail(Choose.java:908)
	net.sf.saxon.expr.instruct.Instruction.process(Instruction.java:136)
	net.sf.saxon.expr.ForExpression.lambda$process$0(ForExpression.java:399)
	net.sf.saxon.om.SequenceIterator.forEachOrFail(SequenceIterator.java:135)
	net.sf.saxon.expr.ForExpression.process(ForExpression.java:397)
	net.sf.saxon.expr.instruct.Block.processLeavingTail(Block.java:738)
	net.sf.saxon.expr.instruct.Instruction.process(Instruction.java:136)
	net.sf.saxon.expr.instruct.ElementCreator.processLeavingTail(ElementCreator.java:346)
	net.sf.saxon.expr.instruct.ElementCreator.processLeavingTail(ElementCreator.java:292)
	net.sf.saxon.expr.instruct.Instruction.process(Instruction.java:136)
	net.sf.saxon.expr.parser.ExpressionTool.getItemFromProcessMethod(ExpressionTool.java:663)
	net.sf.saxon.expr.instruct.Instruction.evaluateItem(Instruction.java:334)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:959)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.instruct.UserFunction.call(UserFunction.java:633)
	net.sf.saxon.expr.UserFunctionCall.callFunction(UserFunctionCall.java:538)
	net.sf.saxon.expr.UserFunctionCall.evaluateItem(UserFunctionCall.java:472)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:959)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.LetExpression.eval(LetExpression.java:537)
	net.sf.saxon.expr.LetExpression.evaluateItem(LetExpression.java:559)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:959)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:959)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.instruct.UserFunction.call(UserFunction.java:633)
	net.sf.saxon.expr.UserFunctionCall.callFunction(UserFunctionCall.java:538)
	net.sf.saxon.expr.UserFunctionCall.evaluateItem(UserFunctionCall.java:472)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:959)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.LetExpression.eval(LetExpression.java:537)
	net.sf.saxon.expr.LetExpression.evaluateItem(LetExpression.java:559)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.instruct.UserFunction.call(UserFunction.java:633)
	net.sf.saxon.expr.UserFunctionCall.callFunction(UserFunctionCall.java:538)
	net.sf.saxon.expr.UserFunctionCall.evaluateItem(UserFunctionCall.java:472)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.UserFunctionCall.evaluateArguments(UserFunctionCall.java:637)
	net.sf.saxon.expr.UserFunctionCall.evaluateArguments(UserFunctionCall.java:619)
	net.sf.saxon.expr.UserFunctionCall.callFunction(UserFunctionCall.java:513)
	net.sf.saxon.expr.UserFunctionCall.iterate(UserFunctionCall.java:482)
	net.sf.saxon.expr.CardinalityChecker.iterate(CardinalityChecker.java:212)
	net.sf.saxon.expr.LetExpression.iterate(LetExpression.java:519)
	net.sf.saxon.expr.instruct.Choose.iterate(Choose.java:981)
	net.sf.saxon.expr.LetExpression.iterate(LetExpression.java:519)
	net.sf.saxon.value.MemoClosure.makeSequence(MemoClosure.java:86)
	net.sf.saxon.value.MemoClosure.iterate(MemoClosure.java:80)
	net.sf.saxon.expr.UserFunctionCall.iterate(UserFunctionCall.java:482)
	net.sf.saxon.expr.instruct.Choose.iterate(Choose.java:981)
	net.sf.saxon.expr.instruct.Choose.iterate(Choose.java:981)
	net.sf.saxon.expr.instruct.Choose.iterate(Choose.java:981)
	net.sf.saxon.expr.instruct.Choose.iterate(Choose.java:981)
	net.sf.saxon.value.MemoClosure.makeSequence(MemoClosure.java:86)
	net.sf.saxon.value.MemoClosure.iterate(MemoClosure.java:80)
	net.sf.saxon.expr.VariableReference.iterate(VariableReference.java:555)
	net.sf.saxon.expr.SlashExpression.iterate(SlashExpression.java:922)
	net.sf.saxon.functions.Exists$1.effectiveBooleanValue(Exists.java:64)
	net.sf.saxon.expr.instruct.Choose.choose(Choose.java:930)
	net.sf.saxon.expr.instruct.Choose.evaluateItem(Choose.java:958)
	net.sf.saxon.expr.LetExpression.evaluateItem(LetExpression.java:567)
	net.sf.saxon.expr.TailCallLoop.evaluateItem(TailCallLoop.java:121)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:151)
	net.sf.saxon.expr.parser.Evaluator$5.evaluate(Evaluator.java:148)
	net.sf.saxon.expr.TailCallLoop.tailCallDifferentFunction(TailCallLoop.java:189)
	net.sf.saxon.expr.TailCallLoop.iterate(TailCallLoop.java:107)
	net.sf.saxon.value.MemoClosure.makeSequence(MemoClosure.java:86)
	net.sf.saxon.value.MemoClosure.iterate(MemoClosure.java:80)
	net.sf.saxon.expr.UserFunctionCall.iterate(UserFunctionCall.java:482)
	net.sf.saxon.query.XQueryExpression.iterator(XQueryExpression.java:370)
	net.sf.saxon.s9api.XQueryEvaluator.evaluate(XQueryEvaluator.java:428)
	de.bottlecaps.railroad.webapp.RailroadWebApp.doRequest(RailroadWebApp.java:147)
	de.bottlecaps.railroad.webapp.RailroadServlet.doPost(RailroadServlet.java:31)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:661)
	javax.servlet.http.HttpServlet.service(HttpServlet.java:742)
	org.apache.tomcat.websocket.server.WsFilter.doFilter(WsFilter.java:52)
Note The full stack trace of the root cause is available in the server logs.
@GuntherRademacher GuntherRademacher self-assigned this Jun 30, 2020
@GuntherRademacher
Copy link
Owner

Thanks for reporting that, @fabriciofx.

That whitespace rule is valid syntactically, and it could even be made to a diagram, but it contains infinite recursion, which causes the elimination logic to crash. Infinite recursion is not useful, because it can't produce anything. Yet it should be either be handled or the rule should be left untouched. I will create a fix.

But I would rewrite the rule to avoid infinite recursion and ambiguities. The recursive way to do this would be

whitespace ::= 'space'
             | 'linefeed'
             | 'carriage return'
             | 'horizontal tab'
             | whitespace 'space'
             | whitespace 'linefeed'
             | whitespace 'carriage return'
             | whitespace 'horizontal tab'

and this correctly transforms to

whitespace ::= ('space'
               | 'linefeed'
               | 'carriage return'
               | 'horizontal tab'
               )+

@fabriciofx
Copy link
Author

fabriciofx commented Jul 1, 2020 •
edited
Loading

@GuntherRademacher thanks a lot for your solution and attention! You're awesome!

# for free to join this conversation on GitHub. Already have an account? # to comment
Assignees

@GuntherRademacher GuntherRademacher

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@fabriciofx @GuntherRademacher