Находите язык, который не является LL (1)?

Question

Я играл с большим количеством грамматик, которые не являются LL (1) в последнее время, и многие из них могут быть преобразованы в грамматики, которые являются LL (1).

Однако я никогда не видел пример однозначного языка , который не является LL (1).Другими словами, язык, для которого любая однозначная грамматика для языка не является LL (1)), и я не имею ни малейшего представления о том, как мне доказать, что я нашел один, если случайно наткнулся на него.1006 * Кто-нибудь знает, как доказать, что конкретный однозначный язык не является LL (1)?

Answer 1

Я некоторое время размышлял над вопросом, а затем нашел этот язык в Wikipedia :

S -> A | B
A -> 'a' A 'b' | ε
B -> 'a' B 'b' 'b' | ε

Они утверждают, что язык, описанный грамматикой выше, не может быть описан грамматикой LL (k). Вы спрашивали только о LL (1), и это довольно просто. Имея только первый символ, вы не знаете, является ли последовательность 'ab' или 'aab' (или какой-либо более рекурсивной), и поэтому вы не можете выбрать правильное правило. Таким образом, язык определенно не LL (1).

Также для каждой последовательности, генерируемой этой грамматикой, существует только одно дерево деривации. Так что язык однозначен.

Вторая часть вашего вопроса немного сложнее. Гораздо проще доказать, что язык является LL (1), чем наоборот (нет грамматики LL (1), описывающей язык). Я думаю, что вы просто создаете грамматику, описывающую язык, а затем пытаетесь сделать ее LL (1). После обнаружения конфликта, который не может быть разрешен, вы каким-то образом должны воспользоваться им и создать доказательство.