Dériver l'expression régulière pour le style C / ** / commentaires

8

Je travaille sur un analyseur pour un langage de style C, et pour cet analyseur, j'ai besoin de l'expression régulière qui correspond au style C / ** / commentaires. Maintenant, j'ai trouvé cette expression sur le web:

/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/

Cependant, comme vous pouvez le voir, c'est une expression plutôt désordonnée, et je n'ai aucune idée si elle correspond exactement à ce que je veux qu'elle corresponde.

Existe-t-il une manière différente de définir (rigoureusement) des expressions régulières qui sont faciles à vérifier à la main qu'elles sont vraiment correctes, puis convertibles («compilables») en l'expression régulière ci-dessus?

Alex ten Brink
la source
2
Notez que cette approche empêchera les commentaires imbriqués. Si vous créez de toute façon un analyseur complet, vous pouvez envisager d'analyser les commentaires de bloc "correctement". non seulement il est plus clair, vous pouvez également lire des métadonnées structurées à partir de commentaires si vous le souhaitez.
Raphael
Les fragments étaient-ils (!\*)destinés? Voulez-vous dire la notation la plus courante [^*]? Et quoi (!*|!/)?
Gilles 'SO- arrête d'être méchant'
@ Gilles: J'ai mis à jour l'expression. (! * |! /) est censé être quelque chose qui n'est ni * ni /.
Alex ten Brink
@Raphael, en C, les commentaires ne s'emboîtent pas .
vonbrand
@vonbrand: "Le style C" n'est pas très spécifique, donc mentionner qu'une "amélioration naturelle" n'est pas possible est un point valable.
frafl

Réponses:

6

Je peux penser à quatre façons:

  1. Définissez un automate pour la langue qui vous intéresse. Convertissez l'expression régulière en automate (en utilisant les dérivés de Brzozowski). Vérifiez que les deux automates acceptent le même langage (déterminez et minimisez ou utilisez un argument de bisimulation).

  2. Écrivez de nombreux cas de test et appliquez-y votre expression régulière.

  3. Convertissez l'automate défini au point 1 en une expression régulière, en utilisant des techniques standard.

  4. Une combinaison de ce qui précède.

Dave Clarke
la source
5

Si vous voulez être sûr d'analyser les commentaires C, vous devez confronter votre modèle à la spécification C. C99 §6.4.9 définit la syntaxe des commentaires comme suit:

1. Sauf dans une constante de caractère, un littéral de chaîne ou un commentaire, les caractères /* introduisent un commentaire. Le contenu d'un tel commentaire n'est examiné que pour identifier les caractères multi-octets et pour trouver les caractères */qui le terminent.

2. Sauf dans une constante de caractère, un littéral de chaîne ou un commentaire, les caractères //introduisent un commentaire qui inclut tous les caractères multi-octets jusqu'au caractère de nouvelle ligne suivant, sans toutefois l'inclure. Le contenu d'un tel commentaire n'est examiné que pour identifier les caractères multi-octets et pour trouver le caractère de nouvelle ligne de fin.

Il s'agit de la prose anglaise, pas d'une définition formelle, mais il existe une interprétation raisonnablement claire en termes d' automate fini non déterministe (NFA) qui consomme un commentaire:

  • À partir de l'état initial, /suivi par *entre dans l' état de commentaire sur plusieurs lignes , et /ensuite /entre dans l'état de commentaire sur une seule ligne.
  • À partir de l'état de commentaire multiligne, *suivi de /passe à l'état de post-commentaire.
  • À partir de l'état de commentaire sur une seule ligne, une nouvelle ligne entre dans l'état de post-commentaire.
  • Tout autre personnage laisse l'état inchangé.

Notez que pour savoir si l'état initial s'applique, vous devez effectuer un peu plus d'analyse pour détecter les littéraux de chaîne et de caractère.

Une fois que vous avez un NFA, vous pouvez utiliser des techniques standard pour construire une expression régulière (je ne les vois pas dans les articles Wikipedia, mais ils devraient être discutés dans les manuels).

Si vous avez déjà une expression régulière et que vous souhaitez la tester, vous pouvez comparer son langage généré avec celui du NFA déduit de la spécification du langage: l'égalité des langages réguliers est décidable. Une façon de décider de l'égalité est de construire un automate déterministe minimal pour chacun; si les langues sont équivalentes, les DFA minimaux seront isomorphes.

Gilles 'SO- arrête d'être méchant'
la source
Une recherche sur Google Livres donne cette référence pour l'algorithme de Kleene: books.google.co.uk/…
rgrig
0

Si vous écrivez un analyseur, ce genre de choses est géré par l'analyseur lexical. Et là, vous pouvez exprimer cela par des expressions régulières, ou (comme les flexexemples que j'ai vu) "s'échapper dans le langage sous-jacent" et terminer le travail là-bas. C'est-à-dire, en voyant /*juste avancer jusqu'à ce que vous trouviez */(un DFA pour cela est facile à construire, et à partir de là un fragment C est simple à écrire).

vonbrand
la source