Vykdomąjį Semantinis Apibrėžimas Programavimo Kalbų, Naudojant Dviejų lygių Gramatikos (Van Wijngaarden Gramatikų)

Originalus pagal Steven Pemberton – https://homepages.cwi.nl/~steven/vw.html

Abstraktus

Tai buvo seniai žinoma, kad Dviejų lygių Gramatikos (taip pat žinomas kaip Van Wijngaarden Gramatikos) gali būti naudojami ne tik siekiant nustatyti, sintaksės, bet ir semantika programavimo kalbas. Čia mes suteikiame greitas įvadas į gramatikos ir kaip jie gali būti naudojami siekiant nustatyti, semantika programavimo kalba, ir tada pateikti būdas, kad tos sąvokos vykdomąjį.

Vieno Lygio VW Gramatikų

1VWG tai yra notational variantas BNF: naudoti ‘:’ vietoj ‘::=’, o ne ‘;’ ar ne  ‘|’, naudoti ‘< ’arba‘>’, bet ir suteikti terminaluose, kurių pavadinimas baigiasi “simbolis”, atskiros sąvokos (terminalai arba nonterminals) ‘,’, pabaigos taisykles ‘.’.
Pvz.

<vwg> ::= <rule> | <rule> <vwg>

dabar skaito

vwg: rule; vwg, rule.

Čia yra poilsio 1VWG struktūra:

rule: notion, colon symbol, alternatives, stop symbol.
 alternatives: alternative option; alternative option, semicolon symbol, alternatives.
 alternative option: alternative; empty.
 alternative: notion; notion, comma symbol, alternative.
 empty: .
 notion: letter; letter, notion.
 letter: letter a symbol; letter b symbol; ... ; letter z symbol.

Toks apibrėžimas yra taip pat pridedamas sąrašas “atstovybės” simboliai.

Dviejų lygių VW Gramatikų

A 2VWG gali būti laikomas ‘parameterised’ 1VWG. Formalūs parametrai, išreikšti raidės ir skaitmenys, kurių leidžiamas vertes, yra apibrėžti antra, aplinkybės-nemokamai, gramatika. Pakeisti vertes, šių parametrų suteikia 1VWG, kuri vėliau gali būti panaudota, siekiant generuoti stygos įprasta tvarka.

Formalus parametras vadinamas ‘metanotion’, ir yra apibrėžta ‘metarule’:

THING:: letter; rule.

A parameterized taisyklė vadinama ‘hyper taisyklė’:

THING list: THING; THING, THING list.

Esminiai proceso pakeitimo vadinamas ‘Vienodas Pakeitimo’, arba ‘Atitinka Pakeitimo’: pvz., metanotion turi būti nuolat keičiama į hyperrule.

Todėl pirmiau hyper taisyklė stovi dvi taisykles:

letter list: letter; letter, letter list.
 rule list: rule; rule, rule list.

Tai yra tipiškas naudoti hyper taisykles, susitraukimai. Procesą galima apibendrinti, naudojant metanotion, kad efektyviai gamina ‘sąvoka’:

NOTION:: L; L NOTION.
 L:: a; b; c; d; e; f; g; h; i; j; k; l; m; n; o; p; q; r; s; t; u; v; x; y; z.

tada bendras susitraukimai gali būti užrašyta taip:

NOTION list: NOTION; NOTION, NOTION list.
 NOTION option: NOTION; .

kt. Atkreipkite dėmesį, kad šie stovėti už neapribotą skaičius taisyklės. Taip pat atkreipkite dėmesį, kad nuoseklus pakaitinis taikoma tik hyper taisykles, o ne meta taisyklės.
‘SĄVOKA sąrašą’, būtų buvę galima buvo apibrėžta, kaip tai:

NOTION list: NOTION, NOTION list option.

Kartais reikia apeiti nuosekliai pakeitimo. Yra konvencija, kad jeigu vienas ar daugiau skaitmenų turi būti pridedami prie metanotion, pavyzdžiui M1 (nors kai kurie žmonės naudoja primes kaip M′) teigiama, kad egzistuoja metarule M1::M. (Tai iš tikrųjų daro juos tris lygio gramatikos). Pavyzdžiui, naudojant skaitmenis:

NOTION1 separated NOTION2 sequence: NOTION2;
 NOTION2, NOTION1 symbol, NOTION1 separated NOTION2 sequence.

Naudojant šiuos meta taisykles, dabar mes galime nustatyti 1 VWG:

