Kiire alt-üles analüüs: eelnevusgrammatikad

Alt-üles analüüsi korral on kõige tähtsam samm töödeldavas stringis aluse (mingi produktsiooni parema poole) tunnistamine. Selleks on välja töötatud palju algoritme; ühed kiirematest on eelnevusrelatsioonide      kasutamisel põhinevad algoritmid. Eelnevusrelatsioone kasutavaid algoritme on mitmeid, vaatleme järgnevas algoritmi, mis põhineb nn lihtsa eelnevusgrammatika kasutamisel; seda algoritmi kasutati ka TTÜ-s loodud translaatorite kompileerimise (compiler compiler) süsteemis ELMA.

Relatsioon on binaarne relatsioon kõigi terminalide ja mitteterminalide hulgal: U V, kui leiduvad produktsioonid

X uUYv
Y Vw

(kahekordne nool tähendab, et tehakse vähemalt üks derivatsioonisamm!)

See tähendab, et kui redutseeritavas sõnas on järjest sümbilid ...UV... ja U V, siis sümbolist V algab uus alus. Suhte U V arvutamiseks tuleb
a) leida produktsioonide paremates pooltes kõik kõrvutiseisvate sümbolite paarid (U,Y), kus teine sümbol Y on mingi mitteterminal;
b) leida mitteterminali Y jaoks kõik grammatika sümbolid V, millega võib alata mingi Y-st saadav string;
c) märkida suhe U V kõigi selliste sümbolite vahele.

Relatsioon on binaarne relatsioon kõigi terminalide ja mitteterminalide hulgal: U V, kui leidub produktsioon

X uUYv

See tähendab, et sümbolid U, V kuuluvad samasse alusesse (s.t. alus jätkub).

Relatsioon on binaarne relatsioon, mille teine liige on terminal; U a (a on terminal !) kui leiduvad produktsioonid

X uYZv
Y wU

(kahekordne nool - tehakse vähemalt üks derivatsioonisamm!) ja

Z az

või

Z = a

See tähendab, et sümboliga U lõpeb alus. Suhte U a arvutamiseks tuleb:
a) leida produktsioonide paremates pooltes kõik järjestikused sümbolite (Y,Z) paarid, kus esimene sümbol Y on mitteterminal
b) leida kõik sümbolid U, mis võivad tekkida Y-st saadud stringi lõppu (derivatsioonis tehakse vähemalt üks samm!)
c) kui paari teine sümbol Z on mitterminal, leitakse kõik terminalid a, mis võivad tekkida Z-st saadud stringi alguses (või on Z ise terminal a)
d) märkida suhe U a kõigi selliste paaride vahele.

Grammatikat nimetatakse eelnevusgrammatikaks, kui:
1) kõik eelnevusrelatsioonid on üheselt määratud, s.t. mitte mingite sümbolite U,V vahel ei või olla kaht erinevat eelnevusrelatsiooni (võibolla ei ole ühtegi!);
2) grammatikas ei ole kaht sama parema poolega reeglit X U, Y U;
3) grammatikas ei ole tühja parema poolega reegleid X v.a. juhul, kui X on algussümbol ja X ei esine ühegi reegli paremal poolel.

Eelnevusgrammatika puhul on alt-üles analüüs lihtne: igal sammul loetakse analüüsitavat stringi vasakult paremale, kuni leitakse sümbolite jada

U V1 V2 V2 ... Vn a

String V1V2V2 ... Vn on alus, s.t. leidub produktsioon X V1V2V2 ... Vn, seega asendatase string V1V2V2 ... Vn mitteterminaliga X; selliselt jätkates peab analüüsi lõppedes tekkima string #S#, kus S on grammatika algussümbol (# on sümbol, millega analüüsitav string piiratakse mõlemalt poolt enne analüüsi algust).

Näide 1. Grammatika

X aXXb | c

eelnevusrelatsioonid on määratud tabeliga :
 

X

a

b

c

#

X

  

a

    

b

  

c

  

#

      

Sõna acaccbb alt-üles analüüsil tehakse järgmised sammud:

#acaccbb# # acaccbb# # a caccbb# # a c accbb# # a X accbb# ... # a X a c cbb# ... # a X a X c bb# ... # a X a X X bb# ... # a X X b# # X # OK

Näide 2. Grammatika

T a X | b Y | TT |
X 0 X | 1
Y 0 Y | 1

ei ole definitsiooni järgi eelnevusgrammatika (tühja parema poolega reegel!). Kuna selle grammatika eelnevusrelatsioonide tabelis ei ole konflikte (kaks relatsiooni samas ruudus) ja tühja parema poolega reegel on algussümbolist, siis on lihtne seda grammatikat teisendada eelnevusgrammatikaks:

T T1 |
T1 a X | b Y | TT
X 0 X | 1
Y 0 Y | 1

(kontrollida!)
Ülesandeid:
1. Arvutada eelnevusrelatsioonid avaldise grammatikatele:
1.

Avaldis Term | Term + Avaldis | Term - Avaldis
Term Tegur | Tegur * Term | Tegur / Term
Tegur Ident | Const | (Avaldis)

2.

Avaldis Term Avaldise_lõpp
Term Tegur Termi_lõpp
Tegur Ident | Const | (Avaldis)
Avaldise_lõpp + Avaldis | - Avaldis |
Termi_lõpp * Term | / Term |

3.

Avaldis Avaldis + Yksl | Yksl
Yksl Yksl * Tegur | Tegur
Tegur Ident | Const | ( Avaldis )

4.

Avaldis Avaldis + Yksl1 | Yksl1
Yksl1 Yksl
Yksl Yksl * Tegur | Tegur
Tegur Ident | Const | ( Avaldis )

Millised nendest grammatikatest on eelnevusgrammatikad, s.t. sobivad kiireks alt-üles analüüsiks?
2. Kas grammatika

S 0S11 | 011

on eelnevusgrammatika?
3. Kas grammatika (terminalid on rasvaselt)

S if Tingimus then S else S | S ; S |
Tingimus Boolean | Tingimus or Boolean | Tingimus and Boolean
Boolean 0 | 1

on (lihtne) eelnevusgrammatika ? Koostada eelnevusrelatsioonide tabel!
4. Järgnevas on kaks grammatikat reaalarvu kirjeldamiseks:
1.

number 0|1|2|3|4|5|6|7|8|9
numbrid number | number numbrid
r_arv numbrid | numbrid "." numbrid

2.

number 0|1|2|3|4|5|6|7|8|9
numbrid number | number numbrid
r_arv numbrid kümnendosa
kümnendosa "." numbrid

Milline neist on a) LL(1); b)ei ole LL(k) ühegi ka korral; c) on eelnevusgrammatika ? Kui mõnda neist on lihtne väikese modifikatsiooniga muuta LL(1) või eelnevusgrammatikaks, esita see modifikatsioon!
Küsimused, probleemid: ©2004 Jaak Henno id Milline neist on a) LL(1); b) ei ole LL(k) ühegi ka korral; c) on eelnevusgrammatika ? Kui mõnda neist on lihtne väikese modifikatsiooniga muuta LL(1) või eelnevusgrammatikaks, esita see modifikatsioon!
Küsimused, probleemid: ©2004 Jaak Henno