Programmēšanas valodu sintakse un bezkonteksta gramatikas

Mērķi

  • Zināt jēdzienus parsētājs, bezkonteksta gramatika, izvedums, sintakses koks
  • Prast lasīt valodai Java domātās abstraktās sintakses izvedumu shēmas; redzēt kā praktiski izmanto bezkonteksta gramatikas valodas struktūras aprakstam.

Valodas sintakse

Programmēšanas valodai sintakse ir visi tie pareizrakstības likumi, kuri atšķir pareizi uzrakstītu programmu no sintaktiski nepareizas un tātad nesaprotamas programmas. Sintakse nenodarbojas ar programmēšanas valodu konstrukciju nozīmes skaidrošanu (to dara semantika), nedz arī māca kā rakstīt praktiski noderīgas programmas. Tā vienkārši palīdz atšķirt pareizi uzrakstītas programmas no nepareizām.

Programmās var būt dažādu veidu sintakses kļūdas:

  • Nesaprotamas leksēmas. Piemēram, Javas mainīgo nedrīkst saukt par @*#&$^#*, jo tā nosaukumam jāsākas ar burtu, $, vai "_". Vai arī vesels skaitlis, kura pieraksta vidū sastopami burti, utml. Šīs kļūdas var atklāt leksiskais analizators ar regulāru izteiksmju palīdzību - tās atklāj "lokāli", analizējot atsevišķās leksēmas programmas tekstā.
  • Parsēšanas kļūdas. Piemēram, Javas programmās aizmirstas aizverošās figūriekavas. Šīs kļūdas var atrast parsētājs - īpaša programma, kura pārbauda leksēmu virknes atbilstību noteiktai struktūrālai secībai - piemēram, šajā līmenī var pārbaudīt, vai visas atvērtās iekavas ir aizvērtas, vai pirms katra "else" ir atbilstošais "if", un vai katrai komandai beigās ir semikols (;).
  • Ar vienkāršu parsētāju neatklājamas kļūdas. Piemēram, prasību, lai ikviens mainīgais, kurš izmantots Javas programmā, būtu pirms tam programmas tekstā deklarēts, mēdz pārbaudīt, uzbūvējot programmas tekstam atbilstošās datu struktūras, piemēram izmantoto mainīgo tabulas.

Tā kā programmēšanas valodas sintaksi vismaz pirmajā tuvinājumā nosaka parsētāja pieprasītā struktūra, tad šajā nodaļā iepazīsimies ar parsētājiem un bezkonteksta gramatikām (context-free grammars), ko tie pārbauda. Ar vienkāršu parsēšanu neatklājamās kļūdas paliks šajā nodaļā sīkāk neapskatītas.

Kas ir valoda

  • Alfabēts Sigma={...} ir galīga netukša simbolu kopa. (Piemēram, Javas programmas parasti raksta ar ASCII simboliem.)
  • Vārds ir jebkura simbolu virknīte kādā alfabētā. Alfabēta Sigma visu vārdu kopu apzīmē ar Sigma*. (Šajā matemātiskajā izpratnē "vārds" var būt kaut kas daudz lielāks, nekā ikdienas izpratnē - arī pilnu programmas tekstu mēs uzskatām par "vārdu".)
  • Valoda alfabētā Sigma ir vienalga kāda Sigma* apakškopa, t.i. par katru vārdu alfabētā Sigma varam pateikt, vai tas pieder valodai, vai nē. (Mūs interesēs, piemēram, kā aprakstīt to valodu, kuras vārdi ir visas sintaktiski pareizās programmas valodā Java.)

