词法分析器开发：ArrayList contains方法替代及去重问题求助

首先，咱们先解决你当前的重复输出问题——其实这不是contains方法的锅，是你输出逻辑的问题：你在循环里每次都把整个testarray转成字符串再拆分，而且循环遍历的是原数组的所有元素，所以原数组里有几个匹配的关键字就会输出几次。先给你修正这个逻辑，再聊替代方案。

一、先修复你的现有代码 #

1. 先清理关键字集合（去重） #

你原有的keywords ArrayList里有重复的int，先把它改成HashSet自动去重，同时提升contains的效率：

// 用HashSet存储关键字，自动去重，contains方法是O(1)时间复杂度
Set<String> keywords = new HashSet<>(Arrays.asList(
    "auto","case","char","const","continue","default", "do","double","else","break",
    "enum","extern","float","for","goto", "if","int","long","register","return",
    "short","signed", "sizeof","static","struct","switch","typedef","union", 
    "unsigned","void","volatile","while","then","endif"
));

2. 优化读取和输出逻辑 #

你的读取逻辑没问题，但输出逻辑完全没必要反复把整个集合转成字符串再拆分，直接遍历testarray即可，同时用另一个HashSet收集匹配的关键字来实现去重：

// 读取文件部分（保留你的逻辑）
List<String> testarray = new ArrayList<>();
String line;
while((line = bufferedReader.readLine()) != null) {
    String[] test = line.split(" ");
    testarray.addAll(Arrays.asList(test));
}

// 输出部分：收集去重后的关键字
Set<String> matchedKeywords = new HashSet<>();
for(String token : testarray) {
    // 先清理token的空格，避免输入里的"int "这类带空格的内容干扰
    String cleanToken = token.trim();
    if(keywords.contains(cleanToken)) {
        matchedKeywords.add(cleanToken);
    }
}

// 输出结果
System.out.print("Keywords:");
for(String key : matchedKeywords) {
    System.out.print(key + " ");
}
System.out.println();

或者用Java 8+的Stream API更简洁：

List<String> matched = testarray.stream()
    .map(String::trim)
    .filter(keywords::contains)
    .distinct()
    .collect(Collectors.toList());

System.out.print("Keywords:");
matched.forEach(k -> System.out.print(k + " "));

二、contains方法的替代方案 #

如果觉得ArrayList.contains()（O(n)效率）不够高效，或者需要更灵活的匹配，这些方案更适合词法分析器场景：

1. 使用HashSet/LinkedHashSet #

• 正如上面的示例，HashSet.contains()是O(1)时间复杂度，比ArrayList的O(n)快得多，适合关键字数量多的场景。
• 如果需要保留关键字的出现顺序，可以用LinkedHashSet，既能去重又能保持插入顺序。

2. 使用HashMap（关联额外信息） #

如果你的词法分析器需要给每个关键字绑定对应的 token 类型（比如int对应TokenType.INT），用HashMap更合适：

enum TokenType { KEYWORD_INT, KEYWORD_IF, KEYWORD_THEN, ... }
Map<String, TokenType> keywordMap = new HashMap<>();
keywordMap.put("int", TokenType.KEYWORD_INT);
keywordMap.put("if", TokenType.KEYWORD_IF);
// 其他关键字...

// 匹配时
if(keywordMap.containsKey(cleanToken)) {
    TokenType type = keywordMap.get(cleanToken);
    // 处理逻辑：比如生成对应的token对象
}

3. 使用枚举类存储关键字 #

把关键字定义成枚举，类型更安全，避免拼写错误：

enum Keyword {
    AUTO("auto"), CASE("case"), INT("int"), IF("if"), THEN("then"), ELSE("else"), ENDIF("endif");

    private final String value;
    Keyword(String value) { this.value = value; }

    // 提前把所有关键字存入Set，提升匹配效率
    private static final Set<String> KEYWORD_SET = Arrays.stream(values())
        .map(Keyword::getValue)
        .collect(Collectors.toSet());

    public static boolean isKeyword(String s) {
        return KEYWORD_SET.contains(s.trim());
    }
}

// 使用时
if(Keyword.isKeyword(token)) {
    // 处理逻辑...
}

三、除了contains，还有哪些匹配关键字的方法？ #

对于词法分析器来说，这些方法更专业：

1. 正则表达式匹配 #

直接用正则表达式匹配文本中的所有关键字，还能避免把标识符的一部分当成关键字（比如变量intx不会被误判为int）：

// 把所有关键字拼成正则式，用\b匹配单词边界，确保匹配完整的关键字
String keywordPatternStr = "\\b(" + String.join("|", keywords) + ")\\b";
Pattern pattern = Pattern.compile(keywordPatternStr);
Matcher matcher = pattern.matcher(输入文本);

Set<String> matchedKeywords = new HashSet<>();
while(matcher.find()) {
    matchedKeywords.add(matcher.group());
}
// 输出结果...

2. 前缀树（Trie树） #

如果你的关键字数量非常多，前缀树可以高效地在文本中匹配所有关键字，适合高性能的词法分析器。它的核心是把关键字的字符按前缀组织成树结构，遍历文本时同时遍历树，快速判断是否匹配关键字。

3. 词法分析器生成工具（比如Antlr、JFlex） #

如果你是正经开发词法分析器，直接用成熟的工具更省心——这些工具可以帮你定义关键字、标识符、运算符等规则，自动生成高效的词法分析代码，不用自己手动处理字符串匹配。

内容的提问来源于stack exchange，提问作者Bry