Grammar (BNF) and Reverse Polish Notation · Grammaire (BNF) et Notation Polonaise Inversée
| English | Français |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfixe |
| precedence/ˈpresɪdəns/ | prévalence |
| grammar/ˈɡræmə/ | grammaire |
| syntax diagram/ˈsɪntæks ˈdaɪəɡræm/ | diagramme syntaxique |
| Reverse Polish Notation/rɪˈvɜːs ˈpəʊlɪʃ nəʊˈteɪʃn/ | Notation polonaise inverse (RPN) |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Forme de Backus-Naur (BNF) |
| production rules/prəˈdʌkʃn ruːlz/ | règles de production |
| terminal/ˈtɜːmɪnl/ | terminale |
| non-terminal/nɒn ˈtɜːmɪnl/ | non-terminal |
| infix/ˈɪnfɪks/ | infixe |
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.
La notation sans parenthèses, et sans ambiguïté
- Écrire
3 + 4 * 2vous fait dépendre d'une convention : que la multiplication lie plus fort que l'addition. Changer la convention et l'expression prend un autre sens. - Un logicien polonais, Jan Łukasiewicz, a démontré dans les années 1920 que si on place l'opérateur avant ses opérandes, les parenthèses deviennent inutiles. Si on l'inverse, en plaçant l'opérateur après, on obtient une forme qu'une machine peut évaluer avec rien qu'une pile.
- C'est pourquoi la Machine Virtuelle Java et la plupart des interpréteurs de bytecode fonctionnent en postfix. Pas de table de priorité, pas de parenthèses, pas d'ambiguïté.
- Cette leçon montre comment la grammaire 文法 d'un langage est écrite, en BNF et sous forme de diagramme syntaxique, et comment la Notation Polonaise Inversée 逆波兰表示法 est convertie et évaluée.
Backus-Naur Form
- A grammar says which sequences of tokens are valid programs. Backus-Naur Form 巴科斯-诺尔范式 (BNF) writes it as production rules 产生式:
- 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.
Notation Backus-Naur
- Une grammaire définit quelles séquences de jetons constituent des programmes valides. La Notation Backus-Naur 巴科斯-诺尔范式 (BNF) l'exprime sous forme de règles de production 产生式 :
<symbol> ::= alternative1 | alternative2 | ...
- Un symbole terminal 终结符 est du texte littéral apparaissant dans le programme. Un symbole non-terminal 非终结符 est le nom d'une autre règle, écrit entre guillemets angulaires.
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= a | b | c | … | z
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
In BNF, a terminal symbol is: · Dans la BNF, un symbole terminal est :
Terminals are literal tokens; non-terminals are names of other production rules. · Les terminaux sont des jetons littéraux ; les non-terminaux sont des noms d'autres règles de production.
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
La récursion est comment BNF répète
- BNF n'a pas de symbole "répéter", donc la répétition s'écrit en définissant une règle en termes d'elle-même.
- Lire
<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>comme : un identifiant est une lettre unique, ou un identifiant suivi d'une lettre, ou un identifiant suivi d'un chiffre. - Ensemble, ces alternatives signifient "une lettre suivie de n'importe quel nombre de lettres ou de chiffres", ce qui explique aussi pourquoi un identifiant ne peut pas commencer par un chiffre : aucune alternative ne le permet.
- Un diagramme syntaxique 语法图, ou diagramme ferroviaire, exprime les mêmes règles graphiquement, avec une boucle là où BNF utilise la récursion. Les deux notations sont équivalentes.
La boucle et la récursion disent la même chose
Match each grammar/notation term to its meaning. · Reliez chaque terme de grammaire/notation à sa signification.
BNF builds rules from terminals and non-terminals (recursion gives repetition); RPN reorders an expression to drop brackets. · La BNF construit des règles à partir de terminaux et non-terminaux (la récursion permet la répétition) ; la NPI réordonne une expression pour supprimer les crochets.
Why does the rule
The alternatives together mean a letter followed by any number of letters or digits, and no alternative lets one start with a digit. · Les alternatives ensemble signifient une lettre suivie de n'importe quel nombre de lettres ou chiffres, et aucune alternative ne permet de commencer par un chiffre.
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".
Exemple résolu : tester une chaîne contre la grammaire
- En utilisant les règles ci-dessus, lesquels de
count2,2countetmy_varsont des identifiants valides ? count2: valide. Construisez-le :cest un<letter>, donc un<identifier>; ajoutezo,u,n,tselon la deuxième alternative ; ajoutez2selon la troisième.2count: invalide. Toutes les alternatives partent d'un<letter>ou d'un autre<identifier>, et aucune chaîne ne peut commencer par un chiffre.my_var: invalide, car_n'est pas un terminal dans aucune règle ici. Citez la règle qui échoue, pas juste "ça a l'air mal".
Using those rules, which strings are valid identifiers? Select all · tout that apply. · En utilisant ces règles, quelles chaînes sont des identifiants valides ? Sélectionnez toutes celles qui s'appliquent.
A single letter is an identifier by the first alternative. 2count cannot start with a digit, and _ is not a terminal in any rule here. · Une seule lettre est un identifiant selon la première alternative. 2count ne peut pas commencer par un chiffre, et _ n'est pas un terminal dans aucune règle ici.
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.
Infixe et postfix
- Infixe 中缀 place l'opérateur entre ses opérandes,
3 + 4 * 2, et nécessite donc des règles de priorité et des parenthèses pour être non ambiguë. - La Notation Polonaise Inversée, ou postfix 后缀, place l'opérateur après ses opérandes :
3 4 2 * +. Elle n'en a pas besoin. - L'ordre dans lequel les opérateurs apparaissent dans la forme postfix est l'ordre dans lequel ils sont appliqués, ce qui est exactement ce dont une machine a besoin pour être informée.
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.
Conversion de l'infixe vers le postfix
- Utilisez une pile d'opérateurs. Balayez de gauche à droite : envoyez un opérande directement à la sortie ; pour un opérateur, poppez d'abord vers la sortie tout opérateur empilé de priorité supérieure ou égale 优先级, puis poussez-le.
- Poussez une parenthèse ouvrante. Sur une parenthèse fermante, poppez vers la sortie jusqu'à la parenthèse ouvrante correspondante, puis jetez la paire.
- À la fin, poppez tout ce qui reste sur la pile vers la sortie.
Operator precedence — what RPN removes · Précédence des opérateurs — ce que la NPI élimine
In ordinary infix maths × and ÷ bind tighter than + and −, so you must apply rules in the right order. Reverse Polish Notation writes the operands first (3 4 2 × + 1 −), fixing the order so no precedence rules are needed. · En arithmétique infixée ordinaire, × et ÷ lient plus fort que + et −, il faut donc appliquer les règles dans le bon ordre. La Notation Polonaise Inversée écrit les opérandes en premier (3 4 2 × + 1 −), fixant l'ordre pour qu'aucune règle de précédence ne soit nécessaire.
What is the RPN (postfix) form of the infix expression (3 + 4) * 2? · Quelle est la forme NPI (postfixe) de l'expression infixée (3 + 4) * 2 ?
The brackets force 3+4 first: 3 4 +, then multiply by 2: 3 4 + 2 *. · Les crochets imposent 3+4 en premier : 3 4 +, puis multiplier par 2 : 3 4 + 2 *.
Convert (A + B) * (C - D) to Reverse Polish Notation, using * for the multiplication. · Convertissez (A + B) * (C - D) en Notation Polonaise Inverse, en utilisant * pour la multiplication.
Each bracket is converted in turn and the multiplication is popped last, so it appears at the end. No brackets survive. · Chaque crochet est converti tour à tour et la multiplication est extraite en dernier, donc elle apparaît à la fin. Aucun crochet ne survit.
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.
Exemple résolu : convertir, puis évaluer
- Convertissez $(A + B) \times (C - D)$ en RPN. Poussez
(; sortezA; poussez+; sortezB; sur), poppez vers la parenthèse ouvrante correspondante(, donnantA B +. Poussez×. La deuxième parenthèse se comporte de manière identique, donnantC D -. À la fin, poppez le×. Résultat :A B + C D - ×. - Évaluez maintenant pour $A=3, B=4, C=5, D=2$. Poussez 3, poussez 4 ;
+poppe les deux et pousse 7. Poussez 5, poussez 2 ;-poppe les deux et pousse 3.×poppe 7 et 3 et pousse 21. - L'opérateur prend toujours les deux premiers éléments, et le premier poppé est l'opérande de droite. Cela importe pour
-et/, où l'ordre change la réponse.
Evaluate the RPN expression 3 4 2 * +. · Évaluez l'expression NPI 3 4 2 * +.
Push 3, 4, 2; * pops 4 and 2 → 8; + pops 3 and 8 → 11. · Empilez 3, 4, 2 ; * dépile 4 et 2 → 8 ; + dépile 3 et 8 → 11.
Reverse Polish Notation needs no brackets or precedence rules, and can be evaluated directly with a stack. · La Notation Polonaise Inverse ne nécessite ni crochets ni règles de précédence, et peut être évaluée directement avec une pile.
Push operands; each operator pops its operands and pushes the result — which is exactly how a stack machine runs. · Empilez les opérandes ; chaque opérateur dépile ses opérandes et empile le résultat — c'est exactement ainsi qu'une machine à pile fonctionne.
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.
Évaluation avec une pile, étape par étape
- Balayez de gauche à droite : poussez chaque opérande ; sur un opérateur, poppez les deux premiers, appliquez l'opération, et poussez le résultat. À la fin, la pile contient une valeur : la réponse.
| Jeton | Pile après |
|---|---|
3 |
3 |
4 |
3, 4 |
2 |
3, 4, 2 |
* |
3, 8 |
+ |
11 |
- C'est une machine à pile : pas de parenthèses, pas de table de priorité, pas de lookahead. C'est ainsi que la JVM et de nombreux interpréteurs de bytecode évaluent chaque expression.
When evaluating RPN, the first item popped from the stack is the left-hand operand of the operator. · Lors de l'évaluation NPI, le premier élément défilé de la pile est l'opérande de gauche de l'opérateur.
The first popped is the right-hand operand. It makes no difference for + and *, but reversing it breaks subtraction and division. · Le premier défilé est l'opérande de droite. Cela n'a aucune importance pour + et *, mais l'inverser casse la soustraction et la division.
Put the steps of evaluating 3 4 2 * + with a stack in order. · Placez les étapes d'évaluation de 3 4 2 * + avec une pile dans l'ordre.
Operands go on, each operator consumes the top two and leaves its result. No brackets and no precedence table are needed. · Les opérandes sont empilés, chaque opérateur consomme les deux sommets et laisse son résultat. Pas de crochets et pas de table de précédence nécessaires.
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.
Pièges qui font perdre des points
- Un terminal est du texte littéral ; un non-terminal nomme une autre règle. Ne les échangez pas.
- BNF exprime la répétition par récursion. Si une règle se réfère à elle-même, dites-le et précisez ce que cela signifie.
- Dans l'évaluation, l'opérateur prend les deux premiers éléments, et le premier poppé est l'opérande de droite. Inverser cela brise la soustraction et la division.
- RPN n'a pas besoin de parenthèses. Écrire des parenthèses dans une réponse postfix fait perdre le point testé.
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
Vous avez compris
- Les règles de production BNF combinent des terminals (texte littéral) et des non-terminals (noms de règles), et expriment la répétition par récursion ; un diagramme syntaxique est la forme graphique équivalente
- tester une chaîne en la construisant à partir des règles, et nommer la règle qui échoue quand elle est invalide
- infixe a besoin de priorité et de parenthèses ; RPN (postfix) place l'opérateur après ses opérandes et n'en a pas besoin
- convertir avec une pile d'opérateurs, et évaluer en poussant des opérandes et en appliquant chaque opérateur aux deux premiers, le premier poppé étant l'opérande de droite