Kanonik S-iboralar - Canonical S-expressions

A Kanonik S-ifodasi (yoki csexp) umumiy qismning ikkilik kodlash shakli S ifodasi (yoki sexp). Bu foydalanish uchun mo'ljallangan edi SPKI S-iboralar kuchini saqlab qolish va ta'minlash kanonik shakl kabi ilovalar uchun elektron raqamli imzolar ikkilik shaklning ixchamligiga erishish va tahlil tezligini maksimal darajada oshirish.

Bu erda qo'llaniladigan umumiy S-iboralarning ma'lum bir qismidan iborat atomlarbayt satrlari va ro'yxatlar yoki pastki ro'yxatlarni chegaralash uchun foydalaniladigan qavslar. Ushbu S-iboralar to'liq rekursivdir.

S-iboralar odatda matn sifatida kodlangan bo'lsa, bo'shliqlarni o'z ichiga olgan atomlarni chegaralash uchun ishlatiladigan bo'shliqlar va tirnoq belgilari bilan, har bir atomning kanonik kodlashidan foydalanilganda uzunlik prefiksli bayt qatori sifatida kodlangan. Ro'yxatdagi qo'shni elementlarni ajratib turadigan bo'shliqqa ruxsat berilmaydi. Atomning uzunligi an bilan ifodalanadi ASCII kasr sonidan keyin ":".

Misol

Jinsiy aloqa

(ushbu "Canonical S-ekspression" 5 atomdan iborat)

csexp ga aylanadi

(4: this22: Canonical S-express3: has1: 55: atomlar)

Bo'shliq belgisidan qochib qutulish uchun hech qanday tirnoq kerak emas "Canonical S-express", chunki uzunlik prefiksi aniq atom oxiriga ishora qiladi. Ro'yxatdagi keyingi elementdan atomni ajratib turadigan bo'sh joy yo'q.

Xususiyatlari

  • Kanonik kodlashning o'ziga xosligi: Ro'yxat elementlari orasida bo'sh joyni taqiqlash va atomlarni kodlashning faqat bitta usulini ta'minlash har bir S-ifodaning to'liq bitta kodlangan shaklga ega bo'lishini ta'minlaydi. Shunday qilib, ikkita S-ifodaning ularning kodlashlarini taqqoslash bilan ularning ekvivalenti to'g'risida qaror chiqarishimiz mumkin.
  • Ikkilik ma'lumotlarga yordam: Atomlar har qanday ikkilik qator bo'lishi mumkin. Shunday qilib, boshqa usulda kodlanishi kerak bo'lgan kriptografik xash qiymati yoki ochiq kalit moduli 64 yoki boshqa bosma kodlashlar uning ikkilik baytlari sifatida csexp-da ifodalanishi mumkin.
  • Kodlangan ma'lumotni teglar bilan belgilashni qo'llab-quvvatlash: Csexp tarkibiga S-ifodadan tashqari konstruktsiya, mag'lubiyatning kodlanishini ko'rsatish uchun, agar bu kodlash aniq bo'lmasa. Csexp-dagi har qanday atomning oldiga to'rtburchaklar ichida bitta atom qo'shilishi mumkin - masalan, "[4: JPEG]" yoki "[24: text / plain; charset = utf-8]".

Tafsir va cheklovlar

Csexps odatda bo'sh ro'yxatlarga, bo'sh atomlarga va boshqalarga yo'l qo'ysa-da, ba'zi bir csexps foydalanish qo'shimcha cheklovlarni keltirib chiqaradi. Masalan, ishlatilgan csexps SPKI umuman csexps bilan taqqoslaganda bitta cheklov mavjud: har bir ro'yxat atomdan boshlanishi kerak va shuning uchun bo'sh ro'yxatlar bo'lishi mumkin emas.

Odatda, ro'yxatning birinchi atomi element nomi bilan muomala qilinadi XML.

Boshqa kodlashlar bilan taqqoslash

Umumiy foydalanishda boshqa kodlashlar mavjud:

  1. XML
  2. ASN.1
  3. JSON (va YAML "JSON rasmiy pastki qism" ni o'z ichiga oladi, bu yuqori to'plam bilan, ko'proq bo'lishi kerak edi inson tomonidan tushunarli.)

Odatda, csexp-da XML yoki ASN.1-dan kattaroq kattalikdagi bir yoki ikkita o'nlik tartiblari mavjud.[iqtibos kerak ] Bu kichik o'lcham va mos keladigan tezlik[iqtibos kerak ] uning asosiy ustunligini csexp-ga bering. Ajralish ustunligidan tashqari, boshqa farqlar ham mavjud.

