search

GuntherRademacher / rr

RR - Railroad Diagram Generator
Apache License 2.0
467 stars 51 forks source link

Failed to eliminate direct left recursion from this production #4

Open fabriciofx opened 4 years ago

fabriciofx commented 4 years ago

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 commented 4 years ago

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 commented 4 years ago

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