parsing - 构建一个具有大量标记的词法分析器

Question

我已经搜索了两个小时了，但我真的不知道该怎么办。

我正在尝试构建一个分析器，它使用可以匹配数千个单词的词法分析器。这些是自然语言单词，这就是它们如此之多的原因。

我首先以一种简单的方式进行了尝试，一个 token 只有 1000 个不同的匹配:

    TOKEN :
{
    <VIRG: ",">
|   <COORD: "et">
|   <ADVERBE: "vraiment">
|   <DET: "la">
|   <ADJECTIF: "bonne">
|   <NOM: "pomme"
        |   "émails"
        |   "émaux"
        |   "APL"
        |   "APLs"
        |   "Acide"
        |   "Acides"
        |   "Inuk"

[...]

javac编译后返回代码太大。

那么，我如何管理词法分析器中的数千个标记？

1. 我读到，为每个单词使用 n 个标记比为 n 个单词使用一个标记更有效。但在本例中，我将使用 1000 多个 token 的规则，这看起来不是一个更好的主意；

2. 我可以修改 token 管理器，或者构建一个 token 管理器，以便它只匹配列表中的单词；

3. 在这里我知道词法分析器是一个有限状态机，这就是为什么它不可能的原因，那么有没有办法使用其他词法分析器？ ;

4. 我可以自动生成一个巨大的正则表达式来匹配每个单词，但这不会让我事后独立处理这些单词，而且我不确定编写一个 60 行正则表达式是否合适好主意；

5. 也许有办法从文件加载 token ，这个解决方案非常接近解决方案 2 和 3；

6. 也许我应该使用另一种语言？我正在尝试从 XLE(它可以处理超过 70 000 个标记的词典)迁移到 java，这里有趣的是生成 java 文件!

所以在这里，我可以找到使用 javacc 词法分析器处理数千个标记的方法。如果有人习惯了这一点并且有一个想法，那就太好了？

最佳

科朗坦

Answer 1

我不知道javacc是如何构建它的DFA的，但是可以肯定的是，一个能够区分数千个单词的DFA将是相当大的。 (但绝不是大得不合理:我已经可以灵活地构建具有数十万个状态的 DFA，而不会出现重大问题。)

具有大量固定词位的词典的通常方法是使用 DFA 来识别潜在的单词(例如，字母字符序列)，然后在字典中查找该单词以获得标记类型。这也更灵活，因为您可以更新字典而无需重新编译。