online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
   
kategória
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
 
 
 













































 
 

Környezetfüggetlen nyelvek, szintaxisfa, levezetés. Programozasi nyelvek szintaktikaja, BNF.

számítógépes

Fájl küldése e-mail Esszé Projekt


egyéb tételek

 
Be és Kivitel
Web mail és e-mail IP alapon
Elemi programozasi tétele XI.: rendezés buborékos módszerrel
Az Assemly programozas alapjai: a 80*86 processzor regiszterei, címzési módok, PC megszakítasok, a hadver programozas szintjei
Az elsődleges operaciós rendszer telepítése és üzemeltetése
Elemi adattípusok (adatabrazolas, értéktartomany, konstansok, mûveletek, fontosabb függvények, eljarasok)
Szelekciós utasítasok
Görbék szerkesztése
A dBASE adatbaziskezelö rendszer
A programkészítés lépései, módszertana. Algoritmusok Pascal programjai.
 
 

Környezetfüggetlen nyelvek, szintaxisfa, levezetés. Programozási nyelvek szintaktikája, BNF.

KÖRNYEZETFÜGGETLEN NYELVEK

Szabályok alakja: A®w, ahol A Î N, wÎ(TÈN)*, w¹e.


Levezetéseket irányított fagráfokkal szemléltetjük(BNF).

Szintaxisfa, levezetés pontosítása:

Definíció          G= <T, N, S, P> grammatika. G-hez tartozó levezetés 939i81j i fa egy irányított                           fagráf, ha:     - csúcsai  T È N elemei,

                                             - gyökere S,

                                             - ha AÎN esetén az A csúcs közvetlen leszármazottai balról jobbra                                  

                                                B1, ....., Bk Î T È N, akkor létezik P-ben A®B1 ... Bk szabály.

                           S


                  A   

          B1   B2   .....     Bk

Definíció  Levezetési fa eredménye egy szó, melyet balról jobbra haladva a levelekről olvasunk le.

Példa G = <, , S, P>

                   P : S ® if b then A | if b then A else S | a

                   A ® for c do S | a

                   Két levezetési fa, melynek eredménye ugyanaz: if b then for c do of b then a else a

 


1.                        S


                  if         b       then       A


                                             for         c         do           S


                                                                             if       b     then       A       else     S


                                                                                                            a                    a

 

2.

                                     S


                           if       b     then     A     else     S


                                        for      c      do      S            a


                                                                 if       b     then     A


                                                                                              a

                                                                                                                                               G

Tétel  G:= <T, N, S, P> egy környezetfüggetlen grammatika. Ekkor w¹e, wÎT* szóra S  =  w Û létezik G-beli levezetési fa     ®¾    eredménye w.

Bizonyítás: GA := <T, N, A, P>  AÎN grammatika.

(levezetési szabályok ugyanazok, mint G-ben csak a kezdőszimbólum más)

A fenti állítást tetszőleges GA-ra bizonyítjuk. Ennek speciális esete: G=GS.           GA

Tegyük fel, hogy w egy GA-beli levezetési fa eredménye. Bizonyítsuk be: A    =  w.

N a fában szereplő nemterminális jelek száma. Erre vonatkozóan teljes indukcióval bizonyítjuk.

1. n=1  Egy nemterminális jel van ® ez a gyökér: A

                                    A

                      b1      b2     ......     bk                 bi Î T(közvetlen leszármazottai A-nak)

     b1 ... bk = w a kiinduló feltétel miatt. A levezetési fa csak akkor nézhet ki így (definíciója

                                                                                   GA

     miatt), ha minden A®b1 ... bk Î P szabály Þ A   ¾    w

2. Tegyük fel, hogy az állítás minden fára igaz, ahol a nemterminális jelek száma kisebb, mint n-1.

3. Bizonyítsuk be n-re, hogy a fa a következő alakú:

                                A                                    Bi Î TÈN

                                                                       (Az ábrán Bi Î N. Ha Bi Î T, belőle már nem indul

                 B1     B2   ........   Bk                      ki levezetés.)


                 a1     a2               ak

           

                                                                       a1a2 .... ak = w a kiindulási feltevés miatt.

