~snowball-yiddish-dev/snowball-yiddish/trunk : revision 60

1

2

<HTML>

3

<HEAD>

4

<TITLE>Snowball Manual</TITLE></HEAD>

5

6

7

<H1 ALIGN=CENTER>Snowball Manual</H1>

8

9

<H2>Links to resources</H2>

10

11

<TR><TD><A HREF="../q/use.html"> Using Snowball</A>

12

<TR><TD><A HREF="../porter/stemmer.html"> Porter stemmer - a case study</A>

13

</TABLE></DL>

14

</TR>

15

16

17

18

19

<H2>Snowball definition</H2>

20

21

Snowball is a small string-handling language, and its name was chosen as a

22

tribute to SNOBOL (Farber 1964, Griswold 1968), with which it shares the

23

concept of string patterns delivering signals that are used to control the

24

flow of the program.

25

26

<H2>Data types</H2>

27

28

The basic data types handled by Snowball are strings of characters, signed

29

integers, and boolean truth values, or more simply strings, integers

30

and booleans. At present Snowball's characters are 8-bit ASCII, which is

31

sufficient for presenting the algorithms, but at some point Unicode

32

characters will need to be supported.

33

34

<H2>Names</H2>

35

36

A name in Snowball is a letter followed by zero or more letters, digits

37

and underlines. A name can be of type string, integer, boolean,

38

routine, external or grouping. All names must be declared. A

39

declaration has the form

40

<PRE>

41

Ts ( ... )

42

</PRE>

43

where symbol  <TT>T</TT>  is one of  <TT>string</TT>,  <TT>integer</TT>  etc, and the region in

44

brackets contains a list of names separated by whitespace. For example,

45

<PRE>

46

integers ( p1 p2 )

47

booleans ( Y_found )

48

49

routines (

50

shortv

51

R1 R2

52

Step_1a Step_1b Step_1c Step_2 Step_3 Step_4 Step_5a Step_5b

53

)

54

55

externals ( stem )

56

57

groupings ( v v_WXY v_LSZ )

58

</PRE>

59

<TT>p1</TT>  and  <TT>p2</TT>  are integers,  <TT>Y_found</TT>  is boolean, and so on. Snowball is quite

60

strict about the declarations, so all the names go in the same name space,

61

no name may be declared twice, all used names must be declared, no two

62

routine definitions can have the same name, etc. Names declared and

63

subsequently not used are merely reported in a warning message. A name may

64

not be one of the reserved words of Snowball.

65

66

<H2>Literals</H2>

67

68

A literal integer is a digit sequence, and is always interpreted as

69

decimal. A literal string is written between single quotes, for example,

70

<PRE>

71

'aeiouy'

72

</PRE>

73

A string may be preceded by the word  <TT>hex</TT>, in which case the contents are

74

interpreted as being written out in hexadecimal notation, e.g.

75

<PRE>

76

hex '0D0A' /* carriage return, line feed */

77

</PRE>

78

Equivalently

79

<PRE>

80

hex '0d0a' /* lower case also allowed */

81

hex '0D 0A' /* spaces ignored */

82

</PRE>

83

But  <TT>hex 'd0a'</TT>  would be an error: the number of enclosed symbols must be

84

even.

85

86

Strings may include special string macro sequences, to handle unusual

87

character combinations.

88

89

String macros may be defined in the form  <TT>stringdef m 'S'</TT>, where  <TT>'S'</TT>  is a

90

string, and  <TT>m</TT>  a sequence of one or more printing characters terminating

91

with whitespace.

92

93

Two special insert characters are defined by the directive

94

<TT>stringescapes AB</TT>, where  <TT>A</TT>  and  <TT>B</TT>  are printing characters, and  <TT>A</TT>  is not

95

single quote. (<TT>B</TT>  may equal  <TT>A</TT>, but then  <TT>A</TT>  itself can never be escaped.) For

96

example,

97

<PRE>

98

stringescapes []

99

</PRE>

100

A subsequent occurrence of the same directive redefines the insert

101

characters.

102

103

Thereafter,  <TT>[m]</TT>  inside a string causes  <TT>S</TT>  to be substituted in place of  <TT>m</TT>.

104

105

