1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
|
WORKSHEET FILE FORMAT
FROM LOTUS
APPENDIX B - THE FORMULA COMPILER
Copyright(c) 1984, Lotus Development Corporation
161 First Street
Cambridge, Massachusetts 02142
(617) 492-7171
Electronic Edition, December, 1984
All Rights Reserved
APPENDIX B: The Formula Compiler
This appendix describes the internal workings of the formula compiler. The
compiler transforms an ASCII string of characters representing a formula to
its Reverse Polish code. The basic algorithm utilizes and SR parser (SR =
shift and reduce). The aim of the parser is to apply a set of reduction
rules which embody the syntax of the compiler to an input string. Formula
code is compiled to a temporary buffer.
Lexicon Analysis
A lexical analyzer breaks up the input string into lexical units called
tokens. A token is a substring of the original input string operand,
operator, or special symbol (such as comma, parentheses, etc.) In addition,
the lexical analyser supplies two special tokens, "beginning of formula"
(boform) and "end of formula" (eoform), to facilitate the compilation
process. The lexical analyzer identifies and processes literals (both
number and string), cell and range references, operators, and function
calls. It assigns a unique code to each distinct operator, function, or
type of operand.
A function with no arguments is treated like a number.
Syntax Analysis
The syntactical analysis of a formula is accomplished by processing a list
of tokens in left-to-right order. A stack called the syntax is also used
during the syntactical scan. The basic algorithm is as follows:
Repeat the following steps:
1) Get the next token
2) If the token is a literal or cell reference:
a) Push the number code on the syntax stack
b) Push the number code on the syntax stack
3) If the token is a range reference:
a) Compile code to push the range reference
b) Push the range code on the syntax stack
4) Otherwise push the token code for the token on the syntax stack.
For each syntax rule, if the pattern on the top of the syntax matches the
rule pattern take the action associated with the rule and start scanning
from the beginning for any additional rules which may apply.
When a token code is pushed on the syntax stack, an additional word of
zeros is also pushed on the stack. This is used when compiling function
calls to hold the function's argument count.
Rule Matching
A relatively small number of rules are used to process formulas of arbitrary
complexity. If a rule matches the top of the syntax stack, then the
compiler takes a specific action and rule scanning starts again with the
first rule. Each rule matches certain patterns on the syntax stack. A
typical rule might be: if the top of the stack is the token for right
parenthesis, and the next-to-top is a number, and the second form the top
is a left parenthesis, then pop the top three items from the syntax stack
and push the number on the syntax stack.
This rule can be more succinctly represented as:
Stack
Before After Action
)
number
( number none
The Rules
The following are the syntax rules used to process formulas. Note that the
order of the rules is important. The rules for compilation of operators
used additional tables which assign a precedence number and opcode to each
legal unary and binary operator. Thus, for example, there is a single
token code for minus sign (-), but there are two opcodes one for unary
minus and one for binary minus. In addition, these two operators, while
lexically identical, also have different precedence. In general, operators
of higher precedence will be performed before operators of lower precedence
are performed left-to-right. All special operators (boform, eoform,
parentheses, comma, etc.) are implicitly assigned a precedence of zero.
Rule 1 Termination test
Stack
Before After Action
eoform Output a return code to compile buffer
number Return, indicating successful compile
boform
Rule 2 Function argument processing
Stack
Before After Action
' Error if range argument illegal for
number or range function.
( ( Increment argument count on stack
function function
Rule 3 Process final function argument
Stack
Before After Action
) Error if range argument illegal for
number or range function.
( Increment argument count on stack
function number Compile function opcode
If list function, compile argument
count; otherwise error is wrong
argument count.
Rule 4 Parenthesis removal
Stack
Before After Action
) Compile parenthesis opcode
number
( number
operator operator
Rule 5 Binary operators
Stack
Before After Action
op2 If binary op<binary op, rule does
number not match. Otherwise, compile opcode
op1 op2 for operator op1.
Rule 6 Unary operators
Stack
Before After Action
op2 I unary op<binary op, rule does
number op2 not match. Otherwise, compile opcode.
op1 number for operator op 1.
Rule 7 Error detection
Stack
Before After Action
eoform Return indicating unsuccessful compile
Table 9 Operator Precedence Table
Operator Unary Precedence Binary Precedence
+ 6 4
- 6 4
* na 5
/ na 7
^ na 3
= na 3
< > na 3
< = na 3
> = na 3
< na 3
> na 3
#and# na 1
#or# na 1
#not# 2 na
Example:
Using the above rules, we can now see how a particular formula is
compiled. Let us consider the following formula:
3+5*6
This is broken up by the lexical analyzer into seven tokens.
boform
3
+
5
*
6
eoform
The syntax scans proceed as follows until a matching rule is found:
Stack
boform number + number
boform number +
boform number
boform
Compile buffer
push 3 push 3 push 3
push 5
At this point, rule 5 is invoked, but since the precedence of boform is
zero, no action is taken.
Stack
* number
number *
+ number
number +
boform number
boform
Compile buffer
push 3 push 3
push 5 push 5
push 6
At this point, since the binary precedence of + is lower than the binary
precedence of *, rule 5 does apply, and the opcode for * is compiled. The
stack is reduced by replacing number * number by number and scan is made,
but no further rule applies.
Stack
number eoform
+ number
number +
boform number
boform
Compile buffer
push 3 push 3
push 5 push 5
push 6 push 6
Rule 5 applies again, and the opcode for + is compiled, reducing the stack
to boform, number, eoform. Rescanning finds a match on rule 1 which
compiles a return opcode and terminates. The final compiled code is thus:
push 3
push 5
push 6
*
+
return
A Note on the Decompiler
The algorithm for the formula decompiler was taken verbatim from:
Writing Interactive Compilers and Interpreters, P.J. Brown, John Wiley and
Sons, 1979. See chapter 6.2. The algorithm itself is described on pages
216 and 217.
This algorithm is also described in the following article.
More on the Re-creation of Source Code from Reverse Polish, P.J. Brown,
Software Practice and Experience, Vol 7, 545-551 (1977).
WORKSHEET COLUMN DESIGNATORS
Most records within the 1-2-3 Condensed Worksheet format are specified
with column/row designators (for example, column 0, row 0 equals A1). When
determining the column designator, the table below will help make
conversion easier.
Column Hex Dec Column Hex Dec Column Hex Dec
A 0 1 BA 34 52 DA 68 104
B 1 1 BB 35 53 DB 69 105
C 2 2 BC 36 54 DC 6A 106
D 3 3 BD 37 55 DD 6B 107
E 4 4 BE 38 56 DE 6C 108
F 5 5 BF 39 57 DF 6D 109
G 6 6 BG 3A 58 DG 6E 110
H 7 7 BH 3B 59 DH 6F 111
I 8 8 BI 3C 60 DI 70 112
J 9 9 BJ 3D 61 DJ 71 113
K A 10 BK 3E 62 DK 72 114
L B 11 BL 3F 63 DL 73 115
M C 12 BM 40 64 DM 74 116
N D 13 BN 41 65 DN 75 117
O E 14 BO 42 66 DO 76 118
P F 15 BP 43 67 DP 77 119
Q 10 16 BQ 44 68 DQ 78 120
R 11 17 BR 45 69 DR 79 121
S 12 18 BS 46 70 DS 7A 122
T 13 19 BT 47 71 DT 7B 123
U 14 20 BU 48 72 DU 7C 124
V 15 21 BV 49 73 DV 7D 125
W 16 22 BW 4A 74 DW 7E 126
X 17 23 BX 4B 75 DX 7F 127
Y 18 24 BY 4C 76 DY 80 128
Z 19 25 BZ 4D 77 DZ 81 129
AA 1A 26 CA 4E 78 EA 82 130
AB 1B 27 CB 4F 79 EB 83 131
AC 1C 28 CC 50 80 EC 84 132
AD 1D 29 CD 51 81 ED 85 133
AE 1E 30 CE 52 82 EE 86 134
AF 1F 31 CF 53 83 EF 87 135
AG 20 32 CG 54 84 EG 88 136
AH 21 33 CH 55 85 EH 89 137
AI 22 34 CI 56 86 EI 8A 138
AJ 23 35 CJ 57 87 EJ 8B 139
AK 24 36 CK 58 88 EK 8C 140
AL 25 37 CL 59 89 EL 8D 141
AM 26 38 CM 5A 90 EM 8E 142
AN 27 39 CN 5B 91 EN 8F 143
AO 28 40 CO 5C 92 EO 90 144
AP 29 41 CP 5D 93 EP 91 145
AQ 2A 42 CQ 5E 94 EQ 92 146
AR 2B 43 CR 5F 95 ER 93 147
AS 2C 44 CS 60 96 ES 94 148
AT 2D 45 CT 61 97 ET 95 149
AU 2E 46 CU 62 98 EU 96 150
AV 2F 47 CV 63 99 EV 97 151
AW 30 48 CW 64 100 EW 98 152
AX 31 49 CX 65 101 EX 99 153
AY 32 50 CY 66 102 EY 9A 154
AZ 33 51 CZ 67 103 EZ 9B 155
(CONTINUED)
Column Hex Dec Column Hex Dec
FA 9C 156 HA DO 208
FB 9D 157 HB D1 209
FC 9E 158 HC D2 210
FD 9F 159 HD D3 211
FE AO 160 HE D4 212
FF A1 161 HF D5 213
FG A2 162 HG D6 214
FH A3 163 HH D7 215
FI A4 164 HI D8 216
FJ A5 165 HJ D9 217
FK A6 166 HK DA 218
FL A7 167 HL DB 219
FM A8 168 HM DC 220
FN A9 169 HN DD 221
FO AA 170 HO DE 222
FP AB 171 HP DF 223
FQ AC 172 HQ EO 224
FR AD 173 HR E1 225
FS AE 174 HS E2 226
FT AF 175 HT E3 227
FU BO 176 HU E4 228
FV B1 177 HV E5 229
FW B2 178 HW E6 230
FX B3 179 HX E7 231
FY B4 180 HY E8 232
FZ B5 181 HZ E9 233
GA B6 182 IA EA 234
GB B7 183 IB EB 235
GC B8 184 IC EC 236
GD B9 185 ID ED 237
GE BA 186 IE EE 238
GF BB 187 IF EF 239
GG BC 188 IG FO 240
GH BD 189 IH F1 241
GI BE 190 II F2 242
GJ BF 191 IJ F3 243
GK CO 192 IK F4 244
GL C1 193 IL F5 245
GM C2 195 IM F6 246
GN C3 195 IN F7 247
GO C4 196 IO F8 248
GP C5 197 IP F9 249
GQ C6 198 IQ FA 250
GR C7 199 IR FB 251
GS C8 200 IS FC 252
GT C9 201 IT FD 253
GU CA 202 IU FE 254
GV CB 203 IV FF 255
GW CC 204
GX CD 205
GY CE 206
GZ CF 207
ANALYSIS OF 1-2-3 WORKSHEET FILE
The worksheet shown below was created in 1-2-3 and saved to disk.
Key:
A2..A5 Named Range (code 11)
EXAMPLE A2: Label (code 15)
100 A3: Integer (code 13)
12.5 A4: Number (code 14)
87.5 A5: Formula (+A3-A4)
(code 16)
The example shown below is a partial hex dump of this worksheet file. By
reading each record header, you can determine the type of record you are
encountering. The record header will also tell you the length of that
follows the header. By analyzing the record header, you can read the
records you want and skip unrelated records.
362B:0100 06 00 08 00 00 00 00 00 00 00
362B:0110 04 00 2F 00 01 00 01 02 00 01 00 FF 03 00 01 00
362B:0120 00 04 00 01 00 00 05 00 01 00 FF 07 00 1F 00 00
362B:0130 00 01 00 71 00 09 00 08 00 14 00 00 00 00 00 00
362B:0140 00 00 00 00 00 00 00 04 00 04 00 48 00 00 0B 00
362B:0150 18 00 54 45 53 54 00 00 00 00 00 00 00 00 00 00
362B:0160 00 00 00 00 01 00 00 00 04 00 18 00 19 00 00 FF
362B:0170 FF 00 00 FF FF 00 00 FF FF 00 00 FF FF 00 00 FF
362B:0180
362B:05C0
362B:05D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
362B:05E0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
362B:05F0 00 00 00 00 71 71 01 00 0F 00 0E 00 FF 00 00 01
362B:0600 00 27 45 58 41 4D 50 4C 45 00 0D 00 07 00 FF 00
362B:0610 00 02 00 64 00
362B:0620 10 00 1B 00 FF 00 00 04 00 00
362B:0630 00 00 00 00 E0 55 40 0C 00 01 00 80 FE BF 01 00
362B:0640 80 FF BF 0A 03
|
