2009-04-07 65 views
5

Tengo curiosidad, ¿alguien sabe una buena manera de hacer coincidencias de expresiones regulares en C? La única forma en que puedo pensar es a través de Flex. ¿Es esta la única manera o hay una mejor manera?Expresiones regulares en C

Gracias!

Respuesta

13

Uh ... La mejor forma de hacerlo es

#include <regex.h> 

Esa es la POSIX standard API de expresiones regulares.

Para los sistemas que no son POSIX, rodar uno mismo es una alternativa, un motor regex básico no es demasiado difícil de lograr. Estoy seguro de que también hay soluciones listas para usar, no he comprado ninguna.

Ahora que lo pienso, creo que glib tiene uno.

+1

no escriba su propio motor de expresiones regulares. ese es un consejo horrible –

0

Quizás this article ayudará? Le muestra cómo usar las funciones de expresiones regulares definidas en regex.h.

Sí, no es simplemente la expresión regular POSIX maravilloso que lo tienen todo, así que se preguntaron por qué no están en C? Bueno, he encontrado la respuesta y me tiene feliz, que están allí, y aquí cómo utilizar ellos

11

Dependiendo de qué dialecto que está buscando y qué plataforma estás en:

  • Es probable que las expresiones regulares de POSIX estén en la biblioteca estándar de C: consulte <regex.h> y regcomp, regerror, regexec, regfree.
  • libPCRE proporciona la mayor parte de las expresiones regulares de Perl extendida características
  • labia tiene GRegex
  • Henry Spencer's Tcl Regex library.

Henry Spencer también ha hecho otro regex library, utilizado por las versiones actuales de TCL y PostgreSQL. Este es interesante porque es una implementación híbrida de NFA/DFA.

Regexes que aceptan la misma cadena de múltiples maneras (como a * a?) Requieren inherentemente un NFA. La implementación habitual modela el NFA como un DFA utilizando retroceso, que puede ser tanto como O (2^longitud (entrada)) para un patrón particularmente degenerado. Sin embargo, la implementación recursiva simple puede extenderse con la captura, las referencias retrospectivas, las devoluciones de llamadas al código y todas las características "adicionales" habituales que ofrecen muchos idiomas, además de probar las coincidencias.

El enfoque "NFA" rastrea múltiples estados actuales y los actualiza con cada carácter entrante (consulte la descripción de Ross Cox de Thompson NFA regexes para obtener más información). Este enfoque es O (input.length * pattern.length), que es más rápido, inmensamente en el peor de los casos, pero no puede realizar backrefs o capturas ya que no hace un seguimiento de cómo llegó a un estado.

El enfoque de Spencer es un híbrido, compilando algunas partes de un patrón para el enfoque de NFA, y utilizando retroceso solo cuando sea necesario para las capturas que realmente se solicitaron. Esto a menudo es una ganancia sustancial (vea TCL position in the regex-dna shootout).

+0

SUficiente interpretación de expresiones regulares de estilo NFA utiliza retroceso, mientras que el estilo de DFA no? – Vatine

+0

Las expresiones regulares que pueden aceptar la misma cadena de múltiples formas necesitan inherentemente un NFA. La implementación habitual como DFA + backtracking es O (2^n). El enfoque "NFA" mantiene múltiples estados actuales y los actualiza con cada carácter entrante (O (n * m). Consulte http://swtch.com/~rsc/regexp/regexp1.html – puetzk

1

Un enfoque completamente diferente es tratar un Parsing Expression Grammar (PEG). Un PEG viene al problema de coincidencia de patrones desde el punto de vista de un analizador, e incluso puede aprovechar las múltiples reglas que forman una gramática completa. Eso hace posible escribir expresiones que coincidan con paréntesis equilibrados, que de otro modo son bastante difíciles de expresar en la mayoría de los dialectos de expresiones regulares.

Aunque los PEG son relativamente nuevos, no debe haber unas pocas implementaciones por ahí que son utilizables a partir de C.

La implementación de PEG, he utilizado es LPeg. Está perfectamente vinculado a Lua, y casualmente fue escrito por uno de los autores principales de Lua, Roberto Ierusalimschy. Proporciona una implementación completa de PEG, y también incluye un adaptador que traduce una expresión regular en el PEG equivalente para su ejecución.

Enlazar el núcleo Lua a un programa C solo para obtener acceso a LPeg puede sonar como una exageración, pero realmente no sería tan difícil de hacer, incluso si no tenía planeado usar Lua para otros fines.

Cuestiones relacionadas