Immediately after the stringescapes directive,  <TT>[']</TT>  will substitute  <TT>'</TT>  and

106

<TT>[[]</TT>  will substitute  <TT>[</TT>, although macros  <TT>'</TT>  and  <TT>[</TT>  may subsequently be

107

redefined. A further feature is that  <TT>[W]</TT>  inside a string, where  <TT>W</TT>  is a

108

sequence of whitespace characters including one or more newlines, is

109

ignored. This enables long strings to be written over a number of lines.

110

111

For example,

112

<PRE>

113

stringescapes []

114

115

/* special Spanish characters (in ISO Latin) */

116

117

stringdef a' hex 'A0' // a-acute

118

stringdef e' hex '82' // e-acute

119

stringdef i' hex 'A1' // i-acute

120

stringdef o' hex 'A2' // o-acute

121

stringdef u' hex 'A3' // u-acute

122

stringdef u" hex '81' // u-diaeresis

123

stringdef n~ hex 'A4' // n-tilde

124

125

/* and in the next string we define all the characters in Spanish

126

used to represent vowels

127

*/

128

129

define v 'aeiou[a'][e'][i'][o'][u'][u"]'

130

</PRE>

131

<H2>Routines</H2>

132

133

A routine definition has the form

134

<PRE>

135

define R as C

136

</PRE>

137

where  <TT>R</TT>  is the routine name and  <TT>C</TT>  is a command, or bracketed group of

138

commands. So a routine is defined as a sequence of zero or more commands.

139

Snowball routines do not (at present) take parameters. For example,

140

<PRE>

141

define Step_5b as ( // this defines Step_5b

142

['l'] // three commands here: [, 'l' and ]

143

R2 'l' // two commands, R2 and 'l'

144

delete // delete is one command

145

)

146

147

define R1 as $p1 <= cursor

148

/* R1 is defined as the single command "$p1 <= cursor" */

149

</PRE>

150

A routine is called simply by using its name,  <TT>R</TT>, as a command.

151

152

<H2>Commands and signals</H2>

153

154

The flow of control in Snowball is arranged by the implicit use of

155

signals, rather than the explicit use of constructs like the  <TT>if</TT>,

156

<TT>then</TT>,  <TT>break</TT>  of C. The scheme is designed for handling strings, but is

157

perhaps easier to introduce using integers. Suppose  <TT>x</TT>,  <TT>y</TT>,  <TT>z</TT>  ... are

158

integers. The command

159

<PRE>

160

$x = 1

161

</PRE>

162

sets  <TT>x</TT>  to 1. The command

163

<PRE>

164

$x > 0

165

</PRE>

166

tests if  <TT>x</TT>  is greater than zero. Both commands give a signal t or f,

167

(true or false), but while the second command gives t if  <TT>x</TT>  is greater

168

than zero and f otherwise, the first command always gives t. In Snowball,

169

every command gives a t or f signal. A sequence of commands can be turned

170

into as a single command by putting them in a list surrounded by round

171

brackets:

172

<PRE>

173

( C1 C2 C3 ... Ci Ci+1 ... )

174

</PRE>

175

When this is obeyed,  <TT>Ci+1</TT>  will be obeyed if each of the preceding  <TT>C1</TT>  ...

176

<TT>Ci</TT>  give t, but as soon as a  <TT>Ci</TT>  gives f, the subsequent  <TT>Ci+1 Ci+2</TT>  ...

177

are ignored, and the whole sequence gives signal f. If all the  <TT>Ci</TT>  give t,

178

however, the bracketed command sequence also gives t. So,

179

<PRE>

180

$x > 0 $y = 1

181

</PRE>

182

sets  <TT>y</TT>  to 1 if  <TT>x</TT>  is greater than zero. If  <TT>x</TT>  is less than or equal to zero

183

the two commands give f.

184

185

If  <TT>C1</TT>  and  <TT>C2</TT>  are commands, we can build up the larger commands,

186

187

188

<DD>- Do  <TT>C1</TT>. If it gives t ignore  <TT>C2</TT>, otherwise do  <TT>C2</TT>. The resulting

189

signal is t if and only  <TT>C1</TT>  or  <TT>C2</TT>  gave t.

190

191

<DD>- Do  <TT>C1</TT>. If it gives f ignore  <TT>C2</TT>, otherwise do  <TT>C2</TT>. The resulting

192

signal is t if and only  <TT>C1</TT>  and  <TT>C2</TT>  gave t.

193

194

<DD>- Do  <TT>C</TT>. The resulting signal is t if  <TT>C</TT>  gave f, otherwise f.

195

196

<DD>- Do  <TT>C</TT>. The resulting signal is t whatever the signal of  <TT>C</TT>.

197

198

<DD>- Do  <TT>C</TT>. The resulting signal is f whatever the signal of  <TT>C</TT>.

199

</DL></DL>

200

So for example,

201

202

203

<DD>- sets  <TT>y</TT>  to 1 if  <TT>x</TT>  is greater than zero, otherwise to zero.

204

205

206

<DD>- sets  <TT>y</TT>  to 1 if both  <TT>x</TT>  and  <TT>z</TT>  are greater than 0, and gives t.

207

</DL></DL>

208

This last example is the same as

209

<PRE>

210

try($x > 0 $z > 0 $y = 1)

211

</PRE>

212

so that  <TT>and</TT>  seems unnecessary here. But we will see that  <TT>and</TT>  has a

213

particular significance in string commands.

214

215

When a ‘monadic’ construct like  <TT>not</TT>,  <TT>try</TT>  or  <TT>fail</TT>  is not followed by a

216

round bracket, the construct applies to the shortest following valid command.

217

So for example

218

<PRE>

219

try not $x < 1 $z > 0

220

</PRE>

221

would mean

222

<PRE>

223

try ( not ( $x < 1 ) ) $z > 0

224

</PRE>

225

because  <TT>$x < 1</TT>  is the shortest valid command following  <TT>not</TT>, and then

226

<TT>not $x < 1</TT>  is the shortest valid command following  <TT>try</TT>.

227

228

The ‘diadic’ constructs like  <TT>and</TT>  and  <TT>or</TT>  must sit in a bracketed list

229

of commands anyway, for example,

230

<PRE>

231

( C1 C2 and C3 C4 or C5 )

232

</PRE>

233

And then in this case  <TT>C2</TT>  and  <TT>C3</TT>  are connected by the  <TT>and</TT>;  <TT>C4</TT>  and  <TT>C5</TT>  are

234

connected by the  <TT>or</TT>. So

235

<PRE>

236

$x > 0 not $y > 0 or not $z > 0 $t > 0

237

</PRE>

238

means

239

<PRE>

240

$x > 0 ((not ($y > 0)) or (not ($z > 0))) $t > 0

241

</PRE>

242

<TT>and</TT>  and  <TT>or</TT>  are equally binding, and bind from left to right,

243

so  <TT>C1 or C2 and C3</TT>  means  <TT>(C1 or C2) and C3</TT>  etc.

244

245

<H2>AEs and integer commands</H2>

246

247

An AE (arithmetic expression) consists of integer names and literal

248

numbers connected by diadic  <TT>+</TT>,  <TT>-</TT>,  <TT>*</TT>  and  <TT>/</TT>, and monadic  <TT>-</TT>, with the same

249

binding powers and semantics as C. An integer command has the form

250

<PRE>

251

$X op AE

252

</PRE>

253

where  <TT>X</TT>  is an integer name and op is one of the six tests  <TT>==</TT>,  <TT>!=</TT>,  <TT>>=</TT>,  <TT>></TT>,

254

<TT><=</TT>,  <TT><</TT>, or five assignments  <TT>=</TT>,  <TT>+=</TT>,  <TT>-=</TT>,  <TT>*=</TT>,  <TT>/=</TT>. Again, the meanings are the

255

same as in C.

256

257

As well as integer names and literal numbers, the following may be used in

258

AEs:

259

260

<TR><TD><TT>minint</TT>  <TD></TD><TD> - the smallest negative number

261

<TR><TD><TT>maxint</TT>  <TD></TD><TD> - the largest positive number

262

<TR><TD><TT>sizeof s</TT>  <TD></TD><TD> - the number of characters in  <TT>s</TT>, where  <TT>s</TT>  is the name of a string

263

<TR><TD><TT>cursor</TT>  <TD></TD><TD> - the current value of the string cursor

264

<TR><TD><TT>limit</TT>  <TD></TD><TD> - the current value of the string limit

265

<TR><TD><TT>size</TT>  <TD></TD><TD> - the size of the string, in characters

266

</TABLE></DL>

267

The cursor and limit concepts are explained below.

268

269

Examples of integer commands are,

270

<PRE>

271

$p1 <= cursor // signal is f if the cursor is before position p1

272

$p1 = limit // set p1 to the string limit

273

</PRE>

274

275

<H2>String commands</H2>

276

277

If  <TT>s</TT>  is a string name, a string command has the form

278

<PRE>

279

$s C

280

</PRE>

281

where  <TT>C</TT>  is a command that operate on the string. Strings can be processed

282

left-to-right or right-to-left, but we will describe only the

283

left-to-right case for now. The string has a cursor, which we will

284

denote by c, and a limit point, or limit, which we will denote by l. c

285

advances towards l in the course of a string command, but the various

286

constructs  <TT>and</TT>,  <TT>or</TT>,  <TT>not</TT>  etc have side-effects which keep moving it

287

backwards. Initially c is at the start and l the end of the string. For

288

example,

289

<PRE>

290

'a|n|i|m|a|d|v|e|r|s|i|o|n'

291

| |

292

c l

293

</PRE>

294

c, and l, mark the boundaries between characters, and not

295

characters themselves. The characters between c and l will be denoted by

296

c:l.

297

298

If  <TT>C</TT>  gives t, the cursor c will have a new, well-defined value. But if  <TT>C</TT>

299

gives f, c is undefined. Its later value will in fact be determined by the

300

outer context of commands in which  <TT>C</TT>  came to be obeyed, not by  <TT>C</TT>  itself.

301

302

Here is a list of the commands that can be used to operate on strings.

303

304

<H4>a) Setting a value</H4>

305

306

307

<DL>

308

309

<DD>where  <TT>S</TT>  is the name of a string or a literal string. c:l is set equal

310

to  <TT>S</TT>, and l is adjusted to point to the end of the copied string. The

311

signal is t. For example,

312

<PRE>

313

$x = 'animadversion' /* literal string */

314

$y = x /* string name */

315

</PRE>

316

</DL>

317

318

<H4>b) Basic tests</H4>

319

320

<DL>

321

322

<DD>here and below,  <TT>S</TT>  is the name of a string or a literal string. If c:l

323

begins with the substring  <TT>S</TT>, c is repositioned to the end of this

324

substring, and the signal is t. Otherwise the signal is f. For example,

325

<PRE>

326

$x 'anim' /* gives t, assuming the string is 'animadversion' */

327

$x ('anim' 'ad' 'vers')

328

/* ditto */

329

330

$t = 'anim'

331

$x t /* ditto */

332

</PRE>

333

334

<DD>This is like the case for integers described above, but the extra

335

touch is that if  <TT>C1</TT>  gives f, c is set back to its old position after

336

<TT>C1</TT>  has given f and before  <TT>C2</TT>  is tried, so that the test takes place on

337

the same point in the string. So we have

338

<PRE>

339

$x ('anim' /* signal t */

340

'ation' /* signal f */

341

) or

342

( 'an' /* signal t - from the beginning */

343

)

344

</PRE>

345

<DT><TT>true</TT>,  <TT>false</TT>

346

<DD><TT>true</TT>  is a dummy command that generates signal t.  <TT>false</TT>  generates

347

signal f. They are sometimes useful for emphasis,

348

<PRE>

349

define start_off as true // nothing to do

350

define exception_list as false // put in among(...) list later

351

352

</PRE>

353

<TT>true</TT>  is equivalent to  <TT>()</TT>

354

355

<DD>And similarly c is set back to its old position after  <TT>C1</TT>  has given t

356

and before  <TT>C2</TT>  is tried. So,

357

<PRE>

358

$x 'anim' and 'an' /* signal t */

359

$x ('anim' 'an') /* signal f, since 'an' and 'ad' mis-match */

360

</PRE>

361

362

363

<DD>These are like the integer tests, with the added feature that c is set

364

back to its old position after an f signal is turned into t. So,

365

<PRE>

366

$x (not 'animation' not 'immersion')

367

/* both tests are done at the start of the string */

368

369

$x (try 'animus' try 'an'

370

'imad')

371

/* - gives t */

372

</PRE>

373

374

<TR><TD>  <TT>try C</TT>  <TD></TD><TD> is equivalent to <TD></TD><TD>  <TT>C or true</TT>

375

</TABLE></DL>

376

377

<DD>This does command  <TT>C</TT>  but without advancing c. Its signal is the same as

378

the signal of  <TT>C</TT>, but following signal t, c is set back to its old

379

value.

380

381

<TR><TD>  <TT>test C</TT>  <TD></TD><TD> is equivalent to <TD></TD><TD>  <TT>not not C</TT>

382

<TR><TD>  <TT>test C1 C2</TT>  <TD></TD><TD> is equivalent to <TD></TD><TD>  <TT>C1 and C2</TT>

383

</TABLE></DL>

384

385

<DD>This does  <TT>C</TT>  and gives signal f. It is equivalent to  <TT>C false</TT>. Like

386

<TT>false</TT>  it is useful, but only rarely.

387

388

389

<DD>This does  <TT>C</TT>, puts c back to its old value and gives signal t. It is

390

very useful as a way of suppressing the side effect of f signals and

391

cursor movement.

392

393

<TR><TD>  <TT>do C</TT>  <TD></TD><TD> is equivalent to <TD></TD><TD>  <TT>try test C</TT>

394

395

</TABLE></DL>

396

397

<DD>c is moved right until obeying  <TT>C</TT>  gives t. But if c cannot be moved

398

right because it is at l the signal is f. c is set back to the position

399

it had before the last obeying of  <TT>C</TT>, so the effect is to leave c before

400

the pattern which matched against  <TT>C</TT>.

401

<PRE>

402

$x goto 'ad' /* positions c after 'anim' */

403

$x goto 'ax' /* signal f */

404

</PRE>

405

<DT><TT>gopast C</TT>

406

<DD>Like goto, but c is not set back, so the effect is to leave c after

407

the pattern which matched against  <TT>C</TT>.

408

<PRE>

409

$x gopast 'ad' /* positions c after 'animad' */

410

</PRE>

411

<DT><TT>repeat C</TT>

412

<DD><TT>C</TT>  is repeated until it gives f. When this happens c is set back to the

413

position it had before the last repetition of  <TT>C</TT>, and  <TT>repeat C</TT>  gives

414

signal t. For example,

415

<PRE>

416

$x repeat gopast 'a' /* position c after the last 'a' */

417

</PRE>

418

419

<DD>This is like  <TT>C C ... C</TT>  written out AE times, where AE is an arithmetic

420

expression. For example,

421

<PRE>

422

$x loop 2 gopast ('a' or 'e' or 'i' or 'o' or 'u')

423

/* position c after the second vowel */

424

</PRE>

425

The equivalent expression in C has the shape,

426

<PRE>

427

{ int i;

428

int limit = AE;

429

for (i = 0; i < limit; i++) C;

430

}

431

</PRE>

432

<DT><TT>atleast AE C</TT>

433

<DD>This is equivalent to  <TT>loop AE C repeat C</TT>.

434

435

436

<DD>moves c AE character positions towards l, but if AE is negative, or if

437

there are less than AE characters between c and l the signal is f.

438

For example,

439

<PRE>

440

test hop 3

441

</PRE>

442

tests that c:l contains more than 2 characters.

443

444

445

<DD>is equivalent to  <TT>hop 1</TT>.

446

</DL>

447

448

<H4>c) Moving text about</H4>

