Рубрики

ВОРОТА | GATE CS 2008 | Вопрос 55

Парсер LALR (1) для грамматики G может иметь конфликты сдвига-уменьшения (SR) тогда и только тогда, когда
(A) парсер SLR (1) для G имеет конфликты SR
(B) парсер LR (1) для G имеет конфликты SR
(C) парсер LR (0) для G имеет конфликты SR
(D) анализатор LALR (1) для G имеет конфликты уменьшения-уменьшения

Ответ: (Б)
Объяснение:

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

т. е. если парсер LR (1) имеет 2 состояния I и J с элементами A-> a.bP, x и A-> a.bP, y соответственно, где x и y являются символами заглядывания вперед, тогда эти элементы совпадают с Что касается их первого компонента, они могут быть объединены вместе и формировать одно единое состояние, скажем, К. Здесь мы должны взять объединение символов заглядывания вперед. После слияния состояние K будет иметь один элемент A-> a.bP, x, y. Таким образом, формируются состояния LALR (1) (т.е. после слияния состояний LR (1)).

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


A-> a.bB , p
C-> d. , b

i.e. it is getting both shift and reduce at symbol b, 
hence a conflict. 

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

Примечание: Но этот процесс объединения может привести к конфликту RR, и тогда грамматика не будет LALR (1).

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE CS 2008 | Вопрос 55

0.00 (0%) 0 votes