¿Puede el algoritmo de patio de maniobras analizar las expresiones regulares de POSIX?

Question

A primera vista, el shunting yard algorithm parece aplicable al análisis de expresión regular POSIX, pero como no tengo mucha experiencia (o antecedentes teóricos) en la escritura de analizadores, me gustaría preguntar SO antes de saltar y escribir algo solo para obtener atrapado a medio camino.

Quizás una versión más sofisticada de la pregunta es: ¿Cuál es una buena declaración formal de la clase de problemas a los que se puede aplicar el algoritmo del patio de maniobras?

Aclaración: Esta pregunta se refiere a si se puede analizar la sintaxis POSIX re en un árbol de sintaxis abstracta utilizando los principios básicos del algoritmo de derivación, no si puede utilizar expresiones regulares para implementar el algoritmo de derivación. Lo siento, no estaba lo suficientemente claro como para empezar.

Answer 1

Diré que la respuesta a su pregunta es "no, no puede implementar el algoritmo del patio de maniobras con una expresión regular". Esto es por la misma razón por la que no puede analizar HTML arbitrario con expresiones regulares. Lo que se reduce a esto:

Las expresiones regulares no tienen una pila. Debido a que el algoritmo de yarda de derivación se basa en una pila (para empujar y explotar operandos mientras convierte de infijo a RPN), las expresiones regulares no tienen la "potencia" computacional para realizar esta tarea.

Esto pasa por alto muchos detalles, pero una "expresión regular" es una forma de definir un idioma normal. Cuando "usa" una expresión regular, le pide a la computadora que diga: "Mire un cuerpo de texto y dígame si alguna de esas cadenas está en mi idioma. El lenguaje que definí con una expresión regular". Apuntaré al this most excellent answer which you and everyone reading this should upvote para obtener más información sobre los idiomas habituales.

Por lo tanto, ahora necesita un concepto matemático para aumentar los "idiomas regulares" a fin de crear idiomas más potentes. Si fueras a caracterizar el algoritmo del patio de maniobras como una realización de un modelo de potencia computacional, entonces podrías decir que el algoritmo se describiría como context-free grammar (hey, qué sabes, ese enlace usa un árbol de análisis de expresiones como ejemplo).) A push-down automata. Algo con una pila.

Si no está familiarizado con la teoría de los autómatas y las clases de complejidad, esos artículos de wikipedia probablemente no sean tan útiles sin explicarlos desde cero.

El punto es que usted puede usar regex para ayudar a escribir yarda de maniobras. Pero las expresiones regulares no son muy buenas para realizar operaciones que tienen una profundidad arbitraria, que tiene este problema. Así que no pasaría demasiado tiempo yendo por la avenida Regex para este problema.

Answer 2

No veo por qué no sería adecuado. Mirando un viejo código, parece que utilicé una estrategia de análisis completamente diferente para mi último analizador de expresiones regulares, sin embargo (esencialmente, un recorrido desde el principio, construyendo la representación de autómatas resultante sobre la marcha, con una mirada anticipada y recursiva llamadas para implementar la agrupación de expresiones regulares).

Answer 3

Estoy bastante seguro de que sí. Si nos fijamos en el paquete de expresiones regulares de Henry Spencer:

regexp.shar.Z

que sirvió de base para las expresiones regulares de Perl, usted notará que él describe el programa como estar en "forma normal ferrocarril".

Answer 4

Supongo que tendrá algunos problemas porque los diferentes caracteres tienen diferentes significados en diferentes contextos, p. Ej.

^[^a-z][asd-] 

El ^ tiene dos significados diferentes y también lo hace la -. Creo que elegiría un analizador de descenso recursivo.