当前位置： 首页 > news >正文

一个极简的词法分析器实现

news 2025/4/2 20:56:32

文章目录

  • 推荐：Tiny Lexer - 一个极简的C语言词法分析器
    • 特点
    • 核心代码实现
    • 学习价值
    • 扩展建议
  • 用Java实现一个简单的词法分析器
    • 完整实现代码
    • 代码解析
    • 示例输出
    • 扩展建议
  • 用Go实现极简词法分析器
    • 完整实现代码
    • 代码解析
    • 示例输出
    • 扩展建议

最近两天搞一个DSL，不得不重温了一把antlr4和编译原理之词法分析。

推荐：Tiny Lexer - 一个极简的C语言词法分析器

推荐一个非常小巧但完整的C语言词法分析器实现 - Tiny Lexer。它具有以下优点：

特点

  • 代码量极小（约100行核心代码）
  • 纯C实现，无外部依赖
  • 易于理解和学习
  • 包含完整的功能：标识符、数字、运算符识别等

核心代码实现

#include <stdio.h>
#include <ctype.h>
#include <string.h>typedef enum {TOKEN_EOF,TOKEN_NUMBER,TOKEN_IDENTIFIER,TOKEN_OPERATOR,TOKEN_UNKNOWN
} TokenType;typedef struct {TokenType type;char value[32];
} Token;Token get_next_token(const char** input) {Token token = {TOKEN_UNKNOWN, {0}};// 跳过空白字符while (isspace(**input)) {(*input)++;}// 检查文件结束if (**input == '\0') {token.type = TOKEN_EOF;return token;}// 处理数字if (isdigit(**input)) {token.type = TOKEN_NUMBER;int i = 0;while (isdigit(**input) && i < sizeof(token.value)-1) {token.value[i++] = *(*input)++;}token.value[i] = '\0';return token;}// 处理标识符（字母开头）if (isalpha(**input)) {token.type = TOKEN_IDENTIFIER;int i = 0;while ((isalnum(**input) || **input == '_') && i < sizeof(token.value)-1) {token.value[i++] = *(*input)++;}token.value[i] = '\0';return token;}// 处理运算符if (strchr("+-*/=(){};", **input)) {token.type = TOKEN_OPERATOR;token.value[0] = *(*input)++;token.value[1] = '\0';return token;}// 未知字符token.value[0] = *(*input)++;return token;
}int main() {const char* input = "int x = 42 + y;";const char* p = input;while (1) {Token token = get_next_token(&p);if (token.type == TOKEN_EOF) break;const char* type_str;switch (token.type) {case TOKEN_NUMBER: type_str = "NUMBER"; break;case TOKEN_IDENTIFIER: type_str = "IDENTIFIER"; break;case TOKEN_OPERATOR: type_str = "OPERATOR"; break;default: type_str = "UNKNOWN"; break;}printf("Token: %-12s Value: %s\n", type_str, token.value);}return 0;
}

学习价值

  1. 词法分析基本原理：展示了如何将输入流分解为token
  2. 状态机概念：通过条件判断实现了简单的状态转移
  3. 可扩展性：可以轻松添加更多token类型和规则
  4. 实用性：虽然简单，但包含了词法分析的核心功能

扩展建议

学习这个基本实现后，你可以尝试：

  1. 添加更多运算符和关键字识别
  2. 实现更复杂的数字格式（如浮点数）
  3. 添加错误处理机制
  4. 将其扩展为递归下降语法分析器

这个实现去除了所有不必要的复杂性，是学习编译原理前端技术的理想起点。

用Java实现一个简单的词法分析器

下面我将实现一个最简的词法分析器（Lexer），它可以识别以下类型的词法单元（Token）：

  • 整数（如 123）
  • 浮点数（如 3.14）
  • 标识符（如 variable）
  • 运算符（如 +, -, *, /）
  • 分隔符（如 (, ), ;）

完整实现代码

