표현식을 사용하여 Bitwise 연산자로 문법이 모호하다는 것을 나타내는 방법 a >> b^c

Question

이 질문을 해결하려고하지만 실제로 시작하는 방법을 모르겠습니다. 나는 약간의 도움에 감사 할 것입니다.

언어에 대한 비트 연산자는 문법과 함께 아래 표에 표시됩니다. 연산자와 문법 규칙은 우선 순위가 가장 높은 순서대로 순서가 지정됩니다. 문자 a, b 및 c는 해당 언어의 터미널을 나타냅니다.

문법 테이블 :

1. 문법 모호하여 표현임을 확인 : >> B가 모호하지 않도록^C
2. 문법을 재 작성.

Answer 1

드래곤 책은 말한다 : "어떤 문장에 대해 둘 이상의 파스 트리를 생성하는 문법 모호한이라고합니다." 따라서 문법이 모호하다는 것을 보여주기 위해서는 문법에 의해 생성 된 단일 문장에 대해 적어도 두 개의 구문 분석 트리를 표시해야합니다. 이 경우 이미 사용할 문장이 이미 주어져 있으므로 Q1의 경우 a >> b^c에 대해 두 개의 다른 구문 트리를 찾아야합니다. Shiping의 의견은 당신에게 큰 단서를 제공합니다.

Q2에서 "문법 다시 쓰기"를 묻는 질문에 대해서는 결과 문법이 원래 언어와 정확히 동일한 언어를 생성한다는 암묵적인 요구가 있다고 생각됩니다. 그래서 언어에 괄호를 사용하는 Shiping의 제안은 받아 들여지지 않을 것입니다.이를 수행하기위한 일반적인 접근법은 우선 순위 차트의 각 우선 순위 수준에 대해 비 터미널을 도입 한 다음 그러한 비선 점에서 새로운 비 터미널을 사용하도록 문법 규칙을 수정하는 것입니다. 문법은 우선 순위 차트를 존중하는 구문 분석 트리 만 생성 할 수 있습니다.

예를 들어, Q1에서 찾은 두 나무를보십시오. 그 중 하나는 우선 순위 차트를 따르고 하나는 준수하지 않는 것을 관찰해야합니다. 선행을 따르는 트리는 허용하지만 다른 것은 허용하지 않는 새로운 문법을 원합니다.

E -> E + E 
E -> E * E 
E -> a | b 

및

E -> E + T 
T -> T * F 
F -> a | b 

그들은 같은 언어를 생성하지만

, 첫 번째는 모호하지만 두 번째가되지 않습니다 :

다른 단서로서,이 두 문법의 차이를 고려한다.