DIRECTORY Rope; CodeB: CEDAR DEFINITIONS = { StringNotInLanguage: ERROR [s: ROPE, L: Language]; ROPE: TYPE = Rope.ROPE; CreateCode: PROC [membership: Membership, y, f: CHAR, q: SubstitutionFunction] RETURNS [code: Code]; Membership: TYPE = ARRAY CHAR OF Alphabet; Alphabet: TYPE = {S0, S1, S2, None}; SubstitutionFunction: TYPE = ARRAY CHAR OF ROPE; Language: TYPE = {Ll, Ls, Lm}; Code: TYPE = REF CodePrivate; CodePrivate: TYPE; Encode: PROC [code: Code, sl: ROPE] RETURNS [ss: ROPE]; Decode: PROC [code: Code, ss: ROPE] RETURNS [sl: ROPE]; Lowercase: PROC [r: ROPE] RETURNS [lr: ROPE]; }. ฐCodeB.Mesa Copyright c 1986 by Xerox Corporation. All rights reserved. Spreitzer, January 20, 1986 2:18:03 pm PST What's going on We are concerned with establishing a 1-to-1 association between the strings of two languages. One language, call it Ll, consists of all the finite non-empty sequences of characters from some alphabet S0. The other language, call it Ls, consists of all the finite non-empty sequences of characters drawn from S1 (where S1 G S0) that begin with a character from S2 (S2 G S1). We want some restrictions on the association. We want the association to basically have the form of a bunch of (literal) pattern replacements --- that is, where pattern a appears in the string in Ll, pattern b appears in the string in Ls, for a bunch of client-specified a and b. The technique used is as follows. Ignore for the moment the restriction on the initial character of a string in Ls --- we'll translate from Ll to Lm, where Lm = S1+, then make a seperate step from Lm to Ls. For getting from Ll to Lm, we restrict the a's to be single characters. Identify in S1 an "escape character" y. Define a substitution function q, which associates with every character c in S0- (where S0- = S0-S1) a unique string b in S1-+ (where S1- = S1-{y}, and + means a non-empty finite string thereof). Let B be the range of q. The relation is as follows: ync in a string in Ll maps to y2n+1b in Lm when c B S0- and q(c)=b. ynb maps to y2nb when b B B and to ynb otherwise; b must contain only characters from S1-. To translate sm (in Lm) to ss (in Ls), pick another escape character (call it f), this time from S2. Scan sm and find the first character (call it d) that's not f. If you run out of string, or if d B S2, then ss = sm; otherwise ss = fsm. Now we do it precisely. Given S2 G S1 G S0 y B S1, f B S2 q: S0- f B Where S0- = S0 - S1 S1- = S1 - {y} Ll = S0+ Lm = S1+ Ls = S2 S1* B G S1-+ B has the prefix property: A b1, b2 B B : b1 = b2 g n IsPrefix(b1, b2) N is the non-negative integers e is the empty string Define Code(ss, sl) W E sm B Lm , Shrink(sm, sl) & Initialize(ss, sm) Shrink(sm, sl) W if sm=e & sl=e then true else if E n B N, c B S0-, slr B S0* , sl = yncslr then E smr B Lm , sm = y2n+1q(c)smr & Shrink(smr, slr) else if E n B N, b B B, slr B S0* , sl = ynbslr then E smr B Lm , sm = y2nbsmr & Shrink(smr, slr) else if E n B N, b B S1-*, slr B S0* , sl = ynbslr & Best(b, slr) then E smr B Lm , sm = ynbsmr & Shrink(smr, slr) else false Best(b, slr) {means b is as long as it can be} W slr=e V b=e & E slrr B Ll , slr = yslrr V E c B S0-, slrr B Ll , slr = cslrr Initialize(ss, sm) W Verboten(sm) & ss=fsm V nVerboten(sm) & ss=sm Verboten(s) = E n B N, c B S1 - S2, sr B S1* , s = fncsr Auf Cedar สโ– "cedar" style˜code™ Kšœ ฯmœ1™šœก œก œ™Mš œก œกœœก œกœ ™šœœœกœœก ขœก œœก ขœœก œกขก ™1Mš œœก œœ œœก œกขกœกœก œœก œก œ™6—šœœœกœœกœก œœก ขœœก œกขก ™/Mšœœก œœ œœก œกขก œœก œก œ™1—š'œœœกœœก ขœก œœก ขœœก œกขก œœกœก œ™AMšœœก œœ œœก œกขก œœก œก œ™0—M™ —š œกœก œ กœ™0Mšก œก™Mšœกกœœœก œœ œœก œก ™!Mšœœกœœก ขœก œœ œœก œก ™$—šœ ก œก œ™Mšœ ก œœก œก œœœ ก œœก œก ™-—Mš"œ กœœœกœœก œก œก œœก ขœœกœกขก ™8——™ Kš œžœกœžœกœ ˜2K˜Kšžœžœžœ˜K˜Kšฯn œžœกœกœžœกœžœ˜dK˜Kš œ žœžœžœžœ ˜*Kš œ žœก œก œก œ˜$Kš œžœžœžœžœžœ˜0Kš œ žœ œ œ œ˜K˜Kšœžœžœ ˜Kšœ žœ˜K˜Kšฃœžœก œžœžœก œžœ˜7Kšฃœžœก œžœžœก œžœ˜7K˜Kš ฃ œžœžœžœžœ˜-K˜—K˜——…—Z์