import java.util.ArrayList;
import java.util.List;public class SimpleLexer {// Token类型枚举public enum TokenType {INTEGER,    // 整数FLOAT,      // 浮点数IDENTIFIER, // 标识符OPERATOR,   // 运算符DELIMITER,  // 分隔符EOF         // 文件结束}// Token类public static class Token {public final TokenType type;public final String value;public Token(TokenType type, String value) {this.type = type;this.value = value;}@Overridepublic String toString() {return String.format("Token(%s, '%s')", type, value);}}private final String input;private int position = 0;public SimpleLexer(String input) {this.input = input;}// 词法分析主方法public List<Token> tokenize() {List<Token> tokens = new ArrayList<>();while (position < input.length()) {char current = peek();// 跳过空白字符if (Character.isWhitespace(current)) {consume();continue;}// 处理数字if (Character.isDigit(current)) {tokens.add(readNumber());continue;}// 处理标识符（以字母或下划线开头）if (Character.isLetter(current) || current == '_') {tokens.add(readIdentifier());continue;}// 处理运算符if (isOperator(current)) {tokens.add(new Token(TokenType.OPERATOR, Character.toString(consume())));continue;}// 处理分隔符if (isDelimiter(current)) {tokens.add(new Token(TokenType.DELIMITER, Character.toString(consume())));continue;}throw new RuntimeException("Unexpected character: " + current);}tokens.add(new Token(TokenType.EOF, ""));return tokens;}// 读取数字（整数或浮点数）private Token readNumber() {StringBuilder sb = new StringBuilder();boolean hasDecimal = false;while (position < input.length() && (Character.isDigit(peek()) || (!hasDecimal && peek() == '.'))) {if (peek() == '.') {hasDecimal = true;}sb.append(consume());}return new Token(hasDecimal ? TokenType.FLOAT : TokenType.INTEGER, sb.toString());}// 读取标识符private Token readIdentifier() {StringBuilder sb = new StringBuilder();while (position < input.length() && (Character.isLetterOrDigit(peek()) || peek() == '_')) {sb.append(consume());}return new Token(TokenType.IDENTIFIER, sb.toString());}// 辅助方法：查看当前字符但不消耗private char peek() {return input.charAt(position);}// 辅助方法：消耗当前字符并返回private char consume() {return input.charAt(position++);}// 判断是否是运算符private boolean isOperator(char c) {return c == '+' || c == '-' || c == '*' || c == '/';}// 判断是否是分隔符private boolean isDelimiter(char c) {return c == '(' || c == ')' || c == ';';}// 测试public static void main(String[] args) {String input = "x = 123 + (y * 3.14);";SimpleLexer lexer = new SimpleLexer(input);List<Token> tokens = lexer.tokenize();for (Token token : tokens) {System.out.println(token);}}
}

代码解析

  1. Token类型定义：

    • 使用枚举TokenType定义了各种词法单元类型
    • Token类封装了类型和实际值

  2. 核心方法：

    • tokenize()：主方法，逐个字符分析输入字符串
    • readNumber()：读取整数或浮点数
    • readIdentifier()：读取标识符

  3. 辅助方法：

    • peek()：查看当前字符但不移动指针
    • consume()：读取当前字符并移动指针
    • isOperator()和isDelimiter()：判断字符类型

  4. 处理流程：

    • 跳过空白字符
    • 按优先级识别数字、标识符、运算符和分隔符
    • 遇到无法识别的字符抛出异常

示例输出

对于输入"x = 123 + (y * 3.14);"，输出结果为：

Token(IDENTIFIER, 'x')
Token(OPERATOR, '=')
Token(INTEGER, '123')
Token(OPERATOR, '+')
Token(DELIMITER, '(')
Token(IDENTIFIER, 'y')
Token(OPERATOR, '*')
Token(FLOAT, '3.14')
Token(DELIMITER, ')')
Token(DELIMITER, ';')
Token(EOF, '')

扩展建议

这个简单词法分析器可以进一步扩展：

  1. 支持更多运算符（如==, !=等）
  2. 添加关键字识别（如if, while等）
  3. 支持字符串字面量
  4. 添加注释处理
  5. 改进错误处理机制

这个实现是编译器前端的基础组件，可以作为更复杂词法分析器的起点。

用Go实现极简词法分析器

下面是一个用Go语言实现的极简词法分析器，它可以识别以下词法单元：

  • 整数（如 123）
  • 标识符（如 variable）
  • 运算符（如 +, -, *, /）
  • 分隔符（如 (, ), ;）

完整实现代码

