CD Notes
Detailed explanation of tokens, token types, token attributes, and how tokens are represented and used in the compilation process.
What are Tokens?
A token is the fundamental unit produced by the lexical analyzer. It represents a categorized piece of the source program and is passed to the parser for syntax analysis. Each token consists of a token name (or token type) and optionally an attribute value that provides additional information.
The token name is an abstract symbol used by the parser for syntax checking, while the attribute value points to the symbol table entry or contains a literal value for use in later compilation phases.
Token Categories
Programming languages typically define the following categories of tokens:
1. Keywords (Reserved Words)
Keywords are predefined identifiers with special meaning in the language. They cannot be used as user-defined identifiers.
| C Keywords | int, float, char, if, else, while, for, return, void, struct |
| Java Keywords | class, public, private, static, final, abstract, interface |
| Python Keywords | def, class, if, elif, else, while, for, import, return |
2. Identifiers
Identifiers are names given to program entities (variables, functions, classes, etc.).
3. Literals (Constants)
| Integer literals | 42, 0xFF, 0b1010, 0o77 |
| Floating-point | 3.14, 2.5e10, 1.0E-3 |
| String literals | "hello", 'world' |
| Character literals | 'a', '\n', '\t' |
| Boolean literals | true, false |
4. Operators
| Arithmetic | + - * / % ** |
| Relational | < > <= >= == != |
| Logical | && || ! and or not |
| Assignment | = += -= *= /= %= |
| Bitwise | & | ^ ~ << >> |
5. Punctuation/Delimiters
| Separators | ; , . : :: |
| Grouping | ( ) [ ] { } |
| Others | -> => ... @ # |
6. Special Tokens
| End of file | EOF |
| Newline | NEWLINE (significant in Python) |
| Indent/Dedent | INDENT, DEDENT (Python) |
Token Representation
Internal Representation
Tokens are typically represented as structures or objects:
typedef struct {
TokenType type; // e.g., TOKEN_IDENTIFIER, TOKEN_NUMBER
int line; // source line number
int column; // source column number
union {
char *name; // for identifiers
int intVal; // for integer literals
float floatVal; // for float literals
} attribute;
} Token;Token Stream Example
For the source code:
int main() {
int x = 10;
return x + 1;
}The token stream is:
<KEYWORD, "int">
<IDENTIFIER, "main">
<LPAREN, >
<RPAREN, >
<LBRACE, >
<KEYWORD, "int">
<IDENTIFIER, "x">
<ASSIGN, >
<INTEGER, 10>
<SEMICOLON, >
<KEYWORD, "return">
<IDENTIFIER, "x">
<PLUS, >
<INTEGER, 1>
<SEMICOLON, >
<RBRACE, >
<EOF, >Token Attributes
Attributes carry additional information that later phases need:
| Token Type | Attribute | Used By |
|---|---|---|
| IDENTIFIER | Symbol table pointer | Semantic analysis, code gen |
| INTEGER | Numeric value | Code generation |
| FLOAT | Numeric value | Code generation |
| STRING | String table pointer | Code generation |
| OPERATOR | Operator type code | Parser, code gen |
| KEYWORD | — (type is sufficient) | Parser |
Longest Match Rule
When multiple patterns match the input, the lexical analyzer uses the longest match rule:
Priority Rule
When two patterns match the same longest string, priority (typically keyword priority) determines the winner:
Tokenization Algorithm
def get_next_token():
skip_whitespace_and_comments()
if at_end_of_input():
return Token(EOF)
char = peek()
if char.isalpha() or char == '_':
return scan_identifier_or_keyword()
elif char.isdigit():
return scan_number()
elif char == '"':
return scan_string()
elif char in operators:
return scan_operator()
elif char in delimiters:
return scan_delimiter()
else:
report_error(f"Unexpected character: {char}")Handling Special Cases
Multi-character Operators
| Input | ">>=" |
| Step 1 | Read '>' — could be >, >=, >>, >>= |
| Step 2 | Read '>' — could be >>, >>= |
| Step 3 | Read '=' — matches >>= |
| Result | RIGHT_SHIFT_ASSIGN |
Distinguishing Tokens from Context
| Input | "x<y" vs "List<int>" |
| - In expressions | < is LESS_THAN operator |
| - In generics | < is LANGLE bracket |
Interview Questions
- What is a token and what information does it carry?
A token is a pair <token_name, attribute_value> produced by the lexical analyzer. The token name identifies the category (keyword, identifier, operator, etc.), and the attribute value carries additional data like a symbol table pointer or literal value.
- Explain the longest match rule with an example.
When multiple patterns could match, the lexical analyzer chooses the longest matching lexeme. For input "integer", both keyword "int" and identifier pattern match, but "integer" (7 chars) is longer than "int" (3 chars), so it's recognized as an identifier.
- How does the scanner differentiate keywords from identifiers?
Since keywords follow the same pattern as identifiers, the scanner typically recognizes all letter sequences as identifiers first, then checks a keyword table. If the string matches a keyword, it's classified as that keyword; otherwise, it remains an identifier.
- What are token attributes and why are they needed?
Token attributes provide additional information beyond the token type. For identifiers, the attribute is a symbol table pointer; for numbers, it's the numeric value. Later phases need these values for type checking, code generation, etc.
- How are multi-character operators like >>= tokenized?
The scanner uses lookahead: after reading '>', it peeks at the next character. If it's '>', it reads further. If the next is '=', the token is >>=. This greedy approach always builds the longest valid operator token.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Tokens in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, lexical, analysis, tokens, tokens in compiler design
Related Compiler Design Topics