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

Я получил гипотезу от нашего учителя, и он хочет, чтобы мы нашли и подтвердили ее. У нас есть парсер 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) проще в использовании и, возможно, в будущем язык отвергнет эту гипотезу.

Я извиняюсь за плохой английский.
Благодарю.

Всего 1 ответ


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

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

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


Есть идеи?

10000