AnewmethodfortheGotos'elimination：为消除goto的一种新方法

1、.A new method for the GOTOs eliminationDR. D.E ZEGOUR &B. ABBASSINational Computing High School, AlgiersB.P 68Oued Smar, AlgiersAbstract : - We suggest in this paper a new method of algorithms structuration. We will first show how to move from any B-algorithm (algorithm with GOTO) to an automate exp

2、ressed by its transition matrix. Then, we will show how to associate a D-algorithm ( algorithm without GOTO ) to this transition matrix. The proposed method leads to very readable algorithms and shows explicitly the semantic of the original B-algorithm compared to the existing methods.Key-words : Al

3、gorithm, Automate, Algorithm transformation.:8* Work supported by the Ministry of the research of Algiers under the research project entitled CONCORDE.1 Introduction Earlier in programming, GOTO statement was mostly used since the only control structures were the jump statement and the conditional j

4、ump. For the designers of the first programming languages, these control structures still remained and were the basis for constructing programs. In spite of the appearance of programming languages, the use of GOTOs remains incontournable.Authors are still divided in using the GOTO statement. Some of

5、 them believe that the use of GOTO is a powerful tool for constructing programs while others have criticised it. This controversy is summarized in the two following papers :Dijkstra 4 affirmed that the use of GOTO has disastrous effect and proposed to remove it from all programming languages. Knuth

6、5 showed a manner for structuring programs with the GOTO statement and argued that it could be a powerful tool if it is well used.The structuration of algorithms traces its origin to the famous theorem of Bohm and Jacopinni in 1966 who conceived, for the first time, a method which transforms any flo

7、w chart to a D-algorithm ( structured algorithm with only the control structures due to Dijkstra ). The suggested transformation is completely made on the flow chart and it is not recommended since the obtained program is much less readable.Later on, Arsac 1 proposed an other approach for eliminatin

8、g GOTOs. If the transformation of Bohm and Jaccopini is not evident to implement, the one of Arsac is easily programmable since the method is based on the resolution of equations system. however, this method is also not used because it gives a none readable program .More information on the transform

9、ation of Bohm and Jaccopini can be found in 6.In 1985, Williams and Chen 3 proceeded by identification in order to eliminate GOTOs in any Pascal program. Three schemes have been proposed. The inconvenient of this method is that the result is not guaranteed since the above transformation is not achie

10、ved when a scheme is not present.In the study of the different coalesced loops, Ramshaw 7 proposed solutions for resolving all the conflicts except the head-head conflict. Thus, he developed a method for translating programs with GOTO to ones with multilevel exits.We propose in this work a new proce

11、dure which transforms any B-algorithm to a D-algorithm. This method is completely different from the existing ones in the literature. Firstly, we construct, with a very simple manner, an automate which is expressed with its transition matrix from any B-algorithm. Secondly, we associate to this trans

12、ition matrix the corresponding D-algorithm. The paper is organized in nine sections. The next section describes the source and target languages. Then, the general algorithm and the method through an example are presented. In the section which follows, we present some common considerations for writin

13、g the proposed algorithms. Then, we give the rewriting algorithm. We find next the principle construction of the transition matrix and the algorithm which generates the D-algorithm from the transition matrix. Refinements of the proposed algorithms are finally discussed and a conclusion is given.2 So

14、urce and target languagesIn order to present this new method which consists of eliminating GOTO statements, we define two languages namely B-language and D-language. In the former, the only control structures are jump and conditional jump. In the latter, the only control structures are the While sta

15、tement and the if else statement.Any language with GOTO statement can be easily transformed to a B-language and any language with no GOTO statement can be trivially transformed to a D-language. This way, the considered languages are representatives of the two classes of languages.We give below the s

16、yntax of the B-language and the D-language in extended Backus-Naur-Form. Curly braces denote indefinite repetition (zero or more times) and square brackets denote optionality (zero or one times).We notice that the considered languages are not interpreted. Hence, the atomic actions are symbols of no

17、interpreted actions drawn for the set a, b, . Similarly, the tests are symbols from the set t1, t2, .B-language = ; * = | Label: = | |a|b| c| d.= GOTO Label= IF GOTO Label= t1|t2|t3|.The only control structures are conditional and unconditional jumps.a statement may be :- an atomic action - an condi

18、tional jump (IF GOTO)- a jump (GOTO)D-language= ; * = | | a|b|c|d|.=WHILE : ; * ENDWHILE =IF : ; * ELSE ; St* ENDIF =t1|t2|t3|.The only control structures are the alternative and the loop. A statement may be :- an atomic action - an alternative (IF THEN ELSE)- a loop (WHILE)3 The methodMain algorith

