43158
|
1 |
theory Def_Ass imports Vars Com
|
|
2 |
begin
|
|
3 |
|
|
4 |
subsection "Definite Assignment Analysis"
|
|
5 |
|
45212
|
6 |
inductive D :: "vname set \<Rightarrow> com \<Rightarrow> vname set \<Rightarrow> bool" where
|
43158
|
7 |
Skip: "D A SKIP A" |
|
|
8 |
Assign: "vars a \<subseteq> A \<Longrightarrow> D A (x ::= a) (insert x A)" |
|
|
9 |
Semi: "\<lbrakk> D A\<^isub>1 c\<^isub>1 A\<^isub>2; D A\<^isub>2 c\<^isub>2 A\<^isub>3 \<rbrakk> \<Longrightarrow> D A\<^isub>1 (c\<^isub>1; c\<^isub>2) A\<^isub>3" |
|
|
10 |
If: "\<lbrakk> vars b \<subseteq> A; D A c\<^isub>1 A\<^isub>1; D A c\<^isub>2 A\<^isub>2 \<rbrakk> \<Longrightarrow>
|
|
11 |
D A (IF b THEN c\<^isub>1 ELSE c\<^isub>2) (A\<^isub>1 Int A\<^isub>2)" |
|
|
12 |
While: "\<lbrakk> vars b \<subseteq> A; D A c A' \<rbrakk> \<Longrightarrow> D A (WHILE b DO c) A"
|
|
13 |
|
|
14 |
inductive_cases [elim!]:
|
|
15 |
"D A SKIP A'"
|
|
16 |
"D A (x ::= a) A'"
|
|
17 |
"D A (c1;c2) A'"
|
|
18 |
"D A (IF b THEN c1 ELSE c2) A'"
|
|
19 |
"D A (WHILE b DO c) A'"
|
|
20 |
|
|
21 |
lemma D_incr:
|
|
22 |
"D A c A' \<Longrightarrow> A \<subseteq> A'"
|
|
23 |
by (induct rule: D.induct) auto
|
|
24 |
|
|
25 |
end
|