Skip to content

Malformed gramamr files can cause LR parser reductions to loop infinitely. #567

Description

@teo-tsirpanis

Consider a grammar with an LR state machine containing the following state:

State M:
  (EOF) Reduce Production <P> ::=
  <P> Goto State M

If Farkle encounters EOF while in state M, the parser would keep reducing and infinitely loop:

RetryEof:
LrEndOfFileAction eofAction = _lrStateMachine.GetEndOfFileAction(currentState);
if (eofAction.IsAccept)
{
result = semanticValueStack.Peek();
return RunResult.Success;
}
if (eofAction.IsReduce)
{
try
{
currentState = Reduce(ref input, in hotData, ref stateStack, ref semanticValueStack, eofAction.ReduceProduction);
}
catch (ParserApplicationException ex)
{
result = ex.GetErrorObject(input.State.CurrentPosition);
return RunResult.Failure;
}
goto RetryEof;
}

More non-trivial states can also cause the parser to loop. The builder won't emit such state machine, but a grammar from a specially crafted file could.

Not critical for 7.0.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions