#XLS2502A. 赋不重名

赋不重名

题目背景

在编译器的设计中,静态单赋值形式(static single assignment form,通常简写为SSA form或是SSA)是中间表示(IR,intermediate representation)的特性,每个变量仅被赋值一次。在原始的IR中,已存在的变量可被分割成许多不同的版本,在许多教科书当中通常会将旧的变量名称加上一个下标而成为新的变量名称,以至于标明每个变量及其不同版本。在SSA,UD链(use-define chain,赋值代表define,使用变量代表use)是非常明确,而且每个仅包含单一元素。

简单来说,就是每个变量只能被赋值一次,每次赋值需要产生一个新的名字,也就是说下面的代码Code 1为了满足这个要求并且保持原有的语义就需要修改为Code 2的样子。

$$ Code1: \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad Code2: \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \\ \begin{aligned} a ~\leftarrow ~& 1 \quad \quad \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad && a_1 ~ \leftarrow ~ 1 \\ b ~\leftarrow ~& a + 5 && b_1 ~ \leftarrow ~ a_1 + 5 \\ a ~\leftarrow ~& 2 && a_2 ~ \leftarrow ~ 2 \\ c ~\leftarrow ~& a + 3 && c_1 ~ \leftarrow ~ a_2 + 3 \\ \end{aligned} $$

题目描述

tuzi233\text{tuzi233} 正在设计"D语言"的编译器,他希望中间表示是符合SSA形式的。

为此,他得到了一系列形如 “A=B” 的中间表示语句,其中A是变量名,变量名仅由小写字母组成;B是要赋的值,为了简化问题,这里的B均为不包含前导0的数字串;"="表示将A赋值为B。所有语句保证A和B都不为空。

现在请你判断这一系列语句是否是满足SSA形式的。

输入描述

第一行一个正整数 TT,表示测试数据组数。

对于每组数据,第一行输入一个正整数 nn,表示语句条数;

接下来 nn 行每行一个字符串,每个字符串都是形如 "A=B" 的形式,表示一条赋值语句。

输出描述

对于每组测试数据输出一行,如果该组语句满足SSA形式则输出 “Yes”,否则输出"No"(不包括引号)。

你可以用任意的大小写形式输出答案:"yes","YEs","nO"等都认为是正确的。

样例输入

3
1
a=1
2
a=1
a=2
3
a=100
b=100
c=101

样例输出

Yes
No
Yes

样例解释

对于第二组数据,a被赋值了两次,所以不满足SSA形式。

数据范围与约定

1T1041 \le T \le 10^41n31051 \le \sum n \le 3 * 10^5,给定字符串的长度不会超过 2020,保证字符串满足题目中所给形式。