중복 괄호가없는 산술 식의 모호하지 않은 문법

Question

중복 괄호가없는 산술 식의 모호하지 않은 문법을 찾고 있습니다. 예를 들어, 괄호는 id+(id*id)에는 중복되지만 (id+id)*id에는 없습니다.

Answer 1

'중복 괄호가없는 산술 표현식'의 의미에 따라 달라집니다. 이없이 중복 괄호 표현을 받아 들일 것뿐만 아니라 임의의 중첩 된 괄호를 받아 들일 것입니다 :

expr ::= factor 
expr ::= factor mul_div factor 

mul_div ::= '*' | '/' 

factor ::= term 
factor ::= term add_sub term 

add_sub ::= '+' | '-' 

term ::= NUMBER 
term ::= '(' expr ')' 

나는 그 숫자를 가정하고있어 서명 숫자를 인식하는 관리, 그래서 단항 플러스 또는 마이너스가 거기에 없다. 필요한 경우 처리 방법을 알아낼 수 있습니다. 필요한 경우 변수 등을 추가 할 수도 있습니다.

불필요한 괄호가있는 표현식을 거부하는 문법을 의미하는 경우 문맥이없는 문법이 아닌 항목을 검색하고 있다고 생각합니다.

Answer 2

쉽게 할 수 있습니다. 괄호가 필요하게되는 유일한 시간은 곱 표현식의 조각 중 하나로 합계 표현식이 있거나 나누기 표현식 중 하나의 두 번째 조각으로 표현식이있는 경우입니다. 이 경우 두 경우 괄호 안의 자료에 적어도 하나 이상의 맨손 연산자 (추가 괄호로 묶이지 않음)가 있어야 괄호가 중복되지 않도록 할 수 있습니다.

나는 내가별로 좋아하지 않는 입학 시험이나 숙제에 대한 질문에 답할 수있을 것이라고 생각하지만, 불가능하다고하거나 불가능하다고 제안하는 사람들은 모두 잘못되었습니다. 나는 그들을 똑바로 세우고 싶었습니다. .

당신은 같은 표현을 구문 분석 할 :

expr  ::= expr addsub term 
expr  ::= prodterm 
expr  ::= value 

sum  ::= expr addsub term 

addsub ::= '+' | '-' 

term  ::= prodterm 
term  ::= unit 

prodterm ::= term '*' unit 
prodterm ::= term '/' produnit 

unit  ::= '(' sum ')' 
unit  ::= value 

produnit ::= unit 
produnit ::= '(' prodterm ')' 

value  ::= '0-9'* 

고독한 값 주위에 괄호를 가질 수 없어. 단위는 곱셈 표현식의 서브 표현식입니다. produnits는 부서 표현에 괄호 안에있는 꼬리를 허용합니다. (5)는 (값)이 될 수 있는데, 이것은 단지 프로덕트와 유닛들만 괄호를 가지고 있기 때문에 괄호 안에 산술 연산자가 필요합니다. (값)은 어떤 표현식에서도 파생 될 수 없으며, ((anything))은 가능하지 않습니다. 왜냐하면 produnit과 unit 만 괄호를 파생하기 때문입니다. 가깝게 보면, produnit은 괄호가 파생 된 경우 또는 괄호없이 값으로 해석 될 경우 * 또는 a /가 필요합니다. 단위는 + 또는 -가 필요하거나 괄호가 없습니다.

((5 + 6))은 (5 + 6)이 (가) 유닛으로 만 구문 분석 할 수 있기 때문에 실패합니다. 단점으로 간주 할 수는 있지만 단독으로 주변에 괄호를 넣을 방법이 없습니다. 고독한 produnit의 주위에 괄호에있는 단위 또는 produnit.

나는 당신의 선택을 무너 뜨릴 것입니다 : 5 * (6 * 7)은 구문 분석하지 않습니다 - 이것은 단위를 말한 용어입니다. 그러나 생각할 것입니다. 그렇지만 (6 * 7)은 단위가 아닙니다. 하나 이상의 합이있는 표현식 주위에 값 또는 괄호 여야합니다. 하나 이상의 합이 발생하면 괄호는 사소하지 않습니다. 반면에 5/(6 * 7)은 5/6 * 7과 같지 않습니다. 첫 번째는 5/6/7이고 두 번째는 5 * 7/6과 같습니다. 그러나 5/(6)은 5/6과 동일하므로 괄호 안에 단일 값을 사용할 수 없습니다. 마찬가지로 5/(6/7)은 5/6/7과 같지 않습니다. 첫 번째 것은 5 * 7/6이고 두 번째는 5/(6 * 7)과 같기 때문입니다. 즉, 내부에 맨손으로 연산자가있는 경우 분모 주변의 괄호는 절대 관계가 없습니다.

(5 + 6) +7 또한 합계의 왼쪽 (및 오른쪽)이 엄격한 값이거나 합계 주위에 괄호가없는 합계 또는 제품 주위에 괄호가없는 제품이므로 불가능합니다.방향을 바꿀 수는 없습니다

자신이 자신을 납득시킬 수 있으며, 모호하지 않은지 직접 확인할 수 있습니다. 당신은 exponentiation 연산자를 포함하도록 확장하거나 더 높은 우선 순위 연산자 또는 == 또는 <과 같은 우선 순위 연산자를 더 잘 일반화하여 더 잘 보임을 증명할 수 있습니다.

도움이 되었기를 바랍니다.