kategória | ||||||||||
|
||||||||||
|
||
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: 1673