online kép - Fájl  tubefájl feltöltés file feltöltés - adja hozzá a fájlokat onlinefedezze fel a legújabb online dokumentumokKapcsolat
  
 

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
  

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

számítógépes





felso sarok

egyéb tételek

jobb felso sarok
 
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.
 
bal also sarok   jobb also sarok

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


S


if b then A


for c do S


if b then A else S


a a



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.

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

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

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.)




a a ak

a a 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 = a levezetés Þ létezik B1 = a


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 = a B2....Bk   = ...... = a 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

l = 1: A ¾ w

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


b1 b2 ... bk

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

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 w ¾ w ¾ w ¾ ¾ 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: 1584







Felhasználási feltételek