Maximum n-1 nemterminális jelet tartalmazó levezetési fák.

Az indukciós feltevés miatt:

                 GB1                                                                         GA



létezik B1  =  a1 levezetés Þ létezik B1   =  a1

:

:               Gbk                                                                          GA

létezik Bk  = ak levezetés Þ  létezik Bk   =  ak


            A grammatikák szabályai ugyanazok.

A levezetés GA-ban:

     GA                      GA                      GA           GA

A  ¾  B1B2.....Bk    =     a1B2....Bk   =  ......   =      a1...ak=w   ÞAdott  A       w levezetés.

Bizonyítsuk be, hogy konstruálható levezetési fa ®¾  gyökere A, eredménye a. Levezetés hosszára (:=l) vonatkoztatott teljes indukció.

                      GA

1.    l = 1:   A ¾  w.

       Ekkor létezik A ® b1 ... bk = w  szabály. A szintaxisfa:                    A


                                                                                                      b1      b2      ...      bk

2.    Tegyük fel, hogy az állítás igaz minden olyan levezetésre, melynek hossza maximum n.

3.    Bizonyítsuk be n+1 -re:

            GA                                                          GA                    GA

       A   =   w levezetés hossza n+1. Ekkor: A  =  U1  B  U2    ¾    U1  p  U2


                                                                       b1...bi        bj+1...bk         bi+1 ... bj

                                                                                 BÎN

       Létezik GA-ban B®p szabály.

A szintaxisfa konstruálása:

                                A

                                                                  Az indukciós feltevés miatt ilyen fa létezik.

             b1..... bi       B     bj+1.... bk


                       bi+1          bj                         A faépítés konstrukciója szerint a fa így tovább építhető.

Qu.e.d.

                                                                                                             G          G          G        G

Definíció G=<T, N, S, P> környezetfüggetlen grammatika. Az w0  ¾  w1  ¾  w2  ¾ ... ¾ wn+1  legbaloldalibb levezetés, ha minden i=0, ..... , n -re: wi=aAb,  wi+1=agb, ahol aÎT*, bgÎ(TÈN)*, AÎN és A ®gÎP. (Mindig a legbaloldalibb nemtermális jelet helyettesítjük.)

Példa

a,  S  ¾  if b then A  ¾  if b then for c do S  ¾  if b then for c do if b then A else S ¾ if b then     for c do if b then a else S ¾ if b then for c do if b then a else a.

b,  S ¾ if b then A else S ¾ if b then for c do S else S ¾ if b then for c do if b then A else S ¾ if             b then for c do if b then a else S ¾ if b then for c do if b then a else a.

Tétel   G=<T, N, S, P> tetszőleges környezetfüggetlen grammatika. Ekkor minden wÎL(G)-nek   minden legbaloldalibb levezetése S-ből.

Bizonyítás:   A levezetés hosszára vonatkoztatott teljes indukcióval.

Definíció      G többértelmű környezetfüggetlen grammatika, ha létezik wÎT* ®¾ G                      generálja és w-nak létezik legalább két különböző legbaloldalibb levezetése.

Például        Lásd az utolsó példát (a, b,)

Megjegyzés Programozási nyelvek szempontjából érdekes: ahhoz, hogy egy program olvasata        egyértelmű legyen, kell, hogy az őt generáló grammatika egyértelmű legyen.

                     A többértelműség a grammatikák sajátja. Egy nyelvet elképzelhető, hogy le lehet írni      egyértelmű és nemegyértelmű grammatikákkal is.

Definíció      Egy nyelv örökletesen többértelmű, ha nem létezik őt generáló egyértelmű                      grammatika.

Állítás          Ilyen nyelv létezik.

Kérdés         Algoritmus gyártása uÎL(G) eldöntésére, ahol G környezetfüggetlen nyelvtan.

Megoldás     Megpróbálunk építeni egy olyan szintaxisfát, melyre gyökér(t)=S eredménye: u.

                     Ha sikerül: uÎL(G)

                     Ha nem: uÏL(G).

Találat: 972