람다 프로덕션의 단순화, 단항 규칙 및 문법의 유용하지 않은 기호

Question

저는 이것이 일반적인 질문이 아니라는 것을 알고 있습니다. 그러나 나는 이미 약간의 작업을하고있는 예제를 가지고 그것을 어떻게 수행하는지 알고 싶습니다. 그것 ... 한 번이 말했다 :

나는 다음과 같은 문법을 가지고있다. 나는 그것을 단순화하려고 노력했지만 그 정확성을 확신 할 수 없다. 누군가 올바른지 아닌지를 확인해 줄 수 있을까? 나는 비 유용 상징을 제거 할 필요가 마침내

S -> BC | B | C 
A -> aA | a 
B -> bB 
C -> c 

그리고 : 나는 같은 것을 가지고 어디 처음 람다 검진을 적용 문법 단순화해야하는 경우

S -> BC | lambda 
A -> aA | lambda 
B -> bB 
C -> c 

을 첫째로 나는 사람을 제거 불필요한이기 때문에

S -> BC | bB | C 
A -> aA | a 
B -> bB ---> non-productive 
C -> c 

S -> C | b | C 
A -> aA | a --> unreacheable 
C -> c 

마지막으로 나는 이런 식으로 뭔가를 내가 C 제거 있습니다 .. unreacheable있는 것들 그럼 생산적이고되지 않습니다 d 나는 또한 제거 되었기 때문에 BC를 제거합니다. 그래서 다음과 같아야합니다 : S -> b | C

그러나 내가 정직하면 내가 무슨 짓을했는지는 정확하다고 생각하지 않습니다하지만 난 몰라 정확히

Answer 1

당신의 단순화 몇 가지 문제가있을 수 있습니다처럼 보이는 - 혹은 내가 ' 그 다음에 문제가있다. 내가 할 일을 진행할 것이고 당신은 당신의 이해와 비교할 것입니다. 나는 목표를 추정

S -> BC | lambda 
A -> aA | lambda 
B -> bB 
C -> c 

가능한 한 lambda 많은 비 터미널 심볼을 제거하는 것입니다. 첫 번째로 주목해야 할 것은 언어를 변경하지 않고서는 생산물 S -> lambda을 삭제할 수 없다는 것입니다. 다른 모든 lambda 작품은 삭제할 수 있습니다. 우리는 하나의 다른 생산물을 볼 수 있으므로 그것이 제거 될 수 있음을 확신합니다. A -> lambda을 어떻게 제거합니까?

A에 도달 할 수 없습니다. 시작 기호는 S입니다. 따라서 A을 완전히 제거하여 A -> lambda을 쉽게 제거 할 수 있습니다. 우리는이 간단한 등가, 문법에 도착 :

S -> BC | lambda 
B -> bB 
C -> c 

지금, 우리의 목표는 (우리가 이미 모든 외부 -> lambda 제작을 제거했다) 우리가 S, B 및 C 볼 수 있습니다 비 - 터미널 심볼을 제거하기 때문이다. 우리는 시작 기호가 필요하다는 것을 알고 있으므로 S을 그대로 유지할 수 있습니다. B은 비 터미널을 포함하는 bB 만 생성 할 수 있습니다. bB은 결코 비 터미널 만의 문자열로 이어질 수 없습니다. B은 비생산적이며이를 제거 할 수 있습니다.비생산적 인 기호를 제거하면 연결된 표현식이 비단 (non-terminals) 문자열에만 도달 할 수 없으므로 제거해야합니다 (비생산적인 기호가 나타나는 연결 식은 비생산적입니다) :

S -> lambda 

이 문법은 단순한 용어이며, 최소한의 : C에 분석을 적용 는

S -> lambda 
C -> c 

, 우리는 쉽게이 처음이었고, 그래서이 같은 방법으로 제거 할 수있는 도달 할 수없는 A 같다 참조 비 터미널 기호 및 언어 {lambda}.