Грамматика (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/ | инфикс |
Нотация без скобок и двусмысленности
- Запишите
3 + 4 * 2и вы полагаетесь на соглашение: что умножение имеет более высокий приоритет, чем сложение. Измените соглашение, и выражение будет означать нечто иное. - Польский логик Ян Лукасевич в 1920-х годах показал, что если поставить оператор перед операндами, скобки становятся ненужными. Если же поставить оператор после, получится форма, которую машина может вычислить, используя только стек.
- Именно поэтому виртуальная машина Java и большинство интерпретаторов байт-кода работают в постфиксной нотации. Никакой таблицы приоритетов, никаких скобок, никакой двусмысленности.
- Этот урок о том, как записать грамматику языка с помощью BNF и диаграммы синтаксиса, а также как переводить и вычислять обратную польскую нотацию.
Формула Бэкуса-Наура
- Грамматика определяет, какие последовательности токенов являются допустимыми программами. Формула Бэкуса-Наура (BNF) записывает её в виде правил вывода:
<symbol> ::= alternative1 | alternative2 | ...
- Терминальный символ — это буквальная текст, который встречается в программе. Нетерминальный символ — это имя другого правила, записанное в угловых скобках.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
В BNF терминальный символ — это:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Терминалы — это буквенные токены; нетерминалы — имена других правил вывода.
Рекурсия в BNF
- В BNF нет символа «повторение», поэтому повторение записывается путем определения правила через само себя.
- Прочитайте
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>так: идентификатор — это одна буква, или идентификатор, за которым следует буква, или идентификатор, за которым следует цифра. - Совокупность этих альтернатив означает «буква, за которой следует любое количество букв или цифр», что также объясняет, почему идентификатор не может начинаться с цифры: ни одна из альтернатив этого не допускает.
- Диаграмма синтаксиса, или диаграмма железнодорожного пути, выражает те же правила графически, используя цикл там, где BNF использует рекурсию. Эти две нотации эквивалентны.

Цикл и рекурсия говорят одно и то же
Соотнесите каждый термин грамматики/нотации с его значением.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
BNF строит правила из терминалов и нетерминалов (рекурсия обеспечивает повторение); RPN переставляет выражение, чтобы избавиться от скобок.
Почему правило
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Все альтернативы вместе означают букву, за которой следует любое количество букв или цифр, и ни одна альтернатива не позволяет начать с цифры.
Разобранный пример: проверка строки на соответствие грамматике
- Используя правила выше, определите, какие из
count2,2countиmy_varявляются допустимыми идентификаторами? count2: верно. Постройте его:cявляется<letter>, значит,<identifier>; добавьтеo,u,n,tпо второму альтернативному правилу; добавьте2по третьему.2count: недопустим. Каждая альтернатива начинается либо с<letter>, либо с другого<identifier>, и никакая цепочка не может начинаться с цифры.my_var: недопустим, потому что_не является терминалом ни в одном из правил здесь. Укажите правило, которое нарушается, а не просто скажите «это выглядит неправильно».
Используя эти правила, какие строки являются допустимыми идентификаторами? Выберите все подходящие варианты.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Одна буква является идентификатором согласно первой альтернативе. 2count не может начинаться с цифры, а _ не является терминалом ни в одном из этих правил.
Инфиксная и постфиксная записи
- Инфиксная запись ставит оператор между операндами, например
3 + 4 * 2, и поэтому требует правил приоритета и скобок для устранения двусмысленности. - Обратная польская нотация, или постфиксная запись, ставит оператор после операндов:
3 4 2 * +. Она не требует ни того, ни другого. - Порядок, в котором операторы появляются в постфиксной форме, есть порядок их применения, что именно необходимо сообщить машине.
Преобразование инфиксной записи в постфиксную
- Используйте стек операторов. Сканируйте слева направо: отправляйте операнд напрямую в выходной поток; для оператора сначала переместите в выходной поток все накопленные операторы с приоритетом выше или равным, затем поместите его в стек.
- Поместите открывающую скобку. При встречной закрывающей скобке перемещайте в выходной поток до соответствующей открывающей скобки, затем выбросьте пару.
- В конце переместите всё оставшееся в стеке в выходной поток.
Приоритет операторов — то, что убирает обратная польская нотация
В обычной инфиксной математике × и ÷ имеют более высокий приоритет, чем + и −, поэтому правила применяются в правильном порядке. Обратная польская нотация записывает операнды сначала (3 4 2 × + 1 −), фиксируя порядок так, что правила приоритета не нужны.
Какова форма RPN (постфиксная) для инфиксного выражения (3 + 4) * 2?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Скобки вынуждают сначала вычислить 3+4: 3 4 +, затем умножить на 2: 3 4 + 2 *.
Преобразуйте (A + B) * (C - D) в обратную польскую нотацию, используя * для умножения.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Каждая скобка преобразуется по очереди, а умножение извлекается последним, поэтому оно оказывается в конце. Скобок не остается.
Разобранный пример: преобразование, затем вычисление
- 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 - ×. - Теперь вычислите его для значения $A=3, B=4, C=5, D=2$. Поместите в стек 3, поместите в стек 4;
+извлекает оба и помещает 7. Поместите в стек 5, поместите в стек 2;-извлекает оба и помещает 3.×извлекает 7 и 3 и помещает 21. - Оператор всегда берет два верхних элемента, а первый извлеченный является правым операндом. Это важно для
-и/, где порядок меняет результат.
Вычислите RPN-выражение 3 4 2 * +.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Положите 3, 4, 2; * извлекает 4 и 2 → 8; + извлекает 3 и 8 → 11.
Обратная польская нотация не требует скобок или таблиц приоритетов и может быть вычислена непосредственно с помощью стека.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Положите операнды; каждый оператор извлекает свои операнды и помещает результат — именно так работает машина со стеком.
Вычисление со стеком пошагово
- Сканируйте слева направо: push каждый операнд; на операторе, popните два верхних, примените его и pushните результат. В конце стек содержит одно значение: ответ.
| Токен | Стек после |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- Это машина со стеком: нет скобок, нет таблицы приоритетов, нет просмотры вперед. Именно так JVM и многие интерпретаторы байт-кода вычисляют каждое выражение.
При вычислении RPN первый элемент, извлеченный из стека, является левым операндом оператора.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Первый извлеченный элемент — правый операнд. Для + и * это не имеет значения, но изменение порядка нарушает вычитание и деление.
Расставьте шаги вычисления 3 4 2 * + со стеком в правильном порядке.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Операнды кладутся, каждый оператор потребляет два верхних элемента и оставляет результат. Скобки и таблица приоритетов не нужны.
Потерянные баллы
- Терминал — это буквальная текст; нетерминал называет другое правило. Не путайте их местами.
- BNF выражает повторение через рекурсию. Если правило ссылается на само себя, укажите это и объясните его смысл.
- При вычислении оператор берет верхние два элемента, а первый извлеченный элемент является правым операндом. Перепутав это, вы получите неверные результаты для вычитания и деления.
- RPN не требует скобок. Написание скобок в ответе в постфиксной нотации лишит вас баллов за проверенный материал.
Вы поняли
- Правила вывода BNF объединяют терминалы (буквальный текст) и нетерминалы (имена правил), выражая повторение через рекурсию; диаграмма синтаксиса является эквивалентной графической формой
- Проверьте строку, построив её из правил, и назовите правило, которое нарушается, когда она недопустима
- infix требует приоритетов и скобок; RPN (постфикс) помещает оператор после операндов и не нуждается ни в том, ни в другом
- преобразование с помощью стека операторов, вычисление путем push'а операндов и применения каждого оператора к двум верхним, первый из которых является правым операндом