Grammaire (BNF) et Notation Polonaise Inversée
Introduit| English | Sens |
|---|---|
| postfix/ˈpəʊstfɪks/ | postfixe |
| precedence/ˈpresɪdəns/ | précédence |
| 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 inversée |
| Backus-Naur Form/ˈbækəs nɔː fɔːm/ | Forme de Backus-Naur |
| 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-terminale |
| infix/ˈɪnfɪks/ | Infixe |
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.
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>
Dans la BNF, un symbole terminal est :
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Les terminaux sont des jetons littéraux ; les non-terminaux sont des noms d'autres règles de production.
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
Reliez chaque terme de grammaire/notation à sa signification.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Pourquoi la règle
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
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".
En utilisant ces règles, quelles chaînes sont des identifiants valides ? Sélectionnez toutes celles qui s'appliquent.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
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.
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.
Précédence des opérateurs — ce que la NPI élimine
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.
Quelle est la forme NPI (postfixe) de l'expression infixée (3 + 4) * 2 ?
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Les crochets imposent 3+4 en premier : 3 4 +, puis multiplier par 2 : 3 4 + 2 *.
Convertissez (A + B) * (C - D) en Notation Polonaise Inverse, en utilisant * pour la multiplication.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Chaque crochet est converti tour à tour et la multiplication est extraite en dernier, donc elle apparaît à la fin. Aucun crochet ne survit.
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.
Évaluez l'expression NPI 3 4 2 * +.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Empilez 3, 4, 2 ; * dépile 4 et 2 → 8 ; + dépile 3 et 8 → 11.
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.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
É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.
Lors de l'évaluation NPI, le premier élément défilé de la pile est l'opérande de gauche de l'opérateur.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
Placez les étapes d'évaluation de 3 4 2 * + avec une pile dans l'ordre.
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
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.
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é.
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