Примеры грамматик LL (1), LR (1), LR (0), LALR (1)? - PullRequest
Новая
       107

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

55 голосов
/ 26 июня 2011

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

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

Ответы [ 3 ]

36 голосов
/ 05 июля 2011

Примеры из Википедии

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

Возможно, вы также захотите взглянуть на

19 голосов
/ 21 августа 2011

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

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

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

2 голосов
/ 30 июня 2011

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

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

РЕДАКТИРОВАТЬ: Note @BartУточнение Киера о том, что ANTLR может явно пометить грамматику как LL (k) для конкретного k.

...