449

450

451

We have seen in (a) that  <TT>$x = y</TT>, when  <TT>x</TT>  and  <TT>y</TT>  are strings, sets c:l of  <TT>x</TT>

452

to the value of  <TT>y</TT>. Conversely

453

<PRE>

454

$x => y

455

</PRE>

456

sets the value of  <TT>y</TT>  to the c:l region of  <TT>x</TT>.

457

458

A more delicate mechanism for pushing text around is to define a substring,

459

or slice of the string being tested. Then

460

461

<DL>

462

463

<DD>sets the left-end of the slice to c,

464

465

<DD>sets the right-end of the slice to c,

466

467

468

<DD>moves the slice to variable  <TT>s</TT>,

469

470

<DD>replaces the slice with variable (or literal)  <TT>S</TT>.

471

</DL>

472

For example

473

<PRE>

474

/* assume x holds 'animadversion' */

475

$x ( [ // '[animadversion' - [ set as indicated

476

loop 2 gopast 'a'

477

// '[anima|dversion' - c is marked by '|'

478

] // '[anima]dversion' - ] set as indicated

479

-> y // y is 'anima'

480

)

481

</PRE>

482

For any string, the slice ends should be assumed to be unset until they are

483

set with the two commands  <TT>[</TT>,  <TT>]</TT>. Thereafter the slice ends will retain