Piemēri

  • Heksadecimālo ciparu alfabēts: Sigma={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}.
  • Heksadecimālie vārdi: visi vārdi, kurus var pierakstīt ar 0,1,2,3, utt. heksadecimālajiem cipariem, piemēram "", "0", "1", ..., "F", "00", ..., "FF", .... (Pēdiņas nepieder pie vārda, tās tikai norobežo vārdu no abām pusēm.)
  • Tukšais vārds: jebkurā alfabētā ir vārds ar garumu 0, kurā nav neviena burta, valodā Java to pieraksta "".
  • Tukšā valoda: šajā valodā nav neviena vārda. (Ievērojiet, ka tas nav tas pats, kas valoda, kurā ir viens vārds - tukšais vārds.)
  • Valoda no visiem 4-burtu heksadecimālajiem vārdiem {"0000",...,"FFFF"} - ar šo apraksta unikoda burtus.
  • Latviešu leksikas valoda: pieraksta alfabētā {a,ā,...,z,ž}. Satur visus vārdus, kuri ir kādā latviešu valodas vārdnīcā un arī to visas locījumu formas.
  • Latviešu teikumu valoda: pieraksta alfabētā, kas satur latviešu burtus un pieturzīmes. Satur visas simbolu virknītes, kas ir gramatiski pareizi latviešu valodas vārdi. (Šādu valodu būtu ļoti grūti definēt precīzi.)
  • Sintaktiski pareizo Javas programmu valoda: pieraksta ar ASCII simboliem, satur visas simbolu virknes, kuras ir kompilējami javas izejas teksti. (Šāda valoda ir drusku atkarīga no izmantojamām bibliotēkām, bet to var precizēt.)

Kas ir sintakse

Apspriežot valodu lietošanas jautājumus gan programmēšanas, gan dabīgajās valodās, var izšķirt 3 apspriešanas līmeņus:

  • Sintakse (valodā atļautā leksika un teikumu/programmu konstrukcijas)
  • Semantika (šo konstrukciju nozīme)
  • Pragmatika (kā valodu vislabāk lietot)

Programmēšanas valodu sintaksi parasti apraksta ar bezkonteksta gramatikām.

Bezkonteksta gramatiku jēdziens

Bezkonteksta gramatiku apraksta četras lietas:

  1. N - galīga neterminālo simbolu kopa: {A,B,C,...,Statement,Argument,...} (neterminālos simbolus vienosimies rakstīt ar Lielo Sākuma Burtu).
  2. T - galīga terminālo simbolu kopa: {a,b,c,...,0,1,...,9,...,if,(,),...}.
  3. P - gramatikas produkciju kopa. Katra produkcija sastāv no divām pusēm - kreisajā pusē stāv netermināls simbols, bet labajā pusē - vārds, kurš sastāv no terminālajiem un neterminālajiem simboliem.
  4. Neterminālo simbolu kopā vienu simbolu apzīmē par starta simbolu, ar to sākas vārdu izvedums no gramatikas.

Izvedums no gramatikas nozīmē neterminālo simbolu aizvietošanu, izmantojot gramatikas produkciju likumus tikmēr, kamēr vārdā vairs nav neterminālo simbolu. T.i. bezkonteksta gramatika vienmēr definē valodu terminālo simbolu alfabētā T. Izvedumu ar gramatiku var attēlot kā sintakses koku, kurā terminālie simboli kā lapas "izaug" no neterminālajiem simboliem kā stumbra dzinumiem. Starta simbols ir, tēlaini sakot, pirmais dzinums, no kura izaug sintakses koks.

Piemērs: aritmētisku izteiksmju gramatika

Izveidosim gramatiku, lai aprakstītu visas sintaktiski pareizās aritmētiskās izteiksmes, šādā 5 simbolu alfabētā: T={+,*,(,),var}. Tās būs izteiksmes ar saskaitīšanu, reizināšanu, iekavām un īpašu simbolu "var", kas apzīmē kādu mainīgo (t.i. mēs identificējam visus mainīgos ar to pašu simbolu.)

Gramatiku definēsim, ieviešot neterminālo simbolu kopu N = {E}, kur "E" ir vienīgais neterminālais simbols un arī starta simbols. Lūk, šīs gramatikas produkcijas:

E ::= (E)
E ::= E+E
E ::= E*E
E ::= var

Parādīsim, kā var šajā gramatikā izvest sintaktiski pareizu aritmētisku izteiksmi var+var*(var+var):

E -> E+E -> var+E -> var+E*E -> var+E*(E) -> var+var*(E)
    -> var+var*(E+E) -> var+var*(var+E) -> var+var*(var+var) 

Kā redzams, pēdējā izteiksme vairs nesatur neterminālo simbolu "E" un sakrīt ar sākotnējo aritmētisko izteiksmi. Tas apliecina, ka dotā ir gramatiski pareiza aritmētiskā izteiksme. Sintakses koks dots zemāk. Var pamanīt, ka sintakses koks atbilst arī veidam, kā aprēķināt šo aritmētisko izteiksmi.

