search

craff / pacomb

A parsing library that compiles grammars to combinators using elimination of left recursion
MIT License
18 stars 2 forks source link

Use terminals instead of charsets for prediction #15

Closed craff closed 5 years ago

craff commented 5 years ago

This would ensure linear time and constant space for non ambiguous grammars that do not use dependent sequences (with dependent sequence, no hope to predict anything, that's clear).

A problem is to store in input table from Input the result of the terminal to apply it only once at each position. As a grammar may have a lot of terminal (But only a few used at one position ?), it would require to move container to a Log complexity using hashtbl. As we have to record both success and failure of terminals, there might be a dozen of terminals or even more at one position.

This might be a bit slower that charset, but the stability and predactibility in complexity is much more important than a constant factor. And we can still keep charsets as a pretest ... but this is not a good idea for issue #9.

May be one needs to have more grammars using Pacomb to test before choosing.

craff commented 5 years ago

No more prediction needed with the scheduler.