Building a Regex Engine in Fewer Than 40 Lines of Code
1–10 of 37 posts
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#2This does not implement grouping "()" or alternatives "|". Hence, looping is only required on individual characters. This is a considerable simplification over full regexp.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#3This does not implement grouping "()" or alternatives "|". Hence, looping is only required on individual characters. This is a considerable simplification over full regexp.
Which means that this CAN NOT BE USED TO ACCEPT REGULAR LANGUAGES. The language (a|b)*, any number of as or bs in any order, can not be descibed using that parser.
"considerable simplification" sounds like it's kinda regex. It's not even basic regular expressions/regular languages.
Edit: The author reimplements code from https://www.cs.princeton.edu/courses/archive/spr09/cos333/be... which acknowledges that the implemented subset does not match all classes but they propose that the classes they can parse, are already useful. The author of the new article makes no such acknowledgement that their implementation just represents a subset of regular languages.
Of course, the regular languages themselves are also just a subset of regexp, which can match more languages due to constructs like references.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#4Code golf link to a similar challenge https://codegolf.stackexchange.com/questions/125708/regular-...
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#5Code golf link to a similar challenge https://codegolf.stackexchange.com/questions/125708/regular-...
That does indeed implement grouping and alternative
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#6Nice, remind me of a custom Regex engine i built some years ago in JS while trying to build a fast & small lexer, it does not support ? but +, - and sub-rules, it is around 60 LOC if I remind, mostly built by "accident", it work with JSON as input and output a finite state automaton (compiled version ?)
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#7I did that with grouping (), alternatives |, and classes [], for Asterisk some decades ago. They had a very special phonenumbering syntax. Less than 100 lines in C.
In lisp it's trivial, less then 10 lines for a simple matcher.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#8I've written a JS regexp parser and engine. It did not fit in 40 lines.
The most obnoxious part is backreferences. The atom \3 is a backreference if the whole regexp contains at least 3 capture groups; otherwise it is an octal (!) escape for char code 3. But you don't know how many capture groups there are until you're done parsing. This is why JS regexp parsers sometimes must make two passes!
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#9This does not implement grouping "()" or alternatives "|". Hence, looping is only required on individual characters. This is a considerable simplification over full regexp.
I really hated that Lua's "pattern" [1] is never a regular expression nor a regular language. So annoying that it will be better not to have it.
Re: Building a Regex Engine in Fewer Than 40 Lines of Code
#10I'd almost admire how convenient it was that the language that was used ships regexes already.