Парсер LALR (1) и SLR (1)

Question

Я получил гипотезу от нашего учителя, и он хочет, чтобы мы нашли и подтвердили ее.У нас есть парсер SLR (1) и LALR (1).Гипотеза:

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

Если вы ищете в Интернете, вы найдете множество сайтов, которые говорят, что эта грамматика не SLR (1), а LALR (1):

S -> R
S -> L = R
L -> * R
L -> id
R -> L

("id "," * "и" = "являются терминалами, а другие нетерминалами)
Если мы попытаемся найти элементы SLR (1), мы увидим конфликт сдвиг / уменьшение.это правда, но моя гипотеза говорит о другом.В нашей гипотезе мы говорим о языке , описываемом грамматикой, а не самой грамматикой!Мы можем удалить «R» и преобразовать грамматику в LL (1), и это также SLR (1) и LALR (1):

S -> LM
M -> epsilon
M -> = L
L -> * L
L -> id

Вы можете попробовать эту грамматику, и вы увидите, что эта грамматика описывает тот же язык , что и в последней грамматике, с грамматикой SLR (1) и LALR (1)!

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

Извините за плохой английский.
Спасибо.

Answer 1

Каждый язык LR ( k ) имеет грамматику SLR (1).

В статье этой статьи 1976 года имеется доказательство, которое предоставляет алгоритм для построения грамматики SLR (1), если у вас есть грамматика LR ( k ) и знать значение k . К сожалению, не существует алгоритма, который определенно мог бы сказать вам, является ли CFG LR ( k ), тем более, предоставьте значение k . (Если вы как-то знаете, что грамматика - это LR ( k ), вы можете попробовать последовательные значения k , пока не найдете работающее. Но эта процедура никогда не завершится, если грамматика не LR ( k ).)

Сказанное выше взято из данного справочного вопроса на сайте Computing Science StackExchange , который является лучшим местом для такого рода вопросов.

Answer 2

LR (1)> LALR (1)> SLR (1)

LR (1) - самый мощный, LALR (1) - менее мощный, а SLR (1) - наименее мощный. Это факт, из-за того, как вычисляются преднамеренные множества. (1) означает ожидание одного токена. Вот грамматика, которая является LR (1), но не LALR (1) и определенно не SLR (1):

   G : S... <eof>
     ;
   S : c A1 t ';'
     | c A2 n ';'                       
     | r A2 t ';'
     | r A1 n ';'
     ;
  A1 : a 
     ;
  A2 : a 
     ;

Эта грамматика не может быть LALR (1) или SLR (1). Или вы можете удалить А1 и А2 и замените их на, но тогда у вас есть другая грамматика. Проблема в том, что действие может быть присоединено к правилу A1: а и другое действие может быть присоединено к A2: a. Например:

  A1 : a    => X()
     ;
  A2 : a    => Y()
     ;

Генератор синтаксического анализатора SLR (1) сообщит о конфликтах в вашей грамматике, которые не являются реальными конфликтами. Я говорю о реальном мире, используя большие грамматики (например, C11.grm).

Расчет прогнозирования SLR (1) упрощен: вместо него используется механизм поиска LR (0), созданный генератором синтаксического анализатора LALR (1).

Вот почему статья Фрэнка Деремера в 1969 году о LALR (1) так важна.

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