0
$\begingroup$

I'm trying to implement a compiler for a custom language as part of an assignment.

I am still trying to figure out how to build the lexer. From what I understand, for a table-driven lexer, we have 3 tables:

  1. Classification Table
  2. Transition Table
  3. Token Type Table

My problem is mainly coming from the fact that the only example I've seen of the concept of a table-driven lexer is the "famous" (because I see it in every University's online notes) Cooper & Torczon DFA for reading digits. Page 25

From what I gather, the purpose of each of these is as follows:

1: To classify the atomic parts of the language, such as digits (0,1,2,3....) and letters (a,b,c,...)

2: To define what should happen next according to what's just been classified (If digit, go to state X, if letter, go to state Y)

3: Apparently this is used to check whether or not the string is accepted. Honestly I don't even know what the point of this is.

The grammar I'm trying to build a compiler for is much more complicated than the examples I've seen online. It contains more "atomic" symbols, such as operators (*,+,-,/,>, etc..) and reserved keywords (if, for, while, etc...)

By atomic, I mean symbols that stand on their own. (I.e. if is a symbol in its own right, not i and f) This poses a problem for me, since I won't be able to know if I'm reading if or a string of the form aifb

Here's what I'm currently trying to do:

  1. First, I'm building a CAT (classifier table) for all the atomic symbols of the language. I don't know if this is the right thing to do, especially when I have 52 letters (English alphabet), 10 digits and reserved words.
  2. I will then merge all the CATs together. So I will have one big CAT that covers letters, digits, and reserved words.
  3. Then, I will build a (big) transition table, so that when I read a character and determine its classification (problem: What about reserved words that take more than 1 character?) I will know where to transition to next.
  4. These tables are used by a simple DFA class which, once the lexeme is read, will spit out a token.

The assignment specifies that I have to use a table-driven lexer.

$\endgroup$
  • 1
    $\begingroup$ What textbook are you using in this course? $\endgroup$ – rici Mar 21 at 18:38
  • $\begingroup$ @rici the Dragon book $\endgroup$ – Novicegrammer Mar 21 at 18:40
  • 1
    $\begingroup$ So you should be familiar with the chapter on DFAs. Basically, the table-driven lexer is a way of simulating a DFA. $\endgroup$ – rici Mar 21 at 18:43
  • $\begingroup$ @rici That I understand. My problem is, a DFA takes letters from an alphabet. For our purpose, the alphabet consists of whatever character in the code text. But words such as "if" and "for" aren't letters, they're strings (i.e they require successive nextChar() calls to fully "read") - however, in the new language, they're standalone symbols. This is my issue, building a DFA that can differentiate between "if" as a reserved word, and "if" as a substring $\endgroup$ – Novicegrammer Mar 21 at 18:52
  • 1
    $\begingroup$ I added some graphs in case that makes it easier to digest. $\endgroup$ – rici Mar 21 at 19:54
5
$\begingroup$

A table-driven lexer is just a way of simulating a DFA. Lexer generators build DFAs from a lexical description, and then compile the DFA into the tables necessary to produce a lexical scanner.

Note that the goal is to not just identify lexemes, but to classify them by lexical type. Some lexemes have a unique spelling (like if and <=); others represent classes of symbols which have the same syntactic significance but different semantics. (That would be, for example, IDENTIFIER and NUMBER, which are two lexical types, each with a potentially unlimited number of different associated tokens.)

