Las gramáticas ID / LP son un subconjunto de gramáticas de estructura de frases , que se diferencian de otras gramáticas formales al distinguir entre restricciones de dominancia inmediata (ID) y precedencia lineal (LP). Mientras que las reglas tradicionales de estructura de frases incorporan predominio y precedencia en una sola regla, ID / LP Grammars mantiene conjuntos de reglas separados que no necesitan procesarse simultáneamente. Las Gramáticas ID / LP se utilizan en Lingüística Computacional .
Por ejemplo, una regla de estructura de frase típica como , lo que indica que un nodo S domina un nodo NP y un nodo VP, y que el NP precede al VP en la cadena de superficie. En las Gramáticas ID / LP, esta regla solo indicaría el dominio y una declaración de precedencia lineal, como, también se daría.
La idea saltó a la fama por primera vez como parte de la gramática de estructura de frase generalizada ; [1] [2] el enfoque de gramática ID / LP también se utiliza en la gramática de estructura de frases dirigidas por la cabeza , [3] gramática funcional léxica y otras gramáticas de unificación .
El trabajo actual en el Programa Minimalista también intenta distinguir entre dominación y orden. Por ejemplo, artículos recientes de Noam Chomsky han propuesto que, mientras que la estructura jerárquica es el resultado de la operación de construcción de estructura sintáctica Fusionar , el orden lineal no está determinado por esta operación y es simplemente el resultado de la externalización (pronunciación oral, o, en el caso de la lengua de signos, la firma manual). [4] [5] [6]
Definición de dominio y precedencia
Dominio inmediato
El dominio inmediato es la relación asimétrica entre el nodo madre de un árbol de análisis sintáctico y sus hijas, donde se dice que el nodo madre (a la izquierda de la flecha) domina inmediatamente a los nodos hijos (los que están a la derecha de la flecha), pero el las hijas no dominan inmediatamente a la madre. Los nodos hijos también están dominados por cualquier nodo que domine inmediatamente al nodo madre, sin embargo, esta no es una relación de dominio inmediato.
Por ejemplo, la regla sin contexto, muestra que el nodo etiquetado A (nodo madre) domina inmediatamente los nodos etiquetados B, C y D (nodos secundarios) y los nodos etiquetados B, C y D pueden ser dominados inmediatamente por un nodo etiquetado A.
Precedencia lineal
La precedencia lineal es la relación de orden de los nodos hermanos. Las restricciones LP especifican en qué orden pueden aparecer los nodos hermanos bajo la misma madre. Los nodos que emergen antes en cadenas preceden a sus hermanas. [2] LP se puede mostrar en reglas de estructura de frases en la forma significa que B precede a C precede a D, como se muestra en el árbol de abajo.
Una regla que tiene restricciones de ID pero no LP se escribe con comas entre los nodos secundarios, por ejemplo . Dado que no hay un orden fijo para los nodos secundarios, es posible que los tres árboles que se muestran aquí sean generados por esta regla.
Alternativamente, estas relaciones se pueden expresar a través de declaraciones de precedencia lineal, como , para significar que siempre que B y C son hermanas, B debe preceder a C. [2] [7]
El principio de transitividad se puede aplicar a las relaciones LP, lo que significa que si y , luego también. Las relaciones LP son asimétricas: si B precede a C, C nunca puede preceder a B. Una relación LP donde no puede haber nodos intermedios se llama precedencia inmediata, mientras que una LP donde puede haber nodos intermedios (los derivados del principio de transitividad) son se dice que tiene una precedencia débil. [8]
Gramaticalidad en las gramáticas ID / LP
Para que una cadena sea gramatical en una gramática ID / LP, debe pertenecer a un subárbol local que siga al menos una regla de ID y todas las declaraciones LP de la gramática. Si todas las cadenas posibles generadas por la gramática se ajustan a este criterio, entonces es una gramática ID / LP. Además, para que una gramática pueda escribirse en formato ID / LP, debe tener la propiedad de Exhaustive Constant Partial Ordering (ECPO): es decir, que al menos parte de las relaciones ID / LP en una regla se observe en todas las demás. reglas. [2] Por ejemplo, el conjunto de reglas:
(1)
(2)
no tiene la propiedad ECPO, porque (1) dice que C siempre debe preceder a D, mientras que (2) dice que D siempre debe preceder a C.
Ventajas de las gramáticas ID / LP
Dado que las declaraciones LP se aplican independientemente del contexto de la regla de ID, nos permiten hacer generalizaciones en toda la gramática. [2] [7] Por ejemplo, dada la declaración LP, donde V es la cabeza de un VP, esto significa que en cualquier cláusula de cualquier oración, V siempre aparecerá antes que su hermana DP [7] en cualquier contexto, como se ve en los siguientes ejemplos.
Lucy ganó la carrera.
Ava le dijo a Sara que leyera un libro.
Esto se puede generalizar en una regla que se aplique a todo el inglés, , donde X es la cabecera de cualquier frase e YP es su complemento . Las gramáticas que no son ID / LP no pueden hacer tales generalizaciones en toda la gramática, por lo que deben repetir las restricciones de orden para cada contexto individual. [7]
La separación de los requisitos de LP de las reglas de identificación también explica el fenómeno del orden libre de palabras en el lenguaje natural. Por ejemplo, en inglés es posible poner adverbios antes o después de un verbo y hacer que ambas cadenas sean gramaticales. [7]
John de repente gritó. John gritó de repente .
Una regla de PS tradicional requeriría dos reglas separadas, pero esto puede describirse mediante la regla de ID / LP únicaEsta propiedad de las Gramáticas ID / LP permite generalizaciones lingüísticas cruzadas más fáciles al describir las diferencias específicas del idioma en el orden constituyente con declaraciones LP, por separado de las reglas de ID que son similares en todos los idiomas. [7]
Análisis de las gramáticas ID / LP
Dos algoritmos de análisis que se utilizan para analizar las Gramáticas ID / LP son el de Earley Parser y el de Shieber. [9]
Earley Parser en Gramáticas ID / LP
Las reglas de ID y LP imponen restricciones a las cadenas de frases; [9] cuando se trata de cadenas grandes, [9] las restricciones de estas reglas pueden hacer que la cadena analizada se vuelva infinita, lo que dificulta el análisis. El analizador Earley resuelve esto alterando [10] el formato de una gramática ID / LP en una gramática libre de contexto (CFG), dividiendo la gramática ID / LP en una gramática libre de contexto ordenada (CFG) y una gramática libre de contexto no ordenada (UCFG) . Esto permite que los dos algoritmos analicen cadenas de forma más eficiente; [9] en particular, Earley Parser utiliza un método de seguimiento de puntos que sigue una ruta lineal establecida por las reglas de LP. [9] En un CFG, las reglas LP no permiten componentes repetidos en la cadena analizada, pero un UCFG permite componentes repetidos dentro de las cadenas analizadas. [9] Si la gramática ID / LP se convierte a un UCFG, las reglas LP no dominan durante el proceso de análisis, sin embargo, sigue el método de seguimiento de puntos.
Análisis de Earley en CFG
Después de que la gramática ID / LP se haya convertido a la forma equivalente dentro de un CFG, el algoritmo analizará la cadena. Dejarestar de pie para empezar yrepresentan los elementos de la cadena y también representan Categorías sintácticas . Luego, el algoritmo analiza la cadena e identifica lo siguiente:
- La posición original del punto; por lo general, comienza con el elemento más a la izquierda de la cadena.
- La posición actual del punto; esto predice el siguiente elemento.
- La producción de la cadena completa. [9]
(1)
(2) (está siendo predicho)
(3)
Las cadenas analizadas se utilizan juntas para formar una lista de análisis [10], por ejemplo:
que la lista ayudará a determinar si el elemento de producción completado () se acepta dentro de la cadena principal. Lo hace mirando si las cadenas individuales producidas se encuentran en la lista de análisis. Si una o todas las cadenas individuales no se encuentran dentro de la lista de análisis, la cadena general fallará. Si una o todas las cadenas individuales se encuentran en la lista de análisis, se aceptará la cadena general. [10]
Análisis de Earley en UCFG
El UCFG es el equivalente apropiado para convertir la gramática ID / LP en para poder usar Earley Parser. [9] Este algoritmo lee cadenas de forma similar a cómo analiza CFG, sin embargo, en este caso, el orden de los elementos no se aplica; resultando en la falta de cumplimiento de las reglas de LP. Esto permite que algunos elementos se repitan dentro de las cadenas analizadas y el UCFG acepta conjuntos múltiples vacíos junto con conjuntos múltiples llenos dentro de sus cadenas. [9] Por ejemplo:
- La posición de origen del punto; está entre el conjunto vacío y el conjunto lleno.
- La posición actual del punto que predice el siguiente conjunto; el elemento que pasó el punto se moverá al conjunto vacío.
- La producción de la cadena completa. En este caso, la posición de los dos conjuntos en la posición de origen cambiará; el conjunto lleno está en el borde izquierdo y el conjunto vacío está en el borde derecho. [9]
(1)
(2) (están siendo pronosticados)
(3)
Al analizar una cadena que contiene varios elementos desordenados, Earley Parser la trata como una permutación , Y !, y genera cada cadena individualmente en lugar de usar una cadena para representar las cadenas analizadas repetidas. [9] Siempre que el punto se mueve sobre un elemento, el algoritmo comienza a generar cadenas analizadas de los elementos en el borde derecho en posiciones aleatorias hasta que no hay más elementos en el borde derecho. Deje que X 0 represente la cadena original y X 1 como la primera cadena analizada; por ejemplo:
cadena X 1 producirá, ¡3! = 6, diferentes cadenas analizadas del conjunto del borde derecho:
(1) (4)
(2) (5)
(3) (6)
El analizador Earley aplica cada cadena a las reglas individuales de una gramática [9] y esto da como resultado conjuntos muy grandes. Los conjuntos grandes en parte resultan en la conversión de la gramática ID / LP en una gramática equivalente, sin embargo, analizando la ID / LP Grammar es difícil para empezar. [9]
Algoritmo de Shieber
La base del algoritmo de Shieber [9] se basa en el Earley Parser para CFG, [10] sin embargo, no requiere que la gramática ID / LP se convierta en una gramática diferente [10] para poder ser analizada. Las reglas de ID se pueden analizar en una forma separada, S → ID {V, NP, S}, de las reglas LP, V
Análisis directo de una gramática ID / LP ordenada
Al analizar una gramática de ID / LP, directamente, se genera una lista de conjuntos que determinará si la producción de la cadena será aceptada o fallará. El algoritmo sigue 6 pasos (los símbolos utilizados también pueden representar las categorías sintácticas):
- Para todas las reglas de ID, agregue al elemento inicial en la lista de análisis, . [10]
- Si todos los elementos en , , y los elementos, , de no permite que Z sea precedido por ,, y Z no es un elemento de , ; luego la siguiente cadena, se puede agregar a .
- Si todos los elementos, , son elementos de , luego , y y todo de entonces el siguiente elemento se puede agregar a esta lista, .
- Este paso construirá la lista de canciones, , más. Cada artículo, ese es un elemento de y donde , y luego se agrega el siguiente elemento, , a .
- Si los artículos, , son elementos de y artículos, , son elementos de dónde , y ; la cuerda,, se agrega a .
- Si los artículos, , es un elemento de dónde , y ; la cuerda,, se agrega a .
Los pasos 2-3 se repiten exhaustivamente [10] hasta que no se puedan agregar más elementos nuevos y luego continúe con el Paso 4. Los pasos 5-6 también se repiten exhaustivamente [10] hasta que no se puedan agregar más elementos nuevos a la lista de conjuntos. La cadena se aceptará si una cadena se comporta o se parece a la producción,es un elemento de . [10] Por ejemplo:
Establecer listas | Artículos |
---|---|
| |
| |
| |
|
La producción completa de se acepta y produce la siguiente cadena de producción: . [10]
Análisis directo de una gramática ID / LP desordenada
La gramática de ID / LP no ordenada sigue el algoritmo de 6 pasos anterior para analizar las cadenas. La diferencia notable está en las producciones de cada set list; hay una cadena que representa las muchas cadenas individuales dentro de una lista. [9] La siguiente tabla muestra la lista de conjuntos de la Tabla 1.0, en una gramática desordenada:
Lista de conjuntos | Artículos |
---|---|
La cadena de producción completa, da como resultado una cadena similar a la gramática ID / LP ordenada; sin embargo, no se aplica el orden de los elementos dentro de la cadena. La cadena final se acepta ya que coincide con los elementos de la cadena original.
Observe cómo la versión desordenada de ID / LP Grammar contiene muchísimo menos cadenas que la UCFG; El algoritmo de Shieber usa una cadena para representar las múltiples cadenas diferentes para elementos repetidos. Ambos algoritmos pueden analizar las gramáticas ordenadas por igual, sin embargo, el algoritmo de Shieber parece ser más eficiente [9] al analizar una gramática desordenada.
Ver también
- Gramática generalizada de la estructura de la frase
- Ligüística computacional
- Analizando
- Analizador Earley
Referencias
- ^ Gazdar, Gerald; Pullum, Geoffrey K. (1981). "Subcategorización, orden constituyente y la noción 'cabeza ' ". En M. Moortgat; Hvd Hulst; T. Hoekstra (eds.). El alcance de las reglas léxicas . págs. 107-124. ISBN 9070176521.
- ^ a b c d e Gazdar, Gerald; Ewan H. Klein; Geoffrey K. Pullum; Ivan A. Sag (1985). Gramática generalizada de la estructura de la frase . Oxford: Blackwell y Cambridge, MA: Harvard University Press. ISBN 0-674-34455-3.
- ^ Daniels, Mike; Meurers, Detmar (2004). "GIDLP: un formato gramatical para HPSG basado en linealización" (PDF) . Actas de la XI Conferencia Internacional sobre Gramática de la Estructura de la Frase Dirigida por la Cabeza .
- ^ Chomsky, Noam (2007). "Exploraciones biolingüísticas: diseño, desarrollo, evolución". Revista Internacional de Estudios Filosóficos . 15 (1): 1–21. doi : 10.1080 / 09672550601143078 .
- ^ Chomsky, Noam (2011). "Lenguaje y otros sistemas cognitivos. ¿Qué tiene de especial el lenguaje?". Aprendizaje y desarrollo de idiomas . 7 (4): 263–278. doi : 10.1080 / 15475441.2011.584041 .
- ^ Berwick, Robert C .; et al. (2011). "Pobreza del estímulo revisitado" . Ciencia cognitiva . 35 (7): 1207–1242. doi : 10.1111 / j.1551-6709.2011.01189.x . PMID 21824178 .
- ^ a b c d e f Bennett, Paul (1995). Un curso de gramática de estructura de frase generalizada . Londres: UCL Press. ISBN 1-85728-217-5.
- ^ Daniels, M. (2005). Gramática ID / LP generalizada: un formalismo para analizar gramáticas HPSG basadas en linealización . (Tesis o Disertación Electrónica). Obtenido de https://etd.ohiolink.edu/
- ^ a b c d e f g h i j k l m n o p Barton, Jr., G. Edward (1985). "Sobre la complejidad del análisis de ID / LP" . Lingüística computacional . 11 (4): 205–218 - vía Association for Computational Linguistics.
- ^ a b c d e f g h yo j k l Shieber, Stuart M. (1983). "Análisis directo de gramáticas ID / LP" . Lingüística y Filosofía . 7 (2): 1–30 - a través de SRI International.