Грамматика (BNF) и обратная польская нотация
| 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/ | инфиксная запись |
The notation with no brackets, and no ambiguity
- Write
3 + 4 * 2and you are relying on a convention: that multiplication binds tighter than addition. Change the convention and the expression means something else. - A Polish logician, Jan Łukasiewicz, showed in the 1920s that if you put the operator before its operands the brackets become unnecessary. Reverse it, putting the operator after, and you get a form a machine can evaluate with nothing but a stack.
- That is why the Java Virtual Machine and most bytecode interpreters work in postfix. No precedence table, no brackets, no ambiguity.
- This lesson is how a language's grammar 文法 is written down, in BNF and as a syntax diagram, and how Reverse Polish Notation 逆波兰表示法 is converted and evaluated.
Backus-Naur Form
- A grammar says which sequences of tokens are valid programs. Backus-Naur Form 巴科斯-诺尔范式 (BNF) writes it as production rules 产生式:
<symbol> ::= alternative1 | alternative2 | ...
- A terminal 终结符 symbol is literal text that appears in the program. A non-terminal 非终结符 symbol is the name of another rule, written in angle brackets.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
В BNF терминальный символ — это:
Терминалы — это буквенные токены; нетерминалы — имена других правил вывода.
Recursion is how BNF repeats
- BNF has no "repeat" symbol, so repetition is written by defining a rule in terms of itself.
- Read
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>as: an identifier is a single letter, or an identifier followed by a letter, or an identifier followed by a digit. - Together those alternatives mean "a letter followed by any number of letters or digits", which also explains why an identifier cannot start with a digit: no alternative allows it.
- A syntax diagram 语法图, or railroad diagram, expresses the same rules graphically, with a loop where BNF uses recursion. The two notations are equivalent.
The loop and the recursion say the same thing
Соотнесите каждый термин грамматики/нотации с его значением.
BNF строит правила из терминалов и нетерминалов (рекурсия обеспечивает повторение); RPN переставляет выражение, чтобы избавиться от скобок.
Почему правило
Все альтернативы вместе означают букву, за которой следует любое количество букв или цифр, и ни одна альтернатива не позволяет начать с цифры.
Worked example: test a string against the grammar
- Using the rules above, which of
count2,2countandmy_varare valid identifiers? count2: valid. Build it up:cis a<letter>, so an<identifier>; addo,u,n,tby the second alternative; add2by the third.2count: invalid. Every alternative starts from a<letter>or from another<identifier>, and no chain can begin with a digit.my_var: invalid, because_is not a terminal in any rule here. State the rule that fails, not just "it looks wrong".
Используя эти правила, какие строки являются допустимыми идентификаторами? Выберите все подходящие варианты.
Одна буква является идентификатором согласно первой альтернативе. 2count не может начинаться с цифры, а _ не является терминалом ни в одном из этих правил.
Infix and postfix
- Infix 中缀 puts the operator between its operands,
3 + 4 * 2, and therefore needs precedence rules and brackets to be unambiguous. - Reverse Polish Notation, or postfix 后缀, puts the operator after its operands:
3 4 2 * +. It needs neither. - The order in which the operators appear in the postfix form is the order they are applied, which is exactly what a machine needs to be told.
Converting infix to postfix
- Use an operator stack. Scan left to right: send an operand straight to the output; for an operator, first pop to the output any stacked operators of higher or equal precedence 优先级, then push it.
- Push an opening bracket. On a closing bracket, pop to the output until the matching opening bracket, then discard the pair.
- At the end, pop everything left on the stack to the output.
Приоритет операторов — то, что убирает обратная польская нотация
В обычной инфиксной математике × и ÷ имеют более высокий приоритет, чем + и −, поэтому правила применяются в правильном порядке. Обратная польская нотация записывает операнды сначала (3 4 2 × + 1 −), фиксируя порядок так, что правила приоритета не нужны.
Какова форма RPN (постфиксная) для инфиксного выражения (3 + 4) * 2?
Скобки вынуждают сначала вычислить 3+4: 3 4 +, затем умножить на 2: 3 4 + 2 *.
Преобразуйте (A + B) * (C - D) в обратную польскую нотацию, используя * для умножения.
Каждая скобка преобразуется по очереди, а умножение извлекается последним, поэтому оно оказывается в конце. Скобок не остается.
Worked example: convert, then evaluate
- Convert $(A + B) \times (C - D)$ to RPN. Push
(; outputA; push+; outputB; on)pop back to the matching(, givingA B +. Push×. The second bracket behaves identically, givingC D -. At the end pop the×. Result:A B + C D - ×. - Now evaluate it for $A=3, B=4, C=5, D=2$. Push 3, push 4;
+pops both and pushes 7. Push 5, push 2;-pops both and pushes 3.×pops 7 and 3 and pushes 21. - The operator always takes the top two items, and the first popped is the right-hand operand. That matters for
-and/, where order changes the answer.
Вычислите RPN-выражение 3 4 2 * +.
Положите 3, 4, 2; * извлекает 4 и 2 → 8; + извлекает 3 и 8 → 11.
Обратная польская нотация не требует скобок или таблиц приоритетов и может быть вычислена непосредственно с помощью стека.
Положите операнды; каждый оператор извлекает свои операнды и помещает результат — именно так работает машина со стеком.
Evaluating with a stack, step by step
- Scan left to right: push each operand; on an operator, pop the top two, apply it, and push the result. At the end the stack holds one value: the answer.
| Token | Stack after |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- This is a stack machine: no brackets, no precedence table, no lookahead. It is how the JVM and many bytecode interpreters evaluate every expression.
При вычислении RPN первый элемент, извлеченный из стека, является левым операндом оператора.
Первый извлеченный элемент — правый операнд. Для + и * это не имеет значения, но изменение порядка нарушает вычитание и деление.
Расставьте шаги вычисления 3 4 2 * + со стеком в правильном порядке.
Операнды кладутся, каждый оператор потребляет два верхних элемента и оставляет результат. Скобки и таблица приоритетов не нужны.
Marks that slip away
- A terminal is literal text; a non-terminal names another rule. Do not swap them.
- BNF expresses repetition by recursion. If a rule refers to itself, say so and say what it means.
- In evaluation the operator takes the top two items, and the first one popped is the right operand. Getting that backwards breaks subtraction and division.
- RPN needs no brackets. Writing brackets into a postfix answer loses the mark it was testing.
You've got it
- BNF production rules combine terminals (literal text) and non-terminals (rule names), and express repetition by recursion; a syntax diagram is the equivalent graphical form
- test a string by building it from the rules, and name the rule that fails when it is invalid
- infix needs precedence and brackets; RPN (postfix) puts the operator after its operands and needs neither
- convert with an operator stack, and evaluate by pushing operands and applying each operator to the top two, the first popped being the right-hand operand