csexp va XML

csexp va XML farq qiladi, chunki csexp ma'lumotlar taqdim etish formati, XML esa ma'lumotlar taqdim etish formatini va shuningdek, sxema mexanizmini o'z ichiga oladi. Shunday qilib, XML ba'zi bir grammatikaga mos keladigan ma'lum ma'lumotlar turlari uchun "sozlanishi" mumkin (masalan, HTML, ATOM, SVG, MathML, yoki kerak bo'lganda yangilari). Unda hujjatlar grammatikasini aniqlash uchun tillar mavjud: DTD XML standartining o'zi tomonidan belgilanadi, ammo XSD, RelaxNG va Sxemasi qo'shimcha funktsiyalar uchun odatda XML bilan ishlatiladi va XML hech qanday sxema bilan ham ishlashi mumkin. csexp ma'lumotlari, albatta, yuqori darajada amalga oshirilgan sxemalar bilan ishlashi mumkin, ammo bunday mexanizmning o'zi yo'q.

Belgilar va baytlar nuqtai nazaridan, bir csexp "satr" har qanday bayt ketma-ketligiga ega bo'lishi mumkin (har bir atom ustidagi uzunlik prefiksi tufayli), XML esa (odatiy sxema S-ifodalari, JSON va dasturlash tilidagi harflar kabi) muqobil talab qiladi bir nechta belgilar uchun vakolatxonalar (masalan, "<" va aksariyat boshqaruv belgilar). Biroq, bu taqdim etilishi mumkin bo'lgan tuzilmalar va semantikalar doirasiga ta'sir qilmaydi. XML shuningdek, berilgan baytlar ketma-ketligini qanday izohlash uchun mo'ljallanganligini aniqlash mexanizmlarini taqdim etadi: Aytaylik, a Unicode UTF-8 ip, a JPEG fayl yoki butun son; csexp bunday farqlarni tashqi mexanizmlarga qoldiradi.

Eng asosiy darajada, ikkala csexp va XML daraxtlarni aks ettiradi (boshqa tashqi vakolatxonalar kabi). Buning ajablanarli joyi yo'q, chunki XML-ni LISP-ga o'xshash S-iboralar uchun turli xil punktuatsiya qilingan shakl yoki aksincha deb ta'riflash mumkin.[1]

Biroq, XML qo'shimcha semantikani o'z ichiga oladi, odatda tilning bir qismi sifatida emas, balki turli xil konvensiyalar bilan csexp-da erishiladi. Birinchidan, har bir XML elementining nomi bor (csexp ilovalari odatda buning uchun har bir iboraning birinchi farzandidan foydalanadi). Ikkinchidan, XML ma'lumotlar formatini, birinchi navbatda, sxema grammatikasi orqali ta'minlaydi. Shu bilan birga, sxema butun sonlarni, satrlarni, ma'lumotlar moslamalarini turlari bilan (masalan, JPEG) va (ayniqsa, XSD ) boshqa turlari).

XML elementi ham bo'lishi mumkin atributlar, csexp baham ko'rmaydigan qurilish. XML ma'lumotlarini csexp-da ko'rsatish uchun bunday atributlar uchun vakolatxonani tanlash kerak; Shubhasiz, har bir S-ifodasida ikkinchi elementni o'xshash (nomi qiymati) juftlari ro'yxati uchun zaxira qilish kerak LISP uyushma ro'yxati. XML ID va IDREF atributlarning csexp-da ekvivalenti yo'q, ammo ularni csexp dasturiy ta'minoti osongina amalga oshirishi mumkin.

Va nihoyat, XML elementida sharhlar va / yoki ishlov berish ko'rsatmalari bo'lishi mumkin. csexp-da o'ziga xos ekvivalentlar mavjud emas, lekin ularni ifodalash uchun ahamiyatsiz, shunchaki har birining nomini saqlash orqali. Masalan, ularni "* COM" va "* PI" deb nomlash ("*" har doim XML elementlari nomlari bilan to'qnashuvni oldini oladi):

 (4: * COM15: Izoh matni) (3: * PI6: target11: font = "helv")

Ikkala csexp va XML to'liq rekursivdir.

