Kontekstivabade keelte süntaksianalüüs alt-üles

Alt-üles süntaksianalüüsi algoritmid otsivad igal sammul loetavas stringis (töö algamisel on see analüüsitav, ainult terminalidest koosnev string, töö käigus tekib sinna ka mitteterminale) mingi produktsiooni aluse, s.t. parema poole, ja taandavad (redutseerivad) selle siis vastava produktsiooni vasakul pool olevaks mitteterminaliks. Tavaliselt püütakse asendada analüüsitavas stringis esimene (vasakult paremale lugedes) leitud alus. Kogu string peaks lõpuks taanduma grammatika algussümboliks, kuid ka siin võib vajadus tagurdamiseks (backtracking), kui analüüsitavas stringis ei ole enam ühtki alust.

Näide 1. Olgu grammatika G

S a S b S | aS |c

ja analüüsitav sõna aacbc (suured tähed on mitteterminalid, väikesed - terminnalid).

Analüüs algab situatsioonis (# on analüüsitava sõna lõpumarker):

Vasakult paremale lugedes esimene alus on c, mis redutseeritakse mitteterminaliks S; edasi analüüsitakse stringi aaSbc


Stringis aaSbc esimene alus on aS, mis redutseeritakse mitteterminaliks S; edasi analüüsitakse stringi aSbc


Stringis aSbc esimene alus on aS, mis redutseeritakse mitteterminaliks S; edasi analüüsitakse stringi Sbc


Nüüd saame aluse credutseerimisel stringi SbS, mis ei sisalda enam yhtegi alust, seega tuleb teha tagurdus (backtracking) ja proovida eelmisel sammul asendada mitte vasakult-paremale esimene, vaid mõni järgmine alus.


Ülesandeid:
1. Teha alt-üles süntaksianalüüs avaldisele a*a+(2*a*+b)*b, kui avaldis on genereeritud järgmiste grammatikatega
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 |

Kumb grammatika sobib ülalt-alla analüüsiks paremini?

Küsimused, probleemid: ©2004 Jaak Henno