484

the same values until altered.

485

486

<DL>

487

<DT><TT>delete</TT>

488

<DD>is equivalent to  <TT><- ''</TT>

489

</DL>

490

491

This next example deletes all vowels in x,

492

<PRE>

493

define vowel ('a' or 'e' or 'i' or 'o' or 'u')

494

....

495

$ x repeat ( gopast([vowel]) delete )

496

</PRE>

497

As this example shows, the slice markers  <TT>[</TT>  and  <TT>]</TT>  often appear as

498

pairs in a bracketed style, which makes for easy reading of the Snowball

499

scripts. But it must be remembered that, unusually in a computer

500

programming language, they are not true brackets.

501

502

More simply, text can be inserted at c.

503

<DL>

504

<DT><TT>insert S</TT>

505

<DD>insert variable or literal  <TT>S</TT>  before c, moving c to the right of the

506

insert.  <TT><+</TT>  is a synonym for  <TT>insert</TT>.

507

508

<DT><TT>attach S</TT>

509

<DD>the same, but leave c at the left of the insert.

510

</DL>

511

512

<H4>d) Marks</H4>

513

514

515

The cursor, c, (and the limit, l) can be thought of as having a numeric

516

value, from zero upwards:

517

<PRE>

518

| a | n | i | m | a | d | v | e | r | s | i | o | n |