Lexical analysis with a state machine is slightly different from using a DFA to recognise strings, because the point of lexical analysis is to divide the input into a sequence of substrings, each of which is a token. It's important that this sequence is a partitioning of the string; every character is part of some token. That means that each successive token starts exactly where the previous token finished. In particular, that means that you don't have to worry about the if in the middle of different, but you do have to think about the for in fortunate. (All the same, it doesn't present a huge problem.)

As the Dragon book notes (and so do Cooper&Torczon IIRC), the vast majority of lexers use the "maximal munch" procedure (sometimes with a few exceptions), in which the lexeme produced at some point in the input is the longest one matchable with some lexical pattern.

In some cases, it is possible that the lexical analyser will overreach. As an example, consider lexing C, where . and ... are both possible lexemes, but .. is not. If the input contains .., the lexical analyser needs to try to match the pattern .... If that fails, if the input contains .. followed by something other than another . (for example, ..345), the lexical analyser will have to backtrack. It will accept the first . as a token, and then restart the scan with the second . (which will turn out to lead to recognizing the number token .345 in this case).

So the precise algorithm used by the analyser when it is asked to produce the next token is:

  1. Run the DFA until it reaches a state in which the next character has no valid transitions.

  2. While running the DFA, always remember the last accepting state encountered.

  3. When the DFA cannot be advanced any further, if it is not in an accepting state, back up to the last accepting state and return the corresponding token.

It's always a good idea to try to avoid this backtracking, but it is not always possible as the above C example indicates.

We said earlier that the goal of the analyser is to identify the lexical type of the token. How does it do that? Simple. The various patterns are combined into a single DFA, using the standard NFA->DFA transformation. (That's in the Dragon Book.) In the DFA which results from that transformation each state is a set of states from the original NFA, and is an accepting state if any of the associated NFA states is accepting. We map that onto a token type by noting which of the NFAs contains the associated accepting state. If there is more than one NFA which has contributed an accepting state, then we choose one of them arbitrarily. (Usually, we've arranged the patterns in priority order so that we can simply say that the first pattern wins.)

That gives us a mapping from DFA state to pattern number, and that is the role of the Token Type table.

In case that explanation was too theoretic, I've created two graphs. The first one shows DFAs for four patterns: the token <, the token <=, the token if and the token ID (any identifier). In the transitions, please interpret "letter" as meaning "any letter other than i or f", which was just too long to put on the graph. And see the paragraph below about character classification. Four individual pattern DFAs

In the second graph, I show the DFA which results from combining these. I leave it as an exercise to construct the Token Type table. Combined lexer DFA

The Transition table is simple: it just represents the DFA. It maps a pair <state, character> to a new state. Unfortunately, there are a lot of different possible characters -- 256, if we use 8-bit characters -- and usually quite a few states, and that would make for quite a large table, since it is essentially a two-dimensional array. To make the table smaller, we note that many characters have precisely the same transitions in every state. As a simple example, most of the 256 possible input characters are only valid inside character string literals or comments, and in those contexts all of them are effectively identical.

That's what the character classification table is. We gather the possible input characters into a set of equivalence classes, where each equivalence class has exactly the same transitions in every state. Any character with a specific transition -- including the i and the f in if, for example -- will be in an equivalence class by itself. But even then, we'll find that many alphabetic characters are not present in any keyword (upper-case characters, for example). And while some digits may have specific transitions -- 0 is a common case -- there are very few lexicons in which 2 and 3 have specific transitions. So we can probably reduce the number of possible transition characters from 256 to maybe 40 or 50, which is an 80% reduction in size of the transition table. In any case, if you don't want to do that, it's just an optimisation. The analyser will work fine either way.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for the late question: So you're suggesting that any symbol which can be part of a reserved word be in its own exclusive equiv class? I actually think it makes sense, I'm just making sure. $\endgroup$ – Novicegrammer Mar 22 at 14:48
  • 1
    $\begingroup$ @novicegrammar: yes, that's what I'm saying. The way the equivalence classes are computed is conceptually to put two characters in the same class only if they have the same transitions (or lack of transitions) in every state in every DFA. For most languages, that tends to put most lower-case letters into equivalence classes by themselves. But it still allows putting most upper-case letters in a single equivalence class, so it's still an improvement. $\endgroup$ – rici Mar 22 at 15:28
  • $\begingroup$ @novice: you can go further. Flex, for example, has "approximate" ECs, which it calls meta-equivalence classes, which group common transitions between symbols with similar transitions. To look up a transition, you then need to first try with the meta-ec, and then if you don't find a transition, try with the ec itself. It's slower but the tables are smaller. However, finding good meta-ecs is tricky. Ecs can be computed with a simple reasonably fast algorithm. $\endgroup$ – rici Mar 22 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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