var+var*(var+var) sintakses koks

Kāpēc ar tik vienkāršu sintakses definēšanas metodi nepietiek?

Augstākminētais sintakses koks nav vienīgais veids, kā no izteiksmju gramatikas iegūt izteiksmi var+var*(var+var). Principiāli atšķirīgs veids būtu šāds:

E -> E*E -> E+E*E -> var+E*E -> var+E*(E) -> var+var*(E)
    -> var+var*(E+E) -> var+var*(var+E) -> var+var*(var+var) 

Nav grūti pamanīt, ka šim izvedumam atbilstošais sintakses koks ir savādāks (uzzīmējiet to!) un, ka tam atbilstošais izteiksmes rēķināšanas veids arī ir atbilstoši savādāks, t.i. (var+var)*(var+var). Izrādījās, ka mūsu gramatika neņem vērā to, ka reizināšanai ir augstāka prioritāte nekā saskaitīšanai. Lai šo situāciju labotu, vajadzētu lietot citu gramatiku:

E ::= E + T
E ::= T
T ::= T*var 
T ::= var
T ::= (E)

Šī gramatika respektē to, ka reizināšana sasaista reizināmos ciešāk nekā saskaitīšana ("T" nozīmē "terms" jeb monoms).

Tomēr ir daudzi jautājumi, kurus nekādi nav iespējams izteikt ar bezkonteksta gramatikām. Piemēram, Javas sintakses prasība, lai katrs mainīgais pirms lietošanas būtu deklarēts. Ar "pumpēšanas lemmu" palīdzību ir iespējams parādīt, ka ar šīm gramatikām nav iespējams atšķirt visus tos vārdus kuri atbilst pareizi nodeklarētiem mainīgajiem no tiem vārdiem, kuros mainīgie nav deklarēti vai ir deklarēti atkārtoti.

Kāds tam ir sakars ar Javu

Javas valodas veidotāji ir definējuši Javas formālo gramatiku dokumentā, kuru sauc "The Java Language Specification", sk. http://java.sun.com/docs/books/jls/. Tur izmanto bezkontekstu valodu apraksta dialektu, kurš atgādina EBNF (extended Backus-Naur forms). Kā Javas mācību grāmata tomēr tas nav visai piemērots, jo ir garš (ap 800 lappuses) un diezgan tehnisks.

"if" konstrukcija šajā specifikācijā definēta šādi:

IfThenStatement:
    if ( Expression ) Statement
IfThenElseStatement:
    if ( Expression ) StatementNoShortIf else Statement
IfThenElseStatementNoShortIf:
    if ( Expression ) StatementNoShortIf else StatementNoShortIf

Ievērojiet, cik delikāti Javas autori izvairījušies no kārdinājuma definēt divdomīgu gramatiku. Aiz "then" (atslēgvārdu "then" Javā, protams neraksta), ja izmantojam arī "else" drīkst atrasties tikai tāds "if", kurš vai nu vispār nav "if"-konstrukcija, vai arī ir pilna "if" konstrukcija kopā ar visu "else".

Simbols "?" aiz netermināļa nozīmē, ka attiecīgā daļa var būt un var arī nebūt. Piemēram šāds pieraksts:

ForStatement:
    for ( ForInit? ; Expression? ; ForUpdate? ) Statement

ir saīsināts apzīmējums visām 8 iespējām, kā pieraksta "for" ciklu:

ForStatement:
    for ( ; ; ) Statement
    for ( ; ; ForUpdate ) Statement
    for ( ; Expression ; ) Statement
    for ( ; Expression ; ForUpdate ) Statement
    for ( ForInit ; ; ) Statement
    for ( ForInit ; ; ForUpdate ) Statement
    for ( ForInit ; Expression ; ) Statement
    for ( ForInit ; Expression ; ForUpdate ) Statement

Katrai no šīm iespējām ir sava semantika, jeb nozīme. Teiksim, rinda "for (;;) Statement" apzīmē mūžīgo ciklu.


Lapa mainīta 2004-11-15 22:38:12