Может ли парсер LR (1) разобрать грамматику этого типа?Левая рекурсия в LR (1) синтаксические анализаторы
S -> SA | A
A -> aSb | ab
Я пытаюсь написать программу на Java, который реализует этот тип синтаксического анализатора, но я только получить правильные результаты на грамматик без левой рекурсии.
Анализаторы LR (1) могут обрабатывать некоторые типы левых рекурсий, хотя не все лево-рекурсивные грамматики являются LR (1).
Давайте посмотрим, является ли ваша конкретная грамматика LR (1). Дополняя грамматика дает
S»→ S
S → SA | A
A → aSb | абы
Наши наборы конфигурированию поэтому
(1)
S' -> .S [$] (Go to 2)
S -> .SA [$a] (Go to 2)
S -> .A [$a] (Go to 3)
A -> .aSb [$a] (Shift on a and go to 4)
A -> .ab [$a] (Shift on a and go to 4)
(2)
S' -> S. [$] (Accept on $)
S -> S.A [$a] (Go to 3)
A -> .aSb [$a] (Shift on a and go to 4)
A -> .ab [$a] (Shift on a and go to 4)
(3)
S -> A. [$a] (reduce on $ or a)
(4)
A -> a.Sb [$a] (Go to 6)
A -> a.b [$a] (Shift on b and go to 10)
S -> .SA [ab] (Go to 11)
S -> .A [ab] (Go to 12)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(5)
A -> ab. [$a] (Reduce on a or $)
(6)
A -> aS.b [$a] (Shift on b and go to 7)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(7)
A -> aSb. [$a] (Reduce on a or $)
(8)
A -> a.Sb [ab] (Go to 14)
A -> a.b [ab] (Shift on b and go to 16)
S -> .SA [ab] (Go to 11)
S -> .A [ab] (Go to 12)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(9)
S -> SA. [$a] (Reduce on a or $)
(10)
A -> ab. [$a] (Reduce on a or b)
(11)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(12)
S -> A. [ab] (Reduce on a or b)
(13)
S -> SA. [ab] (Reduce on a or b)
(14)
A -> aS.b [ab] (Shift on b and go to 15)
S -> S.A [ab] (Go to 13)
A -> .aSb [ab] (Shift on a and go to 8)
A -> .ab [ab] (Shift on a and go to 8)
(15)
A -> aSb. [ab] (Reduce on a or b)
(16)
A -> ab. [ab] (Reduce on a or b)
Есть нет сдвига/или уменьшение/уменьшения конфликтов в этой грамматике, и поэтому он должен быть LR (1) (если я не сделал ошибку где-то !)
Надеюсь, это поможет!
Оказывается, это также грамматика SLR, поэтому LR является излишним. Вместо того, чтобы требовать 16 состояний с LR, требуется только 10 состояний с SLR.
(1)
S' -> .S S => (Go to 2)
S -> .SA A => (Go to 3)
S -> .A a => (Shift and go to 4)
A -> .aSb
A -> .ab
(2)
S' -> S. $ => (Accept on $)
S -> S.A A => (Go to 5)
A -> .aSb a => (Shift and go to 6)
A -> .ab
(3)
S -> A. [$b] => (reduce on $ or b)
(4)
A -> a.Sb S => (Go to 7)
A -> a.b A => (Go to 9)
S -> .SA a => (Shift and go to 6)
S -> .A b => (Shift and go to 8)
A -> .aSb
A -> .ab
(5)
S -> SA. [$b] => (reduce on $ or b)
(6)
A -> a.Sb S => (Go to 7)
A -> a.b A => (Go to 3)
S -> .SA a => (Shift and go to 4)
S -> .A b => (Shift and go to 8)
A -> .aSb
A -> .ab
(7)
A -> aS.b A => (Go to 5)
S -> S.A a => (Shift and go to 6)
A -> .aSb b => (Shift and go to 10)
A -> .ab
(8)
A -> ab. [$b] => (reduce on $ or b)
(9)
S -> A. [$b] => (reduce on $ or b)
(10)
A -> aSb. [$b] => (reduce on $ or b)
ОК, спасибо ... Я думаю, что у меня есть некоторые проблемы с первым набором, так что если у меня есть S-> S + A | a, первый 1 (S) = [+, a]? – SegFault
Нет, это было бы неправильно. FIRST_1 (S) - это набор всех терминалов, которые могут находиться в начале строки, производной от S. Вы не можете получить строку, начинающуюся с + здесь, поэтому FIRST-набор будет просто {a}. – templatetypedef
Вы правы ... – SegFault