用C++编写一个非常简单的词法分析器

Question

注意：我正在使用C++14标志进行编译... 我正在尝试在C++中创建一个非常简单的词法分析器。我正在使用正则表达式来识别不同的令牌。我的程序能够识别令牌并显示它们。但输出的格式为

int 
main
hello 
2
*
3
+
return

我希望输出的形式为：

int IDENTIFIER
hello IDENTIFIER
* OPERATOR 
3 NUMBER 
so on...........

我无法达到上述输出。

这是我的程序：

#include <iostream>
#include <string>
#include <regex>
#include <iterator>
#include <map>

using namespace std;

int main()
{
    string str = " hello how are 2 * 3 you? 123 4567867*98";

    // define list of token patterns
    map<string, string> v
    {
        {"[0-9]+" ,  "NUMBERS"} ,
        {"[a-z]+" ,  "IDENTIFIERS"},
        {"[\\*|\\+",   "OPERATORS"}
    };

    // build the final regex
    string reg = "";
    for(auto it = v.begin(); it != v.end(); it++)
        reg = reg + it->first + "|";

    // remove extra trailing "|" from above instance of reg..
    reg.pop_back();
    cout << reg << endl;

    regex re(reg);
    auto words_begin = sregex_iterator(str.begin(), str.end(), re);
    auto words_end = sregex_iterator();

    for(sregex_iterator i = words_begin; i != words_end; i++)
    {
        smatch match = *i;
        string match_str = match.str();
        cout << match_str << "\t" << endl;
    }

    return 0;
}

什么是最优的方法来完成它，并保持令牌在源程序中出现的顺序？

- kshitij singh

---

看起来你只是在寻找与你的模式匹配的内容，但没有将它们与名称关联起来，是这样吗？如果是这样的话，考虑单独搜索每个模式的整个文本，我认为这将解决你的问题。 - Jonathan H

是的，我无法将它们与名称关联起来。这完全正确。您建议的方法我之前想过，但它有两个缺点... 1）仅为不同模式搜索整个文本（假设为1000行）不是一个好主意。它是一项昂贵的操作。2）即使我搜索整个文本，标记的顺序也不会保持...输出将包含...所有标识符，然后是所有数字等等，这是不必要的。 - kshitij singh

使用一个众所周知的词法分析器（如 lex 或 flex）。你可以在大约5分钟内为所需构建一个词法分析器（并且它将更加高效）。 - Martin York

Answer 1

我只需要一次迭代来完成这个操作。你只需要在每个令牌类型的正则表达式周围添加括号，然后就可以访问这些子匹配字符串。如果一个子匹配字符串不为空，那么就意味着它被匹配到了。你知道子匹配的索引，因此也知道了v中的索引。

#include <iostream>
#include <string>
#include <regex>
#include <iterator>
#include <vector>

int main()
{
    std::string str = " hello how are 2 * 3 you? 123 4567867*98";

    // use std::vector instead, we need to have it in this order
    std::vector<std::pair<std::string, std::string>> v
    {
        {"[0-9]+" , "NUMBERS"} ,
        {"[a-z]+" , "IDENTIFIERS"},
        {"\\*|\\+", "OPERATORS"}
    };

    std::string reg;

    for(auto const& x : v)
        reg += "(" + x.first + ")|"; // parenthesize the submatches

    reg.pop_back();
    std::cout << reg << std::endl;

    std::regex re(reg, std::regex::extended); // std::regex::extended for longest match

    auto words_begin = std::sregex_iterator(str.begin(), str.end(), re);
    auto words_end = std::sregex_iterator();

    for(auto it = words_begin; it != words_end; ++it)
    {
        size_t index = 0;

        for( ; index < it->size(); ++index)
            if(!it->str(index + 1).empty()) // determine which submatch was matched
                break;

        std::cout << it->str() << "\t" << v[index].second << std::endl;
    }

    return 0;
}

std::regex re(reg, std::regex::extended);用于匹配最长的字符串，这对于词法分析器非常重要。否则它可能将while1213识别为while和数字1213，并且取决于您为正则表达式定义的顺序。

- LogicStuff

Answer 2

这是一个快速且简单粗暴的解决方案，它会迭代每个模式，并尝试匹配整个字符串，然后迭代匹配结果，并将每个匹配位置和名称存储在映射中。映射会根据键（位置）隐式地对匹配结果进行排序，因此您只需要迭代映射即可按位置顺序获取匹配结果，而无需考虑它们的模式名称。

#include <iterator>
#include <iostream>
#include <string>
#include <regex>
#include <list>
#include <map>

using namespace std;

int main(){

    string str = " hello how are 2 * 3 you? 123 4567867*98";

    // define list of patterns
    map<string,string> patterns {
        { "[0-9]+" ,   "NUMBERS" },
        { "[a-z]+" ,   "IDENTIFIERS" },
        { "\\*|\\+",  "OPERATORS" }
    };

    // storage for results
    map< size_t, pair<string,string> > matches;

    for ( auto pat = patterns.begin(); pat != patterns.end(); ++pat )
    {
        regex r(pat->first);
        auto words_begin = sregex_iterator( str.begin(), str.end(), r );
        auto words_end   = sregex_iterator();

        for ( auto it = words_begin; it != words_end; ++it )
            matches[ it->position() ] = make_pair( it->str(), pat->second );
    }

    for ( auto match = matches.begin(); match != matches.end(); ++match )
        cout<< match->second.first << " " << match->second.second << endl;
}

输出：

hello IDENTIFIERS
how IDENTIFIERS
are IDENTIFIERS
2 NUMBERS
* OPERATORS
3 NUMBERS
you IDENTIFIERS
123 NUMBERS
4567867 NUMBERS
* OPERATORS
98 NUMBERS

- Jonathan H

---

这个确实可以解决问题，但是我想学习的是最有效的做法，因为在这里我们还需要为每个模式迭代整个文本。希望你能理解。我只是想学习。 - kshitij singh

@erip 我找到了另一种解决方案，你可能会有兴趣。 - LogicStuff

这正是我在寻找的，您能否详细解释一下？那会对我非常有帮助。 - kshitij singh

请在我的回答下留言，您需要了解什么特别的内容？ - LogicStuff

这是一个不错的实验，可以检查哪个答案具有最佳性能。 - Elvis Teixeira