문법 규칙 세트에서 파생 트리 만들기

Question

문맥이없는 문법에 규칙 집합을 정의하는 2 개의 배열이 있습니다. 어레이 (1)를 왼쪽, 예를 들어 규칙 및 배열이 규칙의 우측되는 사이드하게하여이 가입일

A = B | C would translate to array1[0] = A, array2[0] = B C 

, I는 몇 단계를 정의 정수 주어진 모든 가능한 유도를 구성 할 발생할 수 있습니다. 예를 들어 A ---> C가 1 단계가됩니다. 정수가 3이면 프로그램은 3 단계에서 발생할 수있는 모든 유도를 인쇄합니다.

이 프로그램을 해결하는 방법에 대한 조언을 주시면 감사하겠습니다. 몇 시간 동안 문제를 해결할 수있는 방법을 생각해 보았습니다. 자바를 사용하고 있습니다.

감사합니다.

Answer 1

문자열 객체를 사용하여 파생어를 표현하기 때문에 시작 기호를 사용하고 구분 기호 ""를 사용하여 그 파생어를 분할 할 수 있습니다. 그런 다음 비 터미널에 대한 파생어를 올바른 순서로 검색하여 재귀 적으로 파생 시키려고 할 수 있습니다. 터미널 만 남아있는 경우 구조에 저장된 전체 파생을 인쇄 할 수 있습니다. 지. 모든 파생을 포함하는 목록 그런 다음 다른 옵션을 사용할 수있는 마지막 지점으로 돌아갑니다.

하지만 실제로는 효율적이지 않으므로 모델링이 좋지 않다고 생각합니다. 다루고있는 문제는 일반적으로 파서 구현에 의해 해결됩니다. 지. 컴파일러 구현. 이 리소스 (위키 피 디아) : Parsing을 살펴보십시오. 두 가지 주요 접근법이 있습니다 : 하향식 및 상향식 구문 분석.