519

0 1 2 3 4 5 6 7 8 9 10 11 12 13

520

</PRE>

521

It is these numeric values of c and l which are accessible through

522

<TT>cursor</TT>  and  <TT>limit</TT>  in arithmetic expressions.

523

<DL>

524

<DT><TT>setmark X</TT>

525

<DD>sets  <TT>X</TT>  to the current value of c, where  <TT>X</TT>  is an integer variable.

526

527

<DT><TT>tomark AE</TT>

528

<DD>moves c forward to the position given by AE,

529

530

<DT><TT>atmark AE</TT>

531

<DD>tests if c is at position AE (t or f signal).

532

</DL>

533

In the case of  <TT>tomark AE</TT>, a similar fail condition occurs as with  <TT>hop AE</TT>.

534

If c is already beyond AE, or if position l is before position AE, the

535

signal is f.

536

537

In the stemming algorithms, certain regions of the word are defined by

538

setting marks, and later the failure condition of  <TT>tomark</TT>  is used to see if

539

c is inside a particular region.

540

541

Two other commands put c at l, and test if c is at l,

542

<DL>

543

<DT><TT>tolimit</TT>

544

<DD>moves c forward to l (signal t always),

545

546

<DT><TT>atlimit</TT>

547

<DD>tests if c is at l (t or f signal).

548

</DL>

549

550

<H4>e) Changing l</H4>

551

552

553

In this account of string commands we see c moving right towards l, while

554

l stays fixed at the end. In fact l can be reset to a new position between

555

c and its old position, to act as a shorter barrier for the movement of c.

556

557

<DL>

558

<DT><TT>setlimit C1 for C2</TT>

559

<DD><TT>C1</TT>  is obeyed, and if it gives f the final value of c becomes the new

560

position of l. c is then set back to its old value before  <TT>C1</TT>  was

561

obeyed, and  <TT>C2</TT>  is obeyed. Finally l is set back to its old position.

562

The signal is f if either  <TT>C1</TT>  or  <TT>C2</TT>  gives f, otherwise t.

563

For example,

564

<PRE>

565

$x ( setlimit goto 's' // 'animadver}sion' new l as marked '}'

566

for // below, '|' marks c after each goto

567

( goto 'a' and // '|animadver}sion'

568

goto 'e' and // 'animadv|er}sion'

569

goto 'i' and // 'an|imadver}sion'

570

)

571

)

