Pourquoi les chaînes répétées telles que [wcw | w est une chaîne de a et b] ne peuvent pas être dénotées par des expressions régulières? pls. donnez-moi une réponse détaillée car je suis nouveau à l'analyse lexicale. Merci ...Expressions régulières Analyse lexicale
Les expressions régulières dans leur forme originale décrivent des langages/grammaires réguliers. Ceux-ci ne peuvent pas contenir de structures imbriquées car ces langages peuvent être décrits par une machine à états finis simple. Simplifié vous pouvez imaginer cela comme si chaque mot de la langue se développe strictement de gauche à droite (ou de droite à gauche), où les structures répétitives doivent être définies explicitement et sont statiques. Cela signifie qu'aucune information d'état antérieur ne peut être transmise à des états ultérieurs (quelques caractères plus loin dans l'entrée). Donc, si vous avez votre symbole w vous ne pouvez pas spécifier que l'entrée doit avoir exactement la même chaîne w plus tard dans la séquence. De même, vous ne pouvez pas vous assurer que chaque parenthèse d'ouverture nécessite également un parenten (donc les expressions régulières elles-mêmes ne sont même pas un langage régulier et ne peuvent donc pas être décrites par des expressions régulières :-)). En informatique théorique, nous avons travaillé avec un ensemble très restreint d'opérateurs regex, essentiellement constitués de séquence, alternative (|) et répétition (*), tout le reste peut être décrit avec ces opérations.
Toutefois, les moteurs d'expressions rationnelles permettent généralement de regrouper certains sous-motifs dans des correspondances qui peuvent ensuite être référencées ou extraites ultérieurement. Certains moteurs permettent même d'utiliser une telle référence dans la chaîne d'expression de recherche elle-même, ce qui permet à l'expression de décrire plus qu'une simple langue. Si je me souviens bien, une telle utilisation de backreferences peut même produire des langages qui ne sont pas contextuels.
pointeurs supplémentaires:
Droite. L'exemple wcw ci-dessus ne peut pas être fait en utilisant une grammaire sans contexte autant que je peux voir (certainement pas si c'est wcwcw), mais il est facile de le vérifier en Perl. –
Il peut être, vous ne pouvez pas assurer que c'est la même chaîne de « a » et « b » s parce qu'il n'y a aucun moyen de conserver les informations acquises en traversant la première moitié à utiliser pour traverser la seconde.
Gardez à l'esprit que l'analyse est le sujet principal d'un des cours les plus difficiles que j'ai pris à l'école diplômé (Compilateurs I). Il y a déjà une bonne réponse, mais vous n'avez peut-être pas l'arrière-plan pour l'utiliser. –
Eh bien, ce n'était pas facile. Mais au moins c'était amusant, parfois. Bien qu'ici, il comprenait l'optimisation ainsi que plusieurs algorithmes au-delà de l'analyse syntaxique. Des idées pour rendre ce post plus clair à quelqu'un sans beaucoup de contexte? -.- – Joey