![]() |
![]() |
![]() |
![]() |
![]() |
Algorithms in SDL
A former problem in SDL is the lack of support for writing algorithms. For pure calculations, not involving communication, the graphical form for SDL tends to become ordinary flow charts, which is usually not a good way to describe advanced algorithms. Such, often large, parts of an SDL diagram also hide other, from the SDL point-of-view, more important parts of the diagram, namely the state machine and the communication aspects.
The algorithmic extensions described here addresses these problems by introducing the possibility to write algorithms in textual form within a Task symbol, and also to define procedures and operators in textual form in text symbols. There are two major advantages with this approach, compared to ordinary SDL:
- The algorithms are written in a compact form, similar to ordinary programming languages, and will therefore not hide other important aspects of an SDL diagram.
- The language used within the algorithms contains more powerful algorithmic constructs than ordinary SDL, like if-then-else, and loop statements.
In addition, the algorithmic extensions make it possible to now define procedures and operators in textual form in text symbols in SDL/GR.
These algorithmic extensions to SDL have been approved by ITU Study Group 10 to be incorporated into the official Master List of Changes that will affect the next ITU recommendation for SDL. There are a few minor differences in the support for SDL algorithms in the SDL Suite compared with the ITU definition - these are noted in the descriptions below.
The constructs that are part of the extensions are:
- Compound Statement
- Local Variables
- If Statements
- Decision Statements
- Loop Statements
- Label Statements
- Jump Statements
- Empty Statements
Compound Statement
The basic concept in the algorithmic extensions is the compound statement. A compound statement starts with a `{', which is followed by a sequence of variable declarations and a sequence of statements, and it then ends with a `}'.
A compound statement may be used in three places:
- as the contents of a TASK,
- as the body of a procedure or operator definition in a text symbol,
- as a statement within an enclosing compound statement.
Note also that the enclosing "{ }" should not be included in a Task symbol in the SDL Editor. These braces will be added when the SDL system is converted to SDL/PR for analysis.
Contents in Task symbol in SDL/GR:
a := b+1;if (a>7) b := b+1;task {a := b+1;if (a>7) b := b+1;};A procedure in a text symbol in SDL/GR, or in SDL/PR:
procedure p fpar i integer returns integer{if (i>0)i := i+1;elsei := i-1;return i;}Local Variables
Within a compound statement it is allowed to define a number of local variables. These variables will be created when the compound statement is entered and will be destroyed when the compound statement is left. The semantics of a compound statement is very much like a procedure without parameters, which is defined and called at the place of the compound statement.
A variable declaration within a compound statement looks that same as ordinary variable declarations, except that "exported" and "revealed" are not allowed. Example:
dcla, b integer := 0,c boolean;Statements
A statement within a compound statement my be of any of the following types:
- compound statement
- output statement
- create statement
- set statement
- reset statement
- export statement
- return statement (only in procedures and operators)
- procedure call statement
- assignment statement
- if statement
- decision statement
- loop statement
- label statement
- jump statement
- empty statement
Note that each statement (and each variable declaration statement) ends with a `;'. The following statement types use the same syntax as in ordinary SDL/PR:
- output, create, set, reset, export, return, call, assignment
Example 41 : Ordinary SDL/PR statements
output s1(7) to sender;output s2(true, v1) via sr1;create p2(11);set(now+5, t);reset(t);export(v1);return a+3;call prd1(a, 10);a := a+1;
According to the ITU language definition the keyword call in a procedure call is optional. In the SDL Suite it is, however, required.
If Statements
The structure of an if statement is:
if ( <Boolean expr> )<Statement>else<Statement>where the else part is optional. The Boolean expression is first calculated. If it has the value true, the first statement is executed, otherwise the else statement, if present, is executed.
if (a>0)a := a+1;if (a=0) {a := 100;b := b+1;} else {a := a+1;b := 0;}If there are several possible if statements for an else path (the "dangling else" problem), the innermost if is always selected.
if (a>0)if (b>0)a := a+1;elsea := a-1;if (a>0) {if (b>0)a := a+1;elsea := a-1;}Decision Statements
A decision statement has much in common with the ordinary decisions found in SDL, i.e. it is a multi-branch statement. The major differences between decision statements and ordinary statements is that all paths in a decision statement ends at the enddecision.
decision (a) {(1:10) : {call p(a); a := a-5;}(<=0) : a := a+5;else : a := a-5;}The decision question and the decision answers follows the same syntax and semantics as in ordinary decisions. Following an answer there should be a statement, which might be a compound statement.
Loop Statements
A loop statement is used to repeat the execution of a statement (or usually a compound statement), a number of times. The loop is controlled by a loop variable, which either can be locally defined in the loop or defined somewhere outside of the loop.
The loop control part contains three fields:
- the loop variable indicator with a start value,
- the loop test expression,
- the new loop variable value.
for (a := 1, a<10, a+1)sum := sum+a;should be interpreted as (in C-like syntax):
a = 1;while (a<10) {sum = sum+a;a = a+1;}Note the difference between SDL and C when it comes to the variable update. In C this is a statement, in SDL it is an expression to be assigned to the variable mentioned in the loop variable indicator.
In the loop variable indicator, either a new variable can be defined or a previously defined variable can be used. Example:
for (a := 1, ...for (dcl a integer := 1, ...Other possibilities in loop statements:
- One or more of the loop control part fields can be empty. If, however the loop variable indicator (first field) is empty, then the loop variable update field (third field) must also be empty. Example:
for (a := 1, , a+1) ..for ( , , ) ...- A loop may contain several loop control parts. Example:
for (a := 1, a<10, a+1; b := 1, b<5, b+1)sum := sum+a+b;a = 1;b = 1;while ( (a<10) and (b<5) ) {sum = sum+a;a = a+1;b = b+1;}- Break statements can be used to break out of a loop. See Label Statements and Jump Statements.
- A loop statement may end with a "then" statement, which is executed if the loop is terminated because of the loop test expression becomes false. The "then" statement is not executed if the loop is terminated due to a break statement. Example:
ok := false;for (a:=1, a<10, a+1) {sum := sum+arr(a);if (sum > limit) break;}thenok := true;Label Statements
A label statement is just a label followed by a statement. These labels are only of interest if the statement following the label is a loop statement. The label name can be used in break statements (see below) to break out of a loop statement. Example:
L:for (i:=0, i<10, i+1)sum := sum+a(i);
There are no "join" or "goto" statements allowed in the algorithmic extensions to SDL.
Jump Statements
Jump statements, i.e. break and continue, are used to change the execution flow within a loop.
A continue statement, which only may occur within a loop, is defined as: "skip the remaining part of the loop body and continue with updating the loop variable to its next value."
for (a:=1, a<10, a+1) {if (sum > limit) continue;sum := sum+arr(a);}should be interpreted as (in C like syntax):
a = 1;while (a<10) {if (sum > limit) goto cont;sum = sum + arr[a];cont :a = a+1;}A break statement can be used to stop the execution of the loop and directly goto the statement after the loop.
ok := false;for (a:=1, a<10, a+1) {sum := sum+arr(a);if (sum > limit) break;}thenok := true;should be interpreted as (in C like syntax):
ok = false;a = 1;while (a<10) {sum = sum + arr[a];if (sum > limit) goto brk;a = a+1;}ok = true;brk:A break statement breaks out of the innermost loop statement. By using labeled loop statements breaks out of outer loops can be achieved.
L: for (x:=1, x<10, x+1) {a := 0;for (y:=1, y<10, y+1) {a := a+y;if (call test(x,y)) break L;}}The break statement in the inner loop breaks out from both loops as it mentions the label for the outer loop.
Empty Statements
It is allowed to have an empty statement, represented by just writing nothing. This is sometimes useful, for example as loop statement:
for (i:=1, Arr(i)/=0 and i<Limit, i+1) ;/* This loop sets i to the index of the first zeroelement in the Array Arr. */Grammar for the Algorithmic Extensions
`dcl', `)', `;' are examples of terminal symbols. <Stmt>, <Name> are examples of non-terminal symbols. ::= means defined as. $ means used for empty. * means 0 or more occurencies. + means 1 or more occurencies. | means or.Start of Grammar
<CompoundStmt> ::=`{' <VarDefStmt>* <Stmt>* `}'<VarDefStmt> ::=`dcl' <Name> (`,' <Name>)* <Sort> (`:=' <Expr> | $)( `,' <Name> (`,' <Name>)* <Sort> (`:=' <Expr> | $) )*`;'<Stmt> ::=<CompoundStmt> |<Outputx> `;' |<CreateRequest> `;' |<Setx> `;' |<Resetx> `;' |<Export> `;' |<Return> `;' |<ProcedureCall> `;' |<IfStmt> |<LabelStmt> |<AssignmentStatement> `;' |<DeciStmt> |<LoopStmt> |<JumpStmt> `;' |<EmptyStmt> `;'<IfStmt> ::=`if' `(' <Expr> `)' <Stmt> (`else' <Stmt> | $)<DecisionStmt> ::=`decision' `(' <Expr> `)' `{'( <Answer> <Stmt> )+( `else' <Stmt> | $)`}'<Answer> ::= same as answer in ordinary decisions<LoopStmt> ::=`for' `(' (<LoopClause> (`;' <LoopClause>)* | $) `)'<Stmt>(`then' <Stmt> | $)<LoopClause> ::=(<LoopVarInd> | $) `,' (<Expr> | $) `,' (<Expr> | $)<LoopVarInd> ::=`dcl' <Name> <Sort> `:=' <Expr> |<Identifier> (`:=' <Expr> | $)<LabelStmt> ::=<Label> <Stmt><JumpStmt> ::=<Break> (<Name> / $) |<Continue><EmptyStmt> ::=$End of Grammar
Algorithms in SDL Simulator/SDL Explorer
The textual trace in the SDL Simulator and the SDL Explorer for the new algorithmic extensions will be according to the table below.
IF (true) IF (false) DECISION Value: 7 LOOP variable b := 3 LOOP test TRUE LOOP test FALSE CONTINUE BREAK BREAK LoopNameA compound statement without variables declarations is seen as just a sequence of statements, while a compound statement with variable declarations is seen as a procedure call of a procedure with no name, without parameters. However, no trace information is produced for this implicit procedure call or procedure return.
When it comes to variables, these are available in the simulator interface just in the same way as if compound statements where true procedures. That is, the commands Up and Down can be used to view variables in different scopes. Note that a variable defined in a loop variable indicator introduces a scope of its own.
There is one exception of this general treatment of variables in local scopes and that is procedures defined as a compound statement.
procedure pfpar in/out a integer{dcl b integer;...}the parameter a and the variable b will be in the same scope, the procedure scope. For compound statements within the outermost procedure scope the general rules above apply.
Execution Performance in Applications
Cadvanced
All concepts in the algorithmic extensions have efficient C implementations, except variable declarations in local scopes (including in a loop variable indicator), as such compound statements will become SDL procedure calls.
Cmicro
All concepts in the algorithmic extensions have efficient C implementations. Compound statements containing variables are implemented using C block statements.
http://www.ibm.com/rational |
![]() |
![]() |
![]() |
![]() |