572

</PRE>

573

This checks that x has characters ‘a’, ‘e’ and ‘i’ before the first

574

‘s’.

575

</DL>

576

577

<H4>f) Backward processing</H4>

578

579

String commands have been described with c to the left of l and moving

580

right. But the process can be reversed.

581

582

<DL>

583

<DT><TT>backwards C</TT>

584

<DD>c and l are swapped over, and c moves left towards l.  <TT>C</TT>  is obeyed, the

585

signal given by  <TT>C</TT>  becomes the signal of  <TT>backwards C</TT>, and c and l are

586

swapped back to their old values (except that l may have been adjusted

587

because of deletions and insertions).  <TT>C</TT>  cannot contain another

588

<TT>backwards</TT>  command.

589

590

<DT><TT>reverse C</TT>

591

<DD>A similar idea, but here c simply moves left instead of moving right,

592

with the beginning of the string as the limit, l.  <TT>C</TT>  can contain other

593

<TT>reverse</TT>  commands, but it cannot contain commands to do deletions or

594

insertions - it must be used for testing only. (Without this

595

restriction Snowball's semantics would become very untidy.)

596

</DL>

597

598

Forward and backward processing are entirely symmetric, except that forward

599

processing is the default direction, and literals strings are always

600

written out forwards, even when they are being tested backwards. So the

601

following are equivalent,

602

<PRE>

603

$x (

604

'ani' 'mad' 'version' atlimit

605

)

606

607

$x backwards (

608

'version' 'mad' 'ani' atlimit

609

)

610

</PRE>

611

If a routine is defined for backwards mode processing, it must be included

612

inside a  <TT>backwardmode(...)</TT>  declaration.

613

614

<H4>g)  <TT>substring among</TT></H4>

615

616

The use of  <TT>substring among</TT>  is central to the implementation of the

617

stemming algorithms. It is like a case switch on strings. In its simpler

618

form,

619

<PRE>

620

substring among('S1' 'S2' 'S3' ...)

621

</PRE>

622

searches for the longest matching substring  <TT>'S1'</TT>  or  <TT>'S2'</TT>  or  <TT>'S3'</TT>  ... from

623

position c. (The  <TT>'Si'</TT>  must all be different.) So this has the same

624

semantics as

625

<PRE>

626

('S1' or 'S2' or 'S3' ...)

627

</PRE>

628

- so long as the  <TT>'Si'</TT>  are written out in decreasing order of length.

629

630

<TT>substring</TT>  may be omitted, in which case it is attached to its following

631

<TT>among</TT>, so

632

<PRE>

633

among(...)

634

</PRE>

635

without a preceding  <TT>substring</TT>  is equivalent to

636

<PRE>

637

(substring among(...))

638

</PRE>

639

<TT>substring</TT>  may also be detached from its  <TT>among</TT>, although it must

640

precede it textually in the same routine in which the  <TT>among</TT>  appears.

641

The general form of  <TT>substring ... among</TT>  is,

642

<PRE>

643

substring

644

...

645

among( 'S11' 'S12' ... (C1)

646

'S21' 'S22' ... (C2)

647

...

648

649

'Sn1' 'Sn2' ... (Cn)

650

)

651

</PRE>

652

Obeying  <TT>substring</TT>  searches for a longest match among the  <TT>'Sij'</TT>. The

653

signal from  <TT>substring</TT>  is t if a match is found, otherwise f. When the

654

<TT>among</TT>  comes to be obeyed, the  <TT>Ci</TT>  corresponding to the matched  <TT>'Sij'</TT>  is

655

obeyed, and its signal becomes the signal of the  <TT>among</TT>  command.

656

657

<TT>substring/among</TT>  pairs must match up textually inside each routine

658

definition. But there is no problem with an  <TT>among</TT>  containing other

659

<TT>substring/among</TT>  pairs, and  <TT>substring</TT>  is optional before  <TT>among</TT>  anyway.

660

The essential constraint is that two  <TT>substring</TT>s must be separated by an

661

<TT>among</TT>, and each  <TT>substring</TT>  must be followed by an  <TT>among</TT>.

662

663

The effect of obeying  <TT>substring</TT>  when the preceding  <TT>among</TT>  is not obeyed

664

is undefined. This would happen for example here,

665

<PRE>

666

try($x != 617 substring)

667

among(...) // among is bypassed in the exceptional case where x == 617

668

</PRE>

669

The significance of separating the  <TT>substring</TT>  from the  <TT>among</TT>  is to allow

670

them to work in different contexts. For example,

671

<PRE>

672

setlimit tomark L for substring

673

674

among( 'S11' 'S12' ... (C1)

675

...

676

677

'Sn1' 'Sn2' ... (Cn)

678

)

679

</PRE>

680

Here the test for the longest  <TT>'Sij'</TT>  is constrained to the region between c

681

and the mark point given by integer  <TT>L</TT>. But the commands  <TT>Ci</TT>  operate outside

682

this limit. Another example is

683

<PRE>

684

reverse substring

685

