문맥 자유 문법 파스 트리

Question

나는 x와 y가 같은 수의 문자열을 가지고있다. CFG는 xy, xyxy, xyxyxy, xxxyyy 및 xxyxyy 형식으로 받아 들여야합니다.

것은 나는이 생산 규칙 올라와있다 :

S -> SAB | 전자 ​​

A -> xSy | 전자 ​​

B -> ySx | 전자 ​​

을 임 파스 트리를 만드는 작업,하지만 완전히 이해하지 오전. 이것은 내가 위의 파스 트리가 xyxy를 나타냅니다 제대로 이해하고있는 경우

         S 
           /| \ 
            S A B 
           // | \ \ 
           e x S y e 
            /| \ 
            S A B 
           // | \ \ 
           e x S y e 
             | 
             e 

일을 .... 내가

방법이 XXYY을 상징 하는가 계속하면 이렇게 한 한 무엇인가?

어떻게 xxyxyy를 나타낼 수 있습니까? 이것은 내가 이해하고 있지 않다 무엇

...

Answer 1

첫째, 트리에 대한 올바른 읽기 순서 무엇이 확실하지 않다 - 나는 비교 (그것이 일반적으로 거의 모든 함께있는 순서, 원인의 가정 the Wikipedia article on tree traversals) 그러나 나는 그것이 맞다는 것을 절대적으로 확신하지 않는다.. (이것이 틀린 경우 다른 나무가 필요하지만 아이디어는 번역해야합니다.)

예제 트리는 xxyy을 나타냅니다. 추가로 S - A - S - A - ... 체인을 가장 하단의 ε으로 대체하면 xx…yy의 임의 체인이 생성됩니다.

xy…xy을 표현하기 위해, 당신은 xSy 또는 ySx에 A들과 B의 확대 대체 것, 즉 : S → SAB, 다음 B → ε 및 A → xSy; 다음 계층에서 S → SAB을 다시 확장하십시오. 대신 이제 A → ε 및 B -> ySx을 수행하십시오. 필요한 경우 계속하십시오. 예 :

  S 
      /|\ 
     /| \ 
     S A B 
     //|\ \ 
     ε/| \ ε 
     x S y 
      /|\ 
     /| \ 
     S A B 
     // /|\ 
     ε ε/| \ 
      y S x 
       | 
       ε 

이 xyxy 일치해야하고, 다시 긴 시퀀스 하단에 확장 할 수 있습니다.

공간 절약을 위해 구문 분석 트리의 루트에서 "척추"라는 가장 긴 경로를 호출합니다. (여기에있는 간단한 예제의 경우 모든 "척추"경로는 편리하게 끝 기호입니다. 따라서 나무에 대한 설명은 고유합니다 (충분히). 일반적으로 '측면 경로'는 더 복잡하므로이 정의는 일반적으로 쓸모가 없습니다. , 잘 작동합니다.)

여기에 그려지는 나무의 경우 "척추"는 SASBSε (가운데를 읽음)입니다. 임의의 중첩을 위해 확장되면 (SASB)*(SA)?Sε이됩니다.

위의 그림에서 나무가 "척추"SASASε이고 임의로 긴 시퀀스가 ​​xxx…yyy 인 경우 (SA)*Sε이됩니다.

xxyxyy은 동일한 방식으로 쉽게 설명됩니다. "척추"는 SASASBSε입니다.일반적

(이 문법) "역 - 대칭"의 임의의 시퀀스 (후반전 반전 전반하고 X/Y 교환 - 즉 x|y, xyx|yxy, xxy|xyy가, ...), 사용자가 구성 할 수있다 첫 번째 절반을 가져다가 x → SA, y → SB을 확장하고 중간에 도달하면 Sε을 추가하여이 '척추' (물론, xxyyyx과 같은 복잡한 패턴의 경우 실패합니다. 이러한 비대칭 패턴에 대한 트리를 신속하게 찾아내는 방법을 찾는 것은 독자의 연습 과제로 남겨 둡니다.)