1 条题解

  • 0
    @ 2025-8-24 21:38:28

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar fanypcd
    For the Union.

    搬运于2025-08-24 21:38:28，当前版本为作者最后更新于2021-07-26 22:43:41，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    P2509 [SCOI2008]警告 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

    写在前面的话

    第一篇 c++ 题解。

    见过真正恶心的模拟题吗，这道就是了。（我贡献了 4 页提交记录（我敲 勇 的。

    这可以为你以后的开发工作打（提）下（前）基（劝）础（退）

    总之题目就是想让你实现一个简单的编译器，支持输出未定义的变量和不可到达的行两种警告。

    对于这道题，我只想说它不仅考验了一个 OIer 的代（心）码（理）能（素）力（质），还有你的代码习惯，特别是模块化编程的思想（如果有人能在一个 main 里面搞完我就佛了）。

    几个坑点

    先放前面，以便调题自闭的人来康康：

    1. 如果 IF 中两个分支均定义了某个变量，那么这个变量在 IF 后也算定义了（分支中 RETURN 则算所有变量都定义过）
    2. 如果一个 IF 的两个条件分支都 RETURN，这个 IF 后的语句作废
    3. ELSE & END IF 不算 unreachable line
    4. RETURN 后即使有变量未初始化也不考虑了
    5. 一行内一个变量最多算一次未定义

    题目做法

    读入

    我们先定义一个 get(i, pos) 函数，表示从读入的代码文本中第 i 行第 pos 列开始连续的一段文本，返回值为 string 。（显然一个连续文本段的前后都是不合法字符（如空格）。）

    可以这样实现：

    bool check(char x)
{
	if((x >= 'A' && x <= 'Z') || (x >= '0' && x <= '9') || (x == '+' || x == '-' || x == '*' || x == '/') || (x == '>' || x == '<' || x == '='))
	{
		return 1;
	}
	return 0;
}
string get(int i, int &pos)
{
	int num = (pos ? 0 : 1);//这里是因为 0 位置前面也得算作一个不合法位
	string ret;
	for(; pos < s[i].size(); pos++)
	{
		if(check(s[i][pos]))
		{
			ret.push_back(s[i][pos]);
		}
		else
		{
			if(++num == 2)
			{
				break;
			}
		}
	}
	return ret;
}

    这样我们调用一次 get 就可以得到连续的一段文本了，便于后续的处理。

    然后我们分别考虑处理每一种语句。

    因为变量最多有 26 个（ A - Z ），我们可以用一个整型的每一个二进制位表示对应的变量出现情况。

    令函数 work(i, j, defined) 对文本段中行数为 [i,j][i,j]​ （包含 i 和 j ），且之前的变量定义状态为 defined 的文本进行处理。函数的返回值（ int ）表示在函数中定义过的变量（如果处理的这一段必定 RETURN 返回 0x7fffffff ）。

    现在只需要考虑分别处理：

    • PARAM
    • IF THEN & ELSE & END IF & 条件判断语句
    • 赋值语句
    • RETURN

    处理 PARAM 语句

    PARAM 语句后的变量在全局均要算作已初始化，所以逐个读入所有变量，修改 defined 对应位即可。

    if(newword == "PARAM")
{
    for(; pos < s[idx].size(); )
    {
        newword = get(idx, pos);
        if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
        {
            defined |= (1 << (newword[0] - 'A'));
        }
    }
}

    其中：idx 表示遍历到的行号，pos 表示当前行枚举到的位置。

    这是最好处理的语句了。

    处理 IF 语句 & 条件判断语句

    这是最难的语句，需要 72 行 1425 长度。

    IF 语句可不能直接处理完就跳过，因为坑点 1 所以我们需要处理到这个 IF 对应的 END IF 为止。

    并且如果中间有 ELSE 还要特殊处理条件分支中定义的变量（或者 RETURN 标记（坑点 2 ））。

    定义 shownshown 中逐位保存条件分支中定义的变量（ RETURN 标记记在 27 位，因为只有 26 个单词（其实 26 位也可以，因为从 0 开始））

    shownshown​ 初值设置为 0xffffffff 即二进制下每一位都是 1 （因为要做 & 运算）。

    然后对于每个分支，shown &= work(···)​（如果只有一个条件分支，shown = 0xffffffff ）。

    至于怎么判断这个 IF 对应的 ELSE 和 END IF 位置，相信敢来写这题的都知道 stack 是什么吧。

    else if(newword == "IF")
{
    int vis = 0;//这里 vis 是记录 IF 后的条件判断语句中未定义变量的出现次数，至多 1 次。
    for(; pos < s[idx].size(); )
    {
        newword = get(idx, pos);
        if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
        {
            if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
            {
                E[++cnt].id = newword[0];
                E[cnt].line = idx;
                E[cnt].opt = 2;
                vis |= (1 << (newword[0] - 'A'));
            }
        }
    }
    int i, wz, flag = 0;
    string nw;
    stack<int> st;
    st.push(idx);
    for(i = idx + 1; i <= r && !st.empty(); i++)
    {
        wz = 0;
        nw = get(i, wz);
        if(nw == "IF")
        {
            st.push(i);
        }
        else if(nw == "ELSE" && st.size() == 1)
        {
            flag = i;
            if(shown == 0xffffffff)
            {
                shown = work(st.top() + 1, i - 1, defined);
            }
            else
            {
                shown &= work(st.top() + 1, i - 1, defined);
            }
        }
        else if(nw == "END")
        {
            st.pop();
        }
    }
    if(flag)
    {
        shown &= work(flag + 1, i - 2, defined);
    }
    else
    {
        shown = 0xffffffff;
        work(idx + 1, i - 2, defined);
    }
    idx = i - 1;
    if((shown & (1 << 27)) && shown != 0xffffffff)//如果所有条件分支必定 RETURN，则后面语句 unreachable
    {
        idx++;
        for(; idx <= r; idx++)
        {
            wz = 0;
            nw = get(idx, wz);
            if(nw != "ELSE" && nw != "END")
            {
                E[++cnt].line = idx;
                E[cnt].opt = 1;
            }
        }
        shown = 0x7fffffff;//这时视为所有变量都已定义过
    }
}

    处理赋值语句

    赋值语句其实很好处理，有一个坑点就是作为左值的变量如果在右值中出现，视为未定义，如 C = C + 1 。

    注意要判断文本长度一定为 1，然后就差不多了。

    else if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
{
    int vis = 0;
    char mem = newword[0];
    for(; pos < s[idx].size(); )
    {
        newword = get(idx, pos);
        if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
        {
            if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
            {
                E[++cnt].id = newword[0];
                E[cnt].line = idx;
                E[cnt].opt = 2;
                vis |= (1 << (newword[0] - 'A'));
            }
        }
    }
    defined |= (1 << (mem - 'A'));//最后将左值变量记为已定义
}

    处理 RETURN 语句

    到了这里刚才定义 work 的 [l,r][l,r]​ 的好处就凸显出来了，RETURN 语句至多只能影响到 r 行。

    遇见 RETURN，首先判断返回值（是变量的话）是否定义，然后将语句后面的全部输出警告。

    else if(newword == "RETURN")
{
    int vis = 0;
    for(; pos < s[idx].size(); )
    {
        newword = get(idx, pos);
        if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
        {
            if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
            {
                E[++cnt].id = newword[0];
                E[cnt].line = idx;
                E[cnt].opt = 2;
                vis |= (1 << (newword[0] - 'A'));
            }
        }
    }
    int wz;
    string nw;
    idx++;
    for(; idx <= r; idx++)
    {
        wz = 0;
        nw = get(idx, wz);
        if(nw != "ELSE" && nw != "END")
        {
            E[++cnt].line = idx;
            E[cnt].opt = 1;
        }
    }
    shown = 0x7fffffff;
}

    对于 defined 的更新

    每次处理完一块语句后，如果 shown != 0xffffffff 则 defined |= shown。

    if(shown != 0xffffffff)
{
    defined |= shown;
}

    Code：

    #include<bits/stdc++.h>
