začenši in nadaljuje z omenjenimi k terminali.

Slovnica se imenuje LL (k) -slovnica, če je LL (k) slovnica za nekaj k.

Primer 4.7... Razmislite o slovnici G = ((S, A, B), (0, 1, a, b), P, S), kjer P sestavljajo pravila

S -> A | B, A -> aAb | 0, B -> aBbb | 1.

tukaj . G ni LL(k)-slovnica za kateri koli k. Intuitivno, če začnemo z branjem dovolj dolgega niza znakov a, potem ne vemo, katero od pravil S -> A in S -> B je bilo prvo uporabljeno, dokler ne naletimo na 0 ali 1.

Če se obrnemo na natančno definicijo LL(k)-slovnice, postavimo tudi y = a k 1b 2k. Potem pa sklepi

ustrezajo sklepoma (1) in (2) definicije. Prvih k znakov nizov x in y je enakih. Vendar pa je sklep napačen. Ker je k tukaj izbran poljubno, G ni LL-slovnica.

Posledice definicije LL (k) - slovnice

Izrek 4.6. slovnica KS je LL(k)-slovnica, če in samo če za dve različni pravili in od P križišča prazen z vsem takim , kaj .

Dokaz. Potreba... Recimo, da in izpolnjuje pogoje izreka in vsebuje x. Potem, po definiciji FIRST, za nekatera y in z obstajajo sklepi

(Upoštevajte, da smo tukaj uporabili dejstvo, da N ne vsebuje neuporabnih neterminalov, kot se domneva za vse obravnavane slovnice.) Če | x |< k ; то y = z = e . Так как , то G не LL (k)- грамматика .

Ustreznost... Recimo, da G ni LL (k) - slovnica.

Potem sta dva taka zaključka

da verigi x in y sovpadata na prvih k legah, vendar. Zato in so različna pravila iz P in vsakega od nizov in vsebuje verigo FIRST k (x), ki sovpada z verigo FIRST k (y).

Primer 4.8... Slovnica G, sestavljena iz dveh pravil S -> aS | a ne bo slovnica LL (1), saj

PRVI 1 (aS) = PRVI 1 (a) = a.

Intuitivno je to mogoče razložiti takole: če vidimo samo ta prvi znak pri razčlenjevanju verige, ki se začne s simbolom a, ne vemo, katero od pravil S -> aS ali S -> a je treba uporabiti za S. Po drugi strani je G slovnica LL (2). Dejansko v zapisu pravkar predstavljenega izreka, če , potem A = S in. Ker sta za S podani samo dve navedeni pravili, potem in. Ker je FIRST2 (aS) = aa in FIRST2 (a) = a, je po zadnjem izreku G LL (2) -slovnica.

Odstranitev leve rekurzije

Glavna težava pri uporabi napovedne analize je iskanje slovnice za vhodni jezik, ki jo je mogoče uporabiti za sestavo analitične tabele z enolično definiranimi vhodi. Včasih lahko z nekaj preprostimi transformacijami slovnico, ki ni LL (1), zmanjšamo na enakovredno slovnico LL (1). Med temi transformacijami sta najučinkovitejši leva faktorizacija in odstranitev leve rekurzije. Tukaj je treba poudariti dve točki. Prvič, vsaka slovnica po teh transformacijah ne postane LL (1), in drugič, po takih transformacijah lahko nastala slovnica postane manj razumljiva.

Takojšnjo levo rekurzijo, torej rekurzijo pogleda, lahko odstranimo na naslednji način. Najprej združimo A-pravila:

kjer se nobena vrstica ne začne z A. Nato ta niz pravil zamenjamo z

kjer je A "nov neterminal. Iz neterminalnega A se lahko izpišejo enake verige kot prej, vendar zdaj ni leve rekurzije. Ta postopek odstrani vse neposredne leve rekurzije, vendar ne odstrani leve rekurzije, ki vključuje dva ali več korakov. algoritem 4.8 vam omogoča, da odstranite vso levo rekurzijo iz slovnice.

Algoritem 4.8... Odstranitev leve rekurzije.

vhod... KS-slovnica G brez e-pravil (kot A -> e).

