LR(1) грамматика: как сказать? примеры за / против?

Question

В настоящее время я смотрю на GNU Bison для анализа кода программы (или на самом деле для расширения программы, которая использует Bison для этого). Я понимаю, что Bison может только (или: лучше) обрабатывать грамматики LR(1), то есть особую форму контекстно-свободных грамматик; и я на самом деле также (верю, чтобы) понять правила грамматики без контекста и LR(1).

Тем не менее, почему-то мне не хватает хорошего понимания понятия LR(1) грамматики. Предположим, например, SQL. SQL включает - я считаю - грамматику без контекста. Но это также грамматика LR(1)? Как я мог сказать? И если да, что нарушит правила LR(1)?

Answer 1

LR(1) означает, что вы можете выбрать правильное правило для уменьшения, зная все токены, которые будут уменьшены, плюс один токен после них. Нет проблем с AND в булевых запросах и в BETWEEN операция. Например, следующая грамматика - LL (1) и, следовательно, также LR(1):

expr ::= and_expr | between_expr | variable
and_expr ::= expr "and" expr
between_expr ::= "between" expr "and" expr
variable ::= x

Я считаю, что вся грамматика SQL даже проще, чем LR(1). Вероятно, LR(0) или даже LL (n).

Answer 2

Некоторые из моих клиентов создали парсеры SQL и DB2, используя мой генератор парсеров LALR (1), и успешно использовали их много лет. Они прислали мне грамматики LALR (1) (за исключением конфликтов "сдвиг-уменьшение", которые разрешаются так, как вы бы хотели). Для пуристов - не LALR (1), но на практике работают нормально, GLR или LR (1) не нужны. Вам даже не нужен более мощный LR(1), AFAIK.

Я думаю, что лучший способ понять это - найти грамматику SQL и хороший генератор синтаксического анализатора LALR/LR(1) и посмотреть, получите ли вы отчет о конфликте. Как я помню, грамматика SQL (немного устаревшая) LALR (1) доступна в этой загрузке: http://lrstar.org/downloads.html

LRSTAR - это генератор синтаксических анализаторов LR (1), который выдаст вам отчет о конфликте. Это также LR(*), если вы не хотите разрешать конфликты.