LR parsing

[grammarboy]

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?

[Reklama]

[Ivan Nový]

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)) = ∅.

[pistelak]

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

[zboj]

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?

[zboj]

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.

[Reklama]

[Ivan Nový]

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 :-)))

[Ivan Nový]

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

[zboj]

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.