LR (1) путаница в конструкции стола - PullRequest
Новая
       53

LR (1) путаница в конструкции стола

0 голосов
/ 05 ноября 2019

Я запутался в том, как разобрать эту грамматику с помощью LR (1): 

S -> A
A -> A(A) | empty

Я знаю, что осталась рекурсия, но мне сказали, что нет необходимости удалять ее для LR(1). Мои наборы элементов выглядят так: (запятая отделяет грамматику от заглядываний) 

item set 0:
s -> .A, $
A -> .A(A), $(
A -> ., $(

item set 1:
S -> A., $
A -> A.(A), $(

Теперь вот где я запутался: 

item set 2:

A -> A(.A), $(  
A -> .A(A), )(
A -> ., )(

item set 3:
A -> A(A.), $(
A -> A. (A), )(

item set 4:
A -> A(A)., $(

Мне сказали разобрать строку"(())". Когда я сделал это, я понял, что для состояния 4 нужно иметь правильную круглую скобку «)», что имеет смысл. Теперь я проследил это и выяснил, что эта правая круглая скобка должна исходить из первого оператора в наборе элементов 2. 

A -> A(.A), $()

Это приведет к переносу правой круглой скобки в следующие 2 состояния имоя грамматика разобралась бы отлично. Тем не менее, я не совсем понимаю, ПОЧЕМУ здесь должны быть правильные скобки? Не следует ли переносить $ (из набора элементов 1. Откуда взялась эта правильная скобка? Может кто-нибудь объяснить, пожалуйста. Спасибо

1 Ответ

0 голосов
/ 06 ноября 2019

Давайте начнем с предположения, что вы пытаетесь построить (каноническую) машину LR (1), и рассмотрим состояние (набор элементов) 3: 

item set 3:
A -> A(A.), $(
A -> A.(A), )(

Возможны два преемника: GOTO (S3), ')') и GOTO (S3, '(')): 

item set 4: GOTO(S3, ')')
A -> A(A)., $(

item set 5: GOTO(S3, '(')
A -> A(.A), )(
A -> .A(A), )(
A -> .    , )(

Обратите внимание, что набор элементов 5 равен , а не так же, как ваш набор элементов 2, посколькупервый пункт отличается.

Именно из этого и исходит загадка ), которая озадачивает вас, как вы можете видеть, когда закончите конечный автомат LR (1), продолжая переходить из состояния 5: 

item set 6: GOTO(S5, A)
A -> A(A.), )(
A -> A.(A), )(

item set 7: GOTO(S6, ')')
A -> A(A)., )(

Вот и все, потому что GOTO(S6, '(') это набор элементов 5.

Скорее всего, вы пытаетесь построить (и проанализировать) LALR (1) машину. В машине LALR (1) наборы предметов с одинаковыми ядрами объединяются. Когда мы объединяем два набора элементов, промежуточные позиции для соответствующих элементов заменяются объединением промежуточных элементов. Таким образом, мы объединяем наборы элементов 2 и 5: 

  item set 2          item set 5          merged item set
A -> A(.A), $(      A -> A(.A), )(      A -> A(.A), $)(
A -> .A(A), )(      A -> .A(A), )(      A -> .A(A), )(
A -> .    , )(      A -> .    , )(      A -> .    , )(

Аналогично мы объединяем наборы элементов 3 и 6 и наборы элементов 4 и 7 

item set 3+6:
A -> A(A.), $)(
A -> A.(A), )(

item set 4+7:
A -> A(A)., $)(

(есть гораздо более эффективный алгоритмдля построения машин LALR (1), который не включает в себя построение всей машины LR (1) и последующее слияние состояний, но результат точно такой же, и алгоритм слияния, возможно, легче понять.)

...