Tokens, patterns, and lexemes in Compiler Design - Mini Project: Build & Apply

Understanding Tokens, Patterns, and Lexemes

📖 Scenario: You are learning how a simple compiler breaks down source code into meaningful pieces. This process involves identifying tokens, patterns, and lexemes from a line of code.

🎯 Goal: Build a simple representation of tokens, patterns, and lexemes from a given line of code to understand how compilers analyze source code.

📋 What You'll Learn

Create a list of code words as the data set

Define a pattern to identify keywords

Extract tokens by matching code words to the pattern

Complete the final list showing tokens with their lexemes

💡 Why This Matters

🌍 Real World

Compilers and interpreters use tokens, patterns, and lexemes to understand and translate programming code.

💼 Career

Understanding these concepts is essential for roles in compiler development, programming language design, and software tooling.

1

Create the code words list

Create a list called code_words containing these exact strings: 'int', 'main', '(', ')', '{', 'return', '0', ';', '}'.

Compiler Design

# Create the list code_words with the exact code words
# Your code here

Hint

Use square brackets to create a list and include all code words as strings separated by commas.

2

Define the keyword pattern

Create a list called keywords containing these exact strings: 'int' and 'return'.

Compiler Design

code_words = ['int', 'main', '(', ')', '{', 'return', '0', ';', '}']
# Create the list keywords with 'int' and 'return'
# Your code here

Hint

Keywords are special reserved words in programming. List them exactly as given.

3

Extract tokens with their types

Create a list called tokens that contains tuples for each word in code_words. Each tuple should have the word and its type: if the word is in keywords, type is 'keyword', if the word is a parenthesis or brace 'symbol', if the word is a number 'number', otherwise 'identifier'. Use a for loop with word as the iterator variable.

Compiler Design

code_words = ['int', 'main', '(', ')', '{', 'return', '0', ';', '}']
keywords = ['int', 'return']
# Create tokens list with tuples (word, type) using a for loop
# Your code here

Hint

Check each word against keywords, symbols, and numbers to assign the correct token type.

4

Complete the lexemes list

Create a list called lexemes that contains only the first element (the word) from each tuple in tokens using a list comprehension.

Compiler Design

code_words = ['int', 'main', '(', ')', '{', 'return', '0', ';', '}']
keywords = ['int', 'return']
tokens = []
symbols = ['(', ')', '{', '}', ';']
for word in code_words:
    if word in keywords:
        tokens.append((word, 'keyword'))
    elif word in symbols:
        tokens.append((word, 'symbol'))
    elif word.isdigit():
        tokens.append((word, 'number'))
    else:
        tokens.append((word, 'identifier'))
# Create lexemes list with only the words from tokens
# Your code here

Hint

Use a list comprehension to extract the first item from each tuple in tokens.

Practice

1. What is a token in compiler design?

easy

A. The exact sequence of characters in the source code

B. A category or label for a group of characters

C. A rule describing valid sequences of characters

D. A syntax error found during compilation

Solution

1. Step 1: Understand the role of tokens

   Tokens act like words in a sentence, grouping characters into meaningful categories.

2. Step 2: Differentiate tokens from lexemes and patterns

   Lexemes are the actual text, patterns are rules, tokens are the labels for those texts.

3. Final Answer:

   A category or label for a group of characters -> Option B

4. Quick Check:

   Token = label/category [OK]

Hint: Tokens are like word types, not the words themselves [OK]

Common Mistakes:

• Confusing tokens with lexemes
• Thinking tokens are the exact text
• Mixing tokens with syntax errors

2. Which of the following correctly describes a pattern in lexical analysis?

easy

A. The exact characters matched in the source code

B. A syntax error detected during compilation

C. The output of the parser after syntax analysis

D. A rule or regular expression defining valid tokens

Solution

1. Step 1: Define what a pattern is

   Patterns describe the rules or formats that valid tokens must follow, often using regular expressions.

2. Step 2: Eliminate incorrect options

   Exact characters are lexemes, parser output is unrelated, syntax errors are not patterns.

3. Final Answer:

   A rule or regular expression defining valid tokens -> Option D

4. Quick Check:

   Pattern = rule for tokens [OK]

Hint: Patterns are rules, not actual text [OK]

Common Mistakes:

• Confusing patterns with lexemes
• Thinking patterns are output of parsing
• Mixing patterns with errors

3. Given the source code snippet: int count = 10; Which of the following is a correct lexeme for the token identifier?

medium

A. count

B. =

C. 10

D. int

Solution

1. Step 1: Identify the token 'identifier'

   An identifier token represents names like variables or functions.

2. Step 2: Match lexemes to token types

   In the snippet, 'count' is the variable name, so it is the lexeme for the identifier token.

3. Final Answer:

   count -> Option A

4. Quick Check:

   Identifier lexeme = count [OK]

Hint: Identifiers are names, not keywords or symbols [OK]

Common Mistakes:

• Choosing keywords like 'int' as identifiers
• Selecting numbers or operators as identifiers
• Confusing lexemes with token types

4. Identify the error in this tokenization process for the input var_1 = 25;: Tokens identified are var (identifier), _1 (identifier), = (assignment), 25 (number), ; (semicolon).

medium

A. The underscore and digit should be part of the same identifier token

B. The assignment operator should be tokenized as two separate tokens

C. The number 25 should be split into two tokens '2' and '5'

D. The semicolon should not be a token

Solution

1. Step 1: Understand identifier token rules

   Identifiers can include letters, digits, and underscores as one token, not split.

2. Step 2: Analyze the given tokenization

   Splitting 'var_1' into 'var' and '_1' is incorrect; it should be one identifier token.

3. Final Answer:

   The underscore and digit should be part of the same identifier token -> Option A

4. Quick Check:

   Identifier tokens include underscores and digits [OK]

Hint: Keep underscores and digits inside one identifier token [OK]

Common Mistakes:

• Splitting identifiers incorrectly
• Misinterpreting assignment operator tokenization
• Ignoring semicolon as a token

5. You want to design a lexical analyzer that recognizes tokens for integers and identifiers. Which pattern correctly matches an identifier but not an integer?

hard

A. [a-zA-Z0-9]+

B. [0-9]+

C. [a-zA-Z_][a-zA-Z0-9_]*

D. [0-9]*[a-zA-Z]+

Solution

1. Step 1: Understand identifier and integer patterns

   Identifiers start with a letter or underscore, followed by letters, digits, or underscores. Integers are digits only.

2. Step 2: Eliminate incorrect options

   A matches integers like '123'; B matches only integers; D fails to match identifiers ending in digits like 'var1'.

3. Final Answer:

   [a-zA-Z_][a-zA-Z0-9_]* -> Option C

4. Quick Check:

   Identifier pattern starts with letter/underscore [OK]

Hint: Identifiers start with letter/underscore, not digit [OK]

Common Mistakes:

• Allowing digits as first character in identifiers
• Confusing integer patterns with identifiers
• Using patterns that match both integers and identifiers