Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: grammarboy 23. 01. 2016, 02:24:51

Název: LR parsing
Přispěvatel: grammarboy 23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Název: Re:LR parsing
Přispěvatel: Ivan Nový 23. 01. 2016, 08:04:22

Citace: grammarboy  23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Pro silnou LR(k) gramatiku musí platit
Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βX,
(b) A → αX, B → ε, kde X ∈ BEFORE(B),
(c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ FOLLOWk(B) = ∅.
2 Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βXγ,
(b) A → ε, B → βXγ, kde X ∈ BEFORE(A),
(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ EFFk(γ · FOLLOWk(B)) = ∅.

Název: Re:LR parsing
Přispěvatel: pistelak 23. 01. 2016, 13:17:36

Bh£$×8bapOuNN(*$@%%£$₩(*)

Název: Re:LR parsing
Přispěvatel: zboj 23. 01. 2016, 16:26:25

Citace: Ivan Nový  23. 01. 2016, 08:04:22

Citace: grammarboy  23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Pro silnou LR(k) gramatiku musí platit
Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βX,
(b) A → αX, B → ε, kde X ∈ BEFORE(B),
(c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ FOLLOWk(B) = ∅.
2 Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βXγ,
(b) A → ε, B → βXγ, kde X ∈ BEFORE(A),
(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ EFFk(γ · FOLLOWk(B)) = ∅.

A co takhle napsat něco k věci místo trapného copy-paste?

Název: Re:LR parsing
Přispěvatel: zboj 23. 01. 2016, 16:28:56

Citace: grammarboy  23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Shift-shift konflikt nastat nemůže, takže chyba je v implementaci. V té gramatice je shift-reduce konflikt.

Název: Re:LR parsing
Přispěvatel: Ivan Nový 23. 01. 2016, 18:42:29

Citace: zboj  23. 01. 2016, 16:26:25

Citace: Ivan Nový  23. 01. 2016, 08:04:22

Citace: grammarboy  23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Pro silnou LR(k) gramatiku musí platit
Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βX,
(b) A → αX, B → ε, kde X ∈ BEFORE(B),
(c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ FOLLOWk(B) = ∅.
2 Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βXγ,
(b) A → ε, B → βXγ, kde X ∈ BEFORE(A),
(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ EFFk(γ · FOLLOWk(B)) = ∅.

A co takhle napsat něco k věci místo trapného copy-paste?

Jen jsem chtěl naznačit, že existují standardní postupy a algoritmy k testování gramatik, které nevhodná pravidla vyloučí nebo transformují. A testem, že daný soubor pravidel vyhovuje LR(k) se při implementaci začíná. Pokud to otestovat nelze, je lepší s takovou gramatikou či jazykem nepracovat, protože neskýtá záruky, že implementace bude spolehlivá. S pravidly typu S ← 'x' S 'x' | 'x' si poradí CYK algoritmus. Ale to bych bral jako poslední možnost, pokud by selhaly transformace na LR(k) původní gramatiky.

Chytrému napověz, hloupého kopni :-)))

Název: Re:LR parsing
Přispěvatel: Ivan Nový 23. 01. 2016, 19:29:11

Jinak pravidla můžete transformovat takto.
N -> I
N -> R
I -> n
R -> n . n
---------------
N -> n
N -> n . n
-------------
N1 -> n N2
N2 -> . N3
N2 -> e
N3 ->  n
----------------
a je to LL(1) gramatika

Název: Re:LR parsing
Přispěvatel: zboj 24. 01. 2016, 12:52:20

Citace: Ivan Nový  23. 01. 2016, 18:42:29

Citace: zboj  23. 01. 2016, 16:26:25

Citace: Ivan Nový  23. 01. 2016, 08:04:22

Citace: grammarboy  23. 01. 2016, 02:24:51

Implementuju LR parser a na následujícím fragmentu gramatiky mám shift-shift konflikt:

N -> I
N -> R
I -> n
R -> n . n

Je tato gramatika vůbec LR(k)? Pokud ano, jaké budou kernel sety?

Pro silnou LR(k) gramatiku musí platit
Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βX,
(b) A → αX, B → ε, kde X ∈ BEFORE(B),
(c) A → ε, B → ε, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ FOLLOWk(B) = ∅.
2 Pro kazˇdou dvojici pravidel v P
0 ve tvaru
(a) A → αX, B → βXγ,
(b) A → ε, B → βXγ, kde X ∈ BEFORE(A),
(c) A → ε, B → γ, kde X ∈ BEFORE(A), X ∈ BEFORE(B),
platı´ FOLLOWk(A) ∩ EFFk(γ · FOLLOWk(B)) = ∅.

A co takhle napsat něco k věci místo trapného copy-paste?

Jen jsem chtěl naznačit, že existují standardní postupy a algoritmy k testování gramatik, které nevhodná pravidla vyloučí nebo transformují. A testem, že daný soubor pravidel vyhovuje LR(k) se při implementaci začíná. Pokud to otestovat nelze, je lepší s takovou gramatikou či jazykem nepracovat, protože neskýtá záruky, že implementace bude spolehlivá. S pravidly typu S ← 'x' S 'x' | 'x' si poradí CYK algoritmus. Ale to bych bral jako poslední možnost, pokud by selhaly transformace na LR(k) původní gramatiky.

Chytrému napověz, hloupého kopni :-)))

CYK by použil jen vůl.