Как проверить, соответствует ли грамматика SLR(1)?

Как проверить, является ли эта грамматика SLR(1)?

    S' -> S
    S -> [ B
    A -> int
    A -> [ B
    B -> ]
    B -> C
    C -> A ]
    C -> A , C

Сначала я создал его автомат, затем вычислил следующие наборы для нетерминалов, а затем создал таблицу разбора. Я не уверен, что мой автомат правильный, но после разбора таблицы для грамматики SLR(1) я не нашел никаких ошибок. Ниже моя попытка автомата.

I0:
S' -> .S
S -> .[B

I1 (I0 -> S):
S -> [.B
B -> .]
B -> .C
C -> .A]
C -> .A,C
A -> .int
A -> .[B

I3 (I2 -> B)
S -> [B.

I4 (I2 -> ])
B -> ].

I5 (I2 -> C)
B -> C.

I6 (I2 -> A)
C -> A.]
C -> A.,C

I7 (I2 -> int)
A -> int.

I8 (I2 -> [)
A -> [.B
B -> .]
B -> .C
C -> .A]
C -> .A,C
A -> .int
A -> .[B

I8 -> ] = I4
I8 -> C = I5
I8 -> A = I6
I8 -> int = I7
I8 -> [ = I8 

I9 (I6 -> ])
C -> A].

I10 (I6 -> ,)
C -> A,.C
C -> .A]
C -> .A,C
A -> .int
A -> .[B

I11 (I8 -> B)
A -> [B.

I12 (I10 -> C)
C -> A,C.

I10 -> A = I6
I10 -> int = I7
I10 -> [ = I8

conflict parsing grammar lr context-free-grammar
person Octavian    schedule 25.01.2020    source источник
comment
Если вы можете построить таблицу синтаксического анализа и в ней нет конфликтов, это SLR(1). (Конечно, похоже, что так и должно быть; если вы левый фактор C, то это LL (1).)   -  person rici    schedule 25.01.2020

Ответы (1)


arrow_upward
0
arrow_downward

Учитывая, что вы проделали тяжелую работу по поиску всех состояний, теперь пришло время проверить правила SLR(1).

https://en.wikipedia.org/wiki/SLR_grammar

Как вы понимаете, в вашем вопросе отсутствует набор Follow(), который является обязательным в Правилах.

Да, вы можете узнать в своем анализаторе таблиц, есть ли конфликт или нет, но этот ответ зависит больше от опыта, чем от фактической науки. Ознакомьтесь с правилами один за другим, и все будет в порядке :)

В зависимости от того, что вы уверены в правильности своих состояний, я не вижу конфликта Shift/Reduce или Reduce/Reduce, поэтому грамматика SLR(1)

person Confidenc3    schedule 08.07.2020