Примеры LL (1), LR (1), LR (0), LALR (1) грамматики?
Есть ли хороший ресурс в Интернете с набором грамматик для некоторых основных алгоритмов синтаксического анализа (LL (1), LR (1), LR (0), LALR (1))? Я нашел много отдельных грамматик, которые попадают в эти семьи, но я не знаю хорошего ресурса, где кто-то написал большой набор примеров грамматик.
Кто-нибудь знает о таком ресурсе?
Ответы
Ответ 1
Методы анализа - Практическое руководство содержит несколько примеров (то есть, вероятно, полдюжины или около того) для каждого типа грамматики. Вы можете приобрести книгу 2-го издания, хотя 1-е издание доступно бесплатно для автора веб-сайт в формате PDF (около нижней части ссылки).
У автора также есть некоторые тестовые грамматики, которые он связывает с примерами кода из второго издания, которое можно найти здесь.
Примечание: все эти грамматики небольшие (менее пары десятков правил), из-за этого, очевидно, является опубликованной книгой.
Ответ 2
Примеры из wikipedia
Грамматика
S -> F
S -> ( S + F )
F -> a
вход
( a + a )
шаги синтаксического анализа
S -> "(" S "+" F ")"
-> ( "F" + F )
-> ( "a" + F )
-> ( a + "a" )
Грамматика
(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.
Грамматика
S’ -> S S
S -> C C
C -> c C | d
вход
cd
шаги синтаксического анализа
large table
Грамматика
A -> C x A | ε
B -> x C y | x C
C -> x B x | z
вход
xxzxx
шаги синтаксического анализа
traverse large parser table
Вы также можете посмотреть
Ответ 3
Я бы не ожидал, что вы найдете целые коллекции грамматик, организованных таким образом. Что получит организатор взамен?
Что бы вы могли сделать, это найти генераторы парсеров, которые соответствуют каждому семейству (например, LL (1)), и искать примеры входов для этого генератора парсера, все из которых будут LL ( 1) по определению. Например, ANTLR-грамматики представляют собой различные версии LL (k) в зависимости от выбранной вами версии ANTLR (описание ANTLR-версии сообщит, что k принимает); Грамматики Bison - это LALR (1) [игнорирование последней опции GLR]. Если вы перейдете на мой веб-сайт (см. Биографию), вы увидите список грамматик, которые в значительной степени свободны от контекста (то есть не в любом из классов, которые вы описываете).
EDIT: Обратите внимание на @Bart Kier, поясняющее, что ANTLR может явно помечать грамматику как LL (k) для конкретного k.
