Существует ли грамматика LR (k) без эквивалента LL (1)

Question

Мне пока не удалось найти ответ. Существуют ли грамматики, которые являются контекстными и недвусмысленными, которые не могут быть преобразованы в LL (1)?

Я нашел одно производство, что я не мог понять, как преобразовать в LL (1): parameter-type-list производство в C99:

parameter-type-list: 
    parameter-list 
    parameter-list , ... 

Это пример грамматики LR (к), что Безразлично У меня есть эквивалент LL (1), или я делаю что-то неправильно?

редактировать: Я скопировал неправильное имя, я имел в виду, чтобы скопировать параметр декларирование:.

parameter-declaration: 
    declaration-specifiers declarator 
    declaration-specifiers abstract-declarator(opt) 

проблема с описателем и абстрактным описателем как имеющие (в первом наборе, но также леворекурсивный

Answer 1

В общем, LR(k) грамматик являются более мощными, чем LL(k). Это означает, что есть языки с LR(k) анализатором, но не LL(k).

Один из примеров зависят от языка определяется с грамматикой:

S -> a S 
S -> P 
P -> a P b 
P -> \epsilon 

Или, другими словами, строка a-х, а затем тем же или меньшим количеством b-х гг. Это следует из того факта, что парсер должен принять решение о каждом встреченном a - он сопряжен с некоторыми b - смотря вперед не более k символов ввода, но они также могут быть a, не давая полезной информации. Для строгого доказательства, посмотрите на вторую часть принятого ответа здесь https://cs.stackexchange.com/questions/3350/is-this-language-ll1-parseable

Ваш пример, однако, может быть просто left factored в LL (1) грамматикой быть

parameter-type-list -> parameter-list optional-ellipsis 
optional-ellipsis -> \epsilon 
optional-ellipsis -> , ... 

Одно замечание, что FOLLOW набор для parameter-list будет содержать символ ,, и это может привести к конфликту FIRST-FOLLOW. Если это так, нам нужно определить определение parameter-list, чтобы исправить этот конфликт.

Редактировать:parameter-declaration Правило кажется очень сложным для ответа сразу. Вы можете попытаться выполнить левую факторизацию руками для всех конфликтующих альтернатив или с помощью некоторого инструмента помощи, например ANTLR.