Izhod... CS-slovnica G "brez leve rekurzije, enakovredna G.

Metoda... Sledite korakom 1 in 2.

(1) Razporedite neterminale slovnice G v poljubnem vrstnem redu.

(2) Izvedite naslednji postopek:

Po (i-1) iteraciji zunanje zanke v koraku 2 za katero koli pravilo v obliki kjer je k< i , выполняется s >k. Posledično pri naslednji iteraciji (za i) notranja zanka (za j) zaporedno poveča spodnjo mejo za m v ​​katerem koli pravilu dokler m> = i. Potem, ko odstranimo takojšnjo levo rekurzijo za A i -pravila, postane m večje od i.

Pri rekurzivnem razčlenjevanju od zgoraj navzdol se lahko pojavi problem neskončne zanke.

V slovnici za aritmetične operacije bo uporaba drugega pravila povzročila zanko v rutini razčlenjevanja. Takšne slovnice imenujemo levo rekurzivne. Slovnica se imenuje levo rekurzivna, če je v njej neterminal A, za katerega obstaja sklep A => + Aa. V preprostih primerih levo rekurzijo povzročijo pravila, kot je

V tem primeru se uvede nov neterminal in prvotna pravila se nadomestijo z naslednjim.

(če obstaja neterminal А, za katerega obstaja zaključek А → + Аa v 1 ali več korakih). Levi rekurziji se je mogoče izogniti s preoblikovanjem slovnice.

Na primer izdelki A → Aa

Lahko se nadomesti z enakovrednimi:

Za tak primer obstaja algoritem, ki odpravi levo rekurzijo:

1) definiraj na množici neterminalov nek red (А 1, А 2, ..., А n)

2) vzamemo vsak neterminal, če zanj obstaja produkt, ki upošteva neterminal na levi strani, in preoblikujemo slovnico:

za i: = 1 do n do

za j: = 1 do i-1 do

če je Ai → Ajγ, potem Ai → δ1γ

│ δkγ, kjer

Aj → δ1│ δ2│… │ δk

3) izključimo vse primere takojšnje rekurzije v levo (pravilo 1)

To. algoritem pomaga preprečiti zanke.

Izključitev leve rekurzije iz slovnice aritmetičnih izrazov in splošnega pogleda na pravilo za izključitev leve rekurzije:

Splošni pogled na pravilo izključitve leve rekurzije

Leva faktorizacija.

Slovnice LL (1) so potrebne za izbiro želenih izdelkov za razčlenjevanje od zgoraj navzdol, tako da ni zanke.

Včasih je mogoče pretvoriti slovnico v obliko LL (1) z uporabo metode levega faktorizacije.

Na primer: S → če B potem S

│če B potem S, drugače S

Te produkcije kršijo pogoj LL (1) -slovnic. To slovnico je mogoče pretvoriti v LL (1).

S → če B potem S rep

Na splošno lahko to transformacijo definiramo na naslednji način:

uvedemo nov neterminal B, za katerega

| β N Levo faktorizacijo lahko uporabimo za B. Ta postopek se ponavlja, dokler ostaja izbira izdelka nedefinirana (tj. dokler se v njem lahko kaj spremeni).

Sestavljanje PRVEGA sklopa

Prvi niz za neterminal definira nabor terminalov, s katerimi se dani neterminal lahko začne.

1. Če je x terminal, potem najprej (x) = (x). Ker je prvi znak zaporedja iz enega terminala lahko samo terminal sam.

2. Če slovnica vsebuje pravilo Xà e, potem prvi niz (x) vključuje e. To pomeni, da se X lahko začne s praznim zaporedjem, torej je lahko v celoti odsoten.

3. Za vse izdelke tipa XàY1 Y2… Yk naredite naslednje. Naboru najprej (X) dodajte prvi niz (Yi), dokler prvi (Yi-1) ne vsebuje e, prvi (Yi) pa ne vsebuje e. V tem primeru se i spremeni iz 0 v k. To je potrebno, saj če Yi-1 morda ni, je treba ugotoviti, kje se bo v tem primeru začelo celotno zaporedje.