using namespace std;
struct error
{
	int opt, line;
	char id;
};
error E[10005];
bool cmp(error a, error b)
{
	if(a.line != b.line)
	{
		return a.line < b.line;
	}
	return a.id < b.id;
}
int tot, cnt;
string s[10005];
bool check(char x)
{
	if((x >= 'A' && x <= 'Z') || (x >= '0' && x <= '9') || (x == '+' || x == '-' || x == '*' || x == '/') || (x == '>' || x == '<' || x == '='))
	{
		return 1;
	}
	return 0;
}
string get(int i, int &pos)
{
	int num = (pos ? 0 : 1);
	string ret;
	for(; pos < s[i].size(); pos++)
	{
		if(check(s[i][pos]))
		{
			ret.push_back(s[i][pos]);
		}
		else
		{
			if(++num == 2)
			{
				break;
			}
		}
	}
	return ret;
}
int work(int l, int r, int defined)
{
	int pos, shown = 0xffffffff;
	string newword;
	for(int idx = l; idx <= r; idx++)
	{
		pos = 0;
		newword = get(idx, pos);
		if(newword == "PARAM")
		{
			for(; pos < s[idx].size(); )
			{
				newword = get(idx, pos);
				if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
				{
					defined |= (1 << (newword[0] - 'A'));
				}
            }
		}
		else if(newword == "IF")
		{
			int vis = 0;
			for(; pos < s[idx].size(); )
			{
				newword = get(idx, pos);
				if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
				{
					if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
					{
						E[++cnt].id = newword[0];
						E[cnt].line = idx;
						E[cnt].opt = 2;
						vis |= (1 << (newword[0] - 'A'));
					}
				}
			}
			int i, wz, flag = 0;
			string nw;
			stack<int> st;
			st.push(idx);
			for(i = idx + 1; i <= r && !st.empty(); i++)
			{
				wz = 0;
				nw = get(i, wz);
				if(nw == "IF")
				{
					st.push(i);
				}
				else if(nw == "ELSE" && st.size() == 1)
				{
					flag = i;
					if(shown == 0xffffffff)
					{
						shown = work(st.top() + 1, i - 1, defined);
					}
					else
					{
						shown &= work(st.top() + 1, i - 1, defined);
					}
				}
				else if(nw == "END")
				{
					st.pop();
				}
			}
			if(flag)
			{
				shown &= work(flag + 1, i - 2, defined);
			}
			else
			{
				shown = 0xffffffff;
				work(idx + 1, i - 2, defined);
			}
			idx = i - 1;
			if((shown & (1 << 27)) && shown != 0xffffffff)
			{
				idx++;
				for(; idx <= r; idx++)
				{
					wz = 0;
					nw = get(idx, wz);
					if(nw != "ELSE" && nw != "END")
					{
						E[++cnt].line = idx;
						E[cnt].opt = 1;
					}
				}
				shown = 0x7fffffff;
			}
		}
		else if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
		{
			int vis = 0;
			char mem = newword[0];
			for(; pos < s[idx].size(); )
			{
				newword = get(idx, pos);
				if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
				{
					if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
					{
						E[++cnt].id = newword[0];
						E[cnt].line = idx;
						E[cnt].opt = 2;
						vis |= (1 << (newword[0] - 'A'));
					}
				}
			}
			defined |= (1 << (mem - 'A'));
		}
		else if(newword == "RETURN")
		{
			int vis = 0;
			for(; pos < s[idx].size(); )
			{
				newword = get(idx, pos);
				if(newword.size() == 1 && newword[0] >= 'A' && newword[0] <= 'Z')
				{
					if(!(defined & (1 << (newword[0] - 'A'))) && !(vis & (1 << (newword[0] - 'A'))))
					{
						E[++cnt].id = newword[0];
						E[cnt].line = idx;
						E[cnt].opt = 2;
						vis |= (1 << (newword[0] - 'A'));
					}
				}
			}
			int wz;
			string nw;
			idx++;
			for(; idx <= r; idx++)
			{
				wz = 0;
				nw = get(idx, wz);
				if(nw != "ELSE" && nw != "END")
				{
					E[++cnt].line = idx;
					E[cnt].opt = 1;
				}
			}
			shown = 0x7fffffff;
		}
		if(shown != 0xffffffff)
		{
			defined |= shown;
		}
		//printf("!!%d %d %d %d!!\n", l, r, shown, defined);
	}
	return defined;
}
signed main()
{
	while(getline(cin, s[++tot]));
	work(1, tot - 1, 0);
	sort(E + 1, E + cnt + 1, cmp);
	for(int i = 1; i <= cnt; i++)
	{
		if(E[i].opt == 1)
		{
			printf("Line %d: unreachable code\n", E[i].line);
		}
		else if(E[i].opt == 2)
		{
			printf("Line %d: variable %c might not have been initialized\n", E[i].line, E[i].id);
		}
	}
	return 0;
}

    彩蛋

    在校内 OJ 上 A 了这道题后，我终于可以看见我老师的神仙代码了，我写 4.21k 他写 1.87k

    % 就完了。

    #include <algorithm>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
 
