lucaswiman / revex Goto Github PK

Probably using Boltzmann sampling on PEGs from parsimonious.

See:

• http://algo.inria.fr/flajolet/Publications/DuFlLoSc04.pdf "Boltzmann Samplers for the Random Generation of Combinatorial Structures"
• https://arxiv.org/pdf/1608.07922v1.pdf "IMPROVEMENTS TO EXACT BOLTZMANN SAMPLING USING PROBABILISTIC DIVIDE-AND-CONQUER AND THE RECURSIVE METHOD"
• http://igm.univ-mlv.fr/~pivoteau/pivoteau_iwap_10_07_2008.pdf Lecture notes.

• Add handling for character classes, etc. #3
• Fix a bug in the operator precedence of repeats (ab{4} is parsed as (ab){4}).
• Implement ±lookaround syntax from #6.
• Add support for \b
• Documentation.
• CLI.

Added an expected failure test in 690d155. The regex is [ -\/:-@\[-`\{-~] via https://twitter.com/mountain_ghosts/status/847130837644709888

These features are regular, though are a bit difficult to map from the parse tree directly onto a derivative. In particular the following syntaxes:

• (?=...) Matches if ... matches next, but doesn’t consume any of the string. This is called a lookahead assertion. For example, Isaac (?=Asimov) will match 'Isaac ' only if it’s followed by 'Asimov'.
• (?!...) Matches if ... doesn’t match next. This is a negative lookahead assertion. For example, Isaac (?!Asimov) will match 'Isaac ' only if it’s not followed by 'Asimov'.
• (?<=...) Matches if the current position in the string is preceded by a match for ... that ends at the current position. This is called a positive lookbehind assertion. (?<=abc)def will find a match in abcdef, since the lookbehind will back up 3 characters and check if the contained pattern matches. The contained pattern must only match strings of some fixed length, meaning that abc or a|b are allowed, but a* and a{3,4} are not.

Also add support for the \b boundary marker.