Drawtomata / Lexical analyzer and token counter

Lexical analyzer and token counter

Paste a piece of C code above. Drawtomata lists every token with its lexeme, token name and attribute, counts them by class (keywords, identifiers, constants, operators, separators, string literals), and builds the symbol table. The other views trace the transition diagrams, combine token patterns into one DFA, simulate the two-buffer input scheme and run Lex and Yacc files.

Tokens, lexemes and attributes

A lexeme is the text that was matched, a token its class, and the attribute what the parser needs to know about it. For if (x1 <= rate) the stream is <if> <(> <id, 1> <relop, LE> <id, 2> <)>: the identifiers point at symbol-table entries 1 and 2, and relop carries which comparison it is. White space, comments and preprocessor lines are skipped and are not tokens.

Counting tokens

A common exam question asks how many tokens a statement has. printf("sum = %d", x); has 7: printf, (, the whole string literal, the comma, x, ) and the semicolon. A string literal is one token however long it is.

Transition diagrams

Aho draws relational operators, identifiers and unsigned numbers as transition diagrams. States marked * have read one character past the lexeme, so the forward pointer retracts before the token is returned. The tool runs each diagram on your input and shows every move.

Patterns to one DFA

Lex combines all token patterns into one NFA with a new start state, converts it to a DFA, and lets each DFA state announce the first-listed pattern among its final states. Scanning then takes the longest match. For the patterns a, abb and a*b+ the tool reproduces Aho's figure 3.54.

Input buffering

Two halves of N characters each end in a sentinel eof, so the scanner tests for the end of a buffer only when it reads eof instead of on every character. A lexeme longer than N can be lost when the half holding its start is reloaded; try a small N to see it happen.

Lex and Yacc

Paste a .l file and a .y file: yylex takes the longest match (the earlier rule on a tie), and the grammar becomes an LALR(1) table with conflicts settled by %left and %right, the way yacc does it. The tokens from yylex are then parsed step by step.