Csexp ro'yxatidagi birinchi atom, odatda, ro'yxatning "turini" aniqlashda taxminan XML element turi nomiga to'g'ri keladi. Biroq, csexp-da bu har qanday kodlashdagi har qanday atom bo'lishi mumkin (masalan, JPEG, Unicode mag'lubiyati, a WAV fayl,…), XML elementlari nomlari esa identifikator bo'lib, dasturlash tilining identifikatorlari kabi ba'zi belgilar bilan cheklangan. csexp usuli aniqroq umumiyroq; boshqa tomondan, bunday elementni nimada kodlashini va shu bilan uni qanday talqin qilishni aniqlash faqat ma'lum bir foydalanuvchi konventsiyalari bilan belgilanadi, ya'ni csexp dasturi o'zi uchun, masalan, kod, hujjat va shunga o'xshash konventsiyalarni yaratishi kerak. .

Xuddi shunday, csexp atomlari ikkilik (uzunlik prefiksidan iborat bo'lib, undan keyin o'zboshimchalik bilan) bayt), XML esa odamlar tomonidan o'qilishi uchun yaratilgan (munozarali jihatdan kamroq bo'lsa ham) JSON yoki YAML ) - shuning uchun XML-dagi o'zboshimchalik bilan baytlar qandaydir tarzda kodlanishi kerak (masalan, bitmapped rasm qo'shilishi mumkin 64 ). Bu shuni anglatadiki, o'qilmaydigan katta hajmdagi ma'lumotni siqilmagan XML-da saqlash ko'proq joy oladi; boshqa tomondan, muqobil tarjimada omon qoladi belgilar to'plamlari (shu jumladan, turli xil belgilar to'plamlari, chiziqli konvensiyalar va boshqalarni qo'llashi mumkin bo'lgan tarmoq xostlari orqali uzatish).

XML bitta element ichidagi satrlar ketma-ketligini bitta satrga "birlashtiradi", csexp esa ro'yxatdagi atomlar ketma-ketligiga imkon beradi va bu atomlar bir-biridan ajralib turadi, deb taklif qilingan; ammo bu noto'g'ri.[2] Aynan S-iboralar va csexp kabi, XMLda "satrlar" qandaydir tarzda ajratilgan taqdirdagina "qatorlar ketma-ketligi" tushunchasi mavjud:

 <s>String A</s><s>String B</s>   versus <s>String AString B</s>
 ("String A" "String B") ga qarshi ("String AString B")
 (8: String A8: String B) qarshi (16: String AString B)

csexp va boshqalar ASN.1

ASN.1 mashhur ikkilik kodlash shakli. Biroq, u semantikani emas, faqat sintaksisni (ma'lumotlar turlari) ifodalaydi. Ikkita turli xil tuzilmalar - ularning har biri ikkita INTEGERSning ketma-ketligi - simda bir xil tasvirlarga ega (ularni ajratish uchun maxsus yorliqlarni tanlashga to'sqinlik qiladi). ASN.1 tuzilishini tahlil qilish uchun tahlilchiga qanday tuzilmalar to'plamini kutayotganini aytib berish kerak va tahlilchi tuzilish parametrlari bilan tahlil qilinadigan ma'lumotlar turiga mos kelishi kerak. Bu ASN.1 ajralish dasturining murakkabligini oshiradi.

Csexp tuzilishi o'ziga xos semantikaning ba'zi bir belgilariga ega (element nomlarida kodlangan) va csexp tuzilishi uchun ajraluvchi qanday tuzilish ajralmasligiga ahamiyat bermaydi. Simli formatdagi ifoda ichki daraxt shaklida (XML DOM-ga o'xshash) tahlil qilingandan so'ng, ushbu tuzilmaning iste'molchisi uni kutilgan narsaga muvofiqligini tekshirishi mumkin. Sxemasiz XML hujjati xuddi shu kabi csexp kabi ishlaydi, XML hujjati esa ASN.1 kabi ishlashi mumkin.

Tashqi havolalar

Izohlar va ma'lumotnomalar

  1. ^ Ushbu o'xshashlik ramkachilarga ma'lum bo'lgan XML. Masalan, Steven DeRose uni muhokama qildi SGML bo'yicha savollar kitobi: SGML va XML aloqalarini tushunish, Kluwer Academic Publishers, 1997 y. ISBN  978-0-7923-9943-8.
  2. ^ The SAX XML-ga interfeys imkon beradi XML tahlilchi (bitta) matn satrlarini xohlagan tarzda sindirish. Ba'zi dasturlar[iqtibos kerak ] (noto'g'ri) bir nechta qaytarish chiziqlar bitta keng tarqalgan tugun sifatida, bu keng tarqalgan tushunmovchilikni keltirib chiqargan bo'lishi mumkin.