686

among( 'S11' 'S12' ... (C1)

687

...

688

689

'Sn1' 'Sn2' ... (Cn)

690

)

691

</PRE>

692

The substring test is in the opposite direction in the string to the

693

direction of the commands  <TT>Ci</TT>.

694

695

The last  <TT>(Cn)</TT>  may be omitted, in which case  <TT>(true)</TT>  is assumed.

696

697

Another possible abbreviation is that when  <TT>substring</TT>  is omitted, a

698

construct such as

699

<PRE>

700

among( 'S11' 'S12' ... (C C1)

701

'S21' 'S22' ... (C C2)

702

...

703

'Sn1' 'Sn2' ... (C Cn)

704

)

705

</PRE>

706

can be written

707

<PRE>

708

among( (C)

709

'S11' 'S12' ... (C1)

710

'S21' 'S22' ... (C2)

711

...

712

'Sn1' 'Sn2' ... (Cn)

713

)

714

</PRE>

715

and this is just equivalent to

716

<PRE>

717

substring C

718

among( 'S11' 'S12' ... (C1)

719

'S21' 'S22' ... (C2)

720

...

721

'Sn1' 'Sn2' ... (Cn)

722

)

723

</PRE>

724

<H2>Booleans</H2>

725

726

<TT>set B</TT>  and  <TT>unset B</TT>  set  <TT>B</TT>  to true and false respectively, where  <TT>B</TT>  is a

727

boolean name.  <TT>B</TT>  as a command gives a signal t if it is set true, f

728

otherwise. For example,

729

<PRE>

730

booleans ( Y_found ) // declare the boolean

731

732

....

733

734

unset Y_found // unset it

735

do ( ['y'] <-'Y' set Y_found )

736

/* if c:l begins 'y' replace it by 'Y' and set Y_found */

737

738

do repeat(goto (v ['y']) <-'Y' set Y_found)

739

/* repeatedy move down the string looking for v 'y' and

740

replacing 'y' with 'Y'. Whenever the replacement takes

741

place set Y_found. v is a test for a vowel, defined as

742

a grouping (see below). */

743

744

745

/* Y_found means there are some letters Y in the string.

746

Later we can use this to trigger a conversion back to

747

lower case y. */

748

749

....

750

751

