Примеры LL (1), LR (1), LR (0), LALR (1) грамматики?

Есть ли хороший ресурс в Интернете с набором грамматик для некоторых основных алгоритмов синтаксического анализа (LL (1), LR (1), LR (0), LALR (1))? Я нашел много отдельных грамматик, которые попадают в эти семьи, но я не знаю хорошего ресурса, где кто-то написал большой набор примеров грамматик.

Кто-нибудь знает о таком ресурсе?

+45
источник поделиться
3 ответа

Методы анализа - Практическое руководство содержит несколько примеров (то есть, вероятно, полдюжины или около того) для каждого типа грамматики. Вы можете приобрести книгу 2-го издания, хотя 1-е издание доступно бесплатно для автора веб-сайт в формате PDF (около нижней части ссылки).

У автора также есть некоторые тестовые грамматики, которые он связывает с примерами кода из второго издания, которое можно найти здесь.

Примечание: все эти грамматики небольшие (менее пары десятков правил), из-за этого, очевидно, является опубликованной книгой.

+16
источник

Примеры из wikipedia

LL (1)

Грамматика

S -> F
S -> ( S + F )
F -> a

вход

( a + a )

шаги синтаксического анализа

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )       

LR (0)

Грамматика

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1 

вход

1 + 1

шаги синтаксического анализа

need to build a parser table and traverse through states.

LR (1)

Грамматика

S’ -> S S 
S  -> C C 
C  -> c C | d

вход

cd

шаги синтаксического анализа

large table

LALR

Грамматика

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

вход

xxzxx

шаги синтаксического анализа

traverse large parser table

Вы также можете посмотреть

+33
источник

Я бы не ожидал, что вы найдете целые коллекции грамматик, организованных таким образом. Что получит организатор взамен?

Что бы вы могли сделать, это найти генераторы парсеров, которые соответствуют каждому семейству (например, LL (1)), и искать примеры входов для этого генератора парсера, все из которых будут LL ( 1) по определению. Например, ANTLR-грамматики представляют собой различные версии LL (k) в зависимости от выбранной вами версии ANTLR (описание ANTLR-версии сообщит, что k принимает); Грамматики Bison - это LALR (1) [игнорирование последней опции GLR]. Если вы перейдете на мой веб-сайт (см. Биографию), вы увидите список грамматик, которые в значительной степени свободны от контекста (то есть не в любом из классов, которые вы описываете).

EDIT: Обратите внимание на @Bart Kier, поясняющее, что ANTLR может явно помечать грамматику как LL (k) для конкретного k.

+2
источник

Посмотрите другие вопросы по меткам или Задайте вопрос