문맥 자유 문법 - 이해하게 도와주세요

Question

나는 Tom Simpson의 "Understanding Computation"이라는 책을 읽었습니다. (그런데 훌륭한 책입니다. 그런데 저에게 많은 것을 가르쳐 주었고 저와 같은 누군가를위한 값진 자원이었습니다. 공식화 된 수학 교육이지만 컴퓨터 과학에 대해 더 잘 이해하고 싶습니다. 매우 추천합니다!) 그리고 우리는 Context Free Grammar (CFG)에 대해서 이야기하고 있습니다. 충분한 정신 모형을 개발할 수 없었던 CFG에 대한 한 가지 중요한 점이 있습니다. 예를 들어 설명해 드리겠습니다.

이 책에서는 전체 프로그래밍 언어에서 볼 수있는 매우 엄격한 가능성의 하위 집합 만 처리 할 수있는 매우 제한된 CFG 예제 (단순함을 위해)를 의도적으로 사용합니다 (작은 따옴표로 표시된 내용은 토큰 , 꺽쇠 괄호 안에 물건) 문자를 나타냅니다 : 여기

<statement> ::= <while> | <assign> 
<while> ::= 'w' '(' <expression> ')' '{' <statement> '}' 
<assign> ::= 'v' '=' <expression 
<expression> ::= <less-than> 
<less-than> ::= <multiply> '<' <less-than> | <multiply> 
<multiply> ::= <term> '*' <multiply> | <term> 
<term> ::= 'n' | 'v' 

방법의 몇 가지 예입니다 - 내 현재의 정신 모델을 사용하여 - 나는이 소리의 일부를 읽을 것이다 것은 :

"A 문은 while 루프 될 수 있습니다 또는 할당 "
이 제한된 예제의 목적 상, 이것은 나에게 완벽하게 이해된다.

"용어는 ​​숫자 리터럴 또는 변수 중 하나 일 수 있습니다."
다시 말하지만, 제한된 범위에서 볼 때 이것은 나에게 이상적입니다.

"곱셈은 다른 곱셈 또는 항을 곱한 용어가 될 수 있습니다."
좋아, 이제 조금 놀래키! less-than를 곱하면되는 것을 허용하는 "out"을주는 것이이 모든 것을 작동시키는 기본 마법의 일부라는 것을 이해합니다 (즉, 우리의 비 결정적 푸시 다운 오토 마톤이 모든 것을 탐색 할 수있는 메커니즘입니다). 가능한 조합), 논리적으로 - 적어도 내가 읽고있는 방식으로 - 나는 이해할 수 없다. 왜 "OUT"(내가 부르는) 단지 이전 수준까지 밀어되지는 것이다 -하는 말 :

<expression> ::= <less-than> | <multiply> 

우리가 그것을 인 경우에 유효한보다 적게보다는 확인합니다 몇 가지 이유가 먼저 우리가 그것보다 적은 것을 확립 한 경우에만 그 곱셈이되는지 확인하기 위해 검사를 추구한다.

Answer 1

. 당신은의 제품 및 b와 c의 합을 의미하는 첫 번째 표현식에 괄호를 사용했을 경우

a * (b + c) 

어떻게 우리는 CFG이 표현합니까? 합계는 양면에 제품이있는 더하기 기호가 될 수 있습니다. 그러나 제품 일뿐만 아니라 지수 또는 나눗셈 또는 물론 변수 또는 숫자 일 수도 있습니다. 또는 괄호 안의 표현식.

또한 곱셈과 덧셈은 연관 적이지만 모든 수학 연산자가 아닙니다. 예를 들어, 9 - (5 - 2)는 (9 - 5) - 2와 다르며, 관례 상 9 - 5 - 2는 두 번째를 의미하는 것으로 간주됩니다. 따라서 뺄셈은 오른쪽에 다른 빼기가있을 수 있지만 왼쪽에는 없습니다 (괄호로 묶지 않는 한).

비슷한 관찰이 비교에 적용됩니다. 다음에서 :

a + b < 3 * c 

의도는 비교 결과에 대한 산술을하기보다는 태양을 제품과 비교하는 것입니다.

Answer 2

응답은 <less-than>이 중첩 될 수 있다고 생각합니다. <less-than>은 (<multiply> < <less-than>) 또는 간단히 <multiply> 일 수 있습니다.

이론적으로 | <multiply>을 <expression>에 복제 할 수 있지만 단순히 중복됩니다. 어느 쪽이든, (< <less-than>) 계속되는 경우 <less-than>을 설명대로 "출력"해야합니다.

예를 들어, 질문에 정의 된 문법은 다음과 같은 사항에 대해 유효한 것 :

v=n<v 

당신이 XML 표기법을 용서하면 당신은 (얻을, 그것은 내가 설명하는 가지고 올 수있는 최선이었다 내 포인트) :

<statement> 
    <assign> 
     v 
     = 
     <expression> 
      <less-than> 
       <multiply><term>n</term></multiply> 
       &lt; 
       <less-than> 
        <multiply><term>v</term></multiply> 
       </less-than> 
      </less-than> 
     </expression> 
    </assign> 
</statement> 

하지만 | <multiply>으로 <less-than>를 정의하지 않은 경우, 최종 "V"가 이상합니다 (<multiply><term>v</term></multiply>)는 문법의 모든 정의를 충족하지 않습니다 (더 나은 아직 정의 <less-than>w ould 끝내지 마라!당신이 그 문제에

c + a * b 

당신은 아마 C의 합 a와 b의 제품을 의미 들어,

a * b + c 

쓰기 또는 경우)