LR (0) конфликты с Parser

Question

У меня есть сомнения относительно парсеров lr (0). Например, у меня есть последующие грамматики:

S -> S N 
    | 

N -> terminalsymbol 

Если я пытаюсь построить первое состояние Lr0 автомата, я получаю следующее первое состояние:

S ' -> . S $ 

S -> . S N 
S -> . 

Так вот кажется мне глупое сомнение , Поскольку у меня есть «S ->». в первом состоянии, является ли это ситуацией сдвига/уменьшения в парсере lr0? Причина, по которой парсер может перейти к действию сдвига по нетерминалу S, или уменьшить действие пустым переходом (я думаю).

Я уже искал по сети, ища пример с пустыми переходами, но я не нашел его.

Answer 1

Если вы начинаете с расширенной грамматики, это не конфликт.

В исходном состоянии нет никакого действия сдвига, и только одно действие уменьшения. Таким образом, действие сокращения должно происходить безоговорочно.

После того, как вы уменьшить S, вы в конечном итоге в состоянии:

S' -> S . $ 
S -> S . N 
N -> . nonterminal 

, который будет либо сместить метку конца-входа, или на следующий нетерминальный. Если предположить, что это не-терминал, мы в конечном итоге в:

N -> nonterminal . 

, который является еще одним принудительными уменьшить, что приводит нас к

S -> S N . 

, а затем мы вернулись к:

S' -> . S $ 
S -> . S N 
S -> . 

Однако оригинальная грамматика не была LR (0). (Нет языка, который включает как пустую строку, так и некоторую другую строку, может быть LR (0).)