int n, poz;
vector<string> code;
 
void output(int s, int v) {
  if(s & (1 << 26)) return;
  for(int i = 0; i < 26; i++) if(!(s & (1 << i)) && (v & (1 << i)))
    printf("Line %d: variable %c might not have been initialized\n",poz + 1,'A' + i);
}
 
int readValue(const string &s) {
  char c = s[0];
  if(isupper(c)) return 1 << (c - 'A');
  else return 1 << 27;
}
 
int parseArgs(const string &s) {
  istringstream is(s);
  string s2;
  is >> s2;
  int v = 0;
  for(;;) {
    is >> s2;
    if(!is) break;
    v |= 1 << (s2[0] - 'A');
  }
  return v;
}
 
int go(int s) {
  for(;;) {
    if(poz >= n) return s;
    istringstream is(code[poz]);
    string com; is >> com;
    if(com == "END" || com == "ELSE") return s;
    if(s & (1 << 26))
      printf("Line %d: unreachable code\n", poz + 1);
    if(com == "RETURN") {
      string s2; is >> s2;
      int v = readValue(s2);
      output(s,v);
      s |= (1 << 30) - 1;
      ++poz;
    }
    else if(com == "IF") {
      string s2; is >> s2;
      int v = readValue(s2);
      is >> s2; is >> s2;
      v |= readValue(s2);
      output(s,v);
      ++poz;
      int then1 = go(s);
      int else1 = 0;
      istringstream is2(code[poz]);
      is2 >> s2; ++poz;
      if(s2=="ELSE") {
        else1 = go(s);
        ++poz;
      }
      s |= then1 & else1;
    }
    else { // assigment
      int left = readValue(com);
      string s2; is >> s2;
      is >> s2;
      int v = readValue(s2);
      is >> s2;
      if(is){
        is >> s2;
        v |= readValue(s2);
      }
      output(s, v);
      s |= left;
      ++poz;
    }
  }
  return -1;
}
 
int main() {
	char line[100];
	while(fgets(line, 100, stdin) != NULL)
		code.push_back(line);
    n = code.size();
    int v = parseArgs(code[0]);
    poz = 1;
    go(v | (1<<27));
	return 0;
}
    • 1

    [SCOI2008] 警告

    信息

    ID
    1548
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 20ms