do (Y_found repeat(goto (['Y']) <- 'y')

752

</PRE>

753

<H2>Groupings</H2>

754

755

A grouping brings characters together and enables them to be looked for

756

with a single test.

757

758

If  <TT>G</TT>  is declared as a grouping, it can be defined by

759

<PRE>

760

define G G1 op G2 op G3 ...

761

</PRE>

762

where op is  <TT>+</TT>  or  <TT>-</TT>, and  <TT>G1</TT>,  <TT>G2</TT>,  <TT>G3</TT>  are literal strings, or groupings that

763

have already been defined. (There can be zero or more of these additional

764

op components). For example,

765

<PRE>

766

define capital_letter 'ABDEFGHIJKLMNOPQRSTUVWXYZ'

767

define small_letter 'abdefghijklmnopqrstuvwxyz'

768

define letter capital_letter + small_letter

769

define vowel 'aeiou' + 'AEIOU'

770

define consonant letter - vowel

771

define digit '0123456789'

772

define alphanumeric letter + digit

773

</PRE>

774

Once  <TT>G</TT>  is defined, it can be used as a command, and is equivalent to a test

775

<PRE>

776

'ch1' or 'ch2' or ...

777

</PRE>

778

where  <TT>ch1</TT>,  <TT>ch2</TT>  ... list all the characters in the grouping.

779

780

<TT>non G</TT>  is the converse test, and matches any character except the

781

characters of  <TT>G</TT>. Note that  <TT>non G</TT>  is not the same as  <TT>not G</TT>, in fact

782

<PRE>

783

non G is equivalent to (not G next)

784

</PRE>

785

<TT>non</TT>  may be optionally followed by hyphen, so one may write

786

<PRE>

787

non-vowel

788

non-digit

789

</PRE>

790

etc.

791

792

<H2>A Snowball program</H2>

793

794

795

A complete program consists of a sequence of declarations followed by a

796

sequence of definitions of groupings and routines. Routines which are

797

implicitly defined as operating on c:l from right to left must be included

798

in a  <TT>backwardmode(...)</TT>  declaration.

799

800

A Snowball program is called up via a simple

801

802

through its defined

803

externals. For example,

804

<PRE>

805

externals ( stem1 stem2 )

806

....

807

define stem1 as ( ... /* stem1 commands */ )

808

define stem2 as ( ... /* stem2 commands */ )

809

</PRE>

810

The API also allows a current string to be defined, and this becomes the

811

c:l string for the external routine to work on. Its final value is the

812

result handed back through the API.

813

814

The strings, integers and booleans are accessible from any point in the

815

program, and exist throughout the running of the Snowball program. They are

816

therefore like static declarations in C.

817

818

<H2>Comments, and other whitespace fillers</H2>

819

820

At a deeper level, a program is a sequence of tokens, interspersed with

821

whitespace. Names, reserved words, literal numbers and strings are all

822

tokens. Various symbols, made up of non-alphanumerics, are also tokens.

823

824

A name, reserved word or number is terminated by the first character that

825

cannot form part of it. A symbol is recognised as the longest sequence of

826

characters that forms a valid symbol. So  <TT>+=-</TT>  is two symbols,  <TT>+=</TT>  and

827

<TT>-</TT>, because  <TT>+=</TT>  is a valid symbol in the language while  <TT>+=-</TT>  is not.

828

Whitespace separates tokens but is otherwise ignored. This of course is

829

like C.

830

831

Anywhere that whitespace can occur, there may also occur:

832

833

(a) Comments, in the usual multi-line  <TT>/* .... */</TT>  or single line

834

<TT>// ...</TT>  format.

835

836

(b) Get directives. These are like  <TT>#include</TT>  commands in C, and have the form

837

<TT>get 'S'</TT>, where  <TT>'S'</TT>  is a literal string. For example,

838

<PRE>

839

get '/home/martin/snowball/main-hdr' // include the file contents

840

</PRE>

841

(c)  <TT>stringescapes XY</TT>  where  <TT>X</TT>  and  <TT>Y</TT>  are any two printing characters.

842

843

(d)  <TT>stringdef m 'S'</TT>  where  <TT>m</TT>  is sequence of characters not including

844

whitespace and terminated with whitespace, and  <TT>'S'</TT>  is a literal string.

845

846

847

This completes the definition of Snowball.

848

849

850

851

852

853

</TR>

854

855

856

<H2>Snowball syntax</H2>

857

<PRE>

858

859

860

<H2>Appendix 1 - Snowball syntax</H2>

861

862

<TT>||</TT>  is used for alternatives,  <TT>[X]</TT>  means that X is optional, and  <TT>[X]*</TT>

863

means that X is repreated zero or more times. meta-symbols are defined on

864

the left.  <TT><char></TT>  means any character.

865

866

The definition of literal strings does not allow for the escaping

867

conventions. The command  <TT>?</TT>  is a debugging aid.

868

869

870

<PRE>

871

<letter> ::= a || b || ... || z || A || B || ... || Z

872

<digit> ::= 0 || 1 || ... || 9

873

<name> ::= <letter> [ <letter> || <digit> || _ ]*

874

<s_name> ::= <name>

875

<i_name> ::= <name>

876

<b_name> ::= <name>

877

<r_name> ::= <name>

878

<g_name> ::= <name>

879

<hexdigit> ::= <digit> || a || b || c || d || e || f ||

880

A || B || C || D || E || F

881

<literal string>::= '[<char>]*' || hex '[<hexdigit>]*'

882

<number> ::= <digit> [ <digit> ]*

883

884

S ::= <s_name> || <literal string>

885

G ::= <g_name> || <literal string>

886

887

<declaration> ::= strings ( [<s_name>]* ) ||

888

integers ( [<i_name>]* ) ||

889

booleans ( [<b_name>]* ) ||

890

routines ( [<r_name>]* ) ||

891

externals ( [<r_name>]* ) ||

892

groupings ( [<g_name>]* )

893

894

<r_definition> ::= define <r_name> as C

895

<g_definition> ::= G || <g_definition> + G || <g_definition> - G

896

897

AE ::= (AE) ||

898

AE + AE || AE - AE || AE * AE || AE / AE || - AE ||

899

maxint || minint || cursor || limit || size ||

900

sizeof <s_name> || <i_name> || <integer>

901

902

<i_command> ::= $ <i_name> = AE ||

903

$ <i_name> += AE || $ <i_name> -= AE ||

904

$ <i_name> *= AE || $ <i_name> /= AE ||

905

$ <i_name> == AE || $ <i_name> != AE ||

906

$ <i_name> > AE || $ <i_name> >= AE ||

907

$ <i_name> < AE || $ <i_name> <= AE ||

908

909

<s_command> ::= $ <s_name> C

910

911

C ::= ( [C]* ) ||

912

<i_command> || <s_command> || C or C || C and C ||

913

not C || test C || try C || do C || fail C ||

914

goto C || gopast C || repeat C || loop AE C ||

915

atleast AE C || S || = S || insert S || attach S ||

916

<- S || delete || hop AE || next ||

917

=> <s_name> || [ || ] || -> <s_name> ||

918

setmark <i_name> || tomark AE || atmark AE ||

919

tolimit || atlimit || setlimit C for C ||

920

backwards C || reverse C ||

921

substring || among ( [<literal string> || (C)]* ) ||

922

set <b_name> || unset <b_name> || <b_name> ||

923

<r_name> || <g_name> || non [-] <g_name> ||

924

true || false || ?

925

926

P ::= [P]* || <declaration> ||

927

<r_definition> || <g_definition> ||

928

backwardmode ( P )

929

930

<program> ::= P

931

932

933

934

synonyms: <+ for insert

935

</PRE>

936

937

938

</DL>

939

</PRE>

940

</TR>

941

942

943

</TABLE>

944

</BODY>

945

</HTML>