Slovnica, ki vsebuje levo rekurzijo, ni slovnica LL (1). Upoštevajte pravila

A→ Aa(leva rekurzija v A)

A→ a

Tukaj a simbol predhodnika za obe neterminalni različici A... Podobno slovnica, ki vsebuje levo rekurzivno zanko, ne more biti slovnica LL (1), npr.

A→ pr

B→ CD

C→ AE

Slovnico, ki vsebuje levo rekurzivno zanko, je mogoče pretvoriti v slovnico, ki vsebuje samo levo rekurzijo naprej, poleg tega pa je z uvedbo dodatnih neterminalov levo rekurzijo mogoče v celoti odpraviti (pravzaprav jo nadomesti z desno rekurzijo, ki ne predstavlja problem v zvezi z LL (1) -lastnostmi).

Kot primer si oglejte slovnico z generativnimi pravili

S→ Aa

A→ Bb

B→ Kp

C→ Dd

C→ e

D→ Az

ki ima levo rekurzivno zanko, ki vključuje A, B, C, D... Če želite zamenjati to zanko z levo rekurzijo naprej, razvrstimo neterminale na naslednji način: S, A, B, C, D.

Upoštevajte vsa pravila generiranja obrazca

Xi→ Xj γ,

kje Xi in Xj- neterminali, in γ - niz terminalskih in neterminalnih simbolov. Glede pravil za katere j ≥ i, se ne ukrepa. Vendar ta neenakost ne more veljati za vsa pravila, če obstaja leva rekurzivna zanka. V vrstnem redu, ki smo ga izbrali, imamo opravka z enim pravilom:

D→ Az

Ker A pred D v tem naročilu. Zdaj pa začnimo z zamenjavo A z uporabo vseh pravil, ki jih imajo A na levi strani. Kot rezultat dobimo

D→ Bbz

V kolikor B pred D po vrstnem redu se postopek ponovi, kar daje pravilo:

D→ Ccbz

Nato ponovi še enkrat in poda dve pravili:

D→ ecbz

D→ Ddcbz

Preoblikovana slovnica zdaj izgleda takole:

S→ Aa

A→ Bb

B→ Kp

C→ Dd

C→ e

D→ Ddcbz

D→ ecbz

Vsa ta pravila generiranja imajo zahtevano obliko, leva rekurzivna zanka pa je nadomeščena z levo rekurzijo naprej. Za odpravo rekurzije naprej levo, uvedemo nov neterminalni simbol Z in zamenjaj pravila

D→ ecbz

D→ Ddcbz

D→ ecbz

D→ ecbzZ

Z→ dcbz

Z→ dcbzZ

Upoštevajte, da pred in po transformaciji D generira regularni izraz

(ecbz) (dcbz) *

Če povzamemo, lahko pokažemo, da če je neterminal A se pojavi na levi strani r+ s generativna pravila, r od tega uporabljajo levo rekurzijo naprej in s- ne, tj.

A→ Aα 1, A→ Aα 2,..., A→ Aα r

A→ β 1, A→ β 2,..., A→ β s

potem je mogoče ta pravila nadomestiti z naslednjim:

Neformalen dokaz je, da pred in po transformaciji A ustvari regularni izraz ( β 1 | β 2 |... | β s) ( α 1 | α 2 |... | α r) *

Treba je opozoriti, da z odpravo leve rekurzije (ali leve rekurzivne zanke) še vedno ne dobimo slovnice LL (1), saj za nekatere neterminale na levi strani pravil nastalih slovnic obstajajo alternativne desne strani, ki se začnejo z istimi simboli. Zato je treba po odstranitvi leve rekurzije nadaljevati s transformacijo slovnice v obliko LL (1).

17. Pretvorba slovnic v obliko LL (1). Faktorizacija.

Faktorizacija

V mnogih situacijah je mogoče slovnice, ki nimajo atributa LL (1), pretvoriti v slovnice LL (1) s postopkom faktorizacije. Oglejmo si primer takšne situacije.

P→ začni D; Z konec

D→ d, D

D→ d

Z→ s; Z

Z→ s

