5 ms·
Just a note on "Why not to use regular expression". Because it's impossible depending on the language complexity REs are level 3 https://en.wikipedia.org/wiki/
by raverbashing 10y ago
Just a note on "Why not to use regular expression". Because it's impossible depending on the language complexity
REs are level 3 https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy
- ftomassetti 10y agoThat is also a good reason not to, but unfortunately that escape to most people
- exDM69 10y agoClassic regular expressions are level 3 in the Chomsky classification, but most regex implementations have features that aren't a part of "regular languages". The upside is that they are more expressive, but the downside is that it's no longer O(n) to parse a string. Worst case for some regexes can be exponential, never run untrusted regexes on your server unless you use a safe implementation like re2 which was developed for Google Code Search.
- srssays 10y ago...and if you're generating your lexer (with ragel, flex, etc) then you are using regular expressions.
- farresito 10y agoHow is it usually done in most high performance compilers, if I may ask?
- nv-vn 10y agoParsed by hand
- posterboy 10y agoThat strikes me as odd, but who am I to argue with the wisdom of the crowd. http://stackoverflow.com/questions/6319086/are-gcc-and-clang-parsers-really-handwritten http://stackoverflow.com/questions/6319086/are-gcc-and-clang... (short answer, yes)
- lallysingh 10y agoC++ is a context sensitive language, so (at least some) hand parsing is necessary.
- munificent 10y agoYou can use a generated parser for C/C++, I believe. You just need to insert a little shim between the lexer and parser to look up identifiers in the symbol table and mark which name tokens refer to types versus functions or variables.
- joshuata 10y agoYou are (essentially) correct. The language itself is context-free, and therefore parse-able as a regular language. Looking up identifiers in symbol tables is part of the type checking phase of compilation. This is a pretty common misconception, that type constraints effect the parsing complexity of a language. Language type only relates to the process of building an abstract syntax tree from an input, not validating it.
- munificent 10y ago> therefore parse-able as a regular language. You mean "context-free" not "regular" here, but either way, I believe that C is actually context-sensitive: (a)(b); Is this: 1. Evaluating "b" and casting it to type "a"? 2. Evaluating the parenthesized expression "a" which yields a function, and then calling it, passing in "b"? The only way to distinguish the two is by knowing whether "a" is a type or not. You could argue that as long as the parser produces a suitably vague AST, it doesn't need to know the distinction and can pass it on to later phases. I think that might work because I don't know of cases where the syntax actually diverges based on the type of a symbol. But in practice, I think most parsers want to produce a more precise AST that distinguishes cast expressions from function calls.
- joshuata 10y agoYou are right, the regular/context-free comment was a typo. You are also correct about c being non-context-free[0]. I have just seen many explanations of language hierarchy online mistaking type-checking for language complexity that it is a pet peeve of mine. [0] http://eli.thegreenplace.net/2007/11/24/the-context-sensitivity-of-cs-grammar http://eli.thegreenplace.net/2007/11/24/the-context-sensitiv...
- base698 10y agoI always thought a hilarious interview question was, "what's regular about a regular expression?" Similar to, "What's Cascading about Cascading Style Sheets?"
- betenoire 10y agoI know the answers to those questions... but don't get the joke... What's the joke?
- kmill 10y agoWhat is your answer to the first question? In Kleene's original paper (which I've only skimmed), he is interested in "events" for nerve computation models, and defines "regular events" to be some minimal set of events which is closed under concatenation, alternation, and star. He admits "regular" should be replaced by a better word --- this never happened. http://cs.stackexchange.com/questions/1771/why-is-a-regular-language-called-regular http://cs.stackexchange.com/questions/1771/why-is-a-regular-... If I were to make up history, I would say "oh, regular refers to finite state machines, so a regular language is a language recognizable by a finite state machine," but it appears my made-up history does not exactly match reality. This is not too far off, though, since in the paper he shows that regular events are exactly the kinds of events his nerve networks recognize, and there appears to be something about finite automata in the last section. They could have been called "rational languages" instead, because of a connection with rational functions. In fact, there are manipulations of rational series in Kleene's paper to prove some things about the languages. (I don't get the joke myself --- unless the joke is that you can't take the "regular" out of "regular language.")
- betenoire 10y agoI share your understanding, and yeah, the joke is probably that the word "regular" sounds "easy" or "normal" (shit another loaded term). I was just curious if I was missing more