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

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

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

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

Является ли это примером грамматики LR(k), у которой нет эквивалента LL(1), или я делаю что-то не так?

редактировать: я скопировал неправильное имя, я хотел скопировать объявление параметра:

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

проблема заключается в том, что декларатор и абстрактный декларатор имеют ( в своем первом наборе, но также остаются рекурсивными.


c parsing ll lr context-free-grammar
person Bobby Sacamano    schedule 17.07.2015    source источник
comment
Рекомендуется помещать пример/код в свой вопрос вместо ссылки.   -  person Ely    schedule 18.07.2015
comment
На первый вопрос, возможно, ответили здесь: stackoverflow.com/questions/8809545/   -  person    schedule 18.07.2015
comment
Полный набор сравнений (без примеров): cs.stackexchange.com/questions/43/   -  person o11c    schedule 18.07.2015
comment
@deniss грамматика, которую парень перечисляет как не LL (1), неоднозначна, поэтому она не совсем убедительна   -  person Bobby Sacamano    schedule 18.07.2015
comment
@ Бобби Сакамано, почему это двусмысленно? Бизон с canonical-lr принимает его без конфликтов.   -  person    schedule 18.07.2015
comment
aab имеет два разных дерева синтаксического анализа с любой из первых двух альтернатив S в корне — Гюнтер   -  person Bobby Sacamano    schedule 18.07.2015
comment
@Bobby Sacamano, это утверждение касается старой версии сообщения, где оно было S ::= a S b | a S | \epsilon   -  person    schedule 18.07.2015
comment
о, я неправильно прочитал метку времени. Есть ли способ доказать, что для этого не существует эквивалента LL (1)?   -  person Bobby Sacamano    schedule 18.07.2015
comment
@Bobby Sacamano, cs.stackexchange.com/questions /3350/   -  person    schedule 18.07.2015

Ответы (1)


arrow_upward
4
arrow_downward

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

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

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

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

Ваш пример, однако, может быть просто с учетом левого фактора в грамматике LL(1), чтобы быть

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

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

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

person Community    schedule 17.07.2015