【题解】UVA12421 (Jiandan) Mua (I) - Lexical Analyzer

ExplodingKonjac · 2023-05-23 21:12:00 · 题解

【原题链接】

提供一种实现非常简单的做法。

题目分析

题目说要贪心取最长的 token，那我们就维护一个当前位置，每次枚举所有 token 类型，看看从当前位置开始分别能匹配多长，取其中最长的。然后移动当前位置的指针。

那么怎么求匹配的长度呢？提到匹配，肯定使用正则表达式啦。

鲜为人知的是，C++11 标准提供了 regex 库，位于头文件 <regex>。里面实现了正则表达式的相关功能。

regex 库的使用可以看这里。这题中用到的主要是 std::regex 类（表示一个正则）、std::regex_search 函数（查找匹配位置）和 std::smatch 类（储存匹配结果）。

各种 token 对应的正则：

• 保留字：and|break|do|else|elseif|end|false|for|function|if|in|local|nil|not|or|repeat|return|then|true|until|while；

• 浮点数和十进制整数：([0-9]+\.[0-9]*|\.[0-9]+|[0-9]+)([eE][+-]?[0-9]+)?；

• 十六进制整数：0[xX][0-9a-fA-F]+；

• 字符串（单或双引号）："([^\\"]|\\n|\\\\|\\"|\\')*"|'([^\\']|\\n|\\\\|\\"|\\')*'；

• 运算符：\+|-|\*|/|%|\^|#|==|>=|<=|>|<|~=|\(|\)|\{|\}|\[|\]|;|:|,|\.\.\.|\.\.|\.|=；

• 标识符：[a-zA-Z_]\w*；

• 回车：\n；

• 注释和空白字符：(--[^\n]*)|\s；

• 最后，吞掉匹配不到的异常字符：.。

注意：这里可能出现一个串匹配多个模式，此时选择较靠前的匹配。另外要注意，用 | 串联多个模式串的时候，regex 库总是会有限匹配前面的（而不是最长的，比如 \.|\.\.\. 会把 ... 拆成三个 .）。

代码实现

应该是题解区最简短的。

#include <bits/stdc++.h>
using namespace std;

vector<pair<regex,function<void(string)>>> rules;

template<typename Func>
inline void addRule(const string &reg,Func f)
{
    rules.emplace_back(regex(reg),f);
}
void prework()
{
    addRule(R"(and|break|do|else|elseif|end|false|for|function|if|in|local|nil|not|or|repeat|return|then|true|until|while)",
            [](string s){ cout<<"[RESERVED] "<<s<<'\n'; });
    addRule(R"(([0-9]+\.[0-9]*|\.[0-9]+|[0-9]+)([eE][+-]?[0-9]+)?)",
            [](string s){ cout<<"[NUMBER] "<<s<<'\n'; });
    addRule(R"(0[xX][0-9a-fA-F]+)",
            [](string s){ cout<<"[NUMBER] "<<s<<'\n'; });
    addRule(R"("([^\\"]|\\n|\\\\|\\"|\\')*"|'([^\\']|\\n|\\\\|\\"|\\')*')",
            [](string s){ cout<<"[STRING] "<<s<<'\n'; });
    addRule(R"(\+|-|\*|/|%|\^|#|==|>=|<=|>|<|~=|\(|\)|\{|\}|\[|\]|;|:|,|\.\.\.|\.\.|\.|=)",
            [](string s){ cout<<"[SYMBOL] "<<s<<'\n'; });
    addRule(R"([a-zA-Z_]\w*)",
            [](string s){ cout<<"[NAME] "<<s<<'\n'; });
    addRule(R"(\n)",
            [](string s){ cout<<"[EOL]\n"; });
    addRule(R"((--[^\n]*)|\s)",
            [](string s){});
    addRule(R"(.)",
            [](string s){ cout<<"Unrecognized token "<<s<<'\n'; });
}

int main()
{
#ifndef DADALZY
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
#endif
    prework();
    string s(istreambuf_iterator<char>(cin),
             istreambuf_iterator<char>{});
    for(auto it=s.cbegin();it!=s.cend();)
    {
        function<void(string)> func;
        int len=0;
        for(auto &[reg,f]: rules)
        {
            smatch res;
            regex_search(it,s.cend(),res,reg,regex_constants::match_continuous);
            if(res.length()>len) len=res.length(),func=f;
        }
        func(string(it,it+len)),it+=len;
    }
    return 0;
}