Noam Chomsky revolucionó el estudio de la lengua con la clasificación de la gramática en la jerarquía de Chomsky. Sus teorías no han sido completamente aceptada por todos los lingüistas, pero tuvo un gran impacto en el estudio de los lenguajes de programación. Una parte estándar de los planes de estudio de la informática actual es una clase de Teoría lenguaje formal. Estas clases comienzan con una discusión de las teorías de Chomsky y pasar a discutir los aspectos matemáticos de los lenguajes de programación. Una de las clasificaciones en la jerarquía de Chomsky es gramáticas libres de contexto.
Instrucciones
1 Aprender los conceptos básicos de los lenguajes formales con el fin de comprender la jerarquía de Chomsky y donde la gramática libre de contexto encaja. Gramáticas formales son un conjunto de reglas para producir cadenas de símbolos. Las reglas gramaticales son las reglas de reescritura. El lado izquierdo de la regla puede ser reescrito como el lado derecho de la regla. Hay dos tipos de símbolos: los terminales y no terminales. Los símbolos terminales son las palabras en la lengua. Los no terminales son parte de la gramática y deben ser reescritos para producir palabras en la lengua.
2 Entender la jerarquía de Chomsky con el fin de entender lo que es posible con diferentes clases de gramática. Hay cuatro niveles en la jerarquía de Chomsky: El nivel más bajo - gramática más simple - se expresiones regulares. Las series típicas son algo así como tres letras seguidas de cuatro números. El siguiente nivel es gramáticas libres de contexto, que deben tener sólo un símbolo no terminal en el lado izquierdo de una regla gramatical. El siguiente nivel es el idioma sensibles al contexto, que no tienen restricciones en las reglas de reescritura - este es el modelo para la mayoría de los lenguajes de programación. El nivel más alto depende de si usted es un lingüista o un informático.
3 Mira algunos ejemplos de gramáticas libres de contexto para tener una idea de su poder generativo. La gramática independiente del contexto que genera expresiones aritméticas tiene cinco reglas: "S: = TPT", "P: = +", "P: = +", "T: = TPT", "T:. = Un número" Generación siempre comienza con "S", y una generación típica es "S -> TPT -> 5 + TPT -> 5 + 3 * 4." La gramática independiente del contexto que genera parendthes equilibradas tiene tres reglas: "P: = (P)", "P: = PP" y "P: = la cadena vacía". Una generación de cadena típico podría ser "P -> (P) -> (PP) -> (() P) -> (() (P)) -> (() ((P))) -> (() (())) ". Palimdromes en A y B tienen tres reglas gramaticales: "S: = aSa", "S: = bSb" y "S: = la cadena vacía". Un ejemplo es la generación de "S -> ASA -> aaSaa -> aabSbaa -> aabbaa."
Consejos y advertencias
- La cadena vacía se denomina tradicionalmente épsilon, por lo que la tercera regla de la gramática paréntesis se escribiría "P: = épsilon." Sin esta notación sería imposible deshacerse del no terminal "P" en una gramática libre de contexto.
- Las reglas de una gramática libre de contexto requieren que épsilon nunca aparece en el lado izquierdo de una regla.