19、m For any B-algorithm we associate an automate and give its corresponding D-algorithm. Each label in the B-algorithm represents a state in the automate. Some new labels are necessary. Therefore, they are added to the B-algorithm in order to achieve the transformation. The main algorithm is the follo

20、wing:Step 1. Label the first statement. Label also any conditional jump statement contained in the B-algorithm. If several atomic actions follow each other and they are not labelled, then gather all of them in one sequence. In addition, for each state (label), associate the corresponding condition b

21、y constructing the partnership table COND between the states and the conditions.Step 2.Build the transition matrix from the B-algorithm.Step 3. Give the corresponding D-algorithm.ExampleIn order to explain the method, we suppose that each statement holds in one line. This way, we can remove semicolo

22、ns. However, the algorithms presented later on are general and are written according to the grammar of the language.Let be the following B-algorithm:abE1cdIF t1 GOTO E2xE3IF t2 GOTO E4zGOTO E1E2 rsuGOTO E3uvE4xyzStep 1 : RewritingAfter rewriting, we obtain the following algorithm :$0a, bE1c, d$1IF t

23、1 GOTO E2xE3IF t2 GOTO E4zGOTO E1E2r, s, uGOTO E3u, vE4x, y, zand the following partnership table between the states and the conditions :Step 2 : Transition matrixThe application of the step 2 gives the following transition matrix :For each state S, if the associated condition (in the partnership ta

24、ble COND) is true MAT(S, True) is considered else MAT(S, False) is considered. To consider means that the action before the symbol - is carried out, then go to the state after -.For example, if the condition associated to $1, ie T1, is false, the following statements are carried out : x ; State := E

25、3Notice also that the sequence u, v is removed, as it is not accessible.Step 3 : D-algorithmThis step consists of moving from transition matrix build above to the following D-algorithm :State is a variable. F designates the final state. Initialisation State := $0WHILE ( State # F ) : IF State = $0 :

26、 a; b; State := E1 ELSE IF State = E1 : c; d; State := $1 ELSE IF State = $1 : IF t1 : State := E2 ELSE x; State := E3 ENDIF ELSE IF State = E2 : r; s, u; State := E3 ELSE IF State = E3 : IF t2 : State := E4 ELSE z; State := E1 ENDIF ELSEIF State = E4 : x; y; z; State:=F ENDIF ENDIF ENDIF ENDIF ENDI

27、FENDIFENDWHILEIn this algorithm, we use the control structure IF THEN ELSE in succession. Each if statement corresponds to a row of the matrix. If a state have a value always true in the table COND, give simply the corresponding actions(if they exist)followed by the modification of the current state

28、. If a state has some condition t, give a choice between the two columns of the matrix according the logical value of t.For example, to row E3 of the matrix we associate the following alternative :If Cond(E3) : State := E4 Else z ; State := E1 Endif4 Common considerationsBelow, we define a statement

29、 as a couple (Label, Action). An action may be an atomic action, a GOTO statement or an IF statement.In the algorithms that follow, we shall use the following functions :Get(St) : return the next statement in St.Label(St) : return the label of the statement St, & if the statement does not have a lab

30、el. & designates the null string.Action(St) : return the action of the statement St.In addition, if the action is an IF statement, Test(St) : return the test contained in the IF statement St.We also use the function Ref(St) : which gives the label referenced by the GOTO in the statement St.Each elem

31、ent of the transition matrix is of the form a - b. a denotes a sequence of actions and b a label of the next statement. We will need also the following functions:MATa(State, Value) : denotes the action to undertake at the state State for the value ValueMATb(State, Value) : designates the label of th

32、e next action to undertake.Cond(State) : condition corresponding to the state State in the partnership table COND.5 Rewriting AlgorithmThe main idea consists of rewriting the algorithm by labelling :- the first statement (if not labelled)- any if statement- the last group of statement ( if not label

33、led)This algorithm also constructs the partnership table which associates to each label the condition if the statement is a conditional jump, and the value True otherwise.For this propose, we use :Atomic(St) : Predicate equal to True if St is an atomic action which is not labelled.Add(Label, t) : ad

34、d the condition t to the label Label in the partnership table COND.Output(Label, a): append the statement ( Label, a) to the algorithm being newly build.The algorithm is the following :i := -1Get(St) first statementIF Label(St) = & : Inc(i) ; Label := $iELSE Label := Label(St)ENIFAdd(Label, True)E :

35、= St; Get(St)WHILE Atomic(S) : E := E U St Get(St)ENDWHILEOutput(Label, E )WHILE( St # & ) : IF St is an If statement : IF Label(St) = & : Inc(i) ; Label := $i ELSE Label := Label(St) ENDIF Add(Label, Test(St) Output(Label, Action (St) ) ELSE IF St is a GOTO : Output( Label(St), Action(St) ) ELSE E

36、:= St; Get(St) WHILE Atomic(S) : E := E U St Get(St) ENDWHILE Output(Label, E ) ENDIFGet(St) the next statement ENDWHILE 6 Construction principle of the automateThe algorithm that follows constructs an automate expressed by its transition matrix, from the rewritten B-algorithm and the partnership ta

37、ble obtained in step 1. The rows of the matrix are the states( labels) and the columns are the two logical values True and False.Now, each St represents either a sequence of actions or an if statement or a GOTO statement.We use also the function Skip which ignores all the next sequences not labelled

38、. Get( St) first sequence WHILE St # & : IF St is an If Statement : MATb ( Label(St), True) := Ref(St) Get(St) IF not Label(St): IF St is not a GOTO: MATa(Label(St), False) := Action(St) Get(St) IF not Label(St) IF it is a GOTO : MATb(Label(St), False) := Ref(St) Skip ENDIF ELSE MATb( Label(St), Fal

39、se) := Label(St) St := St ENDIF ELSE MATb( Label(St), False) := Ref(St) Skip ENDIF ELSE MATb( Label(St), False) := Label(St) St := St ENDIFELSE IF St is a GOTO statement : MATb(LastLabel, True) := Ref(St) Skip ELSE MATa(Label(St), True) := Action(St) IF Label(St*) # & : MATb(Label(St), True) := Labe

40、l(St*) ENDIF Get(St) ENDIF ENDIFENDWHILESt*, being the next statement.Discussion :A statement may be an if statement, a GOTO statement or a group of statements.Case of an if statement :We may have the following cases :a) IF statement followed by a labelled statement.E:IF t GOTO GX:.In this case, we

