CS 345 slide 153 Spring 200522 February 2005Repetition (= Iteration = Loop) ConstructsTwo kinds of loop:• definite: iteration count is known before firstiteration• indefinite: termination condition is computed inloop’s bodyThe distinction is a historical artifact: Definite itera-tion was easy to map efficiently onto certain earlyprocessors’ architectures and instruction sets(decrement-and-test).Indefinite iteration• Test precedes body (iteration count 0)Pascal:while B do SPascal equivalent: while B do S= if B then begin S; while B do S endC equivalent:while( B ) SGCN equivalent:do B S odC for-loop:for( S0; B; S1 ) S2=S0; while( B ){ S2; S1 }CS 345 slide 154 Spring 200522 February 2005• Test follows body (iteration count 1)Pascal:repeat S until B (*indefinite iteration*)Pascal equivalent:[ repeat S until B ]= [ S; while not B do S ]C equivalent:do S while(!B)GCN equivalent:S; do ¬B S odDefinite iteration• ascendingPascal (v : integer) for v := E0 to E1 do S (*can’t assign to v in S*)compare with (v: E0 v E1: S )Pascal equivalent:v := E0;while v <= E1 do begin S; v := v + 1 end; v := C equivalent (indefinite):for( int v = E0; v <= E1; v++ ) S; v = GCN equivalent (indefinite):v := E0;do v E1 S; v := v + 1 od;v := CS 345 slide 155 Spring 200522 February 2005• for step size 1Modula–2:FOR v := E0 TO E1 BY C DO S ENDGCN equivalent:v := E0;do (C 0 v E1) (C 0 v E1) S; v := v +C od• for step size = –1Pascalfor v := E0 downto E1 do SModula–2 equivalent:FOR v := E0 TO E1 BY –1 DO S END; v := Pascal equivalent:v := E0;while v >= E1 do begin S; v := v – 1 end; v := CS 345 slide 156 Spring 200522 February 2005Guardless loops• Modula–2LOOPS0;IF E THEN EXIT END;S1ENDC:for(;;){S0;if( E ) break;S1}GCN:S0; do ¬E S1; S0 odReasoning about loopswhile E do S {¬E }Loop’s termination its guard is false.Modula–2 allows EXIT only in (guardless) LOOP.C, however, allowswhile( E ){ … break; … } {¬E ?}Using break in guarded loops breaks theabstraction.CS 345 slide 157 Spring 200522 February 2005Syntactic issues: the Semicolon Controversies• Should the semicolon be a statement separator ora statement terminator?• Should the empty statement be permitted?A (partial) statement grammar (semicolon is aseparator, empty statement not permitted):S ::= stmt | begin SL end G0| while expr do SSL ::= SL ; S | SThenbegin stmt ; stmt endcan be derived as follows:S begin SL end begin SL ; S end begin SL ; stmt end begin S ; stmt end begin stmt ; stmt endBut confusion with English usage leads to a commonprogramming mistake:begin stmt ; stmt ; stmt ; endTo “legalize” the trailing semicolon, a production wasadded:S ::= empty | stmt | begin SL end G1| while Expr do SCS 345 slide 158 Spring 200522 February 2005Now the “error” has a derivationS begin SL end begin SL ; S end begin SL ; end begin SL ; S ; end begin SL ; stmt ; end begin S ; stmt ; end begin stmt ; stmt ; endBut like many solutions, this one causes a newproblem:while expr dostmhas the same interpretation in G0 and G1, whereaswhile expr do ;stmis rejected by G0 but accepted (with presumablyunintended meaning) in G1.Pascal:• semicolons are statement separators• empty statement is permittedC:• semicolons are statement terminators• empty statement is permittedCS 345 slide 159 Spring 200522 February 2005Bothwhile x > 3 do ; (* Pascal *)x := x – 1andwhile( x > 3 );x = x - 1; /* C */are accepted, and both define infinite loops.Modula–2 solves the problem:• semicolons are statement separators• the empty statement is permitted• the compound-statement grammar is changed:S ::= empty | stmt | begin SL end G2| while Expr do SL endNow the stringswhile expr dostmtendwhile expr do ;stmt ;endhave identical meanings.Note that this solution —providing each compound-statement construct with its own end— is the sameone that solved the “dangling-else” problem (Slide23).CS 345 slide 160 Spring 200522 February 2005TypesIn HLL’s, every valid expression has a unique type.An expression’s type determines which operations areapplicable to it.Motivations:• abstraction• type checkingAbstraction provides values and operations thatare closer to the problem domain than the machine’sstorage cells and its built-in operations.HLL’s provide such types as• arrays• strings• records• lists• tuplesMost HLL’s also provide type-definition facilities suchas• enumeration• construction•
View Full Document
Unlocking...