Quelle est la relation entre les langages de programmation, les expressions régulières et les langages formels

J'ai cherché sur le net une réponse à cette question et il semble que tout le monde connaisse implicitement la réponse sauf moi. On peut supposer que cela est dû au fait que les seules personnes qui s’en soucient sont celles qui ont fait des études supérieures sur le sujet. D'un autre côté, j'ai été jeté dans le cul pour un devoir de lycée.

Ma question est, comment les langages de programmation sont-ils exactement liés aux langages formels? Partout où je lis, quelque chose dans le sens des "langages formels est utilisé pour définir la grammaire des langages de programmation" est dit.

D'après ce que j'ai pu rassembler, un langage formel est une série de règles de production qui s'appliquent à un ensemble spécifique de symboles (l'alphabet de la langue). Ces règles de production définissent un ensemble de transformations, telles que:

b -> a

aaa->c

Cela peut être appliqué de telle sorte que:

abab->aaaa aaaa-> ca

Juste comme note latérale, si nous définissons que l'alphabet de notre langage formel comme {a, b, c}, alors a et b sont non terminaux et c est terminal car il ne peut pas être transformé (veuillez me corriger si je me trompe cette).

Compte tenu de tout cela, comment cela s'applique-t-il aux langages de programmation? Souvent, il est également indiqué que l'expression régulière est utilisée pour analyser une langue sous sa forme textuelle afin de s'assurer que la grammaire est correcte. C'est logique. Ensuite, il est indiqué que l'expression régulière est définie par des langages formels. L'expression régulière renvoie vrai ou faux (du moins d'après mon expérience) selon que les automates à états finis qui représentent l'expression régulière atteignent le point de l'objectif. Pour autant que je puisse voir, cela n'a rien à voir avec les transformations *.

Pour la compilation du programme lui-même, je suppose qu'un langage formel serait capable de transformer le code en code de niveau consécutivement inférieur, atteignant finalement l'assemblage via un ensemble complexe de règles, que le matériel pourrait alors comprendre.

Voilà donc les choses de mon point de vue confus. Il y a probablement beaucoup de choses fondamentalement erronées dans ce que j'ai dit, et c'est pourquoi je demande de l'aide.

* Sauf si vous considérez quelque chose comme (a|b)*b*c->trueune règle de production, auquel cas la règle nécessite un automate à états finis (ie: regex). Cela n'a aucun sens car nous venons de dire que

Celui qui vous a dit que les expressions régulières sont utilisées pour analyser le code répandait de la désinformation. Classiquement (je ne sais pas dans quelle mesure cela est vrai dans les compilateurs modernes), l'analyse du code - conversion du code du texte en arbre de syntaxe - se compose de deux étapes:

1. Analyse lexicale: traite le texte brut en morceaux tels que mots - clés , constantes numériques , chaînes , identificateurs , etc. Ceci est classiquement implémenté en utilisant une sorte de machine à états finis, similaire dans son esprit à un automate fini déterministe (DFA).

2. Analyseur: exécuté après l'analyse lexicale et convertit le texte brut en une arborescence de syntaxe annotée. La grammaire des langages de programmation est (en première approximation) sans contexte (en fait, il faut un sous-ensemble encore plus strict), et cela permet à certains algorithmes efficaces d'analyser le code lexifié dans un arbre de syntaxe. Ceci est similaire au problème de savoir si une chaîne donnée appartient à une grammaire sans contexte, la différence étant que nous voulons également la preuve sous la forme d'un arbre de syntaxe.

Les grammaires pour les langages de programmation sont écrites comme des grammaires sans contexte, et cette représentation est utilisée par les générateurs d'analyseurs pour construire des analyseurs rapides pour eux. Un exemple simple aurait des STATEMENT non terminaux puis des règles de la forme STATEMENT IF-STATEMENT, où IF-STATEMENT → if CONDITION alors BLOCK endif, ou similaire (où BLOCK → STATEMENT | BLOCK; STATEMENT, par exemple). Habituellement, ces grammaires sont spécifiées sous forme Backus-Naur (BNF).$\to$$\to$$\to$

Les spécifications réelles des langages de programmation ne sont pas sans contexte. Par exemple, une variable ne peut pas apparaître si elle n'a pas été déclarée dans de nombreuses langues, et les langues avec un typage strict peuvent ne pas vous permettre d'affecter un entier à une variable de chaîne. Le travail de l'analyseur consiste uniquement à convertir le code brut en un formulaire plus facile à traiter.

Je dois mentionner qu'il existe d'autres approches telles que l' analyse de descente récursive qui ne génère pas réellement d'arbre d'analyse, mais traite votre code au fur et à mesure de son analyse. Bien qu'il ne prenne pas la peine de générer l'arbre, à tous les autres égards, il fonctionne au même niveau que celui décrit ci-dessus.

Ceci est quelque chose de lourd pour un devoir de lycée.

La réponse de Yuval Filmus est vraiment bonne, il s'agit donc plutôt d'une réponse supplémentaire pour clarifier certains des points qu'il a soulevés.

Un langage formel est une construction mathématique. Leur utilisation pour les langages de programmation n'est qu'une des nombreuses utilisations possibles; en fait, le linguiste Noam Chomsky a apporté des contributions importantes à la théorie primitive des langues formelles. Il a inventé la hiérarchie Chomsky, qui classe les langues formelles en langues régulières, sans contexte, etc. Les langues formelles sont également appliquées en linguistique pour décrire la syntaxe des langues naturelles comme l'anglais. Pensez-y comme aux vrais nombres: nous pouvons utiliser les vrais nombres pour décrire à la fois des choses concrètes comme la distance de Los Angeles à New York, et des choses abstraites comme le rapport de la circonférence d'un cercle à son diamètre. Même si ces deux choses existent indépendamment des vrais nombres, les vrais nombres sont un système utile pour les décrire. Les langages formels sont un système utile pour décrire à la fois l'anglais et le Python, car les deux ont un format structuré similaire.

$a + b + c = d$$a + b = d - c$$a$$b$$c$ comme des montants en dollars, par exemple, puis l'équation a un sens.

Classiquement, un langage de programmation aura deux grammaires: une grammaire lexicale et une grammaire syntaxique. La grammaire lexicale traite des caractères tels que les lettres, les points-virgules, les accolades et les parenthèses. Il s'agit généralement d'une grammaire régulière, elle peut donc être exprimée avec des expressions régulières ou un DFA ou un NFA. (Il existe des preuves dans la théorie formelle du langage montrant que les trois sont de puissance équivalente — ce qui signifie qu'ils acceptent le même ensemble de langues.) La phase de lexingage du compilateur ou de l'interpréteur est en quelque sorte un mini-interprète pour la grammaire langagière régulière. Il lit les règles de la grammaire et en suivant ces règles, il regroupe les caractères individuels en jetons. Par exemple, si le langage a une ifinstruction qui ressemble plus ou moins à des C, le lexer peut regrouper les caractères iet fdans le seul jetonIF, puis recherchez une parenthèse ouvrante et sortez un jeton OPEN_PAREN, puis gérez ce qui se trouve entre les parenthèses, puis trouvez la parenthèse fermante et sortez a CLOSE_PAREN. Lorsque le lexeur a fini de créer des jetons, il les remet à l'analyseur, qui détermine si les jetons forment réellement des instructions valides du langage de programmation. Donc, si vous écrivez ip a == ben Python, le lexeur fait juste de son mieux pour deviner quel type de jeton ipest (probablement il serait pris pour un identifiant par la plupart des lexeurs), et le passe à l'analyseur, qui se plaint parce que vous ne pouvez pas avoir de identifiant dans cette position.

$a \rightarrow b$

Examinons les règles de grammaire pour l' ifinstruction de Python . Voici la règle:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

Cette règle nous indique comment l'analyseur va déterminer si une chaîne de jetons envoyée par le lexeur est une ifdéclaration. Tout mot entre guillemets simples doit apparaître, exactement comme cela, dans le code source, afin que l'analyseur recherche le mot simple if. L'analyseur va alors essayer de faire correspondre certains jetons à la règle pour test:

test: or_test ['if' or_test 'else' test] | lambdef

testest défini en termes d'autres règles de la grammaire. Remarquez comment testse comprend également dans sa définition; cela s'appelle une définition récursive. C'est la grande puissance des langages sans contexte que les langages ordinaires n'ont pas, et cela permet de définir des choses comme les boucles imbriquées pour la syntaxe du langage de programmation.

Si l'analyseur parvient à faire correspondre certains jetons test, il essaiera de faire correspondre deux points. Si cela réussit, il essaiera de faire correspondre quelques jetons supplémentaires en utilisant la règle pour suite. La section ('elif' test ':' suite)*signifie que nous pouvons avoir n'importe quel nombre de répétitions du texte littéral elif, suivi de quelque chose qui correspond test, suivi de deux points, suivi de quelque chose qui correspond suite. Nous pouvons également avoir zéro répétitions; l'astérisque à la fin signifie "zéro ou autant que nous voulons".

Tout à la fin est ['else' ':' suite] . Cette partie est placée entre crochets; cela signifie que nous pouvons avoir zéro ou un, mais pas plus. Pour faire correspondre cela, l'analyseur doit faire correspondre le texte littéral else, deux points, puis a suite. Voici la règle pour un suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

C'est fondamentalement un bloc dans les langages de type C. Depuis Python utilise des nouvelles lignes et l' indentation pour des choses méchantes, les sorties analyseurs lexicaux NEWLINE, INDENTet des DEDENTjetons pour indiquer à l'analyseur où une nouvelle ligne a commencé, où le code a commencé à être en retrait, et où il a été retourné au niveau extérieur de l' empreinte.

Si l'une de ces tentatives de correspondance échoue, l'analyseur signale une erreur et s'arrête. Si l'analyse de l'ensemble du programme réussit, l'analyseur aura généralement construit un arbre d'analyse comme Yuval couvert dans sa réponse, et éventuellement une table de symboles et d'autres structures de données qui stockent des informations sémantiques. Si le langage est typé statiquement, le compilateur parcourra l'arborescence d'analyse et recherchera les erreurs de type. Il parcourt également l'arborescence d'analyse pour générer du code de bas niveau (langage d'assemblage, bytecode Java, langage intermédiaire .Net, ou quelque chose de similaire), ce qui est réellement exécuté.

Comme exercice, je recommanderais de prendre la grammaire d'un langage de programmation que vous connaissez (encore une fois, Python , Java et voici C # , Javascript , C ) et d'essayer d'analyser manuellement quelque chose de simple, comme peut x = a + b;- être ou if (True): print("Yay!"). Si vous cherchez quelque chose de plus simple, il y a aussi une belle grammaire pour JSON , qui couvre essentiellement la syntaxe des littéraux d'objet en Javascript (comme {'a': 1, 'b': 2}). Bonne chance, ce sont des trucs époustouflants, mais cela s'avère vraiment intéressant lorsque vous n'êtes pas dans une date folle.

En un mot

Les langages de programmation sont composés d'une syntaxe qui représente le programme sous forme de chaînes de caractères et d'une sémantique qui est la signification voulue du programme.

Les langages formels sont une syntaxe sans signification. Il est destiné à étudier la structure d'ensembles de chaînes définies formellement, sans généralement attacher de sens à ces chaînes.

L'expression régulière et d'autres formalismes (tels que les grammaires sans contexte) sont utilisés pour définir des langages formels, utilisés comme composante syntaxique de la programmation et des langages naturels, c'est-à-dire pour représenter des phrases de manière structurée. D'autres mécanismes sont utilisés pour relier cette structure à la sémantique des langages de programmation.

Beaucoup ici est considérablement simplifié, en particulier en ce qui concerne le langage naturel.

Avec beaucoup plus de détails

Pour répondre à votre question, nous devons commencer par le début. Une langue au sens habituel est, de manière informelle, un moyen de transmettre des informations ou des idées. Dans une langue, on distingue généralement la syntaxe et la sémantique. La sémantique est ce dont vous voulez parler / écrire. les informations que vous souhaitez transmettre. La syntaxe est le moyen que vous utilisez pour la transmettre, c'est-à-dire une représentation conventionnelle qui peut être échangée entre personnes, et maintenant aussi entre personnes et appareils, ou entre appareils (ordinateurs).

En règle générale, vous utiliserez le mot dogpour transmettre l'idée d'un chien. Le mot dogest composé de trois lettres, ou d'un son équivalent, et est destiné à être la représentation d'une sorte d'animal. L'idée clé est que la communication se fait par la représentation de ce qui doit être communiqué. Les structures de représentation sont généralement appelées syntaxe, tandis que ce qui est représenté est appelé sémantique. Cela vaut plus ou moins pour le langage naturel ainsi que pour les langages de programmation.

Les mots sont des entités syntaxiques pour représenter des concepts sémantiques plus ou moins élémentaires. Mais ces concepts élémentaires doivent être rassemblés de diverses manières pour donner un sens plus complexe. Nous écrivons the dogpour transmettre que nous voulons dire un chien spécifique et the dog bites the catpour transmettre une idée plus complexe. Mais la façon dont les mots sont organisés doit être fixée par des règles, afin que nous puissions dire lequel du chien et du chat mord réellement l'autre.

Nous avons donc des règles telles que celles sentence -> subject verb complementqui sont censées correspondre aux phrases et nous dire comment les idées associées à chaque partie sont articulées. Ces règles sont des règles syntaxiques, car elles nous indiquent comment organiser la représentation de notre message. Le subjectpeut lui-même être défini par une règle subject -> article noun, etc.

$2x+1=23$$x$$1$$23$

equation -> expression "=" expression  
expression -> expression "+" expression 
expression -> number

La structure des langages de programmation est la même. Les langages de programmation sont sémantiquement spécialisés dans l'expression de calculs à effectuer, plutôt que d'exprimer des problèmes à résoudre, des preuves de théorèmes ou des relations amicales entre animaux. Mais c'est la principale différence.

Les représentations utilisées dans la syntaxe sont généralement des chaînes de caractères ou de sons pour les langues parlées. La sémantique appartient généralement au domaine abstrait, ou peut-être à la réalité, mais toujours abstraite dans nos processus de pensée, ou au domaine comportemental des dispositifs. La communication implique de coder l'information / l'idée dans la syntaxe, qui est transmise et décodée par le récepteur. Le résultat est alors interprété de quelque manière que ce soit par le récepteur.

Donc, ce que nous voyons du langage est principalement la syntaxe et sa structure. L'exemple ci-dessus n'est que l'un des moyens les plus courants de définir des chaînes syntaxiques et leur organisation structurelle. Il y en a d'autres. Pour une langue donnée, certaines chaînes peuvent se voir attribuer une structure et sont réputées appartenir à la langue, d'autres non.

Il en va de même pour les mots. Certaines séquences de lettres (ou sons) sont des mots légitimes, tandis que d'autres ne le sont pas.

Les langages formels ne sont que de la syntaxe sans sémantique. Ils définissent avec un ensemble de règles quelles séquences peuvent être construites, en utilisant les éléments de base d'un alphabet. Les règles peuvent être très variables, parfois complexes. Mais les langages formels sont utilisés à de nombreuses fins mathématiques au-delà de la communication linguistique, que ce soit pour des langages naturels ou pour des langages de programmation. L'ensemble de règles qui définissent les chaînes dans une langue est appelé une grammaire. Mais il existe de nombreuses autres façons de définir les langues.

En pratique, une langue est structurée en deux niveaux. Le niveau lexical définit des mots construits à partir d'un alphabet de caractères. Le niveau syntaxique définit des phrases, ou des programmes construits à partir d'un alphabet de mots (ou plus précisément de familles de mots, pour qu'il reste un alphabet fini). Ceci est nécessairement quelque peu simplifié.

La structure des mots est assez simple dans la plupart des langages (de programmation ou naturels) de sorte qu'ils sont généralement définis avec ce qui est généralement considéré comme le type de langage formel le plus simple: les langages réguliers. Ils peuvent être définis avec des expressions régulières (regexp) et sont assez facilement identifiables avec des dispositifs programmés appelés automates à états finis. Dans le cas des langages de programmation, les exemples d'un mot sont un identifiant, un entier, une chaîne, un nombre réel, un mot réservé tel que if ou repeat, un symbole de ponctuation ou une parenthèse ouverte. Des exemples de familles de mots sont identifiant, chaîne, entier.

Le niveau syntaxique est généralement défini par un type de langage formel légèrement plus complexe: les langues sans contexte, utilisant les mots comme alphabet. Les règles que nous avons vues ci-dessus sont des règles sans contexte pour le langage naturel. Dans le cas des langages de programmation, les règles peuvent être:

statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

Avec de telles règles, vous pouvez écrire:

while aaa /= bbb do aaa = aaa + bbb / 6 qui est une déclaration.

Et la façon dont il a été produit peut être représentée par une structure arborescente appelée arbre d'analyse ou arbre de syntaxe (non complet ici):

                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

Les noms apparaissant à gauche d'une règle sont appelés non-terminaux, tandis que les mots sont également appelés terminaux, car ils sont dans l'alphabet de la langue (au-dessus du niveau lexical). Les non-terminaux représentent les différentes structures syntaxiques, qui peuvent être utilisées pour composer un programme.

Ces règles sont appelées sans contexte, car un non-terminal peut être remplacé arbitrairement en utilisant l'une des règles correspondantes, indépendamment du contexte dans lequel il apparaît. L'ensemble de règles définissant la langue est appelé une grammaire sans contexte.

En fait, il existe des restrictions à ce sujet, lorsque les identificateurs doivent être déclarés pour la première fois, ou lorsqu'une expression doit satisfaire aux restrictions de type. Mais une telle restriction peut être considérée comme sémantique plutôt que syntaxique. En fait, certains professionnels les placent dans ce qu'ils appellent la sémantique statique .

Étant donné n'importe quelle phrase, n'importe quel programme, la signification de cette phrase est extraite en analysant la structure donnée par l'arbre d'analyse pour cette phrase. Par conséquent, il est très important de développer des algorithmes, appelés analyseurs, qui peuvent récupérer la structure arborescente correspondant à un programme, une fois le programme donné.

L'analyseur est précédé de l'analyseur lexical qui reconnaît les mots et détermine la famille à laquelle ils appartiennent. Ensuite, la séquence de mots, ou éléments lexicaux, est donnée à l'analyseur qui récupère la structure arborescente sous-jacente. À partir de cette structure, le compilateur peut alors déterminer comment générer du code, qui est la partie sémantique du programme, du côté du compilateur.

L'analyseur d'un compilateur peut réellement construire une structure de données correspondant à l'arbre d'analyse et la transmettre aux étapes ultérieures du processus de compilation, mais ce n'est pas obligatoire. L'exécution de l'algorithme d'analyse revient à développer une stratégie de calcul pour explorer l'arbre de syntaxe implicite dans le texte du programme. Cet arbre de syntaxe / analyse peut être explicité ou non dans le processus, selon la stratégie de compilation (nombre d'étapes). Ce qui est nécessaire cependant, c'est qu'il y a finalement au moins une exploration ascendante de l'arbre d'analyse, qu'elle soit expliquée ou laissée implicite dans la structure de calcul.

La raison en est intuitivement qu'une méthode formelle standard pour définir la sémantique associée à une structure arborescente syntaxique consiste à utiliser ce qu'on appelle un homomorphisme. N'ayez pas peur du grand mot. L'idée est juste de considérer que le sens de l'ensemble est construit à partir du sens des parties, sur la base de l'opérateur qui les relie

Par exemple, la phrase the dog bites the catpeut être analysée avec la règle sentence -> subject verb complement. Connaître la signification des 3 sous subject- arbres,, verbet complement, la règle qui les compose nous dit que le sujet fait l'action et que le chat est celui qui est mordu.

Ce n'est qu'une explication intuitive, mais elle peut être formalisée. La sémantique est construite vers le haut à partir des constituants. Mais cela cache beaucoup de complexité.

Le fonctionnement interne d'un compilateur peut être décomposé en plusieurs étapes. Le compilateur réel peut fonctionner étape par étape, en utilisant des représentations intermédiaires. Il peut également fusionner certaines étapes. Cela dépend de la technologie utilisée et de la complexité de la compilation du langage en question.

Il existe des différences importantes. Le principal d'entre eux, je dirais, est que l'analyse de vrais langages de programmation consiste à gérer les erreurs de syntaxe. Avec un langage formel, vous diriez simplement "ce n'est pas dans le langage", mais un compilateur qui dit que ce n'est pas très utile - il devrait vous dire ce qui ne va pas, et s'il s'agit d'une petite erreur, continuez idéalement l'analyse afin qu'il puisse signaler plus d'erreurs. Beaucoup de recherches (et d'efforts de mise en œuvre) y sont consacrés. Donc, vraiment, vous ne vous souciez même pas du résultat vrai / faux, vous voulez juste analyser la structure de l'entrée. Les langages formels sont utilisés comme un outil là-bas, et il y a beaucoup de chevauchements, mais vous résolvez vraiment un problème différent.

De plus, dans la plupart des langues, il a été choisi de ne pas appliquer certaines choses dans la grammaire , par exemple l'exemple que vous avez mentionné, "une variable ne peut pas apparaître si elle n'a pas été déclarée". C'est généralement une chose qui serait complètement ignorée par l'analyseur, puis prise dans une analyse distincte (analyse sémantique) qui examine ce genre de chose et n'est pas affectée par des considérations telles que la non-contextualité. Mais pas toujours - par exemple pour analyser C, le hack lexer est souvent utilisé, et C ++ est un exemple célèbre d'un langage qui ne peut pas être analysé sans effectuer simultanément une analyse sémantique sérieuse (en fait, l'analyse C ++ est indécidable, car les modèles sont Turing complets ). Dans les langues plus simples, il a tendance à être divisé, c'est plus facile de cette façon.

Une langue formelle est un ensemble de mots - où un mot est une chaîne de symboles d'un alphabet.

Cela signifie que votre couplage des règles de production et du langage formel est trop fort. Il n'est pas correct que le langage formel soit les règles de production. Les règles de production définissent plutôt le langage formel. Le langage formel est les mots qui peuvent être produits par la règle de production. (Cela nécessite que le langage formel soit du type qui peut être défini par les règles de production, par exemple, les langues régulières peuvent être définies par une grammaire sans contexte)

Le langage régulier correspondant à l'expression (a|b)*c*dest donc défini par les règles de production;

S->ACd
A->
A->aA
A->bA
C->
C->cC

Les mots que ces règles de production génèrent à partir du symbole de départ S sont précisément ces chaînes que l'expression régulière accepte.

Il existe une autre relation entre les expressions régulières et les langages de programmation qui concerne la sémantique. Les constructions de contrôle de base d'un langage impératif sont la composition séquentielle (faire A puis B), le choix (faire A ou B) et la répétition (faire A encore et encore).

Les trois mêmes façons de combiner les comportements se retrouvent dans les expressions régulières. Ajoutez des appels de sous-programme et vous avez une analogie avec EBNF.

Il y a donc beaucoup de similitude entre l'algèbre des expressions régulières et l'algèbre des commandes. Ceci est exploré en détail par Dijkstra dans "L'unification de trois calculs". C'est aussi la base du CCS de Milner, qui répond à la question: et si on ajoutait le parallélisme?