1
$\begingroup$

In my theoretical computer science class we learned about FSMs/lexical analysis/parsing. However, my teacher focused solely on the table-driven approach to the process for simplicity (I think, anyway), where the table is a 2D array with the row being a character and each column being a DFA state transition. The table therefore might look like this (in C++), assuming the character tabulation character is what we're scanning and assuming there are 13 states and 128 characters:

static const unsigned char DFA[128][13] = {
    // ...
    // Tab
    {WS, ACCEPT, ACCEPT, ERROR, ACCEPT, ERROR, ERROR, ERROR, ERROR, ACCEPT, ACCEPT, ACCEPT, ACCEPT},
    // ...
};

One advantage to this approach is that the lexer can be relatively simple to extend, only requiring one to modify the DFA to add new tokens (e.g. <=, :=, ...). All the lexer has to do is look up the character (row in the DFA) and the state that its currently in to transition to another state (the column) (DFA[character_read][current_state]) However, this is burdensome because if you want to add new tokens that aren't already scanned (e.g. a combined token like <= or --), you have to add another state and modify every row in the DFA table to accommodate the change. I can think of a few ways of circumventing this, none of which are very pleasant:

  1. Make the "error" state be state 0 and use std::array to automatically initialize all new columns to the "error" state, and then only initialize the rows you want to actually add.
  2. Parse multi-character tokens in the parser itself (definitely a bad idea because it pollutes the parser with work that should've already been completed).

These problems add up when you want to parse things like unicode characters. I can't think of any way of actually making this work using the table-driven approach, other than generating a size_of_ucd*number_of_states 2D array, which is nearly impossible to open in most text editors because the file is so massive, and it still suffers from the above issues.

I've heard of the directly coded approach, as well as using functions like ispunct and isalpha (or matching characters to unicode character categories), but this seems just as clunky: now modifying your lexer requires you to modify how the lexer composes tokens instead of just modifying a table and not having to touch your main lexer code at all. Using a lexer generator is an option but hand-writing lexers and parsers seems like a much better way of fully understanding how your parser works, and it also requires no extra tools for the build process other than those that your build system requires already. Plus, the code can be made to be very readable, which can't be said for generated code (at least 3/4 of the time).

What are some good solutions to resolving this problem that makes the lexer easy to read and modify? I could see using character ranges as being a possible workaround, but the UCD doesn't appear to be very contiguous, which makes that difficult to do.

$\endgroup$

1 Answer 1

0
$\begingroup$

Real lexical analyser generators group characters into classes that are equivalent.

Let's suppose you are trying to parse C, for example, and we will further suppose that keywords are handled via a symbol table of some kind, so we only need to recognise identifiers. A C identifier starts with an alphabetical character or underscore, and is followed by zero or more alphabetical characters, numeric characters, or underscores.

Do all alphabetical characters share the same transitions from all DFA states? Well, no. The characters f, e, and x (and their upper-case equivalents) play special roles in the lexical syntax of numbers. But most alphabetical characters are equivalent.

Similarly, all numerical characters are equivalent except for 0, which has a special use in representing hexadecimal and octal numbers. But the others are equivalent.

So it makes sense in practice to have a single array mapping characters to character classes, and then define the DFA transitions in terms of character classes, since there are far fewer character classes than characters.

If you want to hand-write a lexical analyser, you could consider using goto statements for your state transitions.

Yes, seriously. Dijkstra's point was that structured code follows structured data. But more abstract models of computation, like finite state machines, might map more directly into other language constructs.

Of course, there's always real-world compiler source code that you could examine for ideas.

$\endgroup$
2
  • $\begingroup$ Wouldn't creating such a table become infeasible though, especially when using unicode? I mean, you could use locale/character identification functions like C's ispunct or isalpha or Rusts is_alphabetic but that feels more of a hack. I'll look into how compilers do it -- thanks for that suggestion! $\endgroup$ Dec 14, 2021 at 1:06
  • $\begingroup$ Yes, I wouldn't hand-write a table-driven lexer. I'm just pointing out that even auto-generated ones don't typically switch directly on characters. $\endgroup$
    – Pseudonym
    Dec 14, 2021 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.