모호함

Question

질문

는 문맥 자유 문법을 보여준다.

어떻게 문자열이 모호한 지 알 수 없습니까? 컴파일러와 자기 학습에 관한 책을 읽었을 때 나는 책에서이 질문을하고 있었고 나는 혼란 스럽다.

가능한 솔루션 내 솔루션은 정확하고 누군가가 나를 인도하시기 바랍니다 수없는 경우 경우

abaca   abaca 
a(aba)aca  aba(aca)a 

사람이 확인할 수 있습니다.

Answer 1

펜과 종이로하는 것이 훨씬 쉽습니다. 모든 가능성 중에서, 나는 초기 기호 S을 도출함으로써 세 가지 가능성을 열거한다.

S -> SbS -> abS -> abScS -> abacS -> abaca 
S -> ScS -> Sca -> SbSca -> abSca -> abaca 
S -> SbS -> SbScS -> abScS -> abSca -> abaca 

다른 것들도 있습니다.보기가 어렵지 않습니다. 그러나 종종 문자열 (abaca)을 원래 기호 (S)로 줄이는 것이 더 쉽습니다. 많은 컴파일러이 무한 재귀 피하기 위해 않습니다

abaca <- Sbaca <- SbSca <- Sca <- ScS <- S 
abaca <- abacS <- abScs <- abS <- SbS <- S 

할 수있는 방법을 손, 방법 (유도 또는 감소)를 선택 한 후 시행 착오에 의해 당신에 따라 만들 수있는 가능한 대체를, 이동하여이있다 문법은 당신을 나무로 이끌 것입니다. 트리에서 목표로 연결되는 노드 (원래 기호 또는 최종 문자열)가 올바른 노드입니다. 둘 이상의 경로가있는 경우 모호합니다.

---

이제, 이러한 유도하고, 다른 사람의 각각은 Parse Tree 소위를 생성합니다. 구문 분석 트리는 초기 기호에서 터미널 문자열을 생성 할 수있는 파생 집합을 나타냅니다. 파스 트리를 더 잘 시각화하기 위해 웹에서 이러한 종류의 트리를 그리는 도구를 찾았습니다. 찾을 수있는 도구는 here입니다.

사용하는 형식은 [NonTerminal terminal [NonTerminal terminal] terminal]입니다. 괄호 대신 대괄호가있는 Lisp과 유사한 목록입니다. 예를 들어 내가 작성한 첫 번째 파생어 인 S -> SbS -> abS -> abScs -> ...은 [S [S a] b [S [S a] c [S a]]]으로 쓸 수 있습니다. [S [S ...] b [S ...]]은 첫 번째 파생을 나타내며, 다음으로는 [S ...]을 두 번째 파생어로 [S a]으로 확장하는 식입니다. 희망이 도구는 귀하의 공식 문법 학습에 도움이!