Lenguaje de programación|Gramática
Desde la perspectiva de producir lenguaje, se dan las definiciones de gramática y lenguaje.
La llamada producción del lenguaje significa formular un número limitado de reglas, con la ayuda de las cuales se pueden producir todas las oraciones de este lenguaje.
1. Definición de gramática
Las reglas que describen la estructura gramatical de una lengua se llaman gramática. La gramática es una tupla de cuatro G=(Vn, Vt, P, S).
Vn es un conjunto finito no vacío, y cada elemento del mismo se denomina símbolo no terminal.
Vt es un conjunto finito no vacío, y cada elemento del mismo; se llama símbolo terminal;
Vn∩Vt=?, Vn y Vt no contienen elementos comunes V=Vn∪Vt, V es el vocabulario de la gramática G, y los símbolos en V se llaman gramática; símbolos.
P es un conjunto finito de producciones, cada producción tiene la forma de una regla de "α→β", α es la parte izquierda de la producción, α∈V y α contiene al menos una no -símbolo terminal, β es la parte derecha de la producción, β∈V*, y β es una expresión candidata de α.
S∈Vn, llamado símbolo de inicio, debe aparecer como parte izquierda en al menos una producción.
2. Clasificación de la gramática
Hay cuatro tipos de gramática: tipo 0, tipo 1, tipo 2 y tipo 3. La diferencia entre estos cuatro tipos de gramáticas radica en las diferentes restricciones impuestas a las producciones.
Gramática tipo 0: Cualquier producción α→β de G tiene α∈(Vn∪Vt) y α contiene al menos un símbolo no terminal, β∈(Vn∪Vt)*;
p>
(Si se imponen las siguientes restricciones a cada producción de gramática de tipo 0, se puede obtener la siguiente gramática.)
Gramática de tipo 1: cualquier producción de G α → β ( S → ε Excepto) todos satisfacen |α|≤|β| (|x| representa el número de símbolos gramaticales en x, ε es la cadena vacía);
Gramática tipo 2: cualquier producción de G es en la forma de A→ β, donde A∈Vn, β∈(Vn∪Vt)*;
Gramática de tipo 3: cualquier producción de G está en la forma de A→a o A→aB ( o A→Ba), donde A , B∈Vn, a pertenece a Vt;
La gramática de tipo 0 es una gramática de frases, su función es equivalente a una máquina de Turing y cualquier lenguaje de tipo 0 es recursivamente enumerable. .
La gramática de tipo 1 es una gramática sensible al contexto. La sustitución de símbolos no terminales debe tener en cuenta el contexto y no se permite la sustitución con la cadena vacía ε.
La gramática de tipo 2 es una gramática libre de contexto y los símbolos no terminales se reemplazan sin considerar el contexto.
La gramática tipo 3 es equivalente a la gramática regular, por lo que también se le llama gramática regular o gramática lineal.
Las reglas léxicas del análisis léxico generalmente usan gramática de tipo 3;
Las reglas gramaticales del análisis gramatical generalmente usan gramática de tipo 2; existen muchos tipos de métodos de análisis gramatical, dependiendo del dirección de generación del árbol de sintaxis, se puede dividir en dos categorías: de abajo hacia arriba y de arriba hacia abajo.