프로그래밍 언어론 - 유도 예제 문제, 풀이(좌측 유도)

 - 좌측 유도(leftmost derivation) : 각 직접 유도 단계에서 가장 왼쪽 넌터미널을 선택하여 이를 대상 으로 생성 규칙을 적용한다.

 

 - 문법

  <S> ::= <A> | <A><S>

  <A> ::= <Id> | (<B>

  <B> ::= <Id>] | <Id><B> | (<B>

  <Id> ::= 0 | 1

 

문법이 위와 같이 주어졌을 때 아래의 문제를 좌측 유도하라.

 

1번 문제 : ( 0 1 ( 1 ] ( ( 1 0 ] 1 

<S>

 => <A><S>

 => (<B><S>

 => (<Id><B><S> 

 => (<Id><Id><B><S>

 => (<Id><Id>(<B><S>

 => (<Id><Id>(<Id>]<S>

 => (<Id><Id>(<Id>]<A><S>

 => (<Id><Id>(<Id>](<B><S>

 => (<Id><Id>(<Id>]((<B><S>

 => (<Id><Id>(<Id>]((<Id><B><S>

 => (<Id><Id>(<Id>]((<Id><Id>]<S>

 => (<Id><Id>(<Id>]((<Id><Id>]<A>

 => (<Id><Id>(<Id>]((<Id><Id>]<Id>

 => ( 0 1 ( 1 ] ( ( 1  0 ] 1 : 유도 가능

 

2번 문제 : 0 ( 1 0 ( 1 ]

<S>

 => <A><S>

 => <Id><S>

 => <Id><A>

 => <Id>(<B>

 => <Id>(<Id><B>

 => <Id>(<Id><Id><B>

 => <Id>(<Id><Id>(<B>

 => <Id>(<Id><Id>(<Id>]

 => 0 ( 1 0 ( 1 ] : 유도 가능

 

3번 문제 : ( 0 ( 1 0 1 ] 0 ]

<S>

=> <A><S>

=> (<B><S>

=> (<Id><B><S>

=> (<Id>(<B><S>

=> (<Id>(<Id><B><S>

=> (<Id>(<Id><Id><B><S>

=> (<Id>(<Id><Id><Id>]<S>

 

<S>를 <A>로 유도한 경우

1. => (<Id>(<Id><Id><Id>]<A>

    => (<Id>(<Id><Id><Id>]<Id>

           or (<Id>(<Id><Id><Id>](<B> : 유도 불가

 

<S>를 <A><S>로 유도한 경우

2. => (<Id>(<Id><Id><Id>]<A><S>

    => (<Id>(<Id><Id><Id>]<Id><S>

    => (<Id>(<Id><Id><Id>]<Id><A>

    => (<Id>(<Id><Id><Id>]<Id><Id>

           or (<Id>(<Id><Id><Id>]<Id>(<B> : 유도 불가

 

 이 경우 맨 마지막의 0 ] 두 문자를 문제의 문장과 같이 구성할 수 있어야 한다. 그렇지만 위의 1, 2 에서 보이는 것처럼 뒤에 대괄호를 유도할 수 없거나 필요없는 소괄호가 앞에 생기거나 문제의 주어진 문자의 개수를 넘어버리는 문제가 생긴다.

 

3번 문제 다른 순서의 유도

<S>

=> <A>

=> (<B>

=> (<Id><B>

=> (<Id>(<B>

=> (<Id>(<Id><B>

=> (<Id>(<Id><Id><B>

 => (<Id>(<Id><Id><Id>]

       or (<Id>(<Id><Id>(<B>

       or (<Id>(<Id><Id><Id><B> : 유도 불가

 

 이 경우 위의 1, 2의 유도에서는 맨 뒤의 두 문자를 빼고 모두가 완성되었지만 뒤의 두 문자를 문제의 문장과 같이 유도하는 것이 불가능했으므로 처음에 <S> => <A> 로 바로 유도를 시작해보았습니다. 마찬가지로 유도불가.

 

<S>

 => <A><S>

 => <A><A>

 => (<B>(<B>

 => (<Id>](<B> : 유도 불가