Anthony Ferrara has a new post, following up from his previous look at tries and lexers, continuing along the path to apply what he learned to a HTTP routing system.
In my last post, Tries and Lexers, I talked about an experiment I was doing related to parsing of JavaScript code. By the end of the post I had shifted to wanting to build a HTTP router using the techniques that I learned. Let's continue where we left off...
He starts off with thinking that lexing and parsing the routes out into their respective tokens instead of breaking them up as many do (i.e. splitting on the slashes). He shows the results of this lexing and some parser code to handle these results and turn them into something useful. He did find that the current setup caused a lot of overhead (255 new states per character) so he optimizes the processing with a "default" trie but it was still pretty intensive.
He decided to go a different way at this point, opting for the radix tree structure instead. He includes the implementation of this tree for parsing the routes and his matching lexer updates. Finally he shows how to apply code generation to the results of these changes and how coming back to the "slash splitting" could help...
Link: http://blog.ircmaxell.com/2015/05/prefix-trees-and-parsers.html
没有评论:
发表评论