DEV Community

Cover image for Compilers, Direct coded scanner

Posted on

Compilers, Direct coded scanner

As i mentioned in the previous posts, i like to learn new thing and share what i learned with others, so i can get feedbacks or at least understand what i learned more, by writing about it.

In a previous post, i tried to explain what i have learned about the basics of a table driven scanner , and how can we generate a one easily after creating a DFA which is going to be painful.

However, a table driven scanners has some downside like the cost of reading a character, and computing the next transition from the transition table, direct coded scanners handle this by simplifying the implementation of table look ups in both transitions and classifier table, and also by reducing the memory used in both of the previous mentioned operations.

Another thing is that the implementation of a direct coded scanner is a little bit different from the table driven one,
while table driven scanner use a general code or an algorithm to handle different DFAs and REs, the direct code scanners implement a specific code for each state in a DFA and the code in these DFAs differ from an RE to another.

Note that the direct coded scanner use a direct comparison to determine whether this character is a part of a state or not, this is an advantage, but also a disadvantage when the characters does not occupy and adjacent slots, in such a case a table driven scanner is more efficient, a hybrid approach which uses table lookups in when needed, in a direct coded scanner is also suitable.

That's it for now, in the next post i will try to share what i learned about hand coded scanners.

Discussion (0)