search

microsoft / ts-parsec

Writing a custom parser is a fairly common need. Although there are already parser combinators in others languages, TypeScript provides a powerful and well-structured foundation for building this. Common parser combinators’ weakness are error handling and ambiguity resolving, but these are ts-parsec’s important features. Additionally, ts-parsec provides a very easy to use programming interface, that could help people to build programming-language-scale parsers in just a few hours. This technology has already been used in Microsoft/react-native-tscodegen.
Other
357 stars 18 forks source link

Worst-case performance of alt (perhaps need an alt_sc?) #33

Closed floyd-may closed 1 year ago

floyd-may commented 2 years ago

The alt combinator has some worst-case performance behavior if there isn't a reasonably fast parse fail in any of its arguments. I discovered this during 2021's Advent of Code challenge where I used typescript-parsec on this problem. Using alt to determine the packet type is impossibly slow. I hand-wrote a parser to get past it, but it seems that an alt_sc may be useful to shortcut to the first succeeding argument rather than attempt parsing all arguments.

ZihanChen-MSFT commented 1 year ago

alt would give you all possible answer, but you are right, alt_sc might be useful when you only need one answer.