Bezkonteksta gramatikas

Last modified by superadmin on 2018-01-12 20:38

Bezkonteksta gramatikas

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)</li>
  • Semantika (šo konstrukciju nozīme)</li>
  • Pragmatika (kā valodu vislabāk lietot)</li>

Programmēšanas valodu sintaksi parasti apraksta ar bezkonteksta gramatikām. 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 -&gt; E+E -&gt; var+E -&gt; var+E*E -&gt; var+E*(E) -&gt; var+var*(E)
    -&gt; var+var*(E+E) -&gt; var+var*(var+E) -&gt; 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.

#pic("App_Grammars_SyntaxTree.gif", "250") Attēls: Sintakses koks

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 -&gt; E*E -&gt; E+E*E -&gt; var+E*E -&gt; var+E*(E) -&gt; var+var*(E)
    -&gt; var+var*(E+E) -&gt; var+var*(var+E) -&gt; 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 daudzas sintakses pazīmes, kuras nav iespējams izteikt ar bezkonteksta gramatikām. Piemēram, Javas sintakses prasību, lai katrs mainīgais pirms lietošanas būtu deklarēts. To izteikšanai izmanto citu formālismu - atribūtu gramatikas (t.i. saista ikvienu gramatikas simbolu ar kādu izrēķināmu izteiksmi). Šādu pieeju izmanto parsētāju ģenerēšanas rīki, piemēram, Bison/Yacc. 

Tags:
Created by Kalvis Apsītis on 2008-05-01 23:42
    
This wiki is licensed under a Creative Commons 2.0 license
XWiki Enterprise 6.4 - Documentation