regex - ¿Qué es una gramática gratuita de contexto?
parsing grammar (2)
¿Puede alguien explicarme qué es una gramática libre de contexto? Después de mirar la entrada de Wikipedia y luego la entrada de Wikipedia sobre la gramática formal, me siento total y totalmente aturdido. ¿Alguien sería tan amable de explicarme qué son estas cosas?
Me pregunto esto porque deseo investigar el análisis sintáctico, y también por el lado, la limitación de un motor de expresiones regulares.
No estoy seguro si estos términos están directamente relacionados con la programación, o si están más relacionados con la lingüística en general. Si ese es el caso, me disculpo, quizás esto podría ser movido si es así?
La teoría del lenguaje está relacionada con la teoría de la computación. ¿Cuál es el aspecto más filosófico de la Informática, sobre cómo decidir qué programas son posibles o cuáles serán posibles de escribir, y qué tipo de problemas es imposible escribir un algoritmo para resolver?
Una expresión regular es una forma de describir un idioma regular. Un lenguaje regular es un lenguaje que puede ser decidido por un autómata finito determinista.
Deberías leer el artículo en Finite State Machines: http://en.wikipedia.org/wiki/Finite_state_machine
Y los idiomas regulares: http://en.wikipedia.org/wiki/Regular_language
Todos los idiomas regulares son idiomas sin contexto, pero hay idiomas sin contexto que no son regulares. Un lenguaje sin contexto es el conjunto de todas las cadenas aceptadas por un Grammer libre de contexto o un autómata de inserción que es una máquina de estados finitos con una única pila: http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages
Hay idiomas más complicados que requieren una Máquina de Turing (Cualquier programa posible que pueda escribir en su computadora) para decidir si una cadena está en el idioma o no.
La teoría del lenguaje también está muy relacionada con el problema P vs. NP, y algunas otras cosas interesantes.
Mi introducción al libro de texto de tercer año de Computer Science fue bastante bueno para explicar esto: Introducción a la teoría de la computación. Por Michael Sipser. Pero me costó $ 160 comprarlo nuevo y no es muy grande. Tal vez puedas encontrar una copia usada o encontrar una copia en una biblioteca o algo que pueda ayudarte.
EDITAR:
Las limitaciones de las expresiones regulares y las clases de idiomas superiores se han investigado mucho en los últimos 50 años más o menos. Puede que le interese el lema del bombeo para los idiomas habituales. Es un medio de probar que cierto idioma no es regular:
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
Si un idioma no es regular, puede ser Context Free, lo que significa que podría describirse con un Grammer sin contexto, o incluso en una clase de idioma superior, podrías demostrar que no está libre de contexto por el lema de bombeo para Context Free idiomas que es similar al de las expresiones regulares.
Un lenguaje puede incluso ser indecidible, lo que significa que incluso una máquina de Turing (puede programar que su computadora pueda funcionar) no puede ser programada para decidir si una cadena debe ser aceptada como en el lenguaje o rechazada.
Creo que la parte que más le interesa son las máquinas de estados finitos (tanto deterministas como deterministas) para ver qué idiomas puede decidir una expresión regular, y el lema de bombeo para probar qué idiomas no son regulares.
Básicamente, un idioma no es regular si necesita algún tipo de memoria o capacidad para contar. El lenguaje de paréntesis correspondiente no es regular, por ejemplo, porque la máquina necesita recordar si ha abierto un paréntesis para saber si tiene que cerrar uno.
El lenguaje de todas las cadenas usando las letras a y b que contienen al menos tres b es un lenguaje regular: a ba ba ba
El lenguaje de todas las cadenas que usan las letras a y b que contienen más b''s que a''s no es regular.
Además, no debería ser que todo el lenguaje finito sea regular, por ejemplo:
El lenguaje de todas las cadenas de menos de 50 caracteres con las letras a y b que contienen más b''s que a''s es regular, ya que es finito, sabemos que podría describirse como (b | abb | bab | bba | aabbb | ababb |. ..) ect hasta que se enumeren todas las combinaciones posibles.
Una gramática libre de contexto es una gramática que satisface ciertas propiedades. En informática, las gramáticas describen los idiomas; específicamente, describen los lenguajes formales.
Un lenguaje formal es simplemente un conjunto (término matemático para una colección de objetos) de cadenas (secuencias de símbolos ... muy similar al uso de programación de la palabra "cadena"). Un ejemplo simple de un lenguaje formal es el conjunto de todas las cadenas binarias de longitud tres, {000, 001, 010, 011, 100, 101, 110, 111}.
Las gramáticas funcionan definiendo transformaciones que puedes hacer para construir una cadena en el lenguaje descrito por una gramática. Las gramáticas dirán cómo transformar un símbolo de inicio (generalmente S) en una cadena de símbolos. Una gramática para el idioma dado anteriormente es:
S -> BBB
B -> 0
B -> 1
La forma de interpretar esto es decir que S puede reemplazarse por B, y B puede reemplazarse por 0, y B puede reemplazarse por 1. Entonces, para construir la cadena 010 podemos hacer S -> BBB -> 0BB -> 01B -> 010.
Una gramática libre de contexto es simplemente una gramática en la que lo que está reemplazando (a la izquierda de la flecha) es un símbolo único "no terminal". Un símbolo no terminal es cualquier símbolo que utiliza en la gramática que no puede aparecer en sus cadenas finales. En la gramática anterior, "S" y "B" son símbolos no terminales, y "0" y "1" son símbolos "terminales". Gramáticas como
S -> AB
AB -> 1
A -> AA
B -> 0
No son regulares ya que contienen reglas como "AB -> 1".