Cómo escribir con la gramática libre de contexto

Massachusetts Institute of Tecnología lingüista Noam Chomsky describe "gramáticas" como un conjunto de reglas para la generación de cadenas de caracteres. A continuación, clasifica estas reglas de acuerdo con la complejidad de las cadenas que podrían generar. Es una forma teórica de ver la lengua y es un tema de debate entre los lingüistas. Es, sin embargo, muy útil en la descripción de los lenguajes de programación. Una parte estándar del plan de estudios de ciencias de la computación es "la teoría del lenguaje formal» - el estudio matemático de la generación de cuerda de reglas gramaticales similares. gramáticas libres de contexto son una de las gramáticas que Chomsky describe.

Instrucciones

1 Entender la jerarquía de Chomsky para tener una idea de lo que es posible - y lo que es imposible - con una gramática libre de contexto. El lenguaje más sencillo Chomsky describe es "expresiones regulares", el siguiente es más compleja las gramáticas libres de contexto, y el siguiente más complejos son los lenguajes sensibles al contexto. La lengua más compleja Chomsky describe las lenguas era de libre disposición.

2 Aprender los términos que se necesitan para entender la una regla básica que define una gramática libre de contexto. Gramáticas tienen dos tipos de símbolos: los terminales y no terminales. -terminales no se pueden reescribir de acuerdo con las reglas de la gramática, las terminales no se pueden reescribir. Hay un símbolo especial - Tradicionalmente, este símbolo es "S" - que se inicia cada proceso de generación de cadenas. Hay otro símbolo "épsilon" especial que es la cadena vacía.

3 Utilice el formato de regla que define un lenguaje libre de contexto: no-terminal solo se reescribe como cualquier combinación de terminales y no terminales. Por ejemplo, la gramática independiente del contexto para generar longitud poco común palíndromos binario tiene cuatro reglas: S -> 0, S -> 1, S -> 0S0 y S -> 1s1. Estas reglas se generan cadenas de longitud impar que se leen igual hacia adelante como hacia atrás. Por ejemplo, S -> 0S0 -> 00S00 -> 001S100 -> 0.011.100.

4 Ver cómo el cambio de reglas gramaticales cambia las cuerdas que se generan, La gramática independiente del contexto que genera todos los palíndromos binarios agrega la regla de gramática S -> épsilon. Para obtener únicamente longitud par palíndromos binarios, añadir el S -> regla épsilon y eliminar las dos reglas: S y S --0 -> 1.

5 Mira otro ejemplo de una gramática libre de contexto. Las expresiones matemáticas pueden ser generados por once reglas: S -> (T), S -> T + T, S -> TT, S -> T T, S -> T / T, T -> (T), T -> T + T, T -> TT, T -> T T, T -> T / T y T -> números. Puede ser de interés señalar que todos los lenguajes de programación se pueden escribir como lenguajes libres de contexto.

Consejos y advertencias

• A veces, varias reglas gramaticales libres de contexto se pueden combinar en una sola regla utilizando el "|" operador que se lee como "o". Por ejemplo, la gramática de palíndromos incluso longitud binaria se puede escribir con una sola regla S -> epsilon | 0S0 | 1S1.
• Epsilon, la cadena vacía, sólo debe aparecer en la parte derecha de una regla. Si aparece en el lado izquierdo de una regla, la gramática es el contexto ya no es libre.