41、put in MATbE, True the Value G and in MATbE, False the value X. b) IF statement followed by a GOTO statement.E:IF t GOTO GGOTO YIn this case, we put in MATbE, True the Value G and in MATbE, False the value Y. c) IF statement followed by a group of statements, then a labelled statement.E:IF t GOTO GG

42、roup X:.In this case, we put in MATbE, True the Value G, in MATaE, False the group of statements and in MATbE, False the value X.d) IF statement followed by a group of statements, then a GOTO statement.E:IF t GOTO GGroup of statementsGOTO YIn this case, we put in MATbE, True the Value G, in MATaE, F

43、alse the group of statements and in MATbE, False the value Y.Case of a group of statementsa) Group of statements followed by a labelled statement.X:Group of statementsY:In this case, we put in MATaE, True the group of statements and in MATbE, True the value Y.b) Group of statements followed by a non

44、 labelled statement.X:Group of statements.In this case, we put only in MATaE, True the group of statements.Case of GOTO statementa) a GOTO statement not labelled and preceded by a group of statements.X:Group of statementsGOTO GIn this case, we put in MATb X, True the label G. X being the last label

45、encountered.b) GOTO is a labelled statementX:GOTO GIn this case, we put in MATb X, True the label G. Note :This algorithm detects all the inaccessible sequences and ignores them.7 Passage from the automate to the D-algorithmFinally, we give the algorithm which builds the D-algorithm from the transit

46、ion matrix obtained in step 2 and the table COND obtained in step one. In this algorithm, we use the procedure Generate : which products a string of characters in output.Let State be a variable containing the current state. F designates the final state.Generate State := $0Generate WHILE State # F n

47、:= 1FOR each Label in COND : Generate IF State = followed by Label : IF Cond(Label) # TRUE : Generate IF +COND(St) + : Generate MATa(Label, True)+; Generate State:= followed by MATb(Label,True) Generate ELSE Generate MATa(Label, False) Generate State:= followed by MATb(Label, False) Generate ENDIF E

48、LSE Generate MATa(Label, True) IF Label is the last state in COND Generate State := F ELSE GenerateState:= followed by MATb(Label,True) ENDIF ENDIF IF Label is not the last state in COND Generate ELSE ENDIF Inc(n)ENDFORGenerate n ENDIFGenerate ENDWHILE8 RefinementsWe may represent in table COND only

49、 the conditions, i.e. we remove all the conditions with the value true.We may also write an even algorithm more readable. First we define the following function:Action (State, Condition) : unrolling the action corresponding to State, then modify the State.We have thus the simple following general al

50、gorithm :State := initial stateWHILE State is not the final state : Action( State, COND(State)ENDWHILE9 ConclusionThis work constitutes a part of project CONCORD 8 in which we made a synthesis on procedural languages. By this work, we think we have contributed to the theory of program transformation. As we have shown, the transformation is very simple compared to ones developed until now. In addition, the resulting algorithm reflects the semantic of the original B-algorithm and it is more readable compared to algorithms obtained by the other methods. On t