¿Son las expresiones regulares ?

16

Si tengo una gramática de tipo 3, se puede representar en un autómata pushdown (sin realizar ninguna operación en la pila) para poder representar expresiones regulares utilizando lenguajes libres de contexto. Pero, ¿puedo saber si una gramática de tipo 3 es , , , etc. sin construir tablas de análisis?L L ( 1 ) S L R ( 1 )LR(1)LL(1)SLR(1)

Andrea Tucci
fuente

Respuestas:

15

Todos los idiomas regulares tienen gramáticas LL (1). Para obtener dicha gramática, tome cualquier DFA para el lenguaje regular (quizás haciendo la construcción del subconjunto en el NFA obtenido de la expresión regular), luego conviértalo en una gramática regular recursiva a la derecha. Esta gramática es entonces LL (1), porque cualquier par de producciones para el mismo no terminal comienza con símbolos diferentes o uno produce ε y tiene $ como token anticipado. En consecuencia, todos los lenguajes regulares también son LR (1), ya que cualquier gramática LL (1) es LR (1). Además, utilizando un resultado importante de este documento , puede mostrar que cualquier lenguaje LR (1) tiene una gramática SLR (1), lo que significa que cualquier lenguaje normal tiene una gramática SLR (1).

Sin embargo, los idiomas normales no son todos LR (0). Los lenguajes LR (0) tienen propiedades muy específicas, en particular, deben estar libres de prefijos. Por lo tanto, el lenguaje regular {a, aa} no es LR (0), aunque es claramente regular (regex a | (aa)). Sin embargo, los idiomas LR (0) no están contenidos adecuadamente en los idiomas regulares; esta gramática para {0 n 21 n | n ≥ 1} es LR (0), pero el idioma no es regular:

S -> E
E -> 0E1 | 2

¡Espero que esto ayude!

templatetypedef
fuente
2
El hecho de que las gramáticas regulares correctas acepten exactamente el conjunto de idiomas regulares generalmente se hace en clase (o incluso en los ejercicios), por lo que la respuesta es mucho más inmediata.
Raphael
2

La sintaxis de expresión regular (simple) (usted dijo "representación") es LR (0). No necesita ninguna búsqueda anticipada para analizar una cadena que representa una expresión regular. Puede decidir esto fácilmente ejecutando un generador de analizadores en una gramática para expresiones regulares: -} También puede codificar fácilmente un analizador de descenso recursivo simple (LL (0)) para expresiones regulares; cualquier cosa que sea LL (0) es LR (0).

No sé si la sintaxis de los llamados "regexps" más complicados como el de Perl es así; pero las expresiones regulares de Perl son estrictamente más poderosas que las expresiones regulares, por lo que no son expresiones regulares simples.

Para determinar si una gramática tiene alguna propiedad, debe ejecutar algún tipo de predicado. Para determinar si es (S) LR (k), debe ejecutar un predicado que pueda verificar esa propiedad. En efecto, dicho predicado debe construir las tablas de análisis, debido a la forma en que se definen.

Ira Baxter
fuente
Perl expresiones regulares funciona en NFA
La pregunta no era sobre cómo funcionaban las expresiones regulares de Perl. Se trataba de si las expresiones regulares (¿Perl?) Eran analizables por ciertas tecnologías. Puedo creer que las expresiones regulares de Perl usan un NFA para hacer su correspondencia, junto con alguna otra captura de datos sensible al contexto, pero no veo la relevancia de la pregunta.
3
-1 Las expresiones regulares no son LR (0). Los lenguajes LR (0) deben estar libres de prefijo, pero la expresión regular a|(aa)describe un lenguaje que no está libre de prefijo. Además, los lenguajes LR (0) no pueden manejar gramáticas con producciones epsilon, por lo que el lenguaje normal {epsilon, a} no es LR (0). Sin embargo, los lenguajes regulares son LL (1) porque puede escribirlos como gramáticas regulares y, por lo tanto, todos son LR (1). Dado que cualquier lenguaje LR (1) tiene una gramática SLR (1), esto significa que todos los idiomas regulares son SLR (1).
templatetypedef
1
Con respecto a LL (0), es al revés: los lenguajes LL (0) son un subconjunto apropiado de lenguajes regulares. Tenga en cuenta que LL (0) significa que no usa anticipación para decidir entre diferentes derivaciones, lo que básicamente significa que no hay decisiones y el lenguaje consiste en una sola palabra. LR (0), por el contrario, es una clase útil; una vez más, no utiliza anticipación para decidir (aquí para las reducciones), pero aún existe cierta diversidad debido al hecho de que el cambio puede distinguir entre diferentes producciones.
1
@ IraBaxter- La sintaxis de las expresiones regulares tampoco es LR (0) porque las expresiones regulares no tienen prefijo libre. Tampoco son LL (0), porque los lenguajes LL (0) solo pueden contener una sola cadena (o ninguna cadena).
templatetypedef