V procesu faktorizacije zamenjamo več pravil za en neterminal na levi strani, katerega desna stran se začne z istim znakom (nizom znakov) z enim pravilom, pri čemer na desni strani skupnemu začetku sledi dodatni neterminal . Prav tako je slovnica dopolnjena s pravili za dodaten neterminal, po katerem iz njega izhajajo različni "ostanki" prvotne desne strani pravila. Za zgornjo slovnico bo to dalo naslednjo slovnico LL (1):

P→ začni D; Z konec

D→ d X X)

X→ , D(v skladu s 1. pravilom za D izvirna slovnica za d sledi, D)

X→ ε (v skladu z 2. pravilom za D izvirna slovnica za d nič (prazen niz))

Z→ s Y(uvajamo dodaten neterminal Y)

Y→ ; Z(v skladu s 1. pravilom za C izvirna slovnica za s sledi; C)

Y→ ε (v skladu z 2. pravilom za C izvirna slovnica za s nič (prazen niz))

Prav tako generativna pravila

S→ aSb

S→ aSc

S→ ε

se lahko s faktorizacijo pretvori v pravila

S→ aSX

S→ ε

X→ b

X→ c

in nastala slovnica je LL (1). Procesa faktorizacije pa ni mogoče avtomatizirati z razširitvijo na splošni primer. Naslednji primer prikazuje, kaj se lahko zgodi. Upoštevajte pravila

1. P→ Qx

2. P→ Ry

3. Q→ m2

4. Q→ q

5. R→ sRn

6. R→ r

Oba niza vodilnih simbolov za dve možnosti P vsebujejo s, in poskuša "vzdržati s zunaj oklepajev", zamenjamo Q in R na desni strani pravil 1 in 2:

P→ sQmx

P→ sRny

P→ qx

P→ ry

Ta pravila je mogoče nadomestiti z naslednjim:

P→ qx

P→ ry

P→ sP 1

P 1 → Qmx

P 1 → Rny

Pravila za P1 so podobna prvotnim pravilom za P in imajo prekrivajoče se nize vodilnih simbolov. Ta pravila lahko preoblikujemo na enak način kot pravila za P:

P 1 → sQmmx

P 1 → qmx

P 1 → sRnny

P 1 → rny

Faktoring, dobimo

V teoriji formalnih slovnic in avtomatov (TFGiA) igra pomembno vlogo t.i. slovnice brez konteksta(KS-slovnice). CS-slovnica je četverica, sestavljena iz niza N neterminalnih simbolov, niza T terminalskih simbolov, niza P pravil (produkcij) in začetnega simbola S, ki pripada množici N.

Vsaka produkcija p od P ima obliko A -> a, kjer je A neterminalni znak (A od N) in a je niz, sestavljen iz terminalskih in neterminalnih znakov. Postopek izpisa besede se začne z vrstico, ki vsebuje samo začetni znak S. Nato se na vsakem koraku eden od neterminalnih znakov, vključenih v trenutno vrstico, nadomesti z desno stranjo ene od produkcij, v kateri je leva. stran. Če po takšni operaciji dobimo niz, ki vsebuje samo terminalske znake, se izhodni proces konča.

Pri številnih teoretičnih problemih je priročno upoštevati t.i normalne oblike slovnice. Proces normalizacije slovnice se pogosto začne z odpravo leve rekurzije. V tem problemu bomo obravnavali le njegov poseben primer, imenovan neposredna leva rekurzija. Za pravilo sklepanja A -> R rečemo, da vsebuje takojšnjo levo rekurzijo, če je prvi znak niza R A.

CS-slovnica je nastavljena. Potrebno je najti število pravil, ki vsebujejo takojšnjo levo rekurzijo.

Vhodni podatki

Prva vrstica vhodne datoteke INPUT.TXT vsebuje število n (1 ≤ n ≤ 1000) pravil v slovnici. Vsaka od naslednjih n vrstic vsebuje eno pravilo. Neterminalni simboli so označeni z velikimi črkami angleške abecede, terminalni pa z malimi črkami. Leva stran izdelave je od desne ločena s simboli ->. Desna stran produkcije je dolga od 1 do 30 znakov.