首页 > ACM题库 > HDU-杭电 > hdu 4659 Liveness Analysis待解决[解题报告]C++
2015
09-17

hdu 4659 Liveness Analysis待解决[解题报告]C++

Liveness Analysis

问题描述 :

A program syntax is defined as below:
PROGRAM ::= STATEMENTS end ‘\n’
STATEMENTS ::= STATEMENT STATEMENTS | epsilon
STATEMENT ::= a [variable] ‘\n’ | u [variable] ‘\n’ | IF-CLAUSE
IF-CLAUSE ::= if ‘\n’ STATEMENTS end ‘\n’ | if ‘\n’ STATEMENTS else ‘\n’ STATEMENTS end ‘\n’

In which ‘\n’ means the new line character, epsilon means an empty string, [variable] means a variable, which is represented by a number between 1 and n (inclusive). Same numbers denote the same variable.
The program runs as follows:
If the statement is "a [variable]", it assigns the variable a new value;
If the statement if "u [variable]", it uses value of the variable to do something interesting;
If there is an IF-CLAUSE, it is possible that condition of this clause is satisfied or not satisfied.

We only need to do liveness analysis on this program. This is why we do not explicitly write assigned values, what we do with the variables and condition of IF-CLAUSEs.
In this task, there are three kinds of liveness for each of the variables.
1. Live. In one or more paths of this program, value of the variable at the beginning of the program is used.
2. Dead. In all paths of this program, the variable is assigned a new value before any use of this variable.
3. Half-dead. In all paths of this program, value of the variable at the beginning of the program is not used, but in one or more paths, the variable is never assigned a new value.

输入:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line is n, number of variables in the program. The following lines is the program.

Number of lines in the input <= 500000

输出:

First line, number of test cases, T.
Following are T test cases. For each test case, the first line is n, number of variables in the program. The following lines is the program.

Number of lines in the input <= 500000

样例输入:

10
1
end
1
a 1
end
1
u 1
end
1
a 1
u 1
end
1
u 1
a 1
end
1
if
a 1
else
a 1
end
end
1
if
a 1
else
u 1
end
end
1
if
a 1
end
end
1
if
u 1
end
end
2
a 1
u 2
end

样例输出:

0
-1
1
-1
1
-1
1
0
1
-1 1