regexp-to-DFA algorithm
I'm writing a regexp-based lexical analyzer generator based on a regexp-to-DFA direct translation algorithm described in the Dragon Book.
It calculates the nullable
, firstpos
, lastpos
, and followpos
functions for concatenation, alternation, and kleene-star nodes. I want to add quantifiers for +
(one or more times) and ?
(zero or one time).
nullable开发者_JAVA技巧
, firstpos
, and lastpos
are easy to calculate, but I'm not sure about followpos
. Is it better to not implement those quantifiers as part of the parsing stage, and instead rewrite it in the lexical analysis stage (I think this is only "syntactic sugar" to kleene-star and alternation)?
精彩评论