| English | 의미 |
|---|---|
| postfix/ˈpəʊstfɪks/ | 포스트픽스 |
| precedence/ˈpresɪdəns/ | 우선순위 |
| grammar/ˈɡræmə/ | 문법 |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | 구문도 |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | 역폴란드 표기법 |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | 바쿠스-나우 형식 |
| production rules/prəˈdʌkʃn ruːlz/ | 생성 규칙 |
| terminal/ˈtɜːmɪnl/ | 종결 기호 |
| non-terminal/nɒn ˈtɜːmɪnl/ | 비종결 기호 |
| infix/ˈɪnfɪks/ | 인플릭스 |
괄호 없이 모호함 없는 표기법
3 + 4 * 2를 쓰면 곱하기가 더하기보다 결합 우선도가 높다는 관례에 의존하게 됩니다. 이 관례를 바꾸면 식의 의미가 달라집니다.- 1920년대에 폴란드의 논리학자 얀 루카시예비츠는 연산자를 피연산자 앞에 배치하면 괄호가 불필요함을 보여줍니다. 반대로 연산자를 뒤에 배치하면 스택 하나만으로 기계가 평가할 수 있는 형태가 됩니다.
- 바로 그 이유로 자바 가상 머신과 대부분의 바이트코드 인터프리터는 포스트픽스 방식으로 작동합니다. 결합 우선도 표나 괄호, 모호함이 없습니다.
- 이 수업에서는 언어의 문법이 BNF와 구도 다이어그램으로 어떻게 기술되고, 역폴란드 표기법이 어떻게 변환 및 평가되는지 다룹니다.
바쿠스-나우르 형식
- 문법은 유효한 프로그램인 토큰 시퀀스를 정의합니다. 바쿠스-나우르 형식(BNF)은 이를 생성 규칙으로 씁니다:
<symbol> ::= alternative1 | alternative2 | ...
- 종단 기호는 프로그램에 나타나는 Literal 텍스트입니다. 비종단 기호는 다른 규칙의 이름이며 각괄호 안에 씁니다.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
BNF에서 단말 기호(terminal symbol)란:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
단말 기호는 리터럴 토큰이며, 비단말 기호(non-terminal)는 다른 생성 규칙의 이름입니다.
재귀가 BNF에서 반복을 구현하는 방법
- BNF에는 '반복' 기호가 없으므로, 반복은 규칙을 자신에 대한 식으로 정의함으로써 표현됩니다.
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>를 읽으면: 식별자는 단일 문자, 또는 식별자에 문자가 이어진 것, 또는 식별자에 숫자가 이어진 것입니다.- 이러한 대안들은 합쳐서 "문자 뒤에 임의의 개수의 문자 또는 숫자가 오는 것"을 의미하며, 식별자가 숫자로 시작할 수 없는 이유(모든 대안이 숫자로 시작하지 않기 때문)도 설명해 줍니다.
- 구도 다이어그램, 또는 철도 다이어그램은 동일한 규칙을 그래프로 표현하며, BNF의 재귀 대신 루프를 사용합니다. 두 표기법은 동치입니다.
루프와 재귀는 같은 내용을 말합니다
각 문법/표기법 용어에 해당하는 의미를 매칭하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
BNF는 단말과 비단말 기호로부터 규칙을 구성하며(재귀가 반복을 제공), RPN은 괄호를 제거하기 위해 식을 재배열합니다.
규칙
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
대안들이 함께 nghĩa는 한 글자로 시작하고 이후 임의의 글자나 숫자가 이어진다는 것이며, 어떤 대안도 숫자로 시작할 수 있게 하지 않습니다.
풀이 예제: 문법에 대해 문자열 테스트하기
- 위 규칙을 사용하여
count2,2count,my_var중 어떤 것이 유효한 식별자입니까? count2: 유효함.构建它:c은<letter>이므로<identifier>;o,u,n,t을 두 번째 대안에 따라 추가;2을 세 번째 대안에 따라 추가.2count: 무효함. 모든 대안은<letter>또는 다른<identifier>에서 시작하므로 숫자로 시작하는 체인을 만들 수 없습니다.my_var: 무효함, 왜냐하면_이 여기의 어떤 규칙에서도 종단 기호가 아니기 때문입니다. "잘못-looking"이라고 말하기보다 실패하는 규칙을 명시하십시오.
위 규칙을 사용할 때 다음 중 유효한 식별자는 무엇입니까? 모두 선택하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
첫 번째 대안에 따라 단일 글자는 식별자입니다. 2count는 숫자로 시작할 수 없으며, _는 이 문법의 어떤 규칙에서도 단말 기호가 아닙니다.
infix와 postfix
- infix는 연산자를 피연산자 사이에 배치하여
3 + 4 * 2처럼 결합 우선도 규칙과 괄호가 모호함을 해결하기 위해 필요합니다. - 역폴란드 표기법, 또는 postfix는 연산자를 피연산자 뒤에 배치합니다:
3 4 2 * +. 이는 둘 다 필요로 하지 않습니다. - postfix 형태에서 연산자가 나타나는 순서는 실제로 적용되는 순서이며, 이것이 기계가 알야할 정확한 내용입니다.
infix를 postfix로 변환하기
- 연산자 스택을 사용합니다. 왼쪽에서 오른쪽으로 스캔합니다: 피연산자는 출력으로 바로 보내고, 연산자의 경우 먼저 더 높은 또는 동등한 결합 우선도를 가진 스택 내의 연산자를 모두 popped하여 출력에 보내고, 그 연산자를 스택에 push합니다.
- 여는 괄호를 push합니다. 닫는 괄호에 도달하면 매칭되는 여는 괄호까지 output에 pop하고, 쌍을 버립니다.
- 끝남에 스택에 남은 모든 것을 output에 pop합니다.
연산자 우선순위 — 역폴란드 표기법이 제거하는 부분
일반 중위 수식에서 ×와 ÷는 +와 −보다 결합력이 강하므로, 올바른 순서로 규칙을 적용해야 합니다. 역폴란드 표기법은 피연산자를 먼저 기록합니다(3 4 2 × + 1 −). 이로 인해 우선순위가 명확해져 별도의 우선순위 규칙이 필요 없습니다.
중위 식 (3 + 4) * 2의 RPN(후위 표기법) 형태는 무엇입니까?
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
괄호로 인해 3+4를 먼저 계산해야 하므로: 3 4 +, 이후 2를 곱해야 하므로: 3 4 + 2 *입니다.
(A + B) * (C - D)를 역폴란드 표기법으로 변환하십시오. 곱셈에는 *를 사용하십시오.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
각 괄호는 순서대로 변환되며, 곱셈 연산자는 마지막에 스택에서/pop되어 맨 뒤에 위치합니다.remaining parentheses are eliminated.
풀이 예제: 변환 후 평가하기
- 식 $(A + B) \times (C - D)$을 RPN으로 변환하십시오.
(을 스택에 적재합니다; 출력A;+을 적재합니다; 출력B;)에서-match하는(로 되돌아와A B +을 생성합니다.×을 적재합니다. 두 번째 괄호 역시 동일한 방식으로 동작하여C D -을 생성합니다. 마지막에×을 제거합니다. 결과:A B + C D - ×. - 이제 $A=3, B=4, C=5, D=2$에 대해 평가. 3을 push, 4를 push;
+이 두 값을 pop하고 7을 push합니다. 5를 push, 2를 push;-이 두 값을 pop하고 3을 push합니다.×이 7과 3을 pop하고 21을 push합니다. - 연산자는 항상 맨 위 두 항목을 취하며, 첫 번째로 pop된 것은 오른쪽 피연산자입니다. 이는
-과/에서 중요하며, 여기서 순서가 답을 바꿉니다.
RPN 식 3 4 2 * +을 계산하십시오.
난이도 2/5 · 140 코인 + 오늘 첫 완료 시 소액 보너스
3, 4, 2를 스택에 push합니다. *에서 4와 2를 pop하여 8을 얻습니다. +에서 3과 8을 pop하여 11을 얻습니다.
역폴란드 표기법은 괄호와 우선순위 규칙 없이 스택을 사용하여 즉시 계산할 수 있습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
피연산자를 push하고, 각 연산자는 피연산자를 pop하여 결과를 push합니다 — 이는 정확히 스택 머신이 작동하는 방식입니다.
스택을 이용한 단계별 평가
- 왼쪽에서 오른쪽으로 스캔: 피연산자를 각각 push; 연산자에 도달하면 맨 위 두 개를 pop하여 적용하고 결과를 push합니다. 끝남에 스택에는 하나의 값인 정답이 남습니다.
| 토큰 | 스택 상태 |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- 이는 스택 머신입니다: 괄호도 없고, 결합 우선도 표도 없으며, look-ahead도 없습니다. JVM과 많은 바이트코드 인터프리터가 모든 식을 평가하는 방식입니다.
RPN을 평가할 때 스택에서 먼저 pop되는 항목은 연산자의 좌변 피연산자입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
먼저 pop되는 것은 우변 피연산자입니다. +와 *에서는 차이가 없지만, 이를 반대로 하면 뺄셈과 나눗셈이 잘못됩니다.
스택을 사용하여 3 4 2 * +를 평가하는 과정을 순서대로 나열하십시오.
난이도 3/5 · 200 코인 + 오늘 첫 완료 시 소액 보너스
피연산자는 스택에 적고, 각 연산자는 최상단 두 값을 소모하여 결과를 남깁니다. 괄호와 우선순위 표가 필요 없습니다.
놓칠 수 있는 점
- 종단 기호는 Literal 텍스트이고, 비종단 기호는 다른 규칙을 가리킵니다. 서로 바꾸지 마십시오.
- BNF는 재귀를 통해 반복을 표현합니다. 규칙이 자신을 참조한다면 그렇다고 밝히고 그 의미를 명시하십시오.
- 평가 시 연산자는 맨 위 두 항목을 취하며, 첫 번째로 pop된 것은 오른쪽 피연산자입니다. 이를 반대로 하면 뺄셈과 나눗셈이 깨집니다.
- RPN에는 괄호가 필요 없습니다. 포스트픽스 답에 괄호를 넣으면 해당 점수를 잃게 됩니다.
이해했습니다
- BNF 생성 규칙은 종단 기호(Literal 텍스트)와 비종단 기호(규칙 이름)를 결합하며 재귀를 통해 반복을 표현하고, 구도 다이어그램은 그 동치인 그래픽 형식입니다.
- 규칙을 통해 문자열을 구성하여 테스트하고, 무효일 때 실패하는 규칙을 명시하십시오.
- 인픽 infix 연산자는 precedence와 괄호가 필요하지만, RPN(포픽 postfix) 은 연산자를 피연산자 뒤에 배치하여 둘 다 불필요합니다.
- 연산자 스택을 사용하여 변환하고, 피연산자를 적재한 뒤 각 연산자를 상위 두 개에 적용하여 평가합니다. 이때 먼저 제거된 것이 오른쪽 피연산자가 됩니다.