- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
LL1aSLL
Zjednodušená ukázka:
Stáhnout celý tento materiálKapitola 6
LL gramatiky
6.1 Definice LL(k) gramatik
Definice 6.1. Necht’ G BP B4N,A6,P,SB5 je CFG, k ≥ BD je cele´cˇı´slo. Definujme funkci
BYC1CACBCC
G
k
BMB4N ∪A6B5
B7
→PB4{w ∈ A6
∗
||w|≤k}B5 prˇedpisem
BYC1CACBCC
G
k
B4αB5BP{w ∈ A6
∗
| B4α ⇒
∗
w ∧|w|≤kB5 ∨B4α ⇒
∗
wx∧|w| BP k ∧x ∈ A6
∗
B5}
a funkci BYC7C4C4C7CF
G
k
BM N →PB4{w ∈ A6
∗
||w|≤k}B5 prˇedpisem
BYC7C4C4C7CF
G
k
B4AB5BP{w ∈ A6
∗
| S ⇒
∗
γAα, w ∈ BYC1CACBCC
G
k
B4αB5}.
Necht’da´le w BP a
BD
a
BE
...a
n
je libovolny´rˇeteˇz. Pak klademe
k BM w BP
⎧
⎨
⎩
a
BD
...a
k
kBD existuje LL(k) gramatika
takova´, zˇe nesplnˇuje podmı´nku (6.7). Ma´ tedy smysl definovat tzv. SLL(k) gramatiky, a to
(naprˇı´klad) takto:
Definice 6.11. Necht’G BPB4N,A6,P,SB5 je redukovana´ CFG, k ≥ BD je cele´cˇı´slo. rˇekneme,
zˇe G je SLL(k) gramatika, pra´veˇ kdyzˇ pro libovolne´ dveˇ nejleveˇjsˇı´ derivace (w ∈ A6
∗
)
B4BDB5 S ⇒
∗
wAα ⇒ wβα ⇒
∗
wx
B4BEB5 S ⇒
∗
w
prime
Aα
prime
⇒ w
prime
γα
prime
⇒
∗
w
prime
y , podmı´nka
B4BFB5 k BM x BP k BM y
implikuje rovnost β BP γ.
R
ˇ
ekneme, zˇe gramatika G je SLL pra´veˇ kdyzˇ je SLL(k) pro neˇjake´ k ∈ N, jazyk L je
SLL(k) pra´veˇ kdyzˇ
Vloženo: 24.04.2009
Velikost: 79,38 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2025 unium.cz