package mainimport ("fmt""unicode"
)// TokenType 表示词法单元类型
type TokenType intconst (EOF TokenType = iota // 文件结束INTEGER             // 整数IDENTIFIER          // 标识符OPERATOR            // 运算符DELIMITER           // 分隔符
)// Token 表示一个词法单元
type Token struct {Type  TokenTypeValue string
}// String 实现Stringer接口
func (t Token) String() string {return fmt.Sprintf("Token(%v, '%s')", t.Type, t.Value)
}// Lexer 词法分析器结构体
type Lexer struct {input    stringposition int
}// NewLexer 创建新的词法分析器
func NewLexer(input string) *Lexer {return &Lexer{input: input}
}// NextToken 获取下一个词法单元
func (l *Lexer) NextToken() Token {// 跳过空白字符l.skipWhitespace()// 检查是否到达输入末尾if l.position >= len(l.input) {return Token{Type: EOF, Value: ""}}current := l.peek()// 处理数字if unicode.IsDigit(current) {return l.readNumber()}// 处理标识符if unicode.IsLetter(current) || current == '_' {return l.readIdentifier()}// 处理运算符if isOperator(current) {token := Token{Type: OPERATOR, Value: string(l.consume())}return token}// 处理分隔符if isDelimiter(current) {token := Token{Type: DELIMITER, Value: string(l.consume())}return token}panic(fmt.Sprintf("未知字符: %c", current))
}// 读取数字
func (l *Lexer) readNumber() Token {start := l.positionfor l.position < len(l.input) && unicode.IsDigit(l.peek()) {l.consume()}return Token{Type: INTEGER, Value: l.input[start:l.position]}
}// 读取标识符
func (l *Lexer) readIdentifier() Token {start := l.positionfor l.position < len(l.input) && (unicode.IsLetter(l.peek()) || unicode.IsDigit(l.peek()) || l.peek() == '_') {l.consume()}return Token{Type: IDENTIFIER, Value: l.input[start:l.position]}
}// 跳过空白字符
func (l *Lexer) skipWhitespace() {for l.position < len(l.input) && unicode.IsSpace(l.peek()) {l.consume()}
}// 查看当前字符但不消耗
func (l *Lexer) peek() rune {if l.position >= len(l.input) {return 0}return rune(l.input[l.position])
}// 消耗当前字符并返回
func (l *Lexer) consume() rune {if l.position >= len(l.input) {return 0}char := rune(l.input[l.position])l.position++return char
}// 判断是否是运算符
func isOperator(r rune) bool {return r == '+' || r == '-' || r == '*' || r == '/'
}// 判断是否是分隔符
func isDelimiter(r rune) bool {return r == '(' || r == ')' || r == ';'
}func main() {input := "x = 123 + (y * 456);"lexer := NewLexer(input)for {token := lexer.NextToken()fmt.Println(token)if token.Type == EOF {break}}
}

代码解析

  1. Token类型定义：

    • 使用TokenType枚举定义词法单元类型
    • Token结构体包含类型和实际值

  2. Lexer结构体：

    • 保存输入字符串和当前位置
    • 提供NextToken()方法逐个生成词法单元

  3. 核心方法：

    • readNumber()：读取整数
    • readIdentifier()：读取标识符
    • skipWhitespace()：跳过空白字符

  4. 辅助方法：

    • peek()：查看当前字符但不移动指针
    • consume()：读取当前字符并移动指针
    • isOperator()和isDelimiter()：判断字符类型

示例输出

对于输入"x = 123 + (y * 456);"，输出结果为：

Token(IDENTIFIER, 'x')
Token(OPERATOR, '=')
Token(INTEGER, '123')
Token(OPERATOR, '+')
Token(DELIMITER, '(')
Token(IDENTIFIER, 'y')
Token(OPERATOR, '*')
Token(INTEGER, '456')
Token(DELIMITER, ')')
Token(DELIMITER, ';')
Token(EOF, '')

扩展建议

这个基础词法分析器可以进一步扩展：

  1. 添加浮点数支持
  2. 支持更多运算符（如==, !=等）
  3. 添加关键字识别
  4. 支持字符串字面量
  5. 添加注释处理
  6. 改进错误处理机制

这个实现展示了Go语言简洁高效的特点，适合作为更复杂词法分析器的基础。


http://www.mrgr.cn/news/96604.html

相关文章：

  • Java-01-源码篇-JUC并发编程-原子类
  • 供应链业务-供应链全局观（一）
  • 数据库--数据库设计
  • OpenHarmony v4.1 Release设置应用随系统自动启动
  • 23 python 数据容器推导式
  • 【学Rust写CAD】21 2D 点(point.rs)
  • Verilog HDL 100道面试题及参考答案
  • [7-02-02].第03节:生产经验 - Broker节点服役和退役
  • Nyquist插件基础：打印格式化字符串(LISP语言)
  • python代码实现离散haar小波变换和db4小波变换
  • kubernetes》》k8s》》 kubeadm、kubectl、kubelet 重启pod
  • SkyWalking+Springboot实战
  • 2025国内DevOps新手突围指南：从Gitee零门槛入门到工具链深度对比
  • 虫洞数观系列二 | Python+MySQL高效封装：为pandas数据分析铺路
  • 分布式计算Ray框架面试题及参考答案
  • Mac Apple silicon如何指定运行amd64架构的ubuntu Docker？
  • 一个判断A股交易状态的python脚本
  • USB有驱ID卡读卡器C#小程序开发
  • 哈希表 - 两数之和(Map) - JS
  • 【Kubernetes】CentOS 7 安装 Kubernetes 1.30.1