vwg: rule list.
 rule: notion, colon symbol, semicolon separated alternative sequence, stop symbol.
 alternative: comma separated notion sequence option.
 notion: letter list.
 letter: letter L symbol.

Atminkite, kad kaip ir su bet aplinkybės nemokamai gramatikos, jūs turite saugokitės kurti dviprasmiškas meta taisyklės. Jei jūs apibrėžta:

optional NOTION: NOTION; EMPTY.
 NOTION list: EMPTY; NOTION, NOTION list.

tada jums nežinome, ar ‘neprivalomų taisyklių sąrašą’ buvo neprivaloma taisyklių sąrašą, arba sąrašą neprivalomų taisyklių.

Metanotions gali būti naudojamas daugiau nei susitraukimai. Čia yra pavyzdys, gaminantis an bncn, gerai žinomas už tai, kad ne aplinkybės-nemokamai:

N:: ZERO; iN.
 ZERO:: .
 aNi: aN, letter a symbol.
 a ZERO: .
 bNi: bN, letter b symbol.
 b ZERO: .
 cNi: cN, letter c symbol.
 c ZERO: .
 anbncn: aN, bN, cN.

Tai gali būti trumpinamas:

N:: ;iN.
 A:: a; b; c.
 ANi: AN, letter A symbol.
 A: .
 anbncn: aN, bN, cN.

Atkreipkite dėmesį, kad šis pavyzdys rodo, kodėl metarules naudoti ‘::’ ir ne tik ‘:’.

Galutinis tipiškas naudoti metanotions yra už vadinamosios ‘teiginiais’, kuri yra metodas, kuris riboja arba bandymų vertės ypač metanotion į hyperrule. Jei ‘pasiseks’, jis sukuria tuščią sub-string, jei ne jis gamina ‘blind alley’, kuri negali būti suderinta su bet hyperrule, ir todėl nėra naudojamos jokios papildomos gamybos procese. Gana dirbtinis pavyzdys:

anbncn: aN1, bN2, cN3, where N1 is N2, where N2 is N3.
 where N is N: .

tai atitinka taisyklę pateiktas aukščiau.

Naudojant VWG Apibrėžti Semantika Programavimo Kalbos

Kadangi jūs galite imituoti Turingo mašina su VWG [van Wijngaarden], tai galima nustatyti visus programavimo kalba, įskaitant jos run-time semantika, su VWG.

Didele kliūtimi automatiškai generuoti taisykles iš VWG yra tradicinis naudotis nemokama metanotions, hyperrules, metanotions, kad atsiranda dešinėje pusėje hyperrule, bet ne dėl jos kairėje pusėje. Pavyzdžiui, tai galėtų būti:

print EXPRESSION: evaluate EXPRESSION giving VALUE, represent VALUE.

Tai sukelia problema, net žmogaus skaitytojas, nes VALUE turi būti sumąstė iš mėlynos, kuris atitinka reikiamą hyperrules. Kartais formuluotė taisyklė siūlo galimą plėtrą (nors, žinoma, tai yra ne padėti į mechaninė generatorius), bet dažnai procesui reikia daug darbo ir backtracking. Programa galėtų susidoroti su tokios konstrukcijos, bet tik ne per brangiai kainuoja laiko, nes jis turėtų išvardyti kiekvieną plėtra nemokamai metanotion, norėdami pamatyti, jei ji tinka, (ir, žinoma, tai negali ir, iš tiesų, paprastai nebūtų, nutraukti).

Tokiu būdu VWG apibrėžimo kalba, būti vykdomąjį, nors būdą turi būti naudojamas, kad būtų išvengta nemokamai metanotions, hyperrules.

Semantinio Apibrėžimas Programavimo Kalba

Idėja čia pateikti duomenys yra apibrėžti VWG kurių pradėti sąvoka yra transliteruota programos versiją, kuri generuoja eilutę simbolių, atstovaujančių produkcijos, kad programa. Pavyzdžiui, ABC programa [ABC],

PUT 1 IN a
WRITE a

būtų parašyta

put digit i number in letter a tag write letter a tag

ir gramatikos būtų gaminti nuo šio pradžios sąvoka

digit one symbol

Programa turi būti transliteruojama tai būdas išvengti susidūrimų tarp žodžius ir sąvokas, gramatikos. Kitaip įvertinti, kokį poveikį

PUT ainbputb IN a

Gramatikos čia pateikta, dėl akivaizdžių priežasčių, yra tik labai paprasta kalba ir rodo principus, ir daug darbo, reikėjo visą apibrėžimas.

Apibrėžimas

Pradėti sąvoka turi atitikti šiuos hyperrule:

COMMANDS: execute COMMANDS in memory.

Tai bus pradėti vykdymo procesą į tuščią ‘atminties’, kuris bus naudojamas surengti vertės kintamųjų. Tai turi kelias metarules:

COMMANDS:: EMPTY; COMMAND COMMANDS.
EMPTY::.
COMMAND:: put EXPR in TARGET;
 write EXPR;
 if TEST indent COMMANDS outdent;
 while TEST indent COMMANDS outdent.

Taigi, mes tik bus apibrėžti įdėti, rašyti, jei ir nors komandos.

EXPR:: TERM; TERM plus EXPR.
TERM:: FACT; FACT times TERM.
FACT:: NUMBER; TAG.
TEST:: EXPR COMP EXPR.
COMP:: lt; le; eq; ne; ge; gt.
TARGET:: TAG.

Išraiškos bus tik to ir dauginimo; bandymai palyginti, ir rodiklių (kintamųjų) paprasta žymes. Atkreipkite dėmesį, kad teisę rekursija taisykles, reglamentuojančias raiškos neturi semantinio efektas, kaip jį būtų BNF gramatika: metarules yra naudojami tik siekiant nustatyti leistinas stygos metanotions, ir kaip jie, kad yra nesvarbus.

NUMBER:: DIGIT number; DIGIT NUMBER.
TAG:: LETTER tag; LETTER TAG.
DIGIT:: digit D.
LETTER:: letter L.
D:: ZERO; i; ii; iii; iiii; iiiii; iiiii i; iiiii ii; iiiii iii; iiiii iiii.
L:: a; b; c; d; e; f; g; h; i; j; k; l; m; n; o; p; q; r; s; t; u; v; w; x; y; z.

(Atkreipkite dėmesį, kad be paleidimo taisyklės, mes turime tik apibrėžta meta taisykles iki dabar).

Įdėti Komandą

Dabar apibrėžimo procesas atskiriant pirmąją COMMAND iš COMMANDS vykdo (arba keičia) ir tada vykdo COMMANDS. Mums pirmiausia apsvarstyti įdėti komandą:

execute put EXPR in TARGET COMMANDS in memory VARS: ....

Dabar, pradedant taisyklė mums davė virš sukurta programa tuščią atminties, tačiau, žinoma, įdėti komandą apskritai dirba ne vienas tuščias. Leiskite mums nustatyti atmintis:

VARS:: EMPTY; VAR VARS.
VAR:: var TAG has VALUE.
VALUE:: ZERO; iVALUE.

Taigi VAR yra mapping iš žymos TAG o VALUE, šiame mažas kalba yra ne neigiamas sveikasis skaičius. VALUE, tikslas mūsų taisyklė įdėti komandą, bus pakeisti EXPR į VALUE, ir pakeisti VARS atminties taip, kad joje kartografavimo iš žymeklį vertę.

Įsivaizduokime akimirkai, kad mes turime rašytinių taisyklių, kurios transformuoja

execute put EXPR in TARGET COMMANDS in memory VARS

prie

execute put VALUE in TARGET COMMANDS in memory VARS

(atkreipkite dėmesį, kad VALUE yra ne EXPR). Tada mes turime dvi galimybes:

  1. VARS jau yra TAG , kad yra TARGET, tokiu atveju mes turime pakeisti savo vertę, arba
  2. VARS nėra TAG , tokiu atveju turime įdėkite ją ir jos vertę.

Ačiū, kad nuosekliai pakeitimo, pirmasis iš jų yra lengviau nustatyti:

execute put VALUE1 in TAG COMMANDS in memory VARS1 var TAG has VALUE2 VARS2:
 execute COMMANDS in memory VARS1 var TAG has VALUE1 VARS2.

Įdėti komandą baigtas: mes gali vykdyti šias komandas atminties kai tik pakeitimai yra nauja verte TAG; nieko nepasikeitė.

Tuo atveju, jei tai yra pirmą naudojimą TAG, reikia ratu:

execute put VALUE in TAG COMMANDS in memory VARS:
 where TAG not in VARS,
 execute COMMANDS in memory VARS var TAG has VALUE.

Ratu darbai tikrinami kiekvienos TAG atminties paeiliui:

where TAG1 not in var TAG2 has VALUE VARS2:
 where TAG1 differs from TAG2, where TAG1 not in VARS2.

kol jis išbandė juos visus:

where TAG not in EMPTY: where true.
where true: .

Tikrinti, kad dvi žymas, yra įvairių būdų, tą patį metodą, bandymai kiekvieną raidę paeiliui, kol dvi raidės, kurios neatitinka rasti:

where LETTER1 TAG1 differs from LETTER2 TAG2:
 where LETTER1 differs from LETTER2;
 where LETTER1 is LETTER2, where TAG1 differs from TAG2.

arba iki tol, kol jis suprato, kad jie buvo iš skirtingų ilgių:

where EMPTY tag differs from TAG: where true.
where TAG differs from EMPTY tag: where true.

Apibendrinti ‘kur yra …’ buvo vartojamas čia:

where ANY is ANY: where true.
ANY:: EMPTY; NOTION.

Tyrimai, jei dvi raidės yra skirtingos yra pasiektas bandymų, jei abėcėlė yra raidės:

where letter L1 differs from letter L2:
 where L1 precedes L2 in abcdefghijklmnopqrstuvwxyz;
 where L2 precedes L1 in abcdefghijklmnopqrstuvwxyz.
where L1 precedes L2 in ANY1 L1 ANY2 L2 ANY3: where true.

Šis apibrėžimas ‘skiriasi nuo’ bus apibendrinti kiek vėliau.

Vertinant Raiškos

Dabar apibrėžti transformacijos EXPR į VALUE. Mes galime apibrėžti vertinimo išraiškų tik atsižvelgdamas įdėti komandas. Tačiau netrukus turime juos vertinti kituose kontekstuose, ir, be to, jie turės tą pačią semantiką ten. Taigi apskritai metodas bus naudinga. Tai bus daroma įterpiant žodelius gamybos nurodant išraiškas, kurios turėtų būti įvertinti:

execute put EXPR in TARGET COMMANDS in memory VARS:
 execute put evaluate EXPR close in TARGET COMMANDS in memory VARS.

Tiek pradžioje ir pabaigoje išraiška, turi būti pažymėtos, nes paprastai tokie žymekliai bus sudėliota. Nuo šiol mes ignoruoti tos aplinkybės, kad išraiška yra vertinami.

Įvertinti išraiška, kuriuose naudotojas, mes pirmiausia įvertinti operands:

ANY1 evaluate EXPR plus TERM close ANY2:
ANY1 evaluate evaluate EXPR close plus evaluate TERM close close ANY2.
ANY1 evaluate TERM times FACT close ANY2:
ANY1 evaluate evaluate TERM close times evaluate FACT close close ANY2.

(Griežtai kalbant, šis pristatomas dviprasmiškumo, nors ir nekalta vienas, nes nei į kairę, arba į dešinę operandas gali būti vertinami pirmą kartą. Norint tai įveikti, taip stiliaus taisyklės gali būti naudojamos:

ANY1 evaluate EXPR plus TERM close ANY2:
     ANY1 evaluate evaluate EXPR close plus TERM close ANY2.
ANY1 evaluate VALUE plus TERM close ANY2:
     ANY1 evaluate VALUE plus evaluate TERM close close ANY2.

)

Dabar mes esame palikti su žemiausio lygio raiškos įvertinti: žymos ir numeriai. Įvertinti žymę mes tik žemėlapis tai, kad jos vertė atmintis:

ANY1 evaluate TAG close ANY2 in memory VARS1 var TAG has VALUE VARS2:
 ANY1 VALUE ANY2 in memory VARS1 var TAG has VALUE VARS2.

Jei žymeklis yra ne atminties ši taisyklė netaikoma, nei visi kiti, reiškia, kad programa yra neapibrėžta.
Vertinant numeriai bus atidėtas iki tol, kol mes turime apibrėžti daugyba ir be to. Užtenka pasakyti dabar, kad jis transformuojasi NUMERĮ į atitinkamą VALUE.

Tą patį metodą, įstatyti žymekliai gali būti naudojami rengiant daugiau sudėtingų kintamųjų, tada mes turime apibrėžti šią paprastą kalbą.

Operatoriai

Ankstesniame skyriuje jau transformuota išraiškas į klaustuku porų vertybes, vertybes, atskirti ‘plius’ arba ‘laikas’. Nuo sveikųjų skaičių į bazę, viena yra naudoti, be to, yra nereikšmingas, nes jis gali būti pasiektas ryšis:

ANY1 evaluate VALUE1 plus VALUE2 close ANY2: ANY1 VALUE1 VALUE2 ANY2.

Daugybos yra pasiekti su pakartotinis papildymas:

ANY1 evaluate VALUE1i times VALUE2 close ANY2:
 ANY1 evaluate evaluate VALUE1 times VALUE2 close plus VALUE2 close ANY2.
ANY1 evaluate ZERO times VALUE close ANY2: ANY1 ZERO ANY2.

Tai yra pasakyti (a*b) = (((a-1)*b)+b), ir (0*b)=0. Dabar galime apibrėžti vertinimo Numeriai:

ANY1 evaluate DIGITS digit D number close ANY2:
 ANY1 evaluate evaluate evaluate DIGITS number close
 times iiiii iiiii close plus D close ANY2.
ANY1 evaluate digit D number close ANY2: ANY1 D ANY2.

Trumpai tariant, pirmoji taisyklė sako

(ND)=(((N)*10)+D)

Jis naudoja naują, jei akivaizdu, metarule:

DIGITS:: DIGIT; DIGIT DIGITS.

Rašyti Komandas

Parašyti komandą vertina savo laisvę, ir gamina atstovavimas gautas skaičius:

execute write EXPR COMMANDS in memory VARS:
 execute write evaluate EXPR close COMMANDS in memory VARS.
execute write VALUE COMMANDS in memory VARS:
 repr VALUE, execute COMMANDS in memory VARS.

Atstovavimas skaičius yra tradicinis VWG ratą:

TEN:: iiiiiiiiii.
VALUE1 repr TEN VALUE2: VALUE1i repr VALUE2.
VALUEi repr D: repr VALUEi, repr D.
repr D: digit D symbol.

Tai gali būti vertinama kaip lygiavertė tokią funkciją:

repr(v1, v2)=
 if v2>=10: return repr(v1+1, v2-10)
 if v1>=1 and v2 in {0..9}: return repr(0, v1) ++ repr(0, v2)
 if v1=0 and v2 in {0..9}: return convert-to-text(v2)

Jei Komandos

Tai yra gana tiesiai į priekį. TEST vertinamas, ir COMMANDS įvykdytas atitinkamai:

execute if TEST indent COMMANDS1 outdent COMMANDS2 in memory VARS:
 execute if test TEST close indent COMMANDS1 outdent COMMANDS2 in memory VARS.

Bandymai TEST bus arba yield sėkmės ar nesėkmės.

Darant prielaidą, apibrėžimas bandymai TEST egzistuoja, jei bandymas bus sėkmingas, mes vykdyti kontroliuojamos komandas, tada vėlesnės. Jeigu bandymas bus nesėkmingas, tik šios komandos yra įvykdyti:

execute if success indent COMMANDS1 outdent COMMANDS2 in memory VARS:
 execute COMMANDS1 COMMANDS2 in memory VARS.
execute if failure indent COMMANDS1 outdent COMMANDS2 in memory VARS:
 execute COMMANDS2 in memory VARS.

Dabar mes galime nustatyti bandymai TEST:

ANY1 test EXPR1 COMP EXPR2 close ANY2:
 ANY1 test evaluate EXPR1 close COMP evaluate EXPR2 close close ANY2.

ir palyginimo operatoriai:

ANY1 test VALUE eq VALUE close ANY2: ANY1 success ANY2.
ANY1 test VALUE1 eq VALUE2 close ANY2:
 where VALUE1 differs from VALUE2, ANY1 failure ANY2.

Šis poreikius ‘skiriasi nuo’ bendrųjų:

where L1 NOTION1 differs from L2 NOTION2:
 where L1 differs from L2;
 where L1 is L2, where NOTION1 differs from NOTION2.
where L1 differs from L2:
 where L1 precedes L2 in abcdefghijklmnopqrstuvwxyz;
 where L2 precedes L1 in abcdefghijklmnopqrstuvwxyz.

Sąvokos ‘ne’ – tai paliekama skaitytojui. Čia yra požymių, kad:

ANY1 test VALUE1 VALUE2 ge VALUE2 close ANY2: ANY1 success ANY2.
ANY1 test VALUE1 ge VALUE1i VALUE2 close ANY2: ANY1 failure ANY2.
ANY1 test VALUE1 le VALUE2 close ANY2: ANY1 test VALUE2 ge VALUE1 close ANY2.
ANY1 test VALUE1 lt VALUE2 close ANY2: ANY1 test VALUE1i le VALUE2 close ANY2.
ANY1 test VALUE1 gt VALUE2 close ANY2: ANY1 test VALUE2 lt VALUE1 close ANY2.

Pridedant KITAS dalis, JEI komanda yra trivialus ir palikti skaitytojui.

Nors Komandos

Galiausiai, mes nustatyti, o komandą:

execute while TEST indent COMMANDS1 outdent COMMANDS2 in memory VARS:
 execute if TEST indent COMMANDS1
 while TEST indent COMMANDS1 outdent
 outdent COMMANDS2 in memory VARS.

Lengva.

Galutinį Žingsnis

Vienas kitas dalykas, dar reikia apibrėžti, ir kad tai, kas atsitinka, kai programos pabaigoje bus pasiektas:

execute EMPTY in memory VARS: EMPTY.

Pavyzdys

Duoti trumpą pavyzdys pažangos sąvoka per šias taisykles, leiskite mums pažvelgti į originalą pavyzdyje. Kiekvienoje eilutėje rodoma viena transformacijos:

put digit i number in letter a tag write letter a tag
execute put digit i number in letter a tag write letter a tag in memory
execute put evaluate digit i number close in letter a tag write letter a tag in memory
execute put i in letter a tag write letter a tag in memory
where letter a tag not in , execute write letter a tag in memory var letter a tag has i
where true, execute write letter a tag in memory var letter a tag has i
execute write letter a tag in memory var letter a tag has i
execute write evaluate letter a tag close in memory var letter a tag has i
execute write i in memory var letter a tag has i
repr i, execute in memory var letter a tag has i
digit i symbol, execute in memory var letter a tag has i
digit i symbol

Poilsio Programavimo Kalba

Daug dalių kalba nėra apibrėžta paprasta kalba, aukščiau, yra tik daugiau tos pačios. Neigiami skaičiai, atimtis, dalyba ir taip yra tik kiekybiniai skirtumai, kaip ir kitų tipų reikšmes, kaip eilutes, matricos. Didelė komplikacijų sukelia funkcijas, ir daugiau sudėtingų kintamųjų. Kai kurie sprendimai yra piešė čia.

Visi kintamieji sudėtingesnis nei, žyma, žyma, jų šaknis. Taigi masyvo atrankos gali būti atstovaujama kaip pora (TARGET, VALUE).

Skambinimo funkcijos, galima padaryti skiriant formalius parametrus ir tada vykdančioji funkcija komandos. Grįžti yra pakeičiant vertės, už likusią kūno funkcija.

Mechaninė Kartos Stygos iš VWG

Dick Grune [Grune] kažkada seniai parašė programa, vos per 1000 eilučių C, kad mano (riboto naudojimo) dvi lygio gramatikos ir pradėti sąvoka, ir spausdinamos visos stygos, gautos iš kurios pradėti sąvoka. Apribojimai yra, kad metanotions gali būti tik viena raidė, gali būti be kairę rekursija, metarules, bei (iš esmės) predikatai negali būti naudojamas.

Turiu išversti šią programą į maždaug 200 linijos ABC [ABC], bet tik su kairėje-rekursija apribojimas likę.

Išvada

Tradicinis metodas, apibrėžiantis programavimo kalbų semantiką su Van Wijngaarden Gramatikos turi, priklauso nuo naudojimo nemokamai metanotions, kurios yra pagrindinė kliūtis kuriant vykdomąjį apibrėžimai kalbomis.

Čia pateikta buvo metodą nustatyti programavimo kalba, naudojant dviejų lygių gramatikos taip, kad sąvoka gali būti aiškinama mechaniškai, bet pirma pradėti sąvoka. Šis privalumas leidžia skaitytojui patikrinti visų pirma išvesti automatiškai, bet atrodo, kad šį procesą suprasti apibrėžimą lengviau skaitytojui, per nebuvimas nemokamai metanotions.

[Pirmą kartą paskelbtas 1982; pakeistos liepos 2014; klaidų ištaisymas Vasaris 2016]

Nuorodos

[ABC] http://www.cwi.nl/~steven/abc/

[Grune] D. Grune. How to produce all sentences from a two-level grammar. Information Processing Letters, 19, puslapis 181-185, 1984.

[van Wijngaarden] Adriaan van Wijngaarden, The Generative Power of Two-Level Grammars. In Proceedings of the 2nd Colloquium on Automata, Languages and Programming, Jacques Loeckx (Ed.). Springer-Verlag, Londone, UK, 9-16, 1974. UK, 9-16, 1974. http://link.springer.com/chapter/10.1007%2F3-540-06841-4_48

 

Grįžti į pagrindinį

Leave a Reply

Your email address will not be published. Required fields are marked *