Re: Parse::RecDescent grammar that winds its way all the way back to start

I am looking at the “Eliminate Backtracking When Possible” section in Parse::RecDescent::FAQ::Original to see if it might have some bearing on my problem.

It would be a purely-recursive rule something like this:

  job_statements : job_statement <commit> job_statements(?)
                   | #NOTHING
[download]

or:

  job_statements : job_statement <commit> job_statements
                   | job_statement
                   | #NOTHING
[download]

But I really hate to recurse like that. If I’ve got a list of two or three hundred job_statements, as I well might, then I’ve obliged the computer to recurse two or three hundred levels deep! (I think ...)

The trouble is, this file layout really is not well-thought-out. (And it isn’t correctly documented, either.) In other words, “it sucks large, yes ... but we are stuck with it.”

Replies are listed 'Best First'.
Re^2: Parse::RecDescent grammar that winds its way all the way back to start by ikegami (Patriarch) on Sep 23, 2010 at 19:49 UTC
But I really hate to recurse like that. `job_statements : job_statement <commit> job_statements(?) \| #NOTHING` [download] and the less efficient `job_statements : job_statement <commit> job_statements \| job_statement \| #NOTHING` [download] are both just recursive versions of `job_statements : job_statement(s?)` [download] If you don't want the recursion, use the last.	[reply] [d/l] [select]
Re^2: Parse::RecDescent grammar that winds its way all the way back to start by JavaFan (Canon) on Sep 23, 2010 at 18:18 UTC
But I really hate to recurse like that. If I’ve got a list of two or three hundred job_statements, as I well might, then I’ve obliged the computer to recurse two or three hundred levels deep! Well, you made the choice of using a recursive descent parser. They aren't known for making the fastests parses. Considering the number of `<commit>`s you have in your grammer, can't you use a limited look-ahead parser? (LL(N), LR(N), ...) No recursion nor backtracking is than needed; syntax errors are more quickly discovered, and you may have an easier time resyncing after a parsing error.	[reply]