https://stackoverflow.com/questions/16880736
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianI am trying to understand the way bottom-up parsing is implemented.
No you aren't. Your question is about lexical analysis. Nothing to do with parsing.
I got it to the point where regular expressions are converted to NFAs and then to DFAs and how a DFA is represented as a two dimensional table.
Again this has nothing to do with parsing. It has little to do with actual lexical analysis either. It is a question about lexical analyzer generation. You are now two steps removed from your stated subject.
The question is wouldn't that be a quite large table with everything in the alphabet listed in one side of it?
It would be as large as it needs to be to represent the DFA, which in turn depends on the rules you specify. Not a real question.
Is it really the way it is supposed to be implemented?
There are lots of ways to represent a DFA. flex(1) provides three or four options, for example, each with a different space/time tradeoff. You would almost certainly start by implementing character classes, which would eliminate 'everything in the alphabet listed in one side of it' immediately.
The other question is as far as I know most languages have some Regex implementation out of the box. Can those Regex utilities be used as some ready implementation of lexical analysis part and then one can go on directly to make the a parse table out the output?
- Again, parsing has nothing to do with lexical analysis.
- A DFA already is a 'ready implementation of lexical analysis'.
- As per @Qtax's comment, a single DFA for the entire ruleset is a lot faster than a series of regular expressions. It is almost certainly more compact as well.
