LL (1)이 아닌 언어를 찾으십니까?

Question

저는 최근에 LL (1)이 아닌 많은 문법을 가지고 놀았으며 그 중 많은 문법이 LL (1) 인 문법으로 변형 될 수 있습니다.

그러나 LL (1)이 아닌의 명확한 언어 의 예는 본 적이 없습니다. 다시 말하면, 언어에 대한 모호하지 않은 문법이 LL (1)이 아닌 언어), 우연히 우연히 만났을 때 내가 발견 한 것을 증명할 수있는 방법에 대한 생각이 전혀 없습니다.

누구나 명확한 모호하지 않은 언어가 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)로 만들려고합니다. 해결할 수없는 충돌을 발견 한 후에는 어떻게 든 그것을 활용하고 증거를 만들어야합니다.