비 결정적이고 비 효과적 인 문법?

Question

wikipedias GLR description에 따르면, 그들은 "비 결정적이고 모호한 문법을 ​​처리합니다." dangling else problem과 같이 모호한 문법을 ​​시각화 할 수 있지만 모호하지 않은 비 결정적 CF 문법이란 무엇입니까?

Answer 1

거의 모든 비 LR (k) 문법은 비 결정적이지만 반드시 모호하지는 않습니다. 분명한 것은 두 가지 방법으로 파싱 할 수있는 큰 크기의 구조가 있고 큰 구조 후 뭔가에 따라 달라지는 경우입니다. 예 : 결정되도록 큰 구조를 분석의 두 가지 방법은 (a 결정적 상기 문법 S ::= A x | A y과 같이 결합 될 수 있는지

그러나

S ::= A x | B y 
A ::= A a | a 
B ::= B a | a 

같은 더 결정적 문법은 종종 재생산 될 수 없다 같은 언어를 파싱하는 방법)

더 흥미로운 것은 언어에 대한 결정 론적 문법이 없다는 것입니다. 이를 위해서는 임의적으로 큰 구조 안에 무언가가 있어야합니다. 예 :

S ::= X x | Y y 
X ::= a X a | x 
Y ::= a Y a | y