Antaŭan paĝon! Indekson! Instrukcion!

Formalaj lingvoj

  1. Metodoj por difini la sintakson

Metodoj por difini la sintakson

  1. La generaj gramatikoj
  2. La formo de Backus—Naur

La generaj gramatikoj

Formale genera gramatiko G estas kvaropo G=(V,S,R,p), kies anoj estas:
V
finia «vortaro» (alfabeto, signaro);
S
ties subaro, S⊂V, finia signaro da bazaj signoj. La ceteraj elementoj de V estas nomataj nocioj, helpsimboloj aŭ sintaksaj variabloj;
p
sintaksa variablo (p∈V∖S) nomata aksiomo (aŭ «starta simbolo», «propozicisimbolo»);
R
aro da derivreguloj.
La derivreguloj havas la formon α→β, kie β∈V* kaj α∈V*(V∖S)V*, t.e. α estas ĉeno el bazaj signoj kaj sintaksaj variabloj entenanta almenaŭ unu variablon, dum β estas ajna ĉeno el bazaj signoj kaj variabloj.

Estu ú,ü∈V*; la ĉeno ü estas tuj derivebla el ú (simbole ú→ü) SSE ú=iαï, ü=iβï kaj α→β∈R. Do, ú→ü se inter la simboloj de ú troveblas subĉeno identa al la maldekstra parto de tia derivregulo, ke anstataŭiginte la subĉenon per la dekstra parto de la regulo oni ricevos ü.

Estu RTF la refleksiva transita fermo de la rilato →, t.e. RTF(u,w) SSE ia (eventuale vakua) sekvenco de tujaj derivaĵoj kondukas de u ĝis w. La sekvencon

u, …, z 

en kiu por ĉiuj tujsekvaj v kaj w veras v→w, oni nomas derivo de z el u en G.

La «lingvo generata de gramatiko G» estas

L(G) = {x | RTF(p,x) ∧ (x∈S*)}

Oni kutimas klasi la generajn gramatikojn en sekvan hierarkion laŭ Ĉomski.

La generajn gramatiko G en la ĝenerala formo difinita supre estas nomata «gramatiko de la tipo nul».

Genera gramatiko G estas kuntekstohava (aŭ de la tipo 1), se por ĉiu ĝia derivregulo α→β veras |α|≤|β| (ĉi tie |x| estas longo, t.e. la nombro de simboloj en la ĉeno x).

Genera gramatiko estas senkunteksta (aŭ de la tipo 2), se ĉiu ĝia derivregulo havas la formon N→β, kie N∈(V∖S) kaj β∈V*.

Genera gramatiko de la tipo 3 estas dekstre lineara gramatiko.

La formo de Backus—Naur

La sintaksaj variabloj de la gramatiko estas prezentataj per (unu aŭ pluraj) vortoj ĉirkaŭitaj de angulaj krampoj, ekz^+e <nomo> aŭ <sensignuma entjero>. La maldekstran (la difinatan) kaj la dekstran (la difinantan) partojn de la derivreguloj disigas la simbolo ::= (oni voĉlegu: estas laŭdifine). Se sintaksa variablo povas havi plurajn difinojn, ili ĉiuj aperas en la dekstra parto de ĝia regulo, disigate de la vertikala streko | (voĉlegu: «aŭ»). Ekzemploj: 
   <cifero> ::= 0|1|2|3|4|5|6|7|8|9 
   <sensignuma entjero> ::= 
      <cifero> | <sensignuma entjero> <cifero> 
   <entjero> ::= <sensignuma entjero> 
                 | + <sensignuma entjero> 
                 | - <sensignuma entjero>

Laŭ tiuj reguloj la sekvaj ĉenoj estas validaj <entjero>j: 

    10 
    -5 
  +199

En la posta praktiko (ekz^+e en la sintaksaj priskriboj de PL/I) estis uzata la «etendita formo de Backus—Naur», en kiu rektaj krampoj signas partojn nedevigajn (preterigeblajn), kaj vinkuloj, la partojn eventuale ripetatajn (iteraciojn); kiel pluan licencon, oni ofte toleras alternativojn ene de tiaj metalingvaj krampoj. Do,

<A>::=<B>|<B><C> 

ekvivalentas al

<A>::=<B>[<C>] 

kaj

<X>::=<Y>|<Y><X> 

ekvivalentas al

<X> ::= { <Y> } 

Kun tiaj konvencioj,

<sensignuma entjero> ::= [+|−] {<cifero>} 

aŭ eĉ

<sensignuma entjero> ::= [+|−] {0|1|2|3|4|5|6|7|8|9}

Laŭ ankoraŭ pli moderna (kaj pli oportuna) modo oni inversigas la konvencion: la sintaksaj variabloj (multe pli oftaj en la reguloj, ol la bazaj signoj) havas formon de simplaj identigiloj (sen angulaj krampoj aŭ aliaj eskapsimboloj), dum la bazaj signoj (aŭ ĉenoj de bazaj signoj) ĉiam aperas inter citiloj aŭ substrekite; la vinkuloj signas eventualajn maleston aŭ iteracion; anstataŭ ::= oni nun preferas simplan egalon (=), kaj la finon de regulo oni markas per punkto. Pli detale tiun sistemon, uzatan en nia Leksikono por sintaksaj difinoj, ni priskribis sub sintakso.

Indekson Instrukcion