문맥 자유 문법의 모호성

문맥 자유 문법 G 일부 문자열에 대해 둘 이상의 파생 트리가 있습니다. w ∈ L(G), 그것은 ambiguous grammar. 해당 문법에서 생성 된 일부 문자열에 대해 맨 오른쪽 또는 맨 왼쪽 파생이 여러 개 있습니다.

문제

문법 G와 생산 규칙을 확인하십시오-

X → X + X | X * X | X | ㅏ

모호하거나 아닙니다.

문자열 "a + a * a"에 대한 파생 트리를 찾아 보겠습니다. 가장 왼쪽에 두 개의 파생물이 있습니다.

Derivation 1− X → X + X → a + X → a + X * X → a + a * X → a + a * a

Parse tree 1 −

Derivation 2− X → X * X → X + X * X → a + X * X → a + a * X → a + a * a

Parse tree 2 −

단일 문자열 "a + a * a"에 대해 두 개의 구문 분석 트리가 있으므로 문법은 G 모호합니다.