| Grammaire non contextuelle. Vocabulaire : symbole initial, symbole non-terminal, symbole terminal, règle de production, dérivation immédiate, dérivation. Langage engendré par une grammaire, langage non contextuel. Non contextualité des langages réguliers. |
Notations : règle de production →, dérivation immédiate ⇒, dérivation ⇒∗. On montre comment définir une expression arithmétique ou une formule de la logique propositionnelle par une grammaire. On peut présenter comme exemple un mini-langage fictif de programmation ou un mini-langage de balisage. Sont hors programme : les automates à pile, les grammaires syntagmatiques générales, la hiérarchie de Chomsky. |
| Exemple d’algorithme d’analyse syntaxique. |
On peut présenter au tableau un algorithme ad hoc d’analyse syntaxique par descente récursive (algorithme top-down ) pour un langage de balisage fictif ( par exemple, la grammaire de symbole initial 𝑆 et de règles de production 𝑆 → 𝑇𝑆\|𝑐, 𝑇 → 𝑎𝑆𝑏 sur l’alphabet {𝑎,𝑏,𝑐}). On ne parle pas d’analyseur LL ou LR. On ne présente pas de théorie générale de l’analyse syntaxique. |