Download "Desarrollo de un entorno para análisis sintáctico de lengua " [P.F.C.]

DESARROLLO
DE
UN
ENTORNO PARA EL ANÁLISIS
SINTÁCTICO DE UNA LENGUA
NATURAL
APLICACIÓN AL CASTELLANO
AUTOR : Juan Manuel Montero Martínez
TUTOR : José Colás Pasamontes
Departamento de Ingeniería Electrónica
Escuela Técnica Superior de Ingenieros De Telecomunicación
Universidad Politécnica de Madrid
PROYECTO FIN DE CARRERA
TITULO
DESARROLLO DE UN ENTORNO PARA EL ANÁLISIS SINTÁCTICO DE
UNA LENGUA NATURAL. APLICACIÓN AL CASTELLANO
AUTOR
JUAN MANUEL MONTERO MARTÍNEZ
TUTOR
JOSÉ COLAS PASAMONTES
DEPARTAMENTO
GRUPO
INGENIERÍA ELECTRÓNICA
TECNOLOGÍA DEL HABLA
MIEMBROS DEL TRIBUNAL CALIFICADOR
PRESIDENTE
JOSÉ MANUEL PARDO MUÑOZ
VOCAL
JOSÉ CARLOS GONZÁLEZ CRISTÓBAL
VOCAL SECRETARIO
FECHA DE LECTURA
CALIFICACIÓN
JOSÉ COLAS PASAMONTES
CAPITULO I
INTRODUCCION ......................................................................................................................
1.1 Justificación ...............................................................................................................
I.2.Ingeniería lingüística.................................................................................................
I.2.1 Síntesis de voz .............................................................................................
I.2.2 Traducción y doblaje automáticos ...........................................................
I.2.3 Correctores sintácticos .............................................................................
I.2.4 Interfaces naturales hombre-máquina ...................................................
I.2.5 estudios teórico-prácticos de lingüística ..................................................
I.2.6 Otros ............................................................................................................
1
1
2
3
4
5
6
8
8
CAPITULO II
LA LENGUA NATURAL .......................................................................................................... 9
II.1 Caracterización ........................................................................................................ 9
II.2 Mecanismos habituales en una lengua natural .................................................. 10
CAPITULO III
LOS LENGUAJES FORMALES ...........................................................................................
III.1 Definición ..............................................................................................................
III.2 Jerarquía de Chomsky ........................................................................................
III.2.1 Tipo 3 .....................................................................................................
III.2.1.1 Limitaciones de los lenguajes regulares .............................
III.2.2 Tipo 2 .....................................................................................................
III.2.2.1 Limitaciones de los lenguajes de contexto ..........................
III.2.3 Tipo 1 ....................................................................................................
III.2.4 Tipo 0 .....................................................................................................
15
15
16
17
18
20
21
23
24
CAPITULO IV
EL MODELO LINGÜÍSTICO ...............................................................................................
IV.1 Presentación ..........................................................................................................
IV.2 Componente léxico ...............................................................................................
IV.3. Componente sintáctico ........................................................................................
IV.4 Componente fonológico .......................................................................................
IV.5 Componente semántico ........................................................................................
IV.6 Esquema orientado al reconocimiento ...............................................................
24
25
26
28
30
30
32
CAPITULO V
COMPILACIÓN DE DICCIONARIOS ................................................................................
V.1 Presentación ............................................................................................................
V.2 Acceso secuencial ...................................................................................................
V.3 Compilación en forma de autómata.....................................................................
V.3.1 Independencia del orden de operaciones .............................................
V.3.2 La suma de gramáticas ..........................................................................
V.3.3 Eficiencia de compilación ......................................................................
34
34
34
35
41
44
44
V.4 Utilización de léxicos en presencia de ruido ....................................................... 48
V.5 Programas empleados............................................................................................ 48
V.5.1. Implementación en PC .......................................................................... 48
CAPITULO VI
ANÁLISIS SINTÁCTICO DE GRAMÁTICAS DE CONTEXTO LIBRE ......................
VI.1 Presentación ..........................................................................................................
VI.2 Análisis LR(1) .......................................................................................................
VI.2.1 Tablas LALR(1) ampliadas .................................................................
VI.3 ATNs ......................................................................................................................
VI.4 Algoritmos generales ...........................................................................................
VI.4.1 Algoritmo de Cocke-Younger-Kasami
......................................................................................................................................................
VI.4.1.1 Preproceso
......................................................................................................................................................
VI.4.1.2 CYK en forma matricial ...................................................................
VI.4.1.3 CYK en forma asíncrona .........................................
VI.4.1.4 CYK en forma síncrona ....................................................................
VI.4.1.5 Algoritmo de reconstrucción ............................................................
VI.4.1.6 Ejemplo de reconocimiento ..............................................................
VI.4.1.7 CYK con predicción ..........................................................................
VI.4.1.8 Diferentes implementaciones ............................................................
VI.4.1.9 Linealización del Chart
......................................................................................................................................................
VI.4.2 Algoritmo de Earley ..........................................................................................
VI.4.2.1 Funcionamiento básico ......................................................................
VI.4.2.2 Reconstrucción del árbol sintáctico .................................................
VI.4.2.3 La cadena vacía ..................................................................................
VI.4.2.4 Un ejemplo completo .........................................................................
VI.4.2.5 Complejidad del algoritmo ...............................................................
50
50
51
52
53
55
55
55
56
56
57
57
58
64
64
67
68
68
68
68
70
80
CAPITULO VII
EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS .....................................
VII.1 Presentación.........................................................................................................
VII.2 Estructura de la gramática ................................................................................
VII.3 Formato del diccionario ....................................................................................
81
81
82
83
VII.4 Formato de los ficheros .REG ...........................................................................
VII.5 Formato del fichero .GRA .................................................................................
VII.6 Semántica de la notación empleada ..................................................................
VII.7 Extensión de las reglas .......................................................................................
VII.8 Dependencias intra-gramaticales ......................................................................
VII.9 MENÚ PRINCIPAL...........................................................................................
VII.9.1 Cargar...................................................................................................
VII.9.1.1 Avisos y errores ....................................................................
VII.9.1.2 Estadísticas ...........................................................................
VII.9.2 Editar ....................................................................................................
VII.9.2.1 Submenú de edición.............................................................
VII.9.3 Finalizar................................................................................................
VII.9.4 Opciones
......................................................................................................................................................
VII.9.5 Mostrar reglas .....................................................................................
VII.9.6 Mostrar símbolos .................................................................................
VII.9.6 Analizar texto.......................................................................................
84
84
86
87
88
90
90
92
94
96
96
97
97
97
98
98
CAPITULO VIII
LINGÜÍSTICA APLICADA .................................................................................................
VIII.1 Los conceptos de oración y enunciado ..........................................................
VIII.2 Sintaxis del enunciado fragmentario
....................................................................................................................................................
VIII.2.1 Fragmentos y elipsis verbal ............................................................
VIII.2.2 Clasificación pragmática de los fragmentos .................................
VIII.2.3 Clasificación sintáctica de los fragmentos ....................................
VIII.3 La oración formal............................................................................................
VIII.3.1 El sintagma nominal ....................................................................................
VIII.3.1.2 Constituyentes del Sintagma Nominal ...........................
VIII.3.1.2.1 El nombre propio..............................................
VIII.3.1.2.2 Los pronombres personales.............................
VIII.3.1.1.3 El nombre común .............................................
VIII.3.1.3 ¿Nominalización o elipsis? ..............................................
VIII.3.2 El sintagma verbal ...........................................................................
VIII.4 La coordinación y la yuxtaposición ..............................................................
VIII.4.1 Paradigma transformacional .........................................................
VIII.4.1 Aritmética coordinativa ..................................................................
VIII.4.2 Coordinación y elipsis .....................................................................
VIII.4.3 Homogeneidad de coordinación.....................................................
VII.5.La sintaxis X con barra ....................................................................................
100
100
100
101
102
102
103
104
105
105
105
106
106
107
108
108
109
110
111
112
CAPITULO IX
EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA : EL NOMBRE PROPIO
.................................................................................................................................................... 113
CAPITULO X
INTEGRACIÓN DE LA SINTAXIS EN LOS SISTEMAS DE RECONOCIMIENTO DE
VOZ........................................................................................................................................... 119
X.1 Parsing de un lattice ............................................................................................ 121
X.1.1 CYK ....................................................................................................... 121
X.1.2 Algoritmos predictivos ......................................................................... 121
X.2 Integración síncrona ............................................................................................ 124
X.2.1 Integración de CYK con la programación dinámica ....................... 124
X.2.2 Guiado del reconocimiento mediante predicción sintáctica ............ 125
CAPITULO XI
LÍNEAS FUTURAS ................................................................................................................ 128
BIBLIOGRAFÍA ..................................................................................................................... 132
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
CAPITULO I
INTRODUCCION Y MOTIVACIONES
1.1 Justificación
El desarrollo vivido en la última década por el reconocimiento del habla ha permitido la
inclusión de módulos no acústicos1 en las nuevas versiones de los sistemas implementados.
Conceptos clásicos de la lingüística como la sintaxis, la semántica, la morfología... entran con
fuerza en la bibliografía reciente, añadiéndose a otros ya habituales como el de léxico o fonética.
Inicialmente, las arquitecturas usadas eran plenamente modulares y de funcionamiento
secuencial: subsistemas de análisis sintáctico, de verificación semántica o de gestión de diálogo
son añadidos para posprocesar la información generada por módulos de tratamiento acústico o
acceso léxico2 (cadenas de fonemas o de palabras). La aséptica separación (al menos
idealmente) entre los problemas acústicos y los propios de la gramático-pragmática permitía su
tratamiento aislado, evitándose los múltiples problemas inevitablemente presentes en toda
interacción fuerte.
La continua evolución de las técnicas registrada en los años ochenta (Programación
Dinámica, Modelos Ocultos de Markov tanto de fonemas como de palabras, reconocimiento de
habla continua... ) va dejando obsoletos los sistemas desarrollados. Cuando estas nuevas
técnicas alcanzan su madurez, comienzan a aparecer artículos y comunicaciones a congresos
interesándose por la definitiva incorporación de información no fonética con objeto de mejorar
las tasas de reconocimiento. Los "lattices"o celosías de fonemas o palabras contenían errores de
inserción, sustitución y borrado que dan lugar a que, aún con buenas tasas de reconocimiento de
palabras, se acepten numerosas frases gramaticalmente erróneas. Esta vez se incorpora el
modelo del lenguaje dentro del propio reconocedor, de tal modo que un autómata (equivalente
en cuanto a potencia expresiva a un lenguaje tipo 3 de la jerarquía propuesta en Chomsky[57] y
que posteriormente explicaremos) guía la tarea de reconocer y evita la aceptación de errores.
La integración del módulo gramatical en el acústico-fonético supuso una mejora,
especialmente en aplicaciones de complejidad limitada donde los autómatas modelaban
1Entendemos
por módulos no acústicos aquellos cuyo fin no es
extraer la información fonética incluida en el habla, sino
procesarla con fines diversos.
2Ambiciosos
esta filosofía.
sistemas como el francés Myrtille I seguían
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
aceptablemente las posibles situaciones3. Sin embargo la investigación se encaminaba
rápidamente hacia el uso de unos modelos del lenguaje humano más complejos. Los algoritmos
surgidos en los años sesenta y setenta, en los albores de la lingüística computacional, cuando se
buscaban métodos potentes y rápidos para compilar lenguajes de programación, fueron
retomados y mejorados para adaptarlos a las nuevas necesidades: ambigüedades, errores en la
cadena de entrada, integración en los sistemas de reconocimiento, integración VLSI de los
mismos...
Teniendo in mente este marco, se inicia una línea de investigación en el DIE para
incorporar información sintáctica a la algorítmica de reconocimiento que ya se poseía,
continuación de las primeras experiencias en sintaxis y guiado mediante autómatas conseguidas
en diversos Proyectos Fin de Carrera previos.
Tras un estudio de la bibliografía reciente y procurando no desbordar nuestras
posibilidades de tiempo y personal investigador, optamos por abordar en paralelo la realización
de una gramática de contexto libre con que modelar el castellano, y el estudio de la complejidad
e integrabilidad de los algoritmos más utilizados. Para ello se hizo necesaria la elaboración de
un entorno que nos permitiera desarrollar cómodamente la gramática de un modo incremental,
realimentado mediante el análisis de textos. También se precisa obtener un diccionario
categorizado que sirva de base para el análisis (ampliado posteriormente al ir introduciendo
nuevos textos).
I.2.Ingeniería lingüística
Con el nacimiento de las llamadas Industrias del Lenguaje4, la utilidad de los
conocimientos gramaticales que esperamos obtener no se reducen al reconocimiento de voz para
gran vocabulario y alta calidad. Entre otros campos donde sería posible usar información
sintáctica, encontramos:
-síntesis de voz
-traducción y doblaje automáticos5
-correctores sintácticos para ayuda a la edición
-interfaces naturales hombre-máquina
3Estos
sistemas son denominados "task-oriented" y se
centran en entornos de accesos a bases de datos bancarias o de
líneas aéreas, bancarias... (Rabiner y Levinson[85], Roe et
all[91] y [92]).
4En
1987 la Comunidad Europea puso en marcha e programa
LIFE ,Languaje Industry For Europe.
La traducción automática requiere gran robustez en el "parsing" para resultar útil (lo mismo sucede en la síntesis de voz).Cada vez son más los
programas comerciales de tratamiento estilístico y gramatical de texto escrito.
5
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
-estudios teórico-prácticos de lingüística
I.2.1 Síntesis de voz
Los sistemas de síntesis de voz a partir de texto, a pesar de haber conseguido una
elevada inteligibilidad en su conversión grafema-fonema, no producen un habla natural como
sería deseable para provocar en los potenciales oyentes humanos un rechazo mínimo, una
aceptación máxima.
Abordar la lectura automática de frases o párrafos largos sin caer en ese pausado
irregular que dan las reglas heurísticas de corto alcance, requiere de información relativamente
completa sobre la estructura de los enunciados (Garrido[91], pág.10 ).
En el siguiente ejemplo tomado de Alcina[75], pág.4576, se puede observar como las
relaciones sintácticas influyen poderosamente en la introducción "lógica" de pausas (señaladas
con barra vertical):
"Cruzan por las calles | viejas enlutadas"
Viejas enlutadas es el sujeto del verbo cruzan, con quien concuerda. La lejanía entre
ambos ( se ha interpuesto por las calles) obliga a la pausa o el paso de entonación ascendente a
descendente con el fin de marcar que existen elementos concordantes en orden diferente al
habitual.
La teoría de la acentuación por foco sugiere asignar el acento a los constituyentes
sintácticos de las oraciones, no a las palabras o las sílabas. Un constituyente (una palabra o
grupo de palabras estrechamente relacionadas) será acentuado si está marcado como focal en las
reglas sintácticas, o si la palabra que lo constituye está señalada como fuerte en el lexicón y el
nodo que la domina inmediatamente es acentuado (Dirksen [92], págs.22-25.
Si el acento recae sobre una palabra marcada como débil no provocará inversiones de
acento caso de intentar acentuarla mediante la regla anterior.
Si se suceden varias palabras débiles complementando a una fuerte (adjetivos y un
sustantivo) será necesario hacer alternativamente alguna de ellas fuerte para llevar un ritmo
agradable y no monótono.
En el Esbozo[73], apartado 1.5, encontramos una clasificación de las categorías del
castellano en débiles y fuertes (acentuadas y no acentuadas).
6El
resto de oraciones del texto de Azorín son más sencillas de pausar, debido a los signos de puntuación que sirven de
guía. Sin embargo, su ausencia no impediría una correcta
entonación:generalmente son causas sintácticas las que han
motivado su inclusión: subordinación, concordancia, dependencias lejanas, la elipsis... Más ejemplos en Esbozo[73], pág.
399.
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
I.2.2 Traducción y doblaje automáticos
Traducir una frase de un idioma a otro no se limita, desgraciadamente, a consultar
palabra tras palabra en un diccionario bilingüe. Las estructuras sintáctico-semánticas son diferentes para las diversas lenguas naturales.
Veamos unos ejemplos de cómo la sintaxis es necesaria para la traducción ingléscastellano y castellano-inglés (aunque, obviamente, no lo único necesario):
-numerosos sintagmas preposicionales con de se convierten en aposiciones antepuestas
(inexistentes en castellano) al traducir del inglés: tipo de interés pasa a interest rate.
-mientras el inglés tiende a anteponer los adjetivos, el castellano tiende a posponerlos:
cuenta corriente será current account.
-la reglas de omisión de determinante difieren: los bonos del Tesoro se convierten en
Treasury notes debido a la aposición.
-la combinación de todo lo anterior, puede dar lugar a una fuerte reordenación: la
transformación efectiva de España sería Spain's efective transformation.
-los sujetos inexistentes o elípticos tan comunes en castellano deben ser explícitos en
inglés. "nobody talks..." o "it's said..." resultaría de la traducción de "no se habla..."
-el ordenamiento libre de sintagmas que caracteriza al castellano debe ser linealizado.
"está llegando una ola que..." debería pasar como "a wave that...is arriving"
-las sustantivaciones de adjetivos... por medio del uso de determinantes, requieren
rodeos lingüísticos: lo político frente a the political cuestion
-los verbos subcategorizadores: transitivos, con preposición... distan mucho de coincidir.
"sorprenderse de..." equivale a "be surprised by..." (obsérvese el cambio de voz activa a voz
pasiva)
-la concordancia de número posee diferente aritmética en ambos idiomas: tres dólares
en castellano, pero three dollar en inglés.
-los pronombres requieren interpretación semántica de sus antecedentes. En "nadie habla
en España de ella misma", ella tiene a España como referente, y no a nadie. Además el referente
puede ser lingüístico (una oración, un sintagma...) o contextual.
-la capacidad de creación de nuevas palabras hace necesaria la utilización de reglas
morfológicas. ¿ Cómo cabría traducir politicismo ?
-existen ambigüedades léxicas bidireccionales dependientes de los contextos sintáctico y
semántico. banco puede ser traducido como bench o como bank. bank, a su vez, podría
corresponderse con banco u orilla.
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
-el contexto pragmático obligaría a usar inteligencia artificial. En el ayuntamiento
compró los bancos por cinco millones" es obvio que la traducción requeriría usar benches y no
banks.
La utilidad de los sistemas de traducción automática, o de ayuda a la traducción, de
traducción automática por el autor, o adaptados a un entorno determinado y restringido, de
traducción inmediata aunque imperfecta... sería inmensa7
I.2.3 Correctores sintácticos (Granda[91], IBM-España[91])
La extensión alcanzada por los microordenadores en todos los ámbitos laborales o
académicos ha permitido que los editores de texto sean una herramienta de trabajo cotidiana
(nosotros mismos utilizamos uno de los más populares en la redacción de este proyecto). Al
incorporarles más y más funciones se han convertido en procesadores de textos, aunque para
una perfecta comodidad en su manejo por parte de nosotros los "escritores", se echa en falta la
corrección automática o semiautomática de esos errores que nuestra impericia, precipitación o
desconocimiento de la lengua nos hacen cometer:
Las actuales funciones de análisis léxico resultan insuficientes. Mediante simple
consulta en el diccionario de cada palabra que usemos, no se pueden corregir errores tan típicos
como:
-palabras unidas o separadas sin querer: tam poco, tanpoco...
-sustitución de letras con resultado de palabra presente en el diccionario: menores por
mejores...
-acentuación diacrítica incorrecta: éste por este, como por cómo...
-comentarios entre guiones o paréntesis, abiertos pero no cerrados o viceversa.
Para una verificación gramatical de amplio espectro, necesitaremos modelar la lengua
formalmente, compilar la información en forma de gramática y probarla mediante córpora
textuales. Aunque, como en la arquitectura propuesta en Granda[91], se adopte un esquema de
análisis sintáctico local (centrado en sintagma) y no global (centrado en la oración), como
haremos nosotros, la información sigue siendo válida y sólo habrá que adaptarla a nuestras
condiciones de análisis sintáctico veloz, robusto... (al fin y al cabo la lengua es la misma
siempre).
I.2.4 Interfaces naturales hombre-máquina
Cualquier lenguaje para la manipulación de una base de datos posee una sintaxis
En Sager[91] encontrarán una visión amplia del tema de la
traducción
automática:reutilización
de
traducciones
previas,traducción incremental...
7
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
artificial que dificulta nuestro acceso a ella (especialmente para los no habituados a la
informática o los "alérgicos" a la misma).Sin embargo, todos conocemos al menos un idioma
(con nuestro propio vocabulario y nuestra propia gramática, eso sí) y por medio de él somos
capaces de pedir información en cualquier organismo público.La utilización de lengua natural
en nuestras interacciones con las máquinas simplificaría notablemente la labor del usuario.
La versatilidad del lenguaje natural multiplica las fuentes de error: la pronunciación o la
ortografía, palabras desconocidas, absurdos que suenan bien, peticiones ambiguas, fragmentos
con significado, correcciones sobre al marcha, sintaxis mala pero comprensible, referencias al
contexto de la petición... Ello justifica la adición de módulos inducción y corrección, de gestión
de diálogo...
Tomando ejemplos de ATIS (Young[91],Seneff[92], Pieraccini[91] y [92]), donde se
muestran peticiones hechas a una base de datos de líneas aéreas, podemos comprobar:
-las oraciones casi se limitan a los modos interrogativo e imperativo
-no abundan ni son variadas la recursión subordinada ni la coordinada
-la semántica viene guiada por los verbos (list... ), que son los que imponen los marcos
de predicación, y las palabras típicas (flight...)
-la correcta asignación de complemento se ve dificultada por los muchos sintagmas
preposicionales. En las figuras comprobamos como sintagmas muy similares realizan funciones
diferentes.
-algunas estructuras sintácticas son más empleadas en este entorno que en la vida
cotidiana,y deben ser tratada muy especialmente. Por ejemplo "from...to..." debería tener menor
prioridad (luego mayor posibilidad de reflejar relaciones lejanas) que "...in NombrePropio",de
tal modo que se pueda integrar una en la otra caso de darse conjuntamente. En:
"from the airport in Dallas to Boulders"
"in Dallas" forma parte del término del sintagma preposicional "from..." y no funciona como
complemento de un hipotético verbo.
Lo mismo sucede con las expresiones de tiempo: before noon, this week...
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
ORACION
Interrogación
OInterrog
Interrogación
OInterrCompl
SNInterrog
V
SNIntSimple
DetInterrogat
N
SPdirecc
PrepDest
SAdjPost
Adj
¿
qué
transportes terrestres hay
SNDest
NomGeoSin
NomGeoSimple
hasta
Barcelona
?
Figure 1 Ejemplos de ATIS(I).
-los pronombres: debemos hallar su antecedente:
"show the flights from.. to... as well as their minimun fares"
ORACION
ORACIÓN
Interrogación
Interrog
¿
OInterrog
Interrogación
OInterrog
Interrog
OInterrCompl
OInterrCompl
SNInterrog
V
SPTemp
SNInterrog
V
SPdirecc
SNIntSimple
SPTempDest
SNIntSimple
PrepOrig SNOrig PrepDest SNDest
DetInterrogat N SAdjPost
PrepDest ArtDet Numeral
DetInterrogat N SAdjPost
NomGeoSin
NomGeoSin
Adj
Adj
NomGeoSimple
NomGeoSimple
¿
qué transportes terrestres hay hasta las tres
?
qué transportes terrestres hay de Madrid
a Barcelona
?
Figure 3
2 Ejemplos
Ejemplos de
de ATIS(III).
ATIS(II).
Figure
I.2.5 estudios teórico-prácticos de lingüística
Un conocimiento profundo del funcionamiento del sistema de la lengua debe conllevar
su imitación y simulación. Las teorías deben ser contrastadas en la práctica, y ésta sirve para su
perfeccionamiento. Hallebeek[91] utiliza un entorno similar al que desarrollaremos aquí para
estudiar la esquemas de nominalización de adjetivos, sintagmas preposicionales... proponiendo
que se traten sintáctica y no léxicamente, categorizando los adjetivos nominalizables como
sustantivos.
CAPITULO I : MOTIVACIONES Y JUSTIFICACIÓN
1
ORACION
Interrogación
OInterrog
Interrogación
OInterrCompl
SNInterrog
V
SNIntSimple
DetInterrogat
N
PrepDest SNDest
SAdjPost
Adj
¿
qué
SPdirecc
NomGeoSin
NomGeoSimple
transportes terrestres hay hasta Barcelona
Figure 4 Ejemplos de ATIS (IV).
?
I.2.6 Otros
-Máquinas de escribir predictivas
-Etiquetado automático de léxico para la confección de diccionarios
-procesamiento inteligente de información textual8
8En
Haller[91] y Sager[91] encontrará ejemplos de investigación en la materia tanto en Alemania como en Gran Bretaña o
España.
CAPITULO II : LA LENGUA NATURAL
9
CAPITULO II
LA LENGUA NATURAL
II.1 Caracterización
Las lenguas son sistemas más o menos complejos que asocian contenidos de
pensamiento y significación a manifestaciones simbólicas tanto orales como escritas. Aunque en
sentido estricto el lenguaje sería la capacidad humana para comunicarse mediante lenguas, se
suele usar para denotar los mecanismos de comunicación no humanos (el lenguaje de las abejas
o el de los delfines) o los creados por los hombres con fines específicos (los lenguajes de
programación, el lenguaje de la lógica, de la aritmética...).
La característica externa9 fundamental de las lenguas naturales (los idiomas humanos
"de propósito general") es su enorme complejidad formal. De la sintaxis, componente clásico de
la mayoría de nuestros modelos de lenguaje, dijo el lingüista norteamericano F. Palmer que era
"aquella disciplina lingüística que todo el mundo espera que estudien los demás". Mientras
cualquier lenguaje de programación puede ser descrito por medio de menos de cuatrocientas
reglas sintácticas, modelar groseramente, en sus mecanismos generales, un idioma como el
castellano precisa de al menos esa cifra (sin incluir las palabras propiamente dichas, que ya son
miles)10.
Otro grave problema descriptivo que presentan es la inexistencia de un único modelo
común a todos los hablantes: cada uno tiene su propio idiolecto (manera individual de hablar),
interiorizado e inconsciente (nadie es capaz de describir con fidelidad su idiolecto, ni cómo lo
ha adquirido). Ello nos obliga a usar córpora textuales que verifiquen nuestras intuiciones
lingüísticas, a escribir nuestra gramática por aproximaciones sucesivas.
9Las
lenguas naturales poseen características de adquisición y modelado cerebral cuyo contenido y alcance,en general,desconocemos.Chomsky ha alternado a lo largo de su vida las
reflexiones puramente lingüísticas con las lingüístico-cerebrales , a la búsqueda de esos universales comunes a las
gramáticas de todas las lenguas que demuestren su teoría del
innatismo.Afortunadamente su teoría formal es independiente de
su filosofía de la mente,pudiéndose usar una sin aceptar la
otra.
10Ver
las descripciones gráficas y textuales que Wirth[82]
da de Modula-2 y compararlas con las breves y muy incompletas
que aparecen en Tomita[86b] para el idioma inglés.
CAPITULO II : LA LENGUA NATURAL
9
La depuración tendrá por fin satisfacer los tres criterios de adecuación que Chomsky
propuso:
-adecuación observacional: predecir correctamente qué oraciones pertenecen o no a la
lengua en cuestión.
Mientras "Todos mis amigos son lingüistas" o "Todos los lingüistas son mis amigos"
constituyen enunciados aceptables, "Mis todos lingüistas son amigos" o "Todos lingüísticos son
los mis amigos" no lo son.
-adecuación descriptiva: además debe especificarse la estructura de relaciones de esas
oraciones.
En "Todos mis amigos lingüistas son lingüistas", las concordancias entre todos, mis,
amigos, lingüistas y son debe ser explicitada para justificar la incorrección de "Todos el amigas
lingüistas es lingüista".
-adecuación explicativa: nuestro modelo debería contener un conjunto muy limitado de
principios simples y generales11.
Dadas frases tan relacionadas como "Los caballos del rancho comen hierba fresca" y
"¿Qué comen los caballos del rancho?", o "Empleados del Ayuntamiento derribaron el edificio"
y "El edificio fue derribado por empleados del Ayuntamiento", deberían de ser explicados de un
modo conjunto y no aislado, duplicando esfuerzos...
Sin embargo, en la práctica estos criterios serán excesivamente exigentes en su conjunto
y para una introducción en el tema; una arquitectura simple, como la que utilizaremos en este
proyecto, hará que el número de reglas que nos garanticen cubrir una amplia porción del
castellano con un mínimo de oraciones agramaticales aceptadas, sea elevado.
II.2 Mecanismos habituales en una lengua natural
Con objeto de dejar clara la diferencia de complejidad entre los lenguajes artificiales y
las lenguas naturales, daremos aquí un breviario de fenómenos lingüísticos presentes en una
lengua natural como el castellano:
-el fenómeno de la recursión (presente también en los lenguajes de programación) se
halla limitado por restricciones de tipo pragmático que hacen casi inaceptables oraciones como:
"tu vecina es muy, muy, muy, muy... pero que muy simpática"
ó
"perseguí al ratón que perseguía al gato que perseguía a la rata ..."
11Además
de las propuestas por Chomsky,muy adecuadas para
un paradigma generativista,diferentes teorías han dado otros
enfoques a la adecuación explicativa.S.C.Dik[81] define objetivos pragmáticos,funcionales y de tipología del lenguaje en
este nivel.
CAPITULO II : LA LENGUA NATURAL
9
-la homonimia (o ambigüedad léxica) hace que a una misma palabra se le puedan
asignar diversos significados con dependencia o no del contexto lingüístico. En:
"las llamas lo asustan"
es el contexto extralingüístico (otro mecanismo típicamente natural) el que nos especifica si con
"llamas" nos estamos refiriendo al conocido herbívoro sudamericano o al efecto de una
combustión.Igual sucede con:
"el régimen me lo tenía prohibido"
donde, variando el contexto, el régimen puede ser político o alimenticio.
-la anfibología estructural: las relaciones entre los constituyentes de la oración es
ambigua, pudiéndose dar más de una interpretación. Al decir:
"Pedro habló a los estudiantes de lingüística"
no queda claro si es que habló de lingüística a los estudiantes, o habló de esa materia, o de
cualquier otra, a los estudiantes que cursan la disciplina de lingüística.
Tomando el idioma inglés encontramos:
"I can't stand John"12
equivalente a "no puedo soportar a John" y "John, no puedo soportarlo".
-ambigüedades temáticas: la asignación de papeles temáticos (instrumento, agente...)
puede también dar lugar a equívocos:
"la invitación del gobernador provocó problemas"13
puede ser una invitación hecha por el gobernador (=AGENTE), o podría ser el gobernador
(=OBJETO) quien fue invitado.
12Hemos
omitido la pausa o cambio de entonación
precedería a "John" y desharía la ambigüedad:todavía
difíciles de reconocer automáticamente.
13Quizá
que
son
deberíamos catalogar esta ambigüedad como léxica,al
variar el significado de la contracción "del",en un caso
significando "hecha por el" y en el otro "hecha al".(Ver
Hernanz[87] de dónde están tomados los ejemplos.
CAPITULO II : LA LENGUA NATURAL
9
-el léxico tiene un carácter dinámico (lleno de importantes irregularidades que
caracterizan el hablar con corrección: anduve y no andé...). Continuamente aparecen nuevas
palabras, nombres, denominaciones... siendo tarea imposible el inventariarlas. Los mecanismos
de derivación y composición de palabras permiten a cualquier hablante ampliar el vocabulario
existente sin que por ello tenga que dejar de ser entendido14. Cada región, familia, clase social,
profesión... incluso cada hablante tiene su propia visión del lenguaje común por todos empleado
(la variedad del fenómeno no es comparable a los dialectos "intencionados" de un lenguaje de
programación).
-la elipsis (existencia de unidades lingüísticas carentes de realización fonética, pero
recuperables a partir de sus huellas en el discurso) es un recurso muy complejo que es propio de
las lenguas naturales. Palabras o secuencias largas de palabras pueden ser omitidas porque un
delicado sistema de redundancias permite su reconstrucción.Desde la ya citada elipsis de sujeto
(redundante por la conjugación del verbo) hasta la omisión de gran parte de la respuesta a una
pregunta, son muchos las posibilidades que nos brinda este mecanismo.
-la anáfora permite que ciertos elementos nos remitan a otros sin necesidad de que
aparezcan explícitamente:
"Qué foto suya que le robó Pedro busca Pepe"
donde "suya" se refiere a Pepe y no a Pedro o a un tercero, Juan.
-la libertad en el ordenamiento de los constituyentes (grupos conexos de elementos del
lenguaje interrelacionados) cuando no de las mismas palabras (como en el caso del latín,aunque
con restricciones) sin por ello alterar necesariamente el significado de lo expresado. En
castellano son típicamente muy móviles los adverbios acabados en -mente:
"Francamente, yo creo que María tiene razón"
"Yo, francamente, creo que María tiene razón"
"Yo creo, francamente, que María tiene razón"
"Yo creo que, francamente, María tiene razón"
"Yo creo que María tiene razón, francamente"
En el ya clásico hipérbaton:
"Del salón en el ángulo oscuro,
de su dueño tal vez olvidada,
silenciosa y cubierta de polvo,
veíase el arpa"
(G. A. Becker)
14Los
actuales correctores ortográficos de los procesadores de texto desconocen palabras empleadas en la redacción de este proyecto
que no presentan apenas dificultad de comprensión para sus lectores:observacionalmente,ingenieril,José Mº Brucart...
CAPITULO II : LA LENGUA NATURAL
9
destaca la concordancia de género, numero y persona entre palabras notablemente dispersas:
olvidada, silenciosa, cubierta, veíase y arpa
o como del salón modifica a ángulo, de su dueño a olvidada, olvidada a "arpa", el primer verso
no es sino un complemento circunstanscial del verbo veíase y el segundo un predicativo.
-la asignación de significados a las oraciones es notablemente más compleja que la que
caracteriza a los lenguajes de programación, sean estos imperativos,funcionales ...15 La
construcción del más complejo de los compiladores es mucho más sencilla que la de un módulo
de interpretación o comprensión de cuentos infantiles.
-las concordancias y otras relaciones intra-oracionales "lejanas". En las interrogativas
parciales como:
"¿Qué casa dijo Pepe que compraría a su prima?"
donde SNInterrogativo[qué casa] es el complemento directo del verbo de la proposición
sustantiva que contiene al verbo compraría.
En el inglés es característica la posibilidad de separación entre la preposición y su
término:
"who did he talk to in the pub?"
donde "who" es núcleo del sintagma nominal asociado a "talk to" (más "lógica" parece "to
whom did he talk in the pub?").
-la existencia e influjo de la entonación, la acentuación y el pausado. Una misma frase
será enunciativa o interrogativa o exclamativa dependiendo de cómo la pronunciemos o de
cómo pongamos los signos de puntuación:
"Quiere que vaya pronto"
"¿Quiere que vaya pronto?"
"¡Quiere que vaya pronto!"
-la subcategorización (necesidad por parte de ciertos elementos de la presencia de otros
15Sorprende,
al consultar los suplementos actualizadores de
una enciclopedia como la Larousse,el notable incremento de
entradas asociadas a la palabra "lenguaje" que se ha producido
tras la aparición de los ordenadores: ensamblador, simbólico,
funcional, lógico, generador de informes,de especificación,
teoría de lenguajes...
CAPITULO II : LA LENGUA NATURAL
9
para tener sentido pleno: la tradicional transitividad verbal, la rección prepositiva...) es mucho
más libre que en las "llamadas a función" o "a procedimiento", equivalente conceptual en el
campo de los lenguajes de programación.
-ante situaciones de ruido o desconocimiento de palabras, el ser humano reacciona
infiriendo, habitualmente con gran acierto.
Por supuesto estos rasgos diferenciadores no ocultan las similitudes generales(la
recursividad, la estructura jerárquica de relaciones entre constituyentes, la categorización de los
elementos...) que justifican el estudio de las lenguas naturales mediante la teoría de lenguajes
formales.
CAPITULO III LOS LENGUAJES FORMALES
15
CAPITULO III
LOS LENGUAJES FORMALES
III.1 Definición
De un modo extensivo, un lenguaje se definiría enumerando todos los enunciados que lo
componen. Como la mayoría de los lenguajes de interés son recursivos en mayor o menor
medida (a partir de un enunciado existen procedimientos que permiten formar otros mayores y
más complejos), debemos encontrar propiedades o conjuntos de propiedades que los definan
unívocamente (definición intensiva).
Dada la oración castellana: "este perro es de mi padre", es posible construir otras como:
"mi madre dice que este perro es de mi padre"
"mi madre dice que este perro es de mi padre y este perro es de mi padre"
"si mi padre asegura que mi madre dice: "este perro es de mi padre", mi madre dice que
este perro es de mi padre"
Como es obvio, resultaría absurdo intentar escribir todas las posibles combinaciones de
palabras aceptadas en castellano.
La posibilidad de una definición intensional completa de un lenguaje es lo que nos
permite llamarlo formal. Para las lenguas naturales, creadas por el hombre de un modo colectivo
y por tanto no personalmente consciente, la formalización no existe: ¡aunque todos somos
generalmente capaces de decir si una frase pertenece a nuestro idioma materno (incluso muchos
son capaces de hacerlo con algunos otros), y comprender su o sus significados, nadie ha sido
capaz en más de dos mil años de interés por el fenómeno lingüístico, de caracterizar uno
biunívocamente!
Pero son los formalismos la llave que puede abrirnos la puerta del tratamiento
informático cómodo y generalizado: dada una secuencia perteneciente a un idioma como el
nuestro y un conjunto de propiedades que debe satisfacer, sólo habremos de aplicarlas
para verificar su gramaticalidad16. Del mismo modo podría llegar a la traducción automática
entre lenguajes formales, a la generación más o menos intencionada y automática de oraciones
correctas...
Más adelante veremos que hay que imponer ciertas
restricciones a los formalismos si queremos que exista un
algoritmo,una secuencia de pasos que nos garantice la finalización ,exitosa o no, de la operación en un tiempo finito.
16
CAPITULO III LOS LENGUAJES FORMALES
15
El paradigma formal más famoso y rápidamente desarrollado para la caracterización de
lenguajes es el derivado del concepto de gramática generativa de Chomsky. En Chomsky[59],
esta celebérrimo lingüista norteamericano partiendo de que un lenguaje L es un subconjunto de
todas las secuencias (finitas o no) que podemos formar mediante la concatenación de elementos
de un vocabulario , define la gramática mediante la cuaterna siguiente:
- : vocabulario finito de símbolos Terminales, que son símbolos porque referencian
realidades objetivas, subjetivas o meramente gramaticales, pero que son terminales por aparecer
efectivamente en los enunciados.
-N : conjunto finito de símbolos No Terminales, metasímbolos que describen directa o
indirectamente cadenas o subcadenas del lenguaje, con propiedades comunes.
-S : un símbolo No Terminal básico (axiomático según la definición de Chomsky), que
describe oraciones ( y no subcadenas) del lenguaje.
-P : un conjunto también finito de reglas de producción que nos dicen cómo se puede
generar los enunciados, cómo partiendo del axioma podemos llegar a la oración terminal. Este
conjunto será un simple subconjunto de:
Install Equation Editor and doubleclick here to view equation.
lo cual expresado en una notación más clásica en lingüística sería:
Install Equation Editor and doubleclick here to view equation.
donde:
Install
InstallEquation
EquationEditor
Editorand
anddoubledoubleclick
clickhere
heretotoview
viewequation.
equation.
siendo posible que tanto  como  como  sean iguales a la cadena nula.
El lenguaje L así definido se obtendría aplicando el siguiente procedimiento no
algorítmico (no garantiza tiempo finito para una gramática genérica):
-S es una forma oracional
-si  es una forma oracional y -> pertenece a P,  también será forma oracional
-una forma oracional compuesta únicamente por símbolos terminales constituirá una
oración del lenguaje.
Como ejemplo veamos la derivación de una oración en castellano basándonos en una
pequeña gramática:
S->SintagmaNominalSujeto SintagmaVerbalPredicado
CAPITULO III LOS LENGUAJES FORMALES
15
->Determiante Sustantivo SVP
->Det Sust Verbo SintagmaNominal
->Det Sust Verb Det Sust
->el chófer destrozó el coche
III.2 Jerarquía de Chomsky
A fin de precisar más que tipo de gramática es capaz de generar un lenguaje lo más
similar posible a los naturales, Chomsky distinguió cuatro formatos de reglas que se
correspondían con gramáticas generativas más o menos potentes.
III.2.1 Tipo 3
Es el descriptivamente más débil.Sus reglas poseen un formato:
Install Equation Editor and doubleclick here to view equation.
5
donde B puede existir o no.
Equivalen, en cuanto a poder descriptivo, a las redes finitas de transición de estados que
se estudian en teoría de autómatas. Dado un lenguaje regular (aquel que es posible caracterizar
usando una gramática de tipo 3), siempre será posible hallar su autómata equivalente (cada
símbolo No Terminal es un estado, cada regla AaB una rama que conecta los estados A y B
por medio del símbolo Terminal a y cada regla Aa nos dice que A se une al estado final a
través del símbolo 'a').
Dada la sencillez estructural de estos lenguajes, la notación chomskiana resulta pesada.
Las notaciones más compactas para la expresión de lenguajes regulares son las BNF (Backus
Normal Form, Backus Naur Form, en homenaje a Backus, su creador, y Naur, su continuador),
que reducen a uno el número de reglas necesarias. Para ello utilizan los siguientes
metasímbolos:
-la barra disyuntiva '|': unifica en una dos reglas con el mismo símbolo No Terminal a la
izquierda del igual. AaA y AbB se convierten en AaA|bB.
-el paréntesis de opcionalidad '(...)': dos reglas iguales salvo una expresión inserta
equivalen a la mayor de ellas con la expresión inserta, entre paréntesis. AaB y Aa se reduce
a Aa(B).
-el signo más de recursividad '+': adjuntado a una expresión equivale a las regla A...A
y A... Por ejemplo: AaA y Aa se transforman en Aa+
-el asterisco que equivale a una expresión con más y entre paréntesis. Así, A* es lo
mismo que (A+).
-el corchete para alterar la prioridad en la interpretación de los metasímbolos. Como '+' y
CAPITULO III LOS LENGUAJES FORMALES
15
'*' tienen mayor prioridad que la barra, son expresiones diferentes: A|B+ y [A|B]+.
Traduciendo esta notación infija a prefija se gana en facilidad de procesamiento pero no
en facilidad de escritura (hay que escribir más).
Cualquiera de estas notaciones no constituye un lenguaje regular de contexto libre
(siguiente nivel en la jerarquía de Chomsky).
NotaciónBNF
Expresión 
Expresión 
Término1

Término1

Término1

Término1

Término

Término

Corchete

Paréntesis 
Expresión
Término | Expresión
Término
Paréntesis
Término *
Término +
Término
Símbolo
Corchete
[ Expresión ]
( Expresión )
1 Gramática de la notación BNF.
Un ejemplo de gramática regular para el Sintagma Nominal del castellano se muestra en
el recuadro 3 donde se ha permitido la utilización de símbolos auxiliares no recursivos (con lo
cual nunca podremos exceder los límites de los lenguajes regulares).
III.2.1.1 Limitaciones de los lenguajes regulares
Un autómata categorial cuidadosamente diseñado y compilado (no el de la figura 3, por
supuesto) puede reconocer un amplio subconjunto de un lenguaje natural como el castellano .
En Subirats[91] se encuentra un texto periodístico completo aceptado por un autómata similar al
nuestro, con frases tan espectaculares como simples:
CAPITULO III LOS LENGUAJES FORMALES
NotaciónBNF
Expresión
Expresión
Término
Término
Término
Término
Término
Término
Término
15










SEC( Expresión )
Término Expresión
DISY( Término Expresión )
OPC( Expresión )
OPC Símbolo
REC-0( Expresión )
REC-0 Símbolo
REC-1( Expresión )
REC-1 Símbolo
Símbolo
2 Gramática de la notación BNF prefija.
"La importante reducción en la remuneración de los bonos del Tesoro hasta el 14,505
por ciento en tasa interna bruta de rentabilidad supone el inicio de un descenso progresivo de los
tipos de los títulos público y adelantará al otoño la reducción de los
Sintagma_Nominal
=
(Determinante)
(Numeral)
(Sintagma_Adjetival)
Núcleo_Nominal (Sintagma_Adjetival) Sintagma_Preposicional*
Determinante = PreArtículo[Artículo | Posesivo | Demostrativo]
Numeral = Cardinal | Ordinal
Núcleo_Nominal = Sustantivo |Infinitivo
Sintagma_Adjetival = Adverbio* [Adjetivo | Participio]+
([ , Adverbio* [Adjetivo | Participio] ]* [y | o] Adverbio* [ Adjetivo |
Participio])
Sintagma_Preposicional
=
Preposición
(Determinante)
(Sintagma_Adjetival) Núcleo_Nominal (Sintagma_Adjetival)
(Numeral)
3 Pequeña gramática del sintagma nominal en castellano.
tipos de interés".
Esta adecuación observacional no oculta la incapacidad de los lenguajes regulares para,
con sencillez y elegancia, decirnos cuál es la estructura de este sintagma nominal (a qué núcleo
nominal a adjetival están complementando cada uno de los sintagmas preposicionales, cómo se
encadenan éstos entre sí...) ni explicar las ambigüedades estructurales de oraciones como las
CAPITULO III LOS LENGUAJES FORMALES
15
vistas en el capítulo dedicado a la lengua natural17.
En Edinburgh[89], cap. 2, se incluye un ejemplo de Gazdar y Pullam contra el carácter
regular del inglés:
Install Equation Editor and doubleclick here to view equation.
que traducido al castellano queda, aproximadamente:
Install Equation Editor and doubleclick here to view equation.
Aunque el ejemplo es extremo e inaceptable (una gramática que falle en esa frase no
puede ser rechazada en la práctica), pretende mostrar que la inserción generalizada y recursiva
de proposiciones en posición relativa y no absoluta, con sus parejas de sujetos y predicados,
constituye un fenómeno lingüístico no elegantemente regular. Cuando todos escuchamos la
oración:
"el coche que el chófer que Pedro contrató condujo ayer parece rápido"
mentalmente asignamos sujeto a los distintos verbos percibiendo la estructura de niveles que
supone la inserción de una proposición dentro de otra; cada verbo no tiene al sustantivo anterior
más cercano como sujeto, sino al anterior más cercano que no tenga un verbo más cercano
aún18.
Trucos como la adición de una pila para la subordinación inserta, o la utilización de
gramáticas ambiguas y desdoblamiento del análisis al pasar por un estado de ambigüedad, o el
etiquetado de los sintagmas al llegar a determinados estados, complican en exceso el sencillo
funcionamiento de los autómatas, y son formas poco recomendables de convertir el lenguaje
aceptado en algo más que regular.
III.2.2 Tipo 2
Describen los llamados lenguajes de contexto libre (en ellos se pueden insertar
proposiciones dentro de proposiciones independientemente del contexto de la oración).
El formato según Chomsky será:
17Esta
capacidad de reconocer cadenas pero no dar
correctamente su estructura supone un caso de capacidad
generativa débil y no fuerte (Edimburgh[89], cap.1).
18
La incapacidad para aceptar un elevado grado de recursividad de inserción parece más ligada con nuestras capacidades
para el lenguaje hablado (inferiores a las que tenemos al leer
o escribir) que al posible carácter regular del lengua natural.
CAPITULO III LOS LENGUAJES FORMALES
15
Install Equation Editor and doubleclick here to view equation.
donde  es una cadena, vacía o no, de símbolos terminales o no terminales.
Equivale, en cuanto a potencia descriptiva, al autómata con pila y nos permite describir
adecuadamente las relaciones intra- e inter-sintagmáticas de la lengua natural:
-concordancia sujeto-verbo
-concordancia sujeto-atributo
-inserción de proposiciones en posiciones centrales


La representación gráfica de un análisis de contexto libre es un clásico árbol sintáctico
con los símbolos No Terminales en los nodos intermedios y símbolos Terminales en los finales.
ORACION
Proposición
SN
DET Nucl
Det N
SVAtrib
SP
Prep
VerbCop
SN
SAdj
DET Nucl SAdjPost
Det N
Atrib
Adj
SPde
SAdjConAdv NexoMonoCop
PrepDe SN
SAdv
Adj
Adj
NombreProp Adv2
las opiniones sobre la realidad efectiva de España son sobremanera deficientes y desoladoras
ORACION
Proposición
SN
DET Nucl
Det N
SVAtrib
SP
Prep
VerbCop
SN
SAdj
DET Nucl SAdjPost
Det N
Atrib
Adj
SPde
PrepDe SN
SAdv
Adv
SAdjCoord
Adj
NexoMonoCop Adj
NombreProp
las opiniones sobre la realidad efectiva de España son sobremanera deficientes y desoladoras
Figure 5 Ejemplos de árboles sintácticos de una frase en
castellano.
CAPITULO III LOS LENGUAJES FORMALES
15
III.2.2.1 Limitaciones de los lenguajes de contexto libre
Mucho se ha argumentado a favor y en contra de si los lenguajes naturales podían ser
descritos sintacticamente mediante gramáticas de contexto libre, basándose desde ejemplos
sencillos aunque muy discutibles, hasta referencias a estructuras presentes en holandés,
bambara... (Perrault[84], Edinburgh[89]).
Hay quien objeta que la multiplicación de categorías sintácticas necesaria para
contemplar las concordancias es claramente antinatural, que sería mejor que los símbolos
llevaran asociados rasgos como el género, el número, la persona... Parece poco natural la
creación de categorías sintácticas como Sintagma Nominal masculino plural propio geográfico,
Sintagma Adjetival largo con sintagma adverbial antepuesto... o incluso de categorías léxicas
como sustantivo masculino plural propio geográfico, adjetivo femenino singular especificativo...
Sin embargo, nuestro intento como ingenieros es modelar la lengua externamente de un modo
sencillo; la multiplicación de reglas y símbolos que supondría una gramática poco elegante
como la del recuadro 4
Los ejemplos del alemán de Suiza, donde existen construcciones del tipo:
Install Equation Editor and doubleclick here to view equation.
o de la lengua Bambara de Senegal, que contiene sintagmas de estructura:
Install Equation Editor and doubleclick here to view equation.
Proposición = SNSujetomasculinosingular SintagmaVerbalsingular
SNSujetomasculinosingular=
(Determinantemasculinosingular)
(SintagmaAdjetivalPreviomasculinosingular)
(SintagmaAdjetivalPreviomasculinosingular)
(SintagmaPreposicional) (OraciónDeRelativo)
Nombremasculinosingular
SintagmaAdjetivalPreviomasculinosingular=
(SintagmaAdverbialPrevioDeGrado)*
AdjetivoPreviomasculinosingular
4 Ejemplos de reglas de una gramática con concordancias.
son dependientes de contexto, pero no afectan al castellano, que es nuestro objetivo.
Se ha argumentado que en oraciones como:
CAPITULO III LOS LENGUAJES FORMALES
15
"Pedro y María compraron un piso y un coche respectivamente"
hay un fenómeno que no es elegante describir mediante GCL (requerirían categorías como
SintagmaNominalcon2elementos...). Sin embargo, la gramaticalidad parece más ligada a la
semántica de "respectivamente", más fácil de verificar por el componente semántico:
"sus dos hermanos heredaron la casa y el coche respectivamente"
En castellano, el ordenamiento libre de los sintagmas dará lugar a constituyentes
discontinuos, cuyos árboles sintácticos deberían tener ramas cruzadas. Dichos árboles no son
posibles si usamos gramáticas de contexto libre, pero cabe la posibilidad de realizar un análisis
sintagmático (más que sintáctico) laso, que luego la semántica reordenará, ligará... Los
hipérbaton suelen requerir del oyente una cierta transformación, un posproceso que no todos los
hablantes son capaces de realizar con corrección (depende mucho de su cultura especialmente
de la literaria si nos enfrentamos a enunciados de corte poético)19.
III.2.3 Tipo 1
Contienen reglas que se ajustan a:
Install Equation Editor and doubleclick here to view equation.
Permiten que la gramática sea sensible al contexto, y un sintagma pueda ser
sistemáticamente igual a otro como en el ejemplo ya visto de la lengua Bambara. Obsérvese en
la figura 5 lo complejo de las reglas necesarias
La complejidad de su parsing es exponencial con la longitud de la cadena de entrada (lo
cual es inaceptable con fines de reconocimiento).
Prácticamente no existen referencias bibliográficas sobre este tipo de gramáticas, las de
menor éxito de toda la jerarquía.
En inglés son comunes las oraciones de relativo con la
preposición al final en lugar de al principio, más difíciles de
tratar correctamente.
19
CAPITULO III LOS LENGUAJES FORMALES
15
S
C
S
b
b
c
C
C
E
E
 a S B
B
C
C
B
D
D
C








a
b
b
c
C
E
E
B
b C
b
c
c
D
D
C
C
III.2.4 Tipo 0
5
Gramática
sensible
al
Su potencia es la de una contexto.
máquina de Turing y sus reglas
de la forma:
Install Equation Editor and doubleclick here to view equation.
No existe algoritmo que en tiempo finito nos diga si una cadena obedece o no las
reglas de una gramática de reescritura tan generalizada.
Cuando Chomsky formuló sus objeciones a las gramáticas de estructura de sintagma
(tipo 2), propuso la utilización de reglas de tipo 0 para el reordenamiento, elisión... de
elementos. La no existencia de algoritmo de parsing mostraba que su potencia superaba en
mucho a las lenguas naturales y el formato de las reglas de reescritura se limitó mucho (los
clásicos movimientos de sintagmas por tematización, interrogación...
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
CAPITULO IV
EL MODELO LINGÜÍSTICO
IV.1 Presentación
Es tradicional dividir la gramática, o modelo de la lengua, en partes de todos conocidas:
-la fonética: estudio de la estructura material del sonido, de sus propiedades y cualidades
físicas que nos permiten diferenciarlos, pronunciarlos... Tono, intensidad, timbre, cantidad y
lugar de articulación son objeto de estudio para la fonética acústica; lugar y modo de
articulación lo son para la fonética articulatoria
-la fonología: qué función desempeñan los elementos fónicos y cuál es su capacidad
para formar mensajes y signos diferentes20: cómo se forman las sílabas, cómo remarcamos la
intensidad en algunas de ellas (acento real, no ortográfico), en qué consiste la entonación y para
qué la usamos...
-la léxico-morfología: estudia las palabras y su forma, abstraídas de cualquier contexto
textual
-la sintaxis: describe cómo se combinan entre sí las palabras para formar oraciones
-la semántica: trata de los significados gramaticales, de la interpretación que damos a los
enunciados21
-la gramática del discurso: influjos lingüísticos más allá del restrictivo mundo de las
oraciones tradicionalmente considerado por la sintaxis
-la pragmática: cómo influye el contexto extralingüístico (sociedad, cultura...) en la
interpretación de los enunciados
20Estas
dos ramas suelen ser el punto de comienzo de
cualquier descripción genérica del castellano. (Esbozo[73],
Alcina y Blecua[75].
21En
el apartado dedicado al concepto de oración diferenciaremos con la máxima claridad posible la oración del enunciado.
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
Aunque es evidente que "el establecimiento de niveles es una mera ficción
metodológica"(Blecua citado en Hernanz[87], pág. 18) y "que no se corresponde con
distinciones naturales" (Saussure, citado en Alcina[75], pág. 132), su simplicidad la hace
especialmente apropiada como punto de partida (tras tantos siglos de preocupación por la lengua
parecemos hallarnos todavía saliendo de nuestras marcas hacia una meta de incierta llegada)
para ir aislando problemas cuya complejidad es suficiente como para no pensar en tratarlos
conjuntamente. Los enfoques modulares y los esquemas simplificados han desempeñado un
importante papel en la historia de la ciencia y de la ingeniería, a los que ahora se une la
simulación automática.
La descomposición empleada en esta obra se basará en la más clásica dentro del marco
generativista22, centrándonos en el subsistema sintáctico por interés del obletivo del proyecto.
Tomamos de Hernanz[87] la 6, que representará el modelo conceptual de lengua que
usaremos. Detallemos a continuación el contenido de cada módulo.
componente léxico
componente sintáctico
componente fonético
componente semántico
Figure 6 Modelo global de la gramática
IV.2 Componente léxico
Aunque en los textos de lingüística se suele denominar a este módulo lexicón o
diccionario, las capacidades léxicas del ser humano sobrepasan ampliamente la función de mero
almacén de datos. Como se ha señalado al caracterizar la lengua natural, el léxico presenta
notables regularidades que no se tienen en cuenta con una simple lista de palabras ( por eso el
concepto actual de diccionario automático no se limita a ser una lista, sino más bien una base de
En Radford[81], al final de cada capítulo, se encuentra
la ampliación detallada, para el paradigma transformacional.
22
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
datos relacional o un autómata basados en morfología...).
Las palabras no son entes simples: se componen de morfemas tanto lexemáticos 23 como
categorizadores24. Si nos basamos en los primeros agrupamos las palabras por familias léxicas
(lo cual es muy importante desde el punto de vista de los significados); si optamos por los
segundos, en categorías léxicas. Por ejemplo:
cas-a, cas-erío, cas-ero... pertenecen a una misma familia léxica a la que podemos
denotar con el más sencillo de sus componentes: casa.
Es obvio el estrecho vínculo existente entre éstas palabras que, sin embargo, no impide
que su comportamiento al relacionarse con otras no sea bien distinto: mientras casa o caserío
son, según la Gramática Tradicional nombres sustantivos, casero es un adjetivo.
Este carácter estructurado25 que poseen las palabras nos permite que ante una palabra
nueva como observacionalmente, y mediante la extracción de su lexema observ- (del verbo
observar) y sus morfemas -acion- (sustantivador) , -al- (adjetivador) y mente (que convierte a
la palabra en adverbio generalmente de modo), deduzcamos que significa "desde el punto de
vista basado en la observación". También nos permite elidir morfemas flexibles cuando, por
redundancia, su información es recuperable. En:
"El príncipe lloró amarga y desconsoladamente"
la coordinación copulativa de dos adverbios de similar morfología categorizadora nos permite
omitir, por razones estéticas normalizadas, el morfema -mente que acompañaría a amarga.
Sin embargo, y a pesar de la potencia del lenguaje humano a la hora de componer o
modificar morfemas para formar palabras, un elemento irregularizador, la norma y la
costumbre, hace que el adverbio más común derivado de observar sea observ-ador-a-mente.
Quizás sólo los que conozcan la existencia de la adecuación observ-acion-al encontrarán
fácilmente el sentido de observacionalmente. Los demás la considerarán una palabra extraña,
propia de un alterador de la norma.
23Los
lexemas o raíces son las partes invariantes de una
familia,aquellas que llevan consigo el núcleo del significado.Pueden ser simples (am- de la familia del verbo amar) o
compuestos (pasamanos),y una misma familia,por razones de
evolución histórica de la lengua, puede ser caracterizada por
más de un esquema (el verbo s-er pertenece a una familia que
además de s- posee los lexemas fu- y sie-).Para una mejor
introducción, consultar el capítulo 2.1 del Esbozo[73].
24Los
morfemas flexivos son los responsables de comunicarnos los rasgos propios de la palabra:su categoría (puede ser
ambigua) ,género,número,persona,tiempo...
25La
escuela del estructuralismo surgió dentro de la
lingüística al tomar al morfema como unidad principal por
oposición a la palabra.
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
Dado que la elaboración de un módulo léxico está siendo abordada ya por otro equipo
del Departamento (aunque no se halla todavía disponible), no hemos gastado tiempo en la
misma labor, y en nuestro sistema lo redujimos a una simple lista de palabras (fácilmente
almacenable en disco o en memoria de un modo eficiente), concentrándonos en el módulo central: el sintáctico26.
IV.3. Componente sintáctico
La Sintaxis, del griego "", que significa ordenamiento, estudia cómo se
combinan y distribuyen las piezas léxicas para formar enunciados pertenecientes a la lengua.
Está claro que secuencias de piezas léxicas que el sistema de la lengua cataloga como
mal formadas. "el madre comió niño helado de su el " posee las mismas palabras que "el niño
comió el helado de su madre", y mientras la segunda nos resulta perfectamente comprensible a
todos los castellano-parlantes, la primera carece de una mínima organización lógica27.
Ligeras variaciones del orden de una oración correcta como la anterior nos hacen ver
que las palabras forman grupos relativamente ligados y que, caso de poder moverse, lo harán
juntas. Así, su acompañará a madre en todos sus movimientos y "de su madre el niño comió el
helado" es aceptable (aunque retórica) pero no "el niño comió el helado de madre su". Es fácil
extraer como constituyentes de la oración: el niño, comió, el helado y de su madre.
Sin embargo, estos constituyentes tampoco son totalmente independientes: "el helado
comió el niño de su madre" no significa lo mismo que la original y "de su madre comió el niño
el helado" es agramatical28 aunque comprensible con un poco de buena intención. La sintaxis
debe desvelar cómo se forman los constituyentes y cuáles son las relaciones existentes entre
ellos. El modo usual de representarlo son los diagramas arbóreos.
Más justificaciones al empleo de análisis jerárquico podrían ser:
-el fenómeno de las concordancias también está regido por criterios de estructura: el y
niño poseen el mismo género y número y la variación de sólo uno de ellos da lugar a
agramaticalidad; el niño concuerda en la persona con el verbo "comió"...
26En
los capítulos de conclusiones y futuras líneas de
investigación se volverá sobre las limitaciones de esta opción.
27Si
no fuera así, la sintaxis tendría una única regla de
formación de predicados:oración será cualquier secuencia de
piezas léxicas en orden y número indeterminados.
28El
ejemplo escogido muestra la libertad de orden de
constituyentes que caracteriza al castellano,sólo limitada por
marcos de subcategorización como los que ligan al verbo con su
complemento directo,la rección prepositiva...
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
-la conversión de una oración enunciativa a interrogativa con sustitución de un
constituyente por un pronombre interrogativo no es razonable si no observamos el árbol sintáctico. "¿Quién comió el helado de su madre?", es correcta; "¿Quién el niño comió el helado?", no
(de su madre está ligado a el helado y para ser pronominalizado es necesario transformar la
frase: "¿De quién era el helado que comió el niño?").
-la entonación y el pausado dependen, como ya hemos visto, de la estructura de
constituyentes (aunque también de la cultura, intenciones, estado anímico... del hablante).
Segmentar correctamente una oración en sintagmas permitiría pausar frases como:
"cuando llegamos a casa | te vi salir"
"posaba el terciopelo de sus patas | en dos simétricos remiendos de tela nueva"
donde los fenómenos de la subordinación oracional y la subcategorización verbal, son
imprescindibles para comprenderlo.
-La distinción entre la aposición entre comas y la enumeración separada por comas,
necesita de información sobre relaciones, a menudo lejanas, en el interior de la oración:
"sus cuadros, todo lo suyo me suele gustar, no parecen comprados por ellos"
frente a:
"sus cuadros, todo lo suyo y de su marido me suele gustar"
-La coordinación puede darse en el nivel sintagmático:
"compró un piso y una casa"
o en el oracional:
"compró un piso y vendió su casa"
siendo diferente la entonación en ambos casos.
-Los paralelismos coordinados :
"lleno de luz y esperanza, de humildad y devoción"
no admiten un tratamiento sintáctico local, pues pueden implicar influencias remotas.
-El vocativo:
"señorita, no se puede"
"no llores, Babs, todo eso no es verdad"
no puede ser entonado como una enumeración o una aposición típicas.
-La interrogativas totales y parciales poseen sus implicaciones sintácticas:
"¿quien vive con vosotros?"
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
frente a:
"¿quien vive con vosotros os dijo eso?"
donde un sencillo error de escritura (supresión de una tilde) provoca la indiferenciación si no se
analiza globalmente la frase.
Por supuesto, existen algunos fenómenos jerárquicos que requerirían árboles con una
estructura más libre o más general: ramas cruzadas, correferencias entre elementos... Las
dificultades para su análisis automatizado nos harán excluirlos29.
IV.4 Componente fonológico
La conversión de los sonidos en fonemas es seguramente el módulo más desarrollado de
nuestro modelo. No obstante, las muchas técnicas empleadas adolecen de falta de "humanidad".
En nuestra capacidad de entender sonidos no empleamos sólo un modelo acústico-fonético de la
lengua30, sino también uno sintáctico-semántico: al ir escuchando y reconociendo fonemas,
morfemas... predecimos automáticamente qué nos podemos encontrar a continuación. Al
encontrarnos con algo incoherente, volvemos sobre lo escuchado e intentamos corregir nuestra
transcripción fonética (formulando palabras hipótesis en cierto modo) que nos hagan coherente
el enunciado o la pregunta.
IV.5 Componente semántico
Busca describir el contenido literal (gramatical, independiente del contexto
extralingüístico) de la oración.
Relacionados con la semántica están dos de los puntos más conflictivos de nuestro
planteamiento: la autonomía de la sintaxis respecto a la semántica y la de ésta respecto a la
pragmática.
Aislar la sintaxis de la semántica podría parecer simple (según Chomsky, su más
ardoroso defensor, es una hipótesis de trabajo básica para adentrarnos en la organización de la
lengua). La Sintaxis buscaría la estructura formal de la oración debida a la categorización o
29Más
información en el capítulo de líneas futuras.
30Aunque
en el aprendizaje de una segunda lengua influye
mucho el grado de maduración del cerebro (los niños,con el
cerebro más virgen,encuentran mucho más fácil esta tarea),así
como las interferencias de la lengua materna,todos hemos
experimentado al aprender otro idioma lo que facilita la
comprensión el hallarse situado en un contexto,predecir la
línea sintáctica y semántica que va a seguir el discurso...La
predisposición a escuchar algo agudiza nuestra capacidad de
acierto si nuestras previsiones se cumplen.
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
tipado de sus elementos; la semántico interpretaría esa estructura a la luz de los significados de
los mismos. La sintaxis sería capaz de hallar una estructura a la oración "sabía que Mª estaba
enferma, pero no era verdad" ( la misma que la de "creía que Mª estaba enferma, pero no era
verdad"); sin embargo, se trata de una oración absurda, como muy lógicamente detectaría una
buena semántica.
Los límites se pueden hacer difusos al analizar la serie siguiente:
1) Mi tío opina que soy un gran cocinero
2) Mi gato opina que soy un gran cocinero
3) Mi nacimiento opina que soy un gran cocinero
4) Mi desde opina que soy un gran cocinero
La oración nº1 no presenta problemas, y todos coincideremos en que es sintáctica y
semánticamemte bien formada (aunque podría ser falsa en la realidad).
Una sintaxis integrada con semántica consideraría anómalo el segundo enunciado, ya
que el verbo opina exigiría a su sujeto la presencia del rasgo [+HUMANO] del cual carece mi
gato. Sin embargo, la oración cobraría pleno sentido en un contexto de cuento fantástico.
¿Puede ser semánticamente correcta sin serlo previamente en el plano sintáctico? Juzgamos que
no: la oración tiene sentido sintáctico, si al verbo en torno al cual gira somos capaz de asignarle
un sujeto ("mi gato") y un complemento directo ("que soy un gran cocinero"), con lo que ve
saciadas sus necesidades sintácticas.
Para la tercera no soy capaz de hallar contexto en el que resulte aceptable. Aunque
pasaría el filtro sintáctico, sería semánticamente mal formada si no tenemos en cuenta el
contexto.
Por fin, la última oración no pasaría la verificación sintáctica usando cualquier
gramática común del castellano.
La confusión entre semántica y pragmática se pone ya de relieve en la segunda oración
de la serie anterior: ¿Es un hecho lingüístico la deducción de que nos encontramos en un
ambiente de cuento, con las implicaciones que ello conlleva? ¿No es algo netamente influido
por la cultura...? No serían pocos los que catalogarían, despectivamente, el texto de un cuento
así como perteneciente a la literatura infantil (luego absurda y poco útil en el estudio de la
comunicación humana).
Igual que al hablar de fonología hemos destacado cómo la sintaxis condiciona, hasta
cierto punto, lo que esperamos oír, un módulo superior semántico-pragmático podría deducir
información de un enunciado sintácticamente erróneo: inducir palabras no escuchadas,
desconocidas, estructuras sintácticas de moda... El modelado de fenómenos tan relacionados
con la inteligencia humana deberían por ahora obligar a una hipotética máquina dialogante a
interrogarnos acerca de lo que acabamos de decir (algo, por cierto, habitual al hablar dos o más
personas).
Reseñar, como colofón, que entre los distintos enfoques dados a la semántica se hallan:
el que pretende emplear de la lógica de predicados, el funcional (el verbo sería el predicado que
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
selecciona a los demás elementos: sus argumentos), el generativista...
IV.6 Esquema orientado al reconocimiento
El esquema lingüístico anteriormente presentado es generativo, y no se adapta al
problema del reconocimiento, que es el objetivo último de nuestro trabajo.
Ya sabemos que al reconocer poseemos una secuencia sonora de la cual deseamos saber,
si es que existe, su transcripción grafémica. Para esta labor disponemos de la información
fonológica que nos permitirá pasar los fonemas a grafemas (se producirán inserciones, sustituciones y borrados). Estos grafemas será preciso unirlos para formar palabras: deberemos
consultar el diccionario léxico (en este nivel comenzarán a aparecer ambigüedades). Un módulo
sintáctico deberá discriminar qué secuencias de palabras son gramaticales y cuales no.
Finalmente la semántica interpretará lo dicho. Nuestro esquema secuencial simplificado será el
de la 13.
componente semántico
componente sintáctico
componente léxico
componente fonético
Figure 7 Esquema simple de reconocimiento.
Entre todos los niveles debería ser posible realimentar información al anterior y que éste
la propague hasta el más bajo, pero la opción elegida suele ser que el módulo inferior sea lo
suficientemente laxo como para aceptar todas las posibilidades (asignándoles una cierta
probabilidad de ocurrencia por él estimada) y permitir que sea su superior quien, manejando un
CAPITULO 4 : EL MODELO LINGÜÍSTICO
25
modelo más completo de la lengua, decida31. Como ya mencionamos al hablar del componente
fonológico, llegados arriba y sin posibilidad de interpretar lo enunciado, sólo nos queda rogar
una repetición de lo dicho, una aclaración a un término...
En los sistemas de dictado automáticos como el
desarrollado para el Inserso (Macías[92]) el módulo sonidofonema trata de encontrar todos los posibles fonemas presentes
en la secuencia sonora y que un módulo posterior de acceso a un
diccionario discrimine las palabras posibles que ,finalmente,un
módulo sintáctico tratarían de combinar formando oraciones
(Smaïli [90]).
31
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
CAPITULO V
COMPILACIÓN DE DICCIONARIOS
V.1 Presentación
Los diccionarios forman parte, de algún u otro modo, de la mayoría de los sistemas de
reconocimiento y síntesis de habla, de procesamiento de textos de lengua natural...
Un reconocedor basado en alófonos tendrá, por ejemplo, al menos dos diccionarios
implícitos o explícitos: el de los alófonos que debe detectar, pequeño y muy ligado al algoritmo
de reconocimiento, y el lexicón de palabras que permitirá extraer éstas de la secuencia, matriz o
celosía de unidades aceptadas.
Para vocabularios pequeños y determinados, si nuestro algoritmo de reconocimiento
permite el guiado sintáctico, la información sobre qué cadenas de alófonos son posibles
permitiría limita considerablemente el espacio de búsqueda: reconocer una cierta unidad fónica
reduce el número de posibles sucesoras (Niemann[86], Antoniol[89], Fissore[89]). La
perplejidad media (cuantas unidades pueden suceder a una dada) tenderá a 1 en vocabularios no
muy amplios.
Nuestro entorno de análisis sintáctico de oraciones escritas también precisa de acceso al
léxico. Dado un texto debemos leerlo carácter a carácter, segmentarlo en unidades que
consideremos como las mínimas significativas (palabras, o quizá, morfemas), extraer del
diccionario la información que sobre ellas dispongamos y, finalmente, realizar el análisis
propiamente dicho.
V.2 Acceso secuencial
La forma más sencilla de guardar y acceder a un diccionario es la secuencial ordenada.
Guardamos en memoria o en disco cada una de las palabras en un orden determinado y, si
necesitamos la información característica de una de ellas,la buscamos ordenadamente.
Aunque la utilización de índices (punteros a la zona de las palabras que empiezan por un
determinado carácter o por una secuencia de caracteres) puede acelerar el proceso de búsqueda (
especialmente si el almacenamiento se realiza en disco magnético), se desperdicia mucho
espacio debido a las redundancias del vocabulario: numerosas palabras comienzan o terminan
con la misma cadena de signos...
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
V.3 Compilación en forma de autómata
Todo vocabulario de cardinal finito, como ya hemos señalado al hablar de los lenguajes
formales, puede ser descrito unívocamente en términos de una gramática tipo 3 ó regular.
Los símbolos terminales de la gramática serían las unidades básicas de las palabras del
vocabulario : alófonos, fonemas, grafemas, morfemas... El axioma será en nuestro caso la
palabra, y los símbolos no terminales carecerán, por lo general, de significación intencionada (
un conjunto de caracteres podría corresponderse con un símbolo no terminal y con un morfema
de nuestro lenguaje, pero no por nuestra voluntad expresa).
Las reglas gramaticales tendrían la forma siguiente:
Install Equation Editor and doubleclick here to view equation.


Install Equation Editor and doubleclick here to view equation.
El autómata presenta dos ventajas:
-puede aprovechar las redundancias del vocabulario para reducir el espacio que
nos ocupa a la hora de almacenarlo, en memoria especialmente
-el tiempo que tarda en reconocer una cadena de entrada es independiente del
tamaño del diccionario y lineal respecto a la longitud de la secuencia
Un modo trivial de compilar el lexicón en forma de autómata finito sería convertir cada
unidad de una palabra en un estado diferente y encadenarlos de acuerdo con la regla que
describe dicha palabra32. Los autómatas por palabras así conseguidos, serían individualmente
deterministas, aunque globalmente indeterministas. Si los sumamos todos ( hacemos comunes
sus estados inicial y final), será normal que al estado inicial le sucedan varios estados con igual
símbolo en su rama intermedia. El algoritmo de conversión de AFN33 a AFD34 queda reducido,
por el carácter arbóreo de nuestro autómata, a la fusión en las cabeceras de palabra de los
estados equivalentes: aquellos que tienen igual predecesor e igual símbolo.
32La
notación que emplearemos de ahora en adelante para
nombrar los estados del autómata se componen del signo asociado
al mismo (un fonema,una letra...) y un subíndice que se
asignará secuencialmente a todos los estados de igual símbolo.
NFA.
33Autómata
Finito Indeterminado,en la bibliografía inglesa
34Autómata
Finito Determinado,en inglés DFA.
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
3
1
2
ini
fin
4
1
2
5
1
3
Ilustr. 8Ejemplo de unificación de cabeceras de palabra.
Obsérvese como usando un vocabulario común ordenado se obtiene una importante
reducción en el número de estados presentes en el autómata.
Similar operación podría ser realizada con los finales de palabra (las "colas"), pero
perderíamos la morfología en árbol, y algunos algoritmos de reconocimiento de voz admiten
sólo este tipo de estructuras para su guiado: la eliminación o no aceptación de un estado supone
la inmediata exclusión de sus sucesores en el árbol35.
Como en castellano los lexemas o prefijos+lexemas suelen tener mayor longitud que los
sufijos terminales, la fusión de "colas" será menos eficiente que la de cabeceras.
Si permitiésemos que una unidad fuese unificada como cola y como cabecera de una
palabra, el autómata podría aceptar palabras no pertenecientes a nuestro
vocabulario. El pequeño vocabulario siguiente:
Esta poda o "prunning"se denomina también "beam search":
la búsqueda se reduce a uno o varios haces de estados.
35
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
cuyo autómata contiene, además de las anteriores palabras, otras dos: "5 1 2" y "4 1 3".
Otro error que podría surgir sería la aparición de ciclos. El vocabulario:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
se podría convertir, tras la unificación de cabeceras, en:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
y en:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
tras la unificación de colas.
El autómata resultante (9) sería:
Install Equation Editor and doubleclick here to view equation.
en vez del correcto:
Install Equation Editor and doubleclick here to view equation.
ini
115
17
115
Ilustr. 9 Autómata tras errónea unificación de colas y cabeceras.
fin
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
La fusión ordenada presenta 2 opciones combinables:
-operar palabra a palabra, o globalmente con todo el vocabulario
-unificar primero las colas y luego las cabeceras, o primero las cabeceras
Partiendo del mini-diccionario:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
si operamos globalmente y unificamos primero las cabeceras, obtendremos:
Install
InstallEquation
EquationEditor
Editorand
anddoubledoubleclick
clickhere
heretotoview
viewequation.
equation.
Install
InstallEquation
EquationEditor
Editorand
anddoubledoubleclick
clickhere
heretotoview
viewequation.
equation.
Install Equation Editor and doubleclick here to view equation.
y, al unificar las colas, queda:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
En cambio, al realizar las operaciones también globalmente pero en orden inverso,
primero colas y luego cabeceras, el resultado es más eficiente:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
La mayor o menor redundancia entre colas o cabeceras hace que se reduzca más o
menos el número de estados. Sin embargo, la unificación de las colas primero puede dar lugar a
autómatas no deterministas como:
Install Equation Editor and doubleclick here to view equation.
donde al hallarnos en 5 sub 0 y recibir un 1 no sabríamos si ir a 1 sub 0 o a 1 sub 1.
Si operamos palabra a palabra, primero las cabeceras y luego las colas, los cuatro pasos
serán:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Al variar el orden de las palabras, obtendremos:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Trabajando palabra a palabra también influye qué unificamos primero, si colas o
cabeceras. Si empezamos por las cabeceras:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
y si por los finales:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Pero aunque el método de unificación de colas y cabeceras no nos da un número de
estados mínimo, si nos garantiza que conforme vamos reconociendo la cadena de entrada
podamos saber qué palabra es la reconocida, sin necesidad de posproceso (buscar en otro
diccionario). Cada palabra está caracterizada por la presencia de una secuencia de dos estados:
el último estado de su máxima cabecera de unificación (el estado inicial es por defecto) y el
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
siguiente (puede ser el estado final si ha habido fusión de cabeceras en esa palabra). En nuestro
primer ejemplo con los números, la secuencias características son
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
V.3.1 Independencia del orden de operaciones
Las diferencias debidas al orden en el que unifiquemos sólo se producen cuando las
palabras contienen unidades que se pueden fundir simultáneamente como cabeceras y como
colas.
Comparando :
Install Equation Editor and doubleclick here to view equation.
y
Install Equation Editor and doubleclick here to view equation.
donde la primera ha unificado antes las cabeceras, vemos que el estado 5 sub 0 posee dos
predecesores y un solo sucesor, cuando podría tener uno de cada, reduciéndose el número total
de estados.
Una regla iterativa podría ser:
-si el cardinal del conjunto de los estados que están asociados al símbolo 'I' es mayor que
el número de estados que los preceden o mayor que el número de estados que los suceden,
podríamos igualar dicho cardinal al menor de los cardinales de los sucesores y los predecesores
(10).
El problema de permitir reducir el número de estados en función de sus sucesores es que
existe la posibilidad de indeterminación. El ya visto:
Install Equation Editor and doubleclick here to view equation.
pasaría a ser:
Install Equation Editor and doubleclick here to view equation.
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
donde se elimina un estado asociado al símbolo 1 (ya que sólo poseía dos sucesores), pero se
crea una indeterminación en el estado 5 sub 0.
Otra regla iterativa muy lógica nos dice que si dos estados del mismo símbolo36 poseen
el mismo conjunto de predecesores o sucesores, deben ser equivalentes. Esta fusión de dos
estados en uno no provoca indeterminación: si previamente dos estados de un mismo símbolo
no tienen un estado común predecesor, al unirse debido a la igualdad de sucesores, tampoco
sucederá (XXXX).
Volviendo al ejemplo anterior y aplicando la última regla:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Se han fundido en uno los estados 1 sub 0 y 1 sub 2,quedando intacto el 1 sub 2.
Dos estados de diferente símbolo asociado nunca podrán
ser equivalentes,ya que para llegar a ellos se llegará por
medio de símbolos de entrada diferentes.
36
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
¡Error!Nombre de archivo no especificado.
Ilustr. 10 Primera regla iterativa.
34
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
Un problema que surge de la aplicación de estas reglas es la pérdida de la información
sobre qué palabra hemos reconocido: no hay una secuencia de dos estados que caracterice a
cada palabra. Por ejemplo la primera contiene las subcadenas: EstadoInicial+ 1 sub 0, 1 sub 0+
2 sub 0, 2 sub 0+EstadoFinal, que son compartidas con otras. Ampliar el número de estados
necesarios para caracterizar nos llevaría a la realización de un vocabulario paralelo (con la
pérdida de la eficiencia en la memoria ocupada) pues siempre es posible encontrar un ejemplo
que necesite más estados para caracterizar sus palabras:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
'Completamente' se caracteriza por una secuencia de cinco estados:
Install Equation Editor and doubleclick here to view equation.
La necesidad de consultar un diccionario en disco retrasará la finalización del
reconocimiento.
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
¡Error!Nombre de archivo no especificado.
Ilustr. 11 El algoritmo de reducción de número de estados.
¡Error!Nombre de archivo no especificado.
Ilustr. 12 Segunda regla iterativa.
34
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
V.3.2 La suma de gramáticas
Cuando se desarrolla un sistema de reconocimiento de vocabulario finito, se debe dar al
propietario la posibilidad de ampliar y redefinir el vocabulario dentro de las limitaciones de
memoria...
Una pequeña ampliación no debería suponer la adición de las nuevas palabras al
diccionario y volver a aplicarle a todo ello el algoritmo de reducción (la complejidad del
algoritmo es dependiente de la longitud del vocabulario): debemos guardar en un fichero los
resultados del algoritmo sobre el léxico original (la secuencia de estados, símbolo y subíndice,
que componen cada palabra), para así poder recuperarlos a la hora de ampliar, añadirle las
nuevas palabras con nuevos estados, y aplicar el algoritmo sobre una base ya bastante
optimizada.
V.3.3 Eficiencia de compilación
La capacidad para compactar vocabularios depende totalmente de las redundancias
contenidas en ellos.
Para un vocabulario poco redundante como los dígitos del cero al nueve la disminución
no vale la pena. Estos casos (que llamaríamos lexemáticos) tienen gran variedad de lexemas y
apenas morfemas.
Una mejor medida nos la dará un diccionario castellano de cierto tamaño. Usando la
máxima reducción:
número de palabras
número total de
alófonos
número total de estados
tamaño de tabla del
autómata
perplejidad del autómata
reducción
440
3083
811
1258
1,5388
3,8015
628
4383
1138
1763
1,5094
3,8515
1004
6893
1577
2578
1,6347
4,3710
Usando al unificación de colas y cabeceras:
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
número de palabras
número total de
alófonos
número total de
estados
tamaño de la tabla del
autómata
perpleji-dad del autómata
reducción
440
3083
812
1250
1,5394
3,7968
628
4383
1139
1765
1,5496
3,8481
1004
6893
1578
2580
1,6350
4,3682
Compilando en forma de árbol:
numero de palabras
número total de
alófonos
número total de estados
tamaño de la tabla
del autómata
perplejidad del autómata
reducción
440
3083
1418
1856
1,3089
2,1742
628
4383
2063
2689
1,3034
2,1246
1004
6893
3163
4165
1,3168
2,1793
Usando un vocabulario mayor y unificación sólo de cabeceras:
número de palabras
número total de
alófonos
número total de
estados
tamaño de la tabla del
autómata
perplejidad del autómata
reducción
499
4448
1834
2330
1,2704
2,4253
994
8913
3703
4696
1,2682
2,4070
1988
17239
7331
9226
1,2619
2,3515
Compilando colas y cabeceras:
numero de palabras
número total de
alófonos
número total de estados
tamaño de la tabla
del autómata
perplejidad del autómata
reducción
499
4448
938
1436
1,5309
5,0441
994
8913
1767
2760
1,5620
5,0441
1988
17239
3222
5209
1,6167
5,3504
La tabla de reconocimiento ha sido también linealizada, reduciéndose su dimensión
(pasa de ser igual al número de estados por el número de símbolos a ser el número de estados
por la perplejidad) a costa de incrementar algo el tiempo de reconocimiento (pasa de ser
proporcional a la longitud de la cadena de entrada a ser proporcional a la misma por la
perplejidad).
De las gráficas deducimos que:
-la unificación de colas y cabeceras es casi tan efectiva reduciendo como la optimizada
-si el vocabulario es muy homogéneo (muchas palabras comenzando por el mismo
alófono), ampliarlo puede suponer una reducción de eficiencia en el caso de buscar un árbol
-si se unifican también cabeceras, al ampliar el vocabulario se amplian las posibles
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
cabeceras comunes y mejora la reducción.
V.4 Utilización de léxicos en presencia de ruido
Si las palabras que debemos reconocer se hallan corrompidas por inserciones,
sustituciones y borrados, los autómatas anteriormente generados no son directamente
utilizables.
En Ascension[93] y Macias[92], se pueden encontrar ejemplos de dos alternativas al
problema que usan los autómatas presentados en este capítulo.
V.5 Programas empleados
Para la obtención de los resultados anteriores, y principalmente para su uso en sistemas
que necesiten guiado o acceso léxico dentro del Departamento, hemos implementado los
diversos algoritmos en C:
-obtención del autómata en forma de árbol usando la memoria (lo que supone limitarse a
poco más de dos mil palabras ) o el disco (permitiendo así compilar decenas de miles de
palabras, a costa de una lentitud exponencialmente mayor)
-unificación de colas y cabeceras con similares limitaciones en cuanto al número de
palabras para memoria y disco
-autómata reducido (sólo en memoria, dado su escaso interés)
Como entrada esperan recibir un fichero .LIS que contenga en cada línea:
Install Equation Editor and doubleclick here to view equation.
Los ficheros disponibles tras la ejecución serán:
-.TAB: cada línea contiene los estados a los que se puede saltar desde el que tiene el
mismo número que la línea.
-.EST: cada línea es un estado, con su número de símbolo y subíndice diferenciador.
-.EX1: contiene pares [número de palabra, símbolo siguiente] que caracterizan, junto a
la información de estado, a cada una de las palabras.
-.EX2: si no tomamos al estado final de cada palabra como caracterizador, contiene dos
números que indican la posiciones mínima y máxima de las zonas de .EX1 asociadas al estado
cuyo número coincide con el número de línea de .EX2.
-.REN: convierte la "numeración en amplitud" en "numeración en profundidad".
CAPITULO V : COMPILACIÓN DE DICCIONARIOS
34
-.ALF: dada la numeración en anchura, nos indica en qué posición de la tabla de
reconocimiento se encuentra el estado correspondiente a una posición de alófono en palabra
coincidente con el número de línea.
-.DIC: cada línea será una palabra del vocabulario reconocible.
V.5.1. Implementación en PC
Las limitaciones de memoria disponible en los PC nos obligaron a ampliar el algoritmo
propuesto.
Para el caso de generación de un árbol, dividimos el vocabulario original en subvocabularios independientes (palabras cuyo alófono inicial difiera aparecían en sublistas
distintas) o no (para vocabularios de decenas de miles de palabras cada subvocabulario
contendría palabras con los dos primeros alófonos iguales) y los compilamos por separado. A la
hora de mezclar los ficheros resultantes, los ficheros .EST los encadenaremos eliminando los
estados INICIAL y FINAL de los subárboles intermedios; para el .DIC, simplemente los
escribiremos secuencialmente; el .EX1 precisa de actualizar los valores de los números de
estado partículares al caso general, realizándose la misma operación con el número de palabra;
finalmente, el .TAB requiere una línea inicial que sea la suma reordenada de todas las línea
iniciales, copiándose las demás con actualización de números de estados acorde con el fichero
creado .EST.
El autómata por unificación de cabeceras y finales de palabras necesita de una doble
operación como la anterior: tras la subdivisión y compilación, mezclaremos los subficheros en
formato:
palabra Estado_0 ... Estado_N
los invertiremos para dar lugar a:
palabra Estado_N ... Estado_0
los subdividiremos de nuevo, unificaremos sus cabeceras invertidas. Tras volver a invertir,
subdividiremos de nuevo, generaremos los ficheros resultado para los subvocabularios y
mezclaremos como antes.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
CAPITULO VI
ANÁLISIS SINTÁCTICO DE GRAMÁTICAS DE
CONTEXTO LIBRE
VI.1 Presentación
Frente a la simplicidad del reconocimiento de lenguajes regulares mediante autómatas,
donde la única variación consiste en construir un autómata como la unión de muchos otros
subautómatas, el "parsing" (reconocimiento de que una cadena pertenece a un lenguaje) admite
más posibilidades al usarse gramáticas de contexto libre.
La forma más inmediata consiste en convertir cada regla sintáctica en un procedimiento
o función. La parte izquierda de la regla da nombre a dicha función y la derecha nos indica qué
procedimientos y en qué secuencia debemos llamarlo para verificar la aplicabilidad de la regla.
Como los símbolo terminales no tienen procedimiento asociado, al encontrarnos uno
comprobaremos si coincide con el símbolo que actualmente estábamos esperando reconocer. De
ser así, avanzaremos al símbolo siguiente y proseguiremos el análisis hasta poder devolver un
código de aceptación; en el caso de haber diferido, intentaremos aplicar otra regla que, por tener
el mismo símbolo no terminal a laizquierda, estará integrada en la misma función. Si no
existieran más reglas o no fuesen aplicables, devolveremos a la función que nos llamó un
código de error.
En cualquier lenguaje de programación moderno37 es fácil diseñar así un compilador de
compiladores (un programa que genera un programa que reconoce cadenas acordes con una
gramática dada), pero:
-la complejidad, debida al retroceso causado por los errores, es en general exponencial
con la longitud en caracteres de la cadena de entrada
-la posibilidad de tener que generar diversos análisis para una misma frase multiplica
aún más la lentitud del "parsing"
- el ordenamiento de las reglas influye en los resultados: las reglas recursivas a
izquierdas deben ser las últimas en ser usadas a la hora de comparar patrones para evitar los
bucles infinitos, o bien, debemos limitar la profundidad de recursión, método siempre
En Prolog (Pereira[87]) es especialmente fácil,aunque es
más difícil su integración con otros programas escritos en
otros lenguajes.
37
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
arriesgado, conflictivo y un tanto arbitrario.
Entre las ventajas destaca lo directo que es añadir rasgos al "parsing", ya que no serán
sino parámetros de las llamadas a las distintas funciones.
Este procedimiento descendente tiene su versión ascendente: para cada símbolo terminal
o secuencia de símbolos terminales intentamos encontrar un símbolo no terminal que permita
generarlos. Estos símbolos no terminales son sometidos a un similar proceso ascendente hasta
poder alcanzar el axioma.
Su complejidad es similar y además no es predictivo, por lo que dificultaría la labor de
guiado del reconocimiento léxico. Aún así existe algún artículo marginal donde se ha empleado
para extraer las oraciones gramaticalmente correctas contenidas en una celosía de palabras
alineadas (Miller[88]).
Los requerimientos de velocidad de análisis de los compiladores dieron lugar a
algoritmos que sólo podían ser usados con gramáticas que podríamos clasificar como de tipo 2'5
de la jerarquía de Chomsky, a medio camino entre las regulares y las de contexto libre.
Un procedimiento descendente así hallado fue el LL(k), que genera una tabla, similar a
la de descripción de un autómata, que permite reconocer en tiempo O(n)38.
Las gramáticas LL(1), las más comunes, son insuficientemente potentes para tratar el
lenguaje natural (ver Sanchís[88],cap. 7 y su referencia a Knuth para más detalles):
-dado un símbolo de entrada en una determinada posición, debe existir un solo camino
gramatical que lo conecte con el axioma.
-no existe ni existirá algoritmo que transforme una gramática cualquiera a gramática
LL(1)
- la existencia de ambigüedades ralentizaría notablemente el parsing
Sin embargo, dada su sencillez, podría ser útil en lenguajes de comandos sencillos, con
características de notación prefija. Por ejemplo la gramática BNF prefija es LL(1): existen unos
prefijos que nos indican qué tipo de frase estamos analizando
VI.2 Análisis LR(1)
Su utilización en la bibliografía de reconocimiento de voz, masiva a partir de que en
Tomita[86a] se ampliara el algoritmo original para permitir gramáticas ambiguas, lo hace
merecedor de un análisis en detalle.
Seguimos la clásica notación en O mayúscula para denotar
el comportamiento medio del algoritmo al variar la longitud de
la cadena que reconocer.Ver Natural Languajes Readings[].
38
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Como LL(1), utiliza una tabla de reconocimiento precompilada que guía su
característico autómata con pila. Dada la existencia de generadores automáticos de estas tablas
fácilmente disponibles (YACC para máquinas UNIX, Bisón para PC...), no detallaremos el
algoritmo que la produce. En Aho[72] se describen varios, de potencia descriptiva creciente y en
Tomita[86b] se encuentra el código en LISP para generar las LALR(1).
VI.2.1 Tablas LALR(1) ampliadas
Las gramáticas que no sean LR(1), aunque sean de contexto libre, darán lugar a tablas de
reconocimiento tablas ambiguas, con varias entradas por casilla.
Tomamos un ejemplo de Tomita[86b] por su tamaño:
estado
det
sust
0
sh3
sh4
verb
prep
$
SP
SV
O
2
1
sh6
2
3
SN
acc
sh7
sh6
re3
re3
re3
re2
re2
1
5
9
8
sh10
4
5
6
sh3
sh4
11
7
sh3
sh4
12
8
re1
re1
9
re5
re5
re5
10
re4
re4
re4
11
re6
re6,sh6
re6
9
re7,sh6
re7
9
12
que parte de las reglas gramaticales:
O
O
SN
SN
SP
SV
claramente simples,
conflictos.
Usando
por
nosotros
resultados
son
->
->
->
->
->
->
SN SV
O SP
(det) sust
SN SP
prep SN
verb SN
con
apenas
2
gramáticas elaboradas
incrementalmente los
inquietantes:
6 Ejemplo de reglas.
fichero
nº reglas
estados
sh/red
red/red
gsimpl2
32
44
22
0
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
gsimpl3
90
106
254
237
gsimpl5
245
339
606
625
gsimpl6
251
346
605
625
Al intentar usar la gramática g1.gra con más de quinientas reglas, bison se quedó sin
memoria en el PC.
Dado que :
-deseábamos realizar un entorno propio para PC,
-que no plantee ningún problema a la hora de escribir las reglas (en todo caso que se
pueda solucionar la optimización con herramientas automáticas),
-que la velocidad es una cuestión relativa si otros algoritmos (como muestra la
bibliografía) son paralelizables e integrables VLSI...
decidimos no optar por este algoritmo muy usado por los investigadores del grupo de Carnegie
Mellon (CMU).
VI.3 ATNs
Muy populares en su tiempo, las Redes de Transición Aumentadas surgieron al añadir a
las RTN registros auxiliares y acciones asociadas a los arcos. En un lenguaje ordenado como el
inglés, los registros pueden ser elegantemente usado para hacer asignaciones temáticas:
SN
A
V
V
B
C
V
SN
D
E
SN
SP
SN
SP
Ilustr. 13 Ejemplo de gramática ATN.
Las transiciones conllevan acciones como las siguientes:
-pasar de A a B, tras el reconocimiento de un Sintagma Nominal, éste pasa a rellenar el
registro de SUJETO
-a la recepción del primer verbo (B->C) lo ponemos en el registro del VerboPrincipal
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
-si recibimos más verbos y el VerboPrincipal no es Auxiliar (to be, to do, to have...),
devolvemos ERROR; si no, copiamos en VerboAuxiliar el contenido de VerboPrincipal y en
éste el último verbo aceptado
-tras recibir un participio precedido de VerboPrincipa==to be, hacemos VOZ=pasiva,
VerboAuxiliar=VerboPrincipal,
VerboPrincipal=ParticipioRecibido,
ComplementoDirecto=SUJETO y borramos SUJETO
-si pasamos de C a D por medio de un sintagma nominal, simplemente rellenamos el
ComplementoDirecto con dicho sintagma.
-ante una nueva recepción de sintagma nominal, copiamos el ComplementoDirecto en el
ComplementoIndirecto y en el ComplementoDirecto el último sintagma


La elegancia del planteamiento es sumamente atractiva. No obstante, la existencia de
problemas como :
-el backtracking (retroceso),
-las dificultades para analizar oraciones ambiguas,
-el tamaño de la red se haría inmanejable al intentar tratar la multitud de fenómenos que
caracterizan a una lengua natural,
-la ausencia de herramientas automáticas que generen las redes,
-la gran libertad de ordenamiento de sintagmas del castellano...
nos desaconsejaron su implementación inmediata.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
VI.4 Algoritmos generales
VI.4.1 Algoritmo de Cocke-Younger-Kasami
Hays atribuye a Cocke la aplicación de la programación dinámica al análisis sintáctico.
Posteriormente Kasami, independientemente, lo redescubrió y Younger demostró que su
complejidad era cúbica. Valiant mostró que equivalía a la operación de cerrar transitivamente
una matriz y que con una constantes de proporcionalidad enormes, podía ser calculado en
tiempo subcúbico. Ruzzo, finalmente, dejo en O(log(n)) la complejidad para la versión paralela
asíncrona.
VI.4.1.1 Preproceso
En todas sus versiones, CYK requiere de una transformación en la gramática a fin de
ponerla en Forma Normal de Chomsky sin cadena vacía. Para ello las reglas deberán tener uno
de los dos siguientes formatos:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
El algoritmo que realiza la conversión aparece en el recuadro 6.
Begin
end
P':=0
añadir a P' todas las reglas de la forma A->BC
añadir a P' todas las reglas de la forma A->a
reservar aparte las reglas del tipo A->B
para cada regla del tipo A->X1 X2...Xk
begin
for (i:=1 TO k-2)
begin
si Xi es NoTerminal
añadir la regla A->Xi A'i
si no
begin
crear la regla X'i->Xi
añadir A->X'i A'i
end
end
end
7 Algoritmo que pasa una gramática extendida a FNC.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Para la eliminación de la cadena vacía de un lenguaje que no la admita como símbolo
plenamente terminal, en Sanchís[88] se muestra un algoritmo.
No todas las gramáticas pueden ser puestas en forma Normal de Chomsky sin cadena
vacía ni eliminación de reglas unitarias del tipo A->B.Por ello les daremos un tratamiento
diferenciado al aplicar CYK.
La conversión multiplica el número de reglas aplicables, aunque ello no tiene por qué
hacer linealmente más lento el "parsing": las reglas son más pero su uso es mucho más simple,
sin necesidad de recorrer los símbolos de su parte derecha ya que sólo tiene dos. Eso sí, es
necesario ordenar las reglas por su parte derecha y guardar con cada símbolo
cuál es la primera regla que contiene dicho símbolo como primero en su parte derecha (si no la
velocidad depende directamente del número medio de reglas, multiplicándose por veinte o
treinta el tiempo de reconocimiento de una frase).
Como las reglas de los dos tipos permitidos no se aplican conjuntamente, una extensión
regular de las reglas originales (las que permiten paréntesis...) disminuye el nº de reglas en FNC
creadas.
Los símbolos generados durante la transformación serán transparentes al usuario, no
apareciendo en los árboles ni en pantalla ni en disco.
VI.4.1.2 CYK en forma matricial
CYK un algoritmo ascendente y orientado a anchura (breath-first). Tras colocar en una
matriz que llamaremos 'chart' los símbolos terminales según su orden de aparición en la cadena
de entrada en las casillas chart[n,n-1], donde n es la longitud de la cadena, la ascensión, en
notación matricial, comprendería dos pasos:
-aplicación de las reglas tipo A->a para traducir las categorías sintácticas Terminales a
No Terminales:
Install Equation Editor and doubleclick here to view equation.
-aplicación de A->BC, desde i=N hasta i=0 y de A->B:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Si tras realizar los cálculos en chart[0,n] hemos incluido el axioma, la cadena es aceptada.
VI.4.1.3 CYK en forma asíncrona
Traducidas a seudocódigo, las anteriores fórmulas dan lugar al recuadro 8.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
for j=1 to n
chart[j-1,j] <- {A / existe A->a}
for i= to
for j= to
for k= to
chart[i,j] <- { A / existen a->BC ,
chart[i,k] incluye B ,
chart[k,j] incluye C}
8 Algoritmo CYK asíncrono.
VI.4.1.4 CYK en forma síncrona
Si vamos calculando conforme recibimos la cadena de entrada (o incluso un "lattice" de
elementos alineados) obtenemos el algoritmo del recuadro 9.
for j=1 to n
begin
chart[j-1,j] <- {A / existe A->a}
for i=j-1 to 0
for k=i+1 to j-1
chart[i,j] <- {A / existe A->BC ,
chart[i,k] incluye B ,
chart[k,j] incluye C }
end
9 Algoritmo CYK síncrono.
VI.4.1.5 Algoritmo de reconstrucción
El árbol sintáctico se irá creando a partir del axioma, que será el nodo raíz por medio del
algoritmo descrito en el recuadro 10.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Reconstruye(i, j, A, nodoAnterior)
begin
nodoA=CreaNodo(A, nodoAnterior)
for k=i+1 to j-1
begin
para cada símbolo B de la casilla chart[i,j]
para cada símbolo C de chart[k,j]
si existe una regla A->B C
begin
nodoB=Reconstruye(i,k,B,nodoA)
nodoC=Reconstruye(k,j,C,nodoA)
end
end
para cada nodo B de chart[i,j]
si existe regla A->B
nodoB=Reconstruye(i,j,B,nodoA)
return nodoA
end
10 Algoritmo recursivo de reconstrucción sin ambigüedades.
Oración=SintagmaNominal SintagmaVerbal
SintagmaNominal1=Determinante Núcleo
Determinante=determinante
SintagmaNominal1=Núcleo
Núcleo=núcleo
SintagmaNominal=SintagmaNominal SintagmaPreposic
SintagmaNominal=SintagmaNominal1
SintagmaPreposic=Preposición SintagmaNominal1
Preposición=preposición
SintagmaVerbal=Verbo SintagmaNominal
Verbo=verbo
Verbo=verbo
11 Gramática en FNC.
VI.4.1.6 Ejemplo de reconocimiento
Usando una gramática que por hallarse en FNC (salvo la regla SN->SN1) no necesita
transformación (así evitamos la complicación de que existan símbolos artificiales en la "chart")
con la frase: "yo vi un hombre en el apartamento con un telescopio" obtenemos la tabla
siguiente:
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
j
1
2
3
4
5
50
6
7
8
9
10
i
0
1
2
núcl,Núcl,
SN1,SN
verb,
Verb
det,Det
3
4
O
O
O
SV
SV
SV
SN1,SN
SN1,SN
SN1,SN
núcl,Núcl,
SN1,SN
SN
SN
prep,Prep
5
SPrep
det,Det
6
7
SN1,SN
SN
núcl,Núcl,
SN1,SN
SN
prep,
Prep
8
SPrep
det,Det
9
SN1,SN
núcl,Núcl,
SN1,SN
La reconstrucción será:
PASO nº0 : Reconstruye(0,10,Oracion,NULL)
PASO nº1 : nodoSintagmaNominal=Reconstruye(0,1 ,SintagmaNominal
,nodoOración ,1)
PASO nº2 : nodoSintagmaNominal1=Reconstruye(0,1,SintagmaNominal1
,nodoSintagmaNominal ,1)
PASO nº3 : nodoNúcleo=Reconstruye(0,1 ,Núcleo,nodoSintagmaNominal1 ,1)
PASO nº4 : nodonúcleo=ReconstruyeDiagonal(0,1 ,núcleo,nodoNúcleo ,1)
PASO nº5 : nodoSintagmaNominal=Reconstruye(1,10,SintagmaNominal
,nodoOración ,1)
PASO nº6 : nodoVerbo=Reconstruye(1,2 ,Verbo,nodoSintagmaVerbal ,1)
PASO nº7 : nodoverbo=ReconstruyeDiagonal(1,2 ,verbo ,nodoVerbo ,1)
PASO nº8 : nodoVerbo=Reconstruye(2,10 ,Verbo,nodoSintagmaVerbal ,1)
PASO nº9 : nodoSintagmaNominal=Reconstruye(2,7,SintagmaNominal
,nodoSintagmaNominal ,1)
PASO nº10 : nodoSintagmaNominal=Reconstruye(2,4,SintagmaNominal
,nodoSintagmaNominal ,1)
PASO nº11 : nodoSintagmaNominal1=Reconstruye(2,4,SintagmaNominal1
,nodoSintagmaNominal ,1)
PASO nº12 : nodoDeterminante=Reconstruye(2,3 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº13 : nododeterminante=ReconstruyeDiagonal(2,3, determinante
,nodoDeterminante ,1)
PASO nº14 : nodoDeterminante=Reconstruye(3,4 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº15 : nodonúcleo=ReconstruyeDiagonal(3,4 ,núcleo
,nodoNúcleo ,1)
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
PASO nº16 : nodoSintagmaNominal=Reconstruye(4,7,SintagmaNominal
,nodoSintagmaNominal ,1)
PASO nº17 : nodoPreposición=Reconstruye(4,5 ,Preposición
,nodoSintagmaPreposic ,1)
PASO nº18 : nodopreposición=ReconstruyeDiagonal(4,5 ,preposición
,nodoPreposición ,1)
PASO nº19 : nodoPreposición=Reconstruye(5,7 ,Preposición
,nodoSintagmaPreposic ,1)
PASO nº20 : nodoDeterminante=Reconstruye(5,6 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº21 : nododeterminante=ReconstruyeDiagonal(5,6 ,determinante
,nodoDeterminante ,1)
PASO nº22 : nodoDeterminante=Reconstruye(6,7 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº23 : nodonúcleo=ReconstruyeDiagonal(6,7 ,núcleo
,nodoNúcleo ,1)
PASO nº24 : nodoSintagmaNominal=Reconstruye(7,10,SintagmaNominal
,nodoSintagmaNominal ,1)
PASO nº25 : nodoPreposición=Reconstruye(7,8 ,Preposición
,nodoSintagmaPreposic ,1)
PASO nº26 : nodopreposición=ReconstruyeDiagonal(7,8 ,preposición
,nodoPreposición ,1)
PASO nº27 : nodoPreposición=Reconstruye(8,10 ,Preposición
,nodoSintagmaPreposic ,1)
PASO nº28 : nodoDeterminante=Reconstruye(8,9 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº29 : nododeterminante=ReconstruyeDiagonal(8,9 ,determinante
,nodoDeterminante ,1)
PASO nº30 : nodoDeterminante=Reconstruye(9,10 ,Determinante
,nodoSintagmaNominal1 ,1)
PASO nº31 : nodonúcleo=ReconstruyeDiagonal(9,10 ,núcleo
,nodoNúcleo ,1)
Oración
SintagmaNominal
SintagmaVerbal
SintagmaNominal1 Verbo
Núcleo
verbo
núcleo
SintagmaNominal
SintagmaNominal
SintagmaNominal
SintagmaPreposic
SintagmaPreposic
Prep SintagmaNominal1
SintagmaNominal1 Preposición SintagmaNominal1
Determinante Núcleo preposición Determinante Núcleo
determinante núcleo
yo
vi
un
hombre
Ilustr. 14 Arbol nº1.
en
prep Determ Núcleo
determ núcleo
determinante núcleo
el
apartamento con un telescopio
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Si añadimos la siguiente regla que permite complementos preposicionales en el nivel
oracional39:
Install Equation Editor and doubleclick here to view equation.
dentro de la primera llamada a Reconstruye encontramos otro posibles paso nº1:
Reconstruye(0,4,Oración,nodoOración). El nuevo análisis (continuando la anterior numeración)
será pues:
PASO nº32 : nodoOración=Reconstruye(0,7 ,Oración ,nodoOración ,2)
PASO nº33 : nodoSintagmaNominal=Reconstruye(0,1,SintagmaNominal
,nodoOración ,2)
PASO nº34 : nodoSintagmaNominal1=Reconstruye(0,1 ,SintagmaNominal1
,nodoSintagmaNominal ,2)
PASO nº35 : nodoNúcleo=Reconstruye(0,1 ,Núcleo,nodoSintagmaNominal1 ,2)
PASO nº36 : nodonúcleo=ReconstruyeDiagonal(0,1 ,núcleo ,nodoNúcleo ,2)
PASO nº37 : nodoSintagmaNominal=Reconstruye(1,7,SintagmaNominal
,nodoOración ,2)
PASO nº38 : nodoVerbo=Reconstruye(1,2 ,Verbo,nodoSintagmaVerbal ,2)
PASO nº39 : nodoverbo=ReconstruyeDiagonal(1,2 ,verbo ,nodoVerbo ,2)
PASO nº40 : nodoVerbo=Reconstruye(2,7 ,Verbo ,nodoSintagmaVerbal ,2)
PASO nº41 : nodoSintagmaNominal=Reconstruye(2,4,SintagmaNominal
,nodoSintagmaNominal ,2)
PASO nº42 : nodoSintagmaNominal1=Reconstruye(2,4,SintagmaNominal1
,nodoSintagmaNominal ,2)
PASO nº43 : nodoDeterminante=Reconstruye(2,3,Determinante
,nodoSintagmaNominal1 ,2)
PASO nº44 : nododeterminante=ReconstruyeDiagonal(2,3 ,determinante
,nodoDeterminante ,2)
PASO nº45 : nodoDeterminante=Reconstruye(3,4 ,Determinante
,nodoSintagmaNominal1 ,2)
PASO nº46 : nodonúcleo=ReconstruyeDiagonal(3,4 ,núcleo ,nodoNúcleo ,2)
PASO nº47 : nodoSintagmaNominal=Reconstruye(4,7,SintagmaNominal
,nodoSintagmaNominal ,2)
PASO nº48 : nodoPreposición=Reconstruye(4,5 ,Preposición
,nodoSintagmaPreposic ,2)
PASO nº49 : nodopreposición=ReconstruyeDiagonal(4,5 ,preposición
,nodoPreposición ,2)
PASO nº50 : nodoPreposición=Reconstruye(5,7 ,Preposición
,nodoSintagmaPreposic ,2)
PASO nº51 : nodoDeterminante=Reconstruye(5,6 ,Determinante
,nodoSintagmaNominal1 ,2)
Creando esta regla se producen las mismas ambigüedades
que añadiendo SV->SV SP y además no varía la tabla de
reconocimiento.
39
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
PASO nº52 : nododeterminante=ReconstruyeDiagonal(5,6 ,determinante
,nodoDeterminante ,2)
PASO nº53 : nodoDeterminante=Reconstruye(6,7 ,Determinante
,nodoSintagmaNominal1 ,2)
PASO nº54 : nodonúcleo=ReconstruyeDiagonal(6,7 ,núcleo ,nodoNúcleo,2)
PASO nº77 : nodoOración=Reconstruye(7,10 ,Oración ,nodoOración ,2)
PASO nº78 : nodoPreposición=Reconstruye(7,8 ,Preposición
,nodoSintagmaPreposic ,2)
PASO nº79 : nodopreposición=ReconstruyeDiagonal(7,8 ,preposición
,nodoPreposición ,2)
PASO nº80 : nodoPreposición=Reconstruye(8,10 ,Preposición
,nodoSintagmaPreposic ,2)
PASO nº81 : nodoDeterminante=Reconstruye(8,9 ,Determinante
,nodoSintagmaNominal1 ,2)
PASO nº82 : nododeterminante=ReconstruyeDiagonal(8,9
,determinante
,nodoDeterminante ,2)
PASO nº83 : nodoDeterminante=Reconstruye(9,10 ,Determinante
,nodoSintagmaNominal1 ,2)
PASO nº84 : nodonúcleo=ReconstruyeDiagonal(9,10 ,núcleo,nodoNúcleo,2)

Oración
Oración
SintagmaPreposic
SintagmaNominal
SintagmaNominal
Núcleo
Preposición SintagmaNominal1
SintagmaNominal1 Verbo
preposición Determ Núcleo
verbo SintagmaNominal
núcleo
SintagmaVerbal
SintagmaPreposic
determ
núcleo
SintagmaNominal1 Preposición SintagmaNominal1
Determinante Núcleo preposición Determinante Núcleo
determinante núcleo
determinante núcleo
yo
vi
un
hombre en
el apartamento
con un telescopio
Ilustr. 15 Árbol parcial nº2.
Nuevamente encontramos una ambigüedad
nº0:Reconstruye(0,4,Oración,nodoOración)
en
el
interior
tras
el
PASO nº55 : nodoOración=Reconstruye(0,4 ,Oración ,nodoOración ,3)
PASO nº56 : nodoSintagmaNominal=Reconstruye(0,1,SintagmaNominal
,nodoOración ,3)
PASO nº57 : nodoSintagmaNominal1=Reconstruye(0,1,SintagmaNominal1
,nodoSintagmaNominal ,3)
PASO nº58 : nodoNúcleo=Reconstruye(0,1 ,Núcleo,nodoSintagmaNominal1 ,3)
PASO nº59 : nodonúcleo=ReconstruyeDiagonal(0,1 ,núcleo ,nodoNúcleo ,3)
PASO nº60 : nodoSintagmaNominal=Reconstruye(1,4,SintagmaNominal
,nodoOración ,3)
paso
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
PASO nº61 : nodoVerbo=Reconstruye(1,2 ,Verbo,nodoSintagmaVerbal ,3)
PASO nº62 : nodoverbo=ReconstruyeDiagonal(1,2 ,verbo ,nodoVerbo ,3)
PASO nº63 : nodoVerbo=Reconstruye(2,4 ,Verbo,nodoSintagmaVerbal ,3)
PASO nº64 : nodoSintagmaNominal1=Reconstruye(2,4 ,SintagmaNominal1
,nodoSintagmaNominal ,3)
PASO nº65 : nodoDeterminante=Reconstruye(2,3
,Determinante,nodoSintagmaNominal1 ,3)
PASO nº66 : nododeterminante=ReconstruyeDiagonal(2,3 ,determinante
,nodoDeterminante ,3)
PASO nº67 : nodoDeterminante=Reconstruye(3,4 ,Determinante
,nodoSintagmaNominal1 ,3)
PASO nº68 : nodonúcleo=ReconstruyeDiagonal(3,4 ,núcleo ,nodoNúcleo ,3)
PASO nº69 : nodoOración=Reconstruye(4,7 ,Oración ,nodoOración ,3)
PASO nº70 : nodoPreposición=Reconstruye(4,5 ,Preposición
,nodoSintagmaPreposic ,3)
PASO nº71 : nodopreposición=ReconstruyeDiagonal(4,5 ,preposición
,nodoPreposición ,3)
PASO nº72 : nodoPreposición=Reconstruye(5,7 ,Preposición
,nodoSintagmaPreposic ,3)
PASO nº73 : nodoDeterminante=Reconstruye(5,6 ,Determinante
,nodoSintagmaNominal1 ,3)
PASO nº74 : nododeterminante=ReconstruyeDiagonal(5,6 ,determinante
,nodoDeterminante ,3)
PASO nº75 : nodoDeterminante=Reconstruye(6,7 ,Determinante
,nodoSintagmaNominal1 ,3)
PASO nº76 : nodonúcleo=ReconstruyeDiagonal(6,7 ,núcleo ,nodoNúcleo ,3)
Oración
Oración
SintagmaPreposic
Oración
SintagmaVerbal
Preposición
núcleo
núcleo
Núcleo
determinante núcleo
vi un hombre
SintagmaPreposic
Prep SintagmaNominal1
SintagmaNominal
SintagmaNominal1
prep Determ
Núcleo
SintagmaNominal1 Verbo SintagmaNominal preposición Determinante Núcleo
determ
Núcleo verbo SintagmaNominal1
determinante
núcleo
Determinante
yo
en
el
apartamento
con un telescopio
Ilustr. 16Árbol nº 3
Tras realizar el primer análisis completo, realizamos el segundo, para lo cual sólo
debemos copiar de un árbol a otro el nodoO1.
Lo mismo sucede con el tercero, pero no con el cuarto. Este último parte de un tercer
análisis mediado: no podemos copiar todo el tercer árbol hasta ahora generado, pues contiene
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
una estructura para "yo vi un hombre en el apartamento". El cuarto sólo necesita nodoO1 y
nodoO2: cada vez que encontremos una ambigüedad en un Reconstruye, debemos copiar el
árbol a izquierdas desde el nodo raíz hasta el nodo anterior, ambos inclusive.
A la salida de PASO nº3'': Reconstruye(), no se puede continuar el cuarto análisis:
debemos indicar que el cuarto nodo, a la derecha de nodoAnterior es igual al tercero.
VI.4.1.7 CYK con predicción
Resulta especialmente útil que el algoritmo sintáctico pudiese predecir, tras realizar los
cálculos asociados a una palabra, cuáles son las posibles siguientes.
Para ello es necesario precompilar la gramática y, para cada símbolo no terminal de la
gramática en Forma Normal de Chomsky cuáles son los símbolos terminales que los pueden
encabezar. El algoritmo (tomado del LL(1) sería (teniendo en cuenta que no se admite la cadena
vacía):
para cada regla A->a..
añadir el terminal 'a' a la Cabecera[A]
Nuevos=FALSO
hacer
begin
Para cada regla A->BC
begin
Añadir a Cabecera[A] la Cabecera[B]
Si ha habido nuevos
Nuevos=VERDADERO
end
end
mientras Nuevos==VERDADERO
12 Algoritmo para el cálculo de las Cabeceras terminales de
los símbolos no terminales.
Para la predicción usaremos el procedimiento del recuadro 12.
VI.4.1.8 Diferentes implementaciones
Jugando con la memoria usada y la velocidad alcanzable son varias las posibles
arquitecturas.
La más veloz de las que sólo precisan un procesador necesitaría un chart tridimensional
de N*N*NT casillas, siendo N el máximo número de palabras por frase y NT el cardinal del
conjunto de símbolos No Terminales.
Las reglas estarían separadas en unitarias y binarias, dada la independencia en su uso, y
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
necesitaríamos una matriz de NT*NT elementos para guardar las reglas
NoTerminal=NoTerminal
El algoritmo que se basa en esta estructura variará respecto a los ya vistos (recuadro 13).
for j=1 to n
begin
para cada regla B->b
begin
incorporar B a Chart[j-1,j]
para cada regla A->B..
Incorporar Cabecera[C] a Predicción[]
end
for i=j-1 to 0
for k=i+1 to j-1
begin
para cada símbolo B de Chart[i][k]
y cada C de Chart[k][j]
Si existe Regla A->BC
begin
Incorporar A a Chart[i][j]
para cada regla D->AE
Incorporar Cabecera[E] a
Predicción[]
end
para cada símbolo B del Chart[i][j]
si existe regla A->B
Incorporar A a Chart[i][j]
end
Comunicar Predicción al Reconocedor
end
13 Algoritmo de predicción integrado en el CYK síncrono.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
for i=1 to N
for j=1 to N
para cada símbolo U
Chart[i][j][U]=NO_USADO
for i=1 to N
begin
para cada símbolo terminal 'a'en posición i
Chart[i-1][i][a]=USADO
for j=i-1 to 0
para cada regla A->BC
for k=j+1 to i-1
si (Chart[i][k][B]==USADO y
Chart[k][j][C]==USADO)
Chart[i][j][A]=USADO
end
14 Algoritmo óptimo para un procesador único.
Como los índices tienen ámbitos de recorrido interdependientes, el número de
operaciones de unificación que realizar será:
Install Equation Editor and doubleclick here to view equation.
82
donde RB es el número de reglas binarias, T el número de símbolos terminales y
NumEquivalentesMedio, el resultado de dividir las casillas ocupadas de la matriz de
equivalentes por NT (si suponemos que la oración en palabras es traducida a lattice alineado de
categorías léxicas, la diagonal puede ser léxicamente ambigua, y de ahí la aparición del factor T
en el tercer sumando).
La ocupación de memoria es demasiado generosa:
Install Equa tion Editor and doubleclick here to view equation.
Por eso no hemos usado esta versión del algoritmo en nuestro entorno para PC40.
Para reducir la Chart no podremos tener una casilla por símbolo no terminal: la tabla
será falsamente bidimensional con una pila en cada posición Chart[][]. El tamaño de la pila
vendrá limitado por una constante calculada empíricamente: NumMedioNT41.
La chart puede reducirse si la linealizamos,pero aún así
su tamaño para frases largas (N==25) y gramáticas amplias
(NT=600) no son admisibles.
40
Lógicamente es posible el desbordamiento de la pila y la
consiguiente imposibilidad de analizar una frase muy ambigua
41
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
El algoritmo es el ya mostrado en el recuadro 14, donde no existe un bucle de recorrido
de reglas sino uno de recorrido de las dos casillas que unificar. Como los símbolos (nunca
repetidos) no se guardan ordenadamente en las pilas, el acceso a las reglas debe ser casi
inmediato. Como el crear una matriz indexada por los símbolos no
terminales de las reglas, o sea donde:
Install Equation Editor and doubleclick here to view equation.
nos haría perder mucho espacio, ordenaremos las reglas por su parte derecha, tanto las
binarias como las unitarias, y para cada símbolo terminal o no guardar unos punteros a la
primera y última regla que tiene a ese símbolo como primero a la derecha del igual. La
ralentización media será igual al número de reglas binarias dividido por el número de símbolos
no terminales (para una gramática normal será menor a dos, con una ocupación de espacio
considerablemente menor):
Install Equation Editor and doubleclick here to view equation.
VI.4.1.9 Linealización del Chart
Para no desaprovechar las casillas de la triangular inferior, observemos en la siguiente
tabla en qué orden son "rellenadas" las casillas, para poder hacerla lineal:
i\j
1
2
3
4
5
0
1º
3ª
6ª
10ª
15ª
2ª
5ª
9ª
14ª
4ª
8ª
13ª
7ª
12ª
1
2
3
4
por causa de una gramática quizás mal definida.
11º
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
VI.4.2 Algoritmo de Earley
Como resultado de su tesis doctoral en Carnegie Mellon, J. Earley construyó el primer
algoritmo de parsing basado en una Chart activa, no llena de símbolos sino de reglas activas
(parcialmente reconocidas) y reglas completas.
Partiendo del concepto de estado que Knuth introdujo en su trabajo sobre gramáticas
LR, Earley desarrolló un algoritmo descendente que podía reconocer oraciones descritas por
medio de una gramática de contexto libre sin restricciones de formato o eliminación de la
cadena vacía.
Si la gramática es ambigua, el tiempo de reconocimiento será proporcional al cubo de la
longitud de la cadena de entrada, aunque para ciertas gramáticas el tiempo medio se puede
reducir a cuadrático o incluso lineal. Usando arquitecturas paralelas con numerosos
procesadores esto es factible para cualquier gramática.
VI.4.2.1 Funcionamiento básico
Describamos el esquema de funcionamiento básico que resulta muy sencillo (figura 15)
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
Inicialización:
Para cada regla S->...
Nuevos=AñadirElemento({S->..,0},Agenda[0])
hacer
begin
Nuevos=0
para cada elemento {A->..B..,0} de Agenda[0]
para cada regla B->...
Nuevos=AñadirElemento({B->..,0}
,Agenda[0])
para cada elemento {A->..,0} en Agenda[0]
para cada elemento {B->..A..,0} de Agenda[0]
Nuevos=AñadirElemento({B->..A..,0}
,Agenda[0])
end
mientras Nuevos=1
Iteración:
for j=1 to N
begin
Nuevos=0
para cada elemento {A->..a..,i} de Agenda[j-1]
si 'a' pertenece a Entrada[j]
Nuevos=AñadirElemento({A->..a..,i}
,Agenda[j])
si Nuevos=0
devolver ERROR
hacer
begin
Nuevos=0
para cada elemento {A->..B..,i} de Agenda[j]
para cada regla B->...
Nuevos=AñadirElemento({B->..,j}
,Agenda[j])
para cada elemento {A->..,i} en Agenda[j]
para cada elemento {B->..A..,k} de
Agenda[i]
Nuevos=AñadirElemento({B->..A..,k}
,Agenda[j])
end
mientras Nuevos=1
end
Si existe algún elemento {S->..,0} en Agenda[N]
devolver BIEN
si no
devolver ERROR
15 Algoritmo básico descrito en AHO[72].
50
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Las operaciones que se realizan iterativamente son tres:
-Predicción: si tenemos un estado {A->..B..,i} es que necesitamos desarrollar B;
debemos recorrer las reglas B->.. para predecir lo que buscamos
-Compleción: si hemos llegado a un estado completo {A->..,i} , algún estado previo
debe haber predicho A y querrá que le avancemos el puntero: {B->..A..,i}
-Avance: una vez hechas todas las posibles predicciones de símbolos terminales,
debemos comprobar que la cadena de entrada posee alguno de ellos y avanzar el puntero
correspondiente del elemento: {A->..a..,i}
VI.4.2.2 Reconstrucción del árbol sintáctico
Reconstruye({A->B1 B2..Bm,i},j)
begin
Añade a ListaDeReglas el elemento (A->B1 B2..Bm)
k=m
l=j
hacer
begin
si Bk es terminal
begin
k=k-1
l=l-1
end
si no
begin
si existe en Agenda[l] un {Bk->,r} tal que
en Agenda[r] esté {A->B1..Bk,i}
begin
Reconstruye({B->,r},l)
end
end
mientras k>0
end
k=k-1
l=r
end
16 Algoritmo de reconstrucción
ausencia de ambigüedades.
del
árbol
sintáctico
en
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Ejecutamos el algoritmo recursivo de la figura 16, comenzando por Reconstruye({S>,0},N) si es que en Agenda[N] encontramos alguna derivación completa del Axioma S: {S>,0}
VI.4.2.3 La cadena vacía
La Cadena vacía requiere un tratamiento especial: será un símbolo no terminal que no
necesita de una compleción para el avance de su puntero.
Cada vez que añadamos un elemento a Agenda[i] {A->....,j} conde el puntero queda a la
izquierda de una cadena vacía, añadiremos también el elemento {A->....,j}
Al reconstruir la estructura de la oración, en el bucle que recorre los símbolos de la parte
derecha de una regla B->B1 ..Bm debemos no sólo distinguir terminales y no terminales sino
también la cadena vacía: al llegar al símbolo nulo del elemento {A->....,j} reduciremos sólo k
y proseguiremos.
VI.4.2.4 Un ejemplo completo
Usando la misma gramático no ambigua del ejemplo con CYK (figura 11) y la misma
oración, obtenemos:
En un primer paso (el de inicialización), el algoritmo predice cuáles son los símbolos
terminales (en este caso son categorías léxico-sintácticas) que pueden encabezar todas las
oraciones posibles: Det, Núcleo. Como nuestra frase (traducida a terminales) es:
"Núcleo Verbo Determinante Núcleo Preposición Determinante Núcleo Preposición
Determinante Núcleo"
Agenda[0]
Oración=SintagmaNominal SintagmaVerbal 0
SintagmaNominal=SintagmaNominal SintagmaPreposic 0
SintagmaNominal=SintagmaNominal1 0
SintagmaNominal1=Determinante Núcleo 0
SintagmaNominal1=Núcleo 0
Determinante=determinante 0
Núcleo=núcleo 0
Como comienza por Núcleo, se avanzarán el puntero del elemento{Núcleo=núcleo 0}:
Agenda[1]
Núcleo=núcleo  0
SintagmaNominal1=Núcleo  0
SintagmaNominal=SintagmaNominal1  0
Oración=SintagmaNominal SintagmaVerbal 0
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
SintagmaNominal=SintagmaNominal SintagmaPreposic 0
SintagmaVerbal=Verbo SintagmaNominal 1
SintagmaPreposic=Preposición SintagmaNominal1 1
Verbo=verbo 1
Preposición=preposición 1
Agenda[2]
Verbo=verbo  1
SintagmaVerbal=Verbo SintagmaNominal 1
SintagmaNominal=SintagmaNominal SintagmaPreposic 2
SintagmaNominal=SintagmaNominal1 2
SintagmaNominal1=Determinante Núcleo 2
SintagmaNominal1=Núcleo 2
Determinante=determinante 2
Núcleo=núcleo 2
Agenda[3]
Determinante=determinante  2
SintagmaNominal1=Determinante Núcleo 2
Núcleo=núcleo 3
Agenda[4]
Núcleo=núcleo  3
SintagmaNominal1=Determinante Núcleo  2
SintagmaNominal=SintagmaNominal1  2
SintagmaVerbal=Verbo SintagmaNominal  1
SintagmaNominal=SintagmaNominal SintagmaPreposic 2
Oración=SintagmaNominal SintagmaVerbal  0
SintagmaPreposic=Preposición SintagmaNominal1 4
Preposición=preposición 4
Agenda[5]
Preposición=preposición  4
SintagmaPreposic=Preposición SintagmaNominal1 4
SintagmaNominal1=Determinante Núcleo 5
SintagmaNominal1=Núcleo 5
Determinante=determinante 5
Núcleo=núcleo 5
Agenda[6]
Determinante=determinante  5
SintagmaNominal1=Determinante Núcleo 5
Núcleo=núcleo 6
Agenda[7]
Núcleo=núcleo  6
SintagmaNominal1=Determinante Núcleo  5
50
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
SintagmaPreposic=Preposición SintagmaNominal1  4
SintagmaNominal=SintagmaNominal SintagmaPreposic  2
SintagmaVerbal=Verbo SintagmaNominal  1
SintagmaNominal=SintagmaNominal SintagmaPreposic 2
Oración=SintagmaNominal SintagmaVerbal  0
SintagmaPreposic=Preposición SintagmaNominal1 7
Preposición=preposición 7
Agenda[8]
Preposición=preposición  7
SintagmaPreposic=Preposición SintagmaNominal1 7
SintagmaNominal1=Determinante Núcleo 8
SintagmaNominal1=Núcleo 8
Determinante=determinante 8
Núcleo=núcleo 8
Agenda[9]
Determinante=determinante  8
SintagmaNominal1=Determinante Núcleo 8
Núcleo=núcleo 9
Agenda[10]
Núcleo=núcleo  9
SintagmaNominal1=Determinante Núcleo  8
SintagmaPreposic=Preposición SintagmaNominal1  7
SintagmaNominal=SintagmaNominal SintagmaPreposic  2
SintagmaVerbal=Verbo SintagmaNominal  1
SintagmaNominal=SintagmaNominal SintagmaPreposic 2
Oración=SintagmaNominal SintagmaVerbal  0
SintagmaPreposic=Preposición SintagmaNominal1 10
Preposición=preposición 10
Como en Agenda[10] encontramos: {Oración=SintagmaNominal SintagmaVerbal ,0}
podemos reconstruir42:
Llamada a RECONSTRUYE(Agenda[10]
,{Oración=SintagmaNominal SintagmaVerbal ,0})
SintagmaVerbal procede de: el elemento de Agenda[10]:
{SintagmaVerbal=Verbo SintagmaNominal ,1}
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaVerbal=Verbo SintagmaNominal ,1})
SintagmaNominal procede de: el elemento de Agenda[10]:
{SintagmaNominal=SintagmaNominal SintagmaPreposic ,2}
Obsérvese que,como en el algoritmo LR(1),las reglas
aplicadas se obtienen primero la de la parte derecha y luego la
de la izquierda.La primera palabra alcanzada será la última y
viceversa.
42
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaNominal=SintagmaNominal SintagmaPreposic
,2})
SintagmaPreposic procede de: el elemento de Agenda[10]:
{SintagmaPreposic=Preposición SintagmaNominal1 ,7}
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaPreposic=Preposición SintagmaNominal1 ,7})
SintagmaNominal1 procede de: el elemento de Agenda[10]:
{SintagmaNominal1=Determinante Núcleo ,8}
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaNominal1=Determinante Núcleo ,8})
Núcleo procede de:el elemento de Agenda[10]:
{Núcleo=núcleo ,9}
Llamada a RECONSTRUYE(Agenda[10]
,{Núcleo=núcleo ,9})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[9]:
{Determinante=determinante ,8}
Llamada a RECONSTRUYE(Agenda[9]
,{Determinante=determinante ,8})
determinante es Terminal
Preposición procede de: el elemento de Agenda[8]:
{Preposición=preposición ,7}
Llamada a RECONSTRUYE(Agenda[8]
,{Preposición=preposición ,7})
preposición es Terminal
SintagmaNominal procede de: el elemento de Agenda[7]:
{SintagmaNominal=SintagmaNominal SintagmaPreposic ,2}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaNominal=SintagmaNominal SintagmaPreposic
,2})
SintagmaPreposic procede de: el elemento de Agenda[7]:
{SintagmaPreposic=Preposición SintagmaNominal1 ,4}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaPreposic=Preposición SintagmaNominal1 ,4})
SintagmaNominal1 procede de: el elemento de Agenda[7]:
{SintagmaNominal1=Determinante Núcleo ,5}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaNominal1=Determinante Núcleo ,5})
Núcleo procede de: el elemento de Agenda[7]:
{Núcleo=núcleo ,6}
Llamada a RECONSTRUYE(Agenda[7]
,{Núcleo=núcleo ,6})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[6]:
{Determinante=determinante ,5}
Llamada a RECONSTRUYE(Agenda[6]
,{Determinante=determinante ,5})
determinante es Terminal
50
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Preposición procede de: el elemento de Agenda[5]:
{Preposición=preposición ,4}
Llamada a RECONSTRUYE(Agenda[5]
,{Preposición=preposición ,4})
preposición es Terminal
SintagmaNominal procede de: el elemento de Agenda[4]:
{SintagmaNominal=SintagmaNominal1 ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal=SintagmaNominal1 ,2})
SintagmaNominal1 procede de: el elemento de Agenda[4]:
{SintagmaNominal1=Determinante Núcleo ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal1=Determinante Núcleo ,2})
Núcleo procede de: el elemento de Agenda[4]:
{Núcleo=núcleo ,3}
Llamada a RECONSTRUYE(Agenda[4]
,{Núcleo=núcleo ,3})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[3]:
{Determinante=determinante ,2}
Llamada a RECONSTRUYE(Agenda[3]
,{Determinante=determinante ,2})
determinante es Terminal
Verbo procede de: el elemento de Agenda[2]:
{Verbo=verbo ,1}
Llamada a RECONSTRUYE(Agenda[2]
,{Verbo=verbo ,1})
verbo es Terminal
SintagmaNominal procede de: el elemento de Agenda[1]:
{SintagmaNominal=SintagmaNominal1 ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal=SintagmaNominal1 ,0})
SintagmaNominal1 procede de: el elemento de Agenda[1]:
{SintagmaNominal1=Núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal1=Núcleo ,0})
Núcleo procede de: el elemento de Agenda[1]:
{Núcleo=núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{Núcleo=núcleo ,0})
núcleo es Terminal
Al añadir la regla de la complementación "oracional", la Agenda aumenta aunque
mínimamente:
Agenda[0]
Oración=SintagmaNominal SintagmaVerbal 0

CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
Oración=Oración SintagmaPreposic 0


Agenda[4]


Oración=Oración  SintagmaPreposic 0


Agenda[7]


Oración=Oración SintagmaPreposic  0

Oración=Oración  SintagmaPreposic 0


Agenda[10]


Oración=Oración SintagmaPreposic  0

Oración=Oración  SintagmaPreposic 0


Como en esta última Agenda[10] encontramos 2 elementos del tipo {Oración=,0},
habrá al menos una ambigüedad que afecta a los niveles más altos del análisis. Además de lo ya
visto, podremos reconstruir:
Llamada a RECONSTRUYE(Agenda[10]
,{Oración=Oración SintagmaPreposic ,0})
SintagmaPreposic procede de: el elemento de Agenda[10]:
{SintagmaPreposic=Preposición SintagmaNominal1 ,7}
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaPreposic=Preposición SintagmaNominal1 ,7})
SintagmaNominal1 procede de: el elemento de Agenda[10]:
{SintagmaNominal1=Determinante Núcleo ,8}
Llamada a RECONSTRUYE(Agenda[10]
,{SintagmaNominal1=Determinante Núcleo ,8})
Núcleo procede de: el elemento de Agenda[10]:
{Núcleo=núcleo ,9}
Llamada a RECONSTRUYE(Agenda[10]
,{Núcleo=núcleo ,9})
núcleo es Terminal
Determinante procede de:el elemento de Agenda[9]:
{Determinante=determinante ,8}
Llamada a RECONSTRUYE(Agenda[9]
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
,{Determinante=determinante ,8})
determinante es Terminal
Preposición procede de: el elemento de Agenda[8]:
{Preposición=preposición ,7}
Llamada a RECONSTRUYE(Agenda[8]
,{Preposición=preposición ,7})
preposición es Terminal
Oración procede de: el elemento de Agenda[7]:
{Oración=Oración SintagmaPreposic ,0}
Llamada a RECONSTRUYE(Agenda[7]
,{Oración=Oración SintagmaPreposic ,0})
SintagmaPreposic procede de: el elemento de Agenda[7]:
{SintagmaPreposic=Preposición SintagmaNominal1 ,4}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaPreposic=Preposición SintagmaNominal1 ,4})
SintagmaNominal1 procede de: el elemento de Agenda[7]:
{SintagmaNominal1=Determinante Núcleo ,5}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaNominal1=Determinante Núcleo ,5})
Núcleo procede de: el elemento de Agenda[7]:
{Núcleo=núcleo ,6}
Llamada a RECONSTRUYE(Agenda[7]
,{Núcleo=núcleo ,6})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[6]:
{Determinante=determinante ,5}
Llamada a RECONSTRUYE(Agenda[6]
,{Determinante=determinante ,5})
determinante es Terminal
Preposición procede de: el elemento de Agenda[5]:
{Preposición=preposición ,4}
Llamada a RECONSTRUYE(Agenda[5]
,{Preposición=preposición ,4})
preposición es Terminal
Oración procede de: el elemento de Agenda[4]:
{Oración=SintagmaNominal SintagmaVerbal ,0}
Llamada a RECONSTRUYE(Agenda[4]
,{Oración=SintagmaNominal SintagmaVerbal ,0})
SintagmaVerbal procede de: el elemento de Agenda[4]:
{SintagmaVerbal=Verbo SintagmaNominal ,1}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaVerbal=Verbo SintagmaNominal ,1})
SintagmaNominal procede de: el elemento de Agenda[4]:
{SintagmaNominal=SintagmaNominal1 ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal=SintagmaNominal1 ,2})
SintagmaNominal1 procede de: el elemento de Agenda[4]:
50
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
{SintagmaNominal1=Determinante Núcleo ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal1=Determinante Núcleo ,2})
Núcleo procede de: el elemento de Agenda[4]:
{Núcleo=núcleo ,3}
Llamada a RECONSTRUYE(Agenda[4]
,{Núcleo=núcleo ,3})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[3]:
{Determinante=determinante ,2}
Llamada a RECONSTRUYE(Agenda[3]
,{Determinante=determinante ,2})
determinante es Terminal
Verbo procede de: el elemento de Agenda[2]:
{Verbo=verbo ,1}
Llamada a RECONSTRUYE(Agenda[2]
,{Verbo=verbo ,1})
verbo es Terminal
SintagmaNominal procede de: el elemento de Agenda[1]:
{SintagmaNominal=SintagmaNominal1 ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal=SintagmaNominal1 ,0})
SintagmaNominal1 procede de: el elemento de Agenda[1]:
{SintagmaNominal1=Núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal1=Núcleo ,0})
Núcleo procede de: el elemento de Agenda[1]:
{Núcleo=núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{Núcleo=núcleo ,0})
núcleo es Terminal
Llegados a este punto, encontramos una nueva ambigüedad: la suboración que se
extiende de yo a telescopio puede ser analizada como:
Oración procede dell elemento de Agenda[7]:
{Oración=SintagmaNominal SintagmaVerbal ,0}
o como:
Oración procede del elemento de Agenda[7]:
{Oración=Oración SintagmaPreposic ,0}
Como la segunda opción ya la hemos explorado, reconstruiremos la primera, previa
copia de las reglas que les serán comunes a ambos análisis ( en este caso, las que van desde la
primera Oración=Oración SontagmaPreposic hasta la segunda Oración=Oración
SintagmaPreposic, la primera inclusive, la segunda no):
Llamada a RECONSTRUYE(Agenda[7]
,{Oración=SintagmaNominal SintagmaVerbal ,0})
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
SintagmaVerbal procede de: el elemento de Agenda[7]:
{SintagmaVerbal=Verbo SintagmaNominal ,1}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaVerbal=Verbo SintagmaNominal ,1})
SintagmaNominal procede de: el elemento de Agenda[7]:
{SintagmaNominal=SintagmaNominal SintagmaPreposic ,2}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaNominal=SintagmaNominal SintagmaPreposic
SintagmaPreposic procede de: el elemento de Agenda[7]:
{SintagmaPreposic=Preposición SintagmaNominal1 ,4}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaPreposic=Preposición SintagmaNominal1 ,4})
SintagmaNominal1 procede de: el elemento de Agenda[7]:
{SintagmaNominal1=Determinante Núcleo ,5}
Llamada a RECONSTRUYE(Agenda[7]
,{SintagmaNominal1=Determinante Núcleo ,5})
Núcleo procede de: el elemento de Agenda[7]:
{Núcleo=núcleo ,6}
Llamada a RECONSTRUYE(Agenda[7]
,{Núcleo=núcleo ,6})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[6]:
{Determinante=determinante ,5}
Llamada a RECONSTRUYE(Agenda[6]
,{Determinante=determinante ,5})
determinante es Terminal
Preposición procede de: el elemento de Agenda[5]:
{Preposición=preposición ,4}
Llamada a RECONSTRUYE(Agenda[5]
,{Preposición=preposición ,4})
preposición es Terminal
SintagmaNominal procede de: el elemento de Agenda[4]:
{SintagmaNominal=SintagmaNominal1 ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal=SintagmaNominal1 ,2})
SintagmaNominal1 procede de: el elemento de Agenda[4]:
{SintagmaNominal1=Determinante Núcleo ,2}
Llamada a RECONSTRUYE(Agenda[4]
,{SintagmaNominal1=Determinante Núcleo ,2})
Núcleo procede de: el elemento de Agenda[4]:
{Núcleo=núcleo ,3}
Llamada a RECONSTRUYE(Agenda[4]
,{Núcleo=núcleo ,3})
núcleo es Terminal
Determinante procede de: el elemento de Agenda[3]:
{Determinante=determinante ,2}
Llamada a RECONSTRUYE(Agenda[3]
50
,2})
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
,{Determinante=determinante ,2})
determinante es Terminal
Verbo procede de: el elemento de Agenda[2]:
{Verbo=verbo ,1}
Llamada a RECONSTRUYE(Agenda[2]
,{Verbo=verbo ,1})
verbo es Terminal
SintagmaNominal procede de: el elemento de Agenda[1]:
{SintagmaNominal=SintagmaNominal1 ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal=SintagmaNominal1 ,0})
SintagmaNominal1 procede de: el elemento de Agenda[1]:
{SintagmaNominal1=Núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{SintagmaNominal1=Núcleo ,0})
Núcleo procede de: el elemento de Agenda[1]:
{Núcleo=núcleo ,0}
Llamada a RECONSTRUYE(Agenda[1]
,{Núcleo=núcleo ,0})
núcleo es Terminal
Los árboles sintácticos coinciden con los ya mostrados aunque con diferente numeración
(el primero de antes es ahora el tercero, el segundo coincide...).
Si la ambigüedad fuera totalmente interna (no afecte ni a la primera ni a la última
palabra de la frase), la reconstrucción del segundo árbol será parcial y, desde ese momento, todo
lo que copiemos en el primer árbol, lo deberemos de copiar en el segundo.
VI.4.2.5 Complejidad del algoritmo
En un caso general de gramática ambigua, el número de operaciones será proporcional
al cubo de N, la longitud de la cadena de entrada. Esto se justifica porque:
-El número de estados en cada Agenda[i] es proporcional a N (es el máximo valor que
puede tomar el registro de nivel), al número de reglas y la longitud media de las mismas.
-la predicción y el avance suponen recorrer una Agenda[] y con cada elemento realizar
una serie de operaciones:su complejidad conjunta será proporcional a N.
-la compleción, por su parte, supone recorrer una Agenda[] y para cada elemento de ella
podríamos tener que recorrer otra Agenda[], con lo cual la complejidad sería proporcional al
cuadrado de N.
-como el número de Agendas[] es N+1, el total dará la proporcionalidad al cubo que ya
habíamos adelantado.
CAPITULO VI : ANÁLISIS SINTÁCTICO ... DE CONTEXTO LIBRE
50
De todos modos estas cifras son engañosas, y lo que hace más lento el algoritmo es la
abundancia de ambigüedades: con una gramática finamente sintonizada la velocidad crece
enormemente.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
CAPITULO VII
EL ENTORNO PARA EL DESARROLLO DE
GRAMÁTICAS
VII.1 Presentación
La necesidad de escribir y probar una gramática se fundió con la de estudiar y tomar
contacto con los algoritmos de análisis sintáctico en la realización de un programa para alcanzar
ambos objetivos.
Entre las facilidades que no deberían faltar destacaremos:
-edición de los ficheros que constituyan la gramática. Sería recomendable edición
orientada al formato si este es mínimamente complejo
-compilación y verificación de los mismos, con mensajes claros acerca de las
incorrecciones detectadas
-transformación de la gramática a formatos de interés: YACC, Wild Card Parsing
(Willemse[90].
-sencillez máxima para la variación del algoritmo sintáctico, a ser posible sin
recompilación
-análisis automático de córpora textuales en modo normal y paso a paso
-visualización de los árboles sintácticos obtenidos
-generación de ficheros de resultados:
-árboles escritos en ASCII
-análisis mediante paréntesis etiquetados
-posibles causas de la incorrección de las frases
agramaticales
-estadísticas sobre la utilización de símbolos y reglas durante el análisis
El programa se desarrolló en entorno PC por razones de accesibilidad, para facilitar su
uso por parte de lingüistas, ingenieros... sin necesidad de un hardware especial.
Tras comenzar la programación con TURBOC (siguiendo la tradición existente ya en el
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
Departamento de Ingeniería Electrónica), al poder disponer de su "lógico heredero" el compilador BORLANDC++, cambiamos inmediatamente (sin más que un pequeño aunque imprevisto
cambio en la semántica de los pre- y post-incrementos). Aunque no hemos explotado sus más
avanzadas posibilidades (la programación orientada a objetos o para MS-WINDOWS) hemos
optado por compilarlo siempre en modo C++ (a pesar de su lentitud).
Por sencillez y portabilidad no hemos usado la pantalla en modo gráfico: los árboles
sintácticos serán presentados en modo texto. Para una presentación más espectacular, que no
útil, existen programas que convierten la estructura de paréntesis etiquetados en árboles en
formato LATEX.
VII.2 Estructura de la gramática
Dado que el presente trabajo tiene un carácter introductorio en el campo de la sintaxis, y
dado el estado cambiante del mismo, la organización y formato de los ficheros gramaticales será
sencilla sin caer en la simpleza. Aunque el saber acumulado tras el empleo del entorno no se
perderá, una estructura avanzada o a la moda podría llegar a suponer una gran cantidad de
tiempo invertido en balde.
Siguiendo un enfoque formal generativista, como en general haremos, decidimos aislar
al máximo los componentes léxico y sintáctico; entre el diccionario y la gramática de contexto
libre existirá un interfaz de traducción con objeto de que los cambios en una afecten
mínimamente al otro y viceversa. Un cambio en las categorías presentes en cualquiera de los
dos, debido quizás a la sustitución del diccionario por una base de datos morfológica o
semántica o por unos de esos robustos módulos de categorización léxica presentes en los
sintetizadores texto-habla, debería suponer tan sólo unos pequeños cambios en el interfaz.
Como ejemplos de ventajas de este planteamiento tenemos:
-la conocida dificultad de los categorizadores para distinguir los nombres sustantivos de
los nombres adjetivos si están basados en morfología y carecen de información sintácticosemántica, no tiene porqué hacernos cambiar la gramática, simplemente habrá que añadir una
línea al interfaz indicando que los diferentes tipos de sustantivos y adjetivos sintácticos se
corresponden con la única categoría léxica nombre que produce el categorizador
-la sustantivización de elementos tales como adjetivos adverbios de lugar y tiempo...
puede ser elegantemente modelada como una traducción de sus categorías léxicas en varias
categorías sintácticas, una de las cuales sería la de sustantivo
-las características especiales de la preposición POR (propia de la pasiva) o de la
preposición SEGÚN (que puede carecer de término sustantivo y aparecer sola) no las impide
funcionar en la mayoría de los casos como preposición ordinaria. Gracias al fichero interfaz, en
esos casos, se puede ocultar su carácter especial traduciéndolo en el fichero interfaz en vez de en
la gramática
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
Palabra_1 NumCategoría_i
FICHERO
.CMT
Palabra_1
NumCategoría_j


Palabra_2 NumCategoría_l

 FICHERO .GRA
Palabra_N
NumCategoría_M
FICHERO .REG
FICHERO .DIC
Ilustr. 17 Organización de la gramática.
VII.3 Formato del diccionario
Las palabras, una por línea del fichero, deberán estar ordenadas: si no, la verificación de
la gramática detectará el error e impedirá su uso). Un programa auxiliar ordena diccionarios con
el formato correcto y de tamaño arbitrario. Si no excediese los 64K, es más rápido pasar el
diccionario previamente a través del filtro SORT del sistema operativo, que utiliza la memoria
para realizar la ordenación. Como no sigue la numeración ASCII y ordena por igual las
mayúsculas y las minúsculas...deberemos ejecutar el programa auxiliar, pero al estar
parcialmente ordenado tardará poco en acabar.
La extensión del diccionario será .DIC, con igual nombre que el resto de los ficheros
gramaticales.
Un fichero adicional .AUX traducirá a categorías léxicas los NumCategorías del
diccionario. Se emplean números por ahorrar espacio y ganar velocidad; con un editor de dos
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
ventanas se puede cómodamente rellenar el diccionario sin equivocarse al categorizar la
palabras.
Formato
de
los
Queda
recuadro 19.
! 54
" 30
"desescuchadas" 3
"politicismo" 2
, 17
- 17
: 55
; 17
? 47
a 51
a 6
abandonado 18
abandonar 10
abandono 2
VII.4
ficheros .REG
recogido
en
el
CategoríaSintáctica_1=CategLéx_i CategLéca_j...


CategoríaSintáctica_h=...


CategoríaSintáctica_N=CategoríaLexica_k...
19 formato .REG
VII.5 Formato del fichero .GRA
Para la definición de la gramática de contexto libre usaremos un lenguaje sencillo cuya
gramática en notación simple es la del recuadro Error! Bookmark not defined.:
V=verb
N=sust
Adj=adj
Adv1=adv advIns advNeg
Adv2=adv advIns advAutónomo
Pron=pron
Prep=prep prepHace
PrepDest=prepDest
PrepOrig=prepOrig prepDe
Det=art demostr posesivo
20 Muestra del fichero interfaz.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
SímboloNoTerminal=Expresión_1
Expresión_1=Expresión_1 | Expresión_2
Expresión_1=Expresión_2
Expresión_2=Expresión_2 Término
Expresión_2=Término
Término=Término2
Término=( Término )
Término2=Símbolo
Término2=Símbolo *
Término2=Símbolo +
Término2=Símbolo Término2
Términos=Término2
Símbolo=CadenaVacía
Símbolo=SímboloNoTerminal
Símbolo=SímboloTerminal
21 Sintaxis del lenguaje de definición de la gramática.
CadenaVacía será un carácter configurable desde el menú de opciones y que
representará al símbolo sin realización fonética. No todos los algoritmos de análisis sintáctico
toleran gramáticas con cadena vacía, a si que su aceptación o no al usar la gramática dependerá
del algoritmo en ese momento activo.
El carácter espacio en blanco ' ' será considerado separador de símbolos, al igual que la
barra disyuntiva '|', el signo de igualdad '=' y el retorno de carro. No lo serán los caracteres
predefinidos '+', '*', '(', ')', que deberán llevar intercalado antes del siguiente símbolo un
separador.
Para utilizar un carácter predefinido dentro de un símbolo cualquiera deberá ir precedido
de la barra de división '/'.
No se debe usar tabuladores ni barra hacia atrás '\', aunque lo permita el verificador. Este
distingue entre mayúsculas y minúsculas.
El símbolo a la derecha del igual en la primera regla definida por nosotros será tomado
como axioma generador del lenguaje. Si deseamos más de un axioma, la primer regla será del
tipo:
Axioma=Axioma_1 | Axioma_2...
Finalmente, queremos reseñar que la notación descrita es una versión simplificada de la
BNF extendida, no permitiéndose en la nuestra la anidación de paréntesis, estructuras del tipo
(Términos)* o (Términos)+ ni la inclusión de barras disyuntivas en el interior de los paréntesis.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
La razón hay que buscarla en la "regularización"43 y desestructuración que puede suponer para
la gramática de contexto libre su uso. Por ejemplo:
-lo incluido dentro de un paréntesis, si tiene una estructura compleja o recursiva, bien
merece la definición de un nuevo símbolo terminal
-si un paréntesis pudiera contener diversas alternativas, es que esas diversas alternativas
realizan una misma función sintáctica que convendría especifica
-la posibilidad de equivocarse al escribir una regla complicada es grande
Por todo esto no optamos por la potencia de la BNF al completo.
ORACION=(MOInicial) ORACION1
ORACION1=Proposición (MOFinal)|OCompuesta (MOFinal)
ORACION=(SP Coma) OImperativa|OImperativa Coma SP
ORACION=Interrogación Proposición1 Interrogación
ORACION=Exclamación Proposición1 Exclamación
ORACION=Exclamación OExclamat Exclamación
OExclamat=OInterrog
ORACION=Interrogación OInterrog Interrogación
VII.6 Semántica de la notación empleada
Cada carácter especial posee una significación predefinida y hasta cierto punto
inalterable.
La barra disyuntiva '|' indica que las cadenas de símbolos que separa son distintos modos
de desarrollar el símbolo no terminal que encabeza la regla.
El signo igual '=' permite marcar al símbolo a su izquierda como no terminal.
Las cadena de símbolos entre paréntesis serán opcionales, es decir, el símbolo no
terminal de la regla podrá desarrollarse tanto con su concurso como sin él.
La adición de un signo más '+' al final de un símbolo equivale a decir que la regla acepta
la autoconcatenación de dicho símbolo un número de veces indeterminado pero no nulo.
La adición del ´*´ equivale a añadir un '+' y encerrarlo todo, el símbolo y el más, entre
paréntesis (pudiéndose así repetir el símbolo de 0 hasta INFINITO).
Si se elige la opción de simplificación de árboles, todos los símbolo acabados en un
número44 o un subrayado '_', no aparecerán en la pantalla ni en los ficheros generados.
43La
notación se hace compacta y formateada como la ideal
para un lenguaje regular.
44Ver
apartado dedicado a la sintaxis X-barra.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
VII.7 Extensión de las reglas
Los algoritmos que emplearemos usan reglas en notación simple o en una derivada de
ella (la Forma Normal de Chomsky típica del CYK). El esfuerzo de compactar varias reglas en
una de formato regular será por lo general estéril, ya que debemos diseñar un algoritmo que
descompacte lo que hemos compactado.
El método directo de compilación de reglas complejas tiene dos pasos:
-desdoblar las disyunciones, creando una nueva regla temporal por cada alternativa. De
la regla:
Install Equation Editor and doubleclick here to view equation.
saldrán:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
En el árbol sintáctico
SímboloNoTerminal=Expresión1,
Expresión1=Expresión2.
de la regla equivale
Expresión1=Expresión1
a
eliminar las reglas
|
Expresión2
y
-aplicar la siguiente semántica definida semiformalmente en la ilustración 23:
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
Partiendo del árbol sintáctico de la regla,e inicializando
a 0 la variable InParéntesis y a 1 MaxRegla:
-si existe una regla Término2=Símbolo,
AñadirSímbolo();
-si Símbolo=SímboloTerminal,
desde la regla nº1 hasta la MaxRegla,
si InParéntesis==1,añadir SímboloTerminal a
las reglas pares;
si no,añadirlo a todas;
-si Símbolo=SímboloNoTerminal,
desde la regla nº1 hasta la MaxRegla,
si InParéntesis==1,añadir SímboloNoTerminal a
las reglas pares;
si no,añadirlo a todas;
-si Términos=Símbolo Término2,
AñadirTérmino2();
-si Términos=Término2
AñadirTérmino2();
-si Símbolo=CadenaVacía,
desde la regla nº1 hasta la MaxRegla,
si InParéntesis==1,añadir CadenaVacía a las
reglas pares;
si no,añadirlo a todas;
-si Término=( Términos ),
copiar las reglas desde la primera hasta MaxRegla
en las posiciones MaxRegla+1 hasta 2*MaxRegla;
MaxRegla=2*MaxRegla;
AñadirTérminos();
23 Algoritmo de extensión de reglas.
Un ejemplo de extensión de regla sería:
Install Equation Editor and doubleclick here to view equation.
que daría lugar a 2 elevado a 6 reglas (donde 6 es el número de paréntesis):
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.

82
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
Install Equation Editor and doubleclick here to view equation.
Evidentemente la compilación de reglas es, de este modo, ineficiente. El número de
reglas así obtenido crece de un modo polinomial y no exponencial.
VII.8 Dependencias intra-gramaticales
La escritura de la gramática en forma de varios fichero relacionados genera un conjunto
de inter-dependencias que conviene no lleguen a ser molestas.
Las categorías léxica de cada una de las palabras del diccionario ha de ser traducida a
categoría(s) sintáctica(s) en el fichero-interfaz45. El "ingeniero lingüístico" que trabaje en el
desarrollo de una gramática estará más seguro si el lexicón contiene al menos una palabra
perteneciente a las categorías léxicas posibles; y que no se emplee ninguna con una categorización gramaticalmente no factible. Además el diccionario deberá tener un formato correcto y
estar correctamente ordenado.
Las categorías sintácticas del fichero .REG han de corresponderse biunívocamente con
los símbolos terminales del .GRA, y éstos deben ser alcanzables a partir del axioma.También
los símbolos no terminales deben ser todos ramificaciones del primero de ellos, el axioma.
No deben existir reglas anulables sin cadena vacía (son indicio de error de escritura). El
carácter opcional de todos los elementos del siguiente sintagma nominal no debe ser así
expresado:
SN=(Det) (Sust) (Adj) (SintagmaPreposicional)
sino que deberíamos escribir:
SN=(Det) (Sust) (Adj) (SintagmaPreposicional) #
suponiendo que la cadena vacía sea aceptada por el algoritmo de análisis y usemos el
carácter '#' como meta-CadenaVacía.
Los ciclos infinitamente ambiguos como (SN=SN1=SN2=SN) deben ser detectados y
rechazados(cualquier SN admitiría un número no finito de análisis igualmente correctos, algo
evidentemente absurdo e indeseable.
Una opción nos debería permitir verificar que no existen recursiones a derechas o a
izquierdas (algo que algunos algoritmos no permiten), así como decidir el modo en el que son
compilados los símbolos afectados por un signo más (cada símbolo de este tipo da lugar a dos
reglas que podrían ser A*=A* A y A*=A, o bien A*=A A* y A*=A).
45Es
recomendable que,cuando la traducción no es ambigua,
los nombres coincidan salvo ligero cambio de mayúsculas por
minúsculas(Ej:Artículo=artículo) siguiendo una convención que
faciliten la escritura.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
¡Error!Nombre de archivo no especificado.
Ilustr. 18 Esquema global del entorno.
82
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
VII.9 MENÚ PRINCIPAL
Al comenzar la ejecución del programa, y tras la cabecera gráfica y la explicativa ,
entramos en el menú principal.
Para escoger una opción debemos colocar la barra de selección sobre ella empleando las
flechas hacia arriba y hacia abajo, la tecla Inicio para ir a la primera opción y a la tecla Fin para
ir a la última. Pulsando entonces Retorno de Carro (o la tecla Intro), se ejecutará la opción
elegida. Pulsando la letra resaltada en mayúsculas dentro de la opción (en mayúsculas o en
minúsculas, dará igual), obtendremos el mismo efecto.
Cuando comenzamos una sesión de trabajo con la intención de empezar, continuar o
depurar el diseño de una gramática, dos serán las opciones más habituales (y que por ello serán
las primeras):
-"Cargar en la memoria una gramática para su utilización"
-"Editar fichero específico o no"
Opciones auxiliares independientes de las anteriores serán:
-Ejecutar comando o fichero del Dos
-Finalizar la sesión de trabajo
Dependientes de que se cargue en memoria una gramática tendremos:
-Analizar fichero de Texto
-Mostrar las Reglas de la gramática
-Mostrar los Símbolos de la gramática
-Listar las palabras de una categoría léxica
VII.9.1 Cargar
Lo normal será comenzar a trabajar deseando probar nuestra gramática con nuevos
textos, y basándonos en los resultados, modificarla o no.
Las características de nuestro modelo por ficheros hacen necesario que se verifique la
corrección de la gramática, y la transforme.
Para una mayor claridad, legibilidad y facilidad de estudio, no escribiremos directamente
el fichero .GRA, sino que en un fichero .CMT (de CoMenTario) escribiremos nuestras reglas en
formato .GRA acompañadas de una líneas de comentarios, notas importantes y ejemplos. Cada
una de esas líneas irá precedida de un par de caracteres de identificación que indicarán que para
crear automáticamente el fichero .GRA, esas líneas deberán ser eliminadas (aunque dicha
información quedará convenientemente guardada, como ya veremos en otra opción).
La lectura del recientemente creado .GRA o del .REG, el .AUX o el .DIC puede dar
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
lugar a detección de incorrecciones, sólo la primera de las cuales se mostrará en pantalla, ya que
a tal efecto se generarán: HayError.GRA, HayError.REG, HayError.AUX y HayError.DIC.
VII.9.1.1 Avisos y errores
Si al revisar el diccionario se encuentra que alguna de las Categorías Léxicas definidas
en .AUX no es asignada a ninguna palabra del diccionario, se incorporará al fichero
AUSENTES.DIC del siguiente modo:
%s=NumeroDeLaCategoríaLéxicaAusente
Si el desajuste se debe que el fichero .AUX que traduce las categorías léxicas a números
(los empleados en el diccionario), nos hemos olvidado de alguna, definida previamente en el
.REG, en AUSENTES.AUX nos encontraremos con:
CategoríaLéxicaInexistente=%u
Cuando una categoría terminal, presente en la gramática, carece de traducción a
categorías léxicas en .REG, AUSENTES.REG contendrá una línea como la que sigue:
CategoríaSintácticaNoTraducida=%s...
Como el fichero .GRA se obtiene automáticamente y sin errores del .CMT, y éste no
depende jerárquicamente de ningún otro, no será posible crear AUSENTES.GRA46.
En HayErrores.DIC podemos también encontrar:
-"Error de Formato en línea %s", que puede ser debido a:
-la presencia de una línea vacía
-la no categorización de la palabra
-que palabra y número de categoría no se hallen
separados
por espacios en blanco.
Si no nos encontramos con línea vacía, en AUSENTES.DIC podremos ver:
PalabraLeída=%u
-"Número de categoría desconocido", o sea, mayor que el máximo contabilizado en
.AUX; en AUSENTES.AUX encontraremos:
46Como
los símbolos no terminales serán únicamente aquellos
que se encuentren a la derecha del igual ,si usamos pero no
"definimos por medio de reglas" uno de ellos , se considerará
que son símbolos terminales y en AUSENTES.REG se nos indicará
la imposibilidad de traducirlos a categorías léxicas.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
%s=NumeroCategoríaSobrante
-"Palabra excesivamente larga", excede el MAXIMO=.
HayErrores.AUX nos puede señalar errores como:
-"Error de formato en línea %s", causado por una línea en blanco o la falta del signo
igual"
-"Símbolo %s presente en .AUX no es usado en .REG": un simple aviso que hay una
categoría léxica que no está siendo usada
-"línea demasiado larga": no se puede leer entera.MÁXIMO=.
Los errores más típicos comisibles al escribir .REG son:
-"Error de formato en línea %s": ausencia del signo igual, utilización de símbolos no
permitidos como '|',... sin ir precedidos por /
-"Categoría léxica con nombre demasiado largo"
-"demasiadas categorías léxicas.MÁXIMO=".
-"línea demasiado larga.MÁXIMO=".
Para su aparición en HayErrores.GRA están reservados:
-"Símbolo demasiado largo %s.MÁXIMO=".
-"Falta el '='en línea %s"
-"Utilización de '|' en símbolo %s de la línea %s"
-"Inmediatamente tras un ')' no pueden aparecer '*' o '+'"
-"Demasiadas reglas.MÁXIMO=".
-"Demasiados símbolos.MÁXIMO=".
-"Demasiadas reglas tras transformación.MÁXIMO=".
-"Demasiados símbolos tras transformación.MÁXIMO=".
-"Presencia inaceptable de la CadenaVacía"
Finalmente, HayErrores.CMT puede contener:
-"Gramática sin reglas"
-"Línea demasiado larga.MÁXIMO=".
En AVISOS.GRA:
-"regla %s no comentada"
-"regla %s carente de NOTAS"
-"regla %s sin ejemplos
-"gramática no comentada": ninguna regla tiene comentario alguno
-"gramática carente de NOTAS": ninguna regla tiene una NOTA
-"gramática sin ejemplos": no se halla presente ningún ejemplo clarificador para ninguna
regla
En AVISOS.GRA:
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
-"la categoría léxica, indirectamente presente a través de %s+, ha sido creada"
-"Debido a la recursión se ha creado las reglas..."
-"Se ha usado recursión a izquierdas"
-"Se ha usado la cadena vacía"
En AVISOS.AUX:
-"No se usa la categoría léxica %s"
En AVISOS.DIC:
-"Falta alguna palabra perteneciente a la categoría %u"
VII.9.1.2 Estadísticas
En Estadist.GRA:
-Relación entre el número de reglas desarrolladas y el número de símbolos:índice de la
compacidad de la forma de escribir la gramática.
-Número de reglas en las que aparece cada símbolo.
-longitud media de las reglas en número de símbolos.
En Estadist.REG
-número medio de categorías léxicas asignadas a una categoría sintáctica.
-relación entre número de categorías léxicas y número de categorías sintácticas
terminales.
En Estadist.DIC:
-longitud media de las palabras del diccionario
-número de las mismas
-tiempo de lectura medio para la última palabra
-número de palabras que comienzan por cada uno de los caracteres ASCII permitidos.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
¡Error!Nombre de archivo no especificado.
Ilustr. 19 Proceso de precompilación.
82
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
VII.9.2 Editar
La simplicidad de los formatos requeridos y la inexistencia de símbolos predefinidos
largos (tampoco hay muchos caracteres reservados), nos desaconsejó la creación de un editor
orientado por sintaxis. Como el entorno no es un fin en sí mismo, ni una mera práctica
académica, las utilidades que posee el editor Norton nos parecieron suficientes para la tarea de
editar los ficheros gramaticales sin mayores dificultades. Destacamos de entre las características
de este editor:
-su reducido tamaño, que permite ejecutarlo desde el entorno sin necesidad de
"overlays"...
-no incluye en el texto caracteres especiales que "falsearían" lo escrito
-permite limitar la longitud de línea, con salto automático de la misma
-si el fichero que editar es grande (léase, el diccionario) y no cabe entero en la memoria,
lo carga parcialmente
-las funciones habituales de manejo de bloques, búsquedas, salto a comienzo o fin de
fichero (consultar la ayuda pulsando la tecla F1)
-es posible editar dos ficheros al mismo tiempo, transferir información de uno a otro,
comparar ambas ventanas...
Este último detalle es muy importante, ya que los ficheros de AUSENCIAS.* deberán
editarse en paralelo con sus respectivos ficheros gramaticales; la exigencias de la jerarquía de
ficheros hace también aconsejable la edición simultaneada del .GRA y el .REG, de este y el
.AUX y,finalmente, del .AUX y el .DIC.
VII.9.2.1 Submenú de edición
De los específicos significados de las extensiones de los distintos fichero generados por
el entorno, o de los necesarios para su funcionamiento, surge el submenú de edición.
Para escribir una gramática sólo necesitaremos usar la opción "Edición de ficheros
gramaticales", que al ser escogida dará paso a otro menú con las distintas gramáticas contenidas
en el directorio actual47. En el caso de no haber ninguna nos lo indicará un mensaje en pantalla:
deberemos editar la nueva gramática desde la opción de "Editar fichero no específico").
Si elegimos una de las gramáticas, lo que aparecerá en la pantalla será un menú, también
de barras, con las extensiones de los ficheros de la gramática seleccionada. Esta será la última
elección, que nos conducirá al editor Norton con el fichero que hemos ido especificando paso a
paso.
La edición de ficheros de textos nos permitirá crear los córpora que comprueben la
bondad de nuestros desarrollos lingüísticos. Al escogerla aparecerá el menú de barras con los
47Realmente
llega con la existencia en dicho directorio de
un fichero .CMT,no son necesarios .GRA,.REG...
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
ficheros .TXT presentes en el directorio.
Dentro de la opción relativa a ficheros de resultados se nos pedirá que escojamos un
texto de los disponibles en el disco, para luego solicitarnos qué tipo de resultado nos interesa, si
árboles sintácticos dibujados mediante caracteres ASCII, paréntesis etiquetados, estadísticas de
utilización de reglas y símbolos o tiempos de "parsing", errores hallados en las oraciones
agramaticales...
Los ficheros AUSENTES.* y HayError.* tienen cada uno su opción de menú y su menú
intermedio, siguiéndose una mecánica de selección similar a los casos anteriores, solamente en
la opción final, "Edición de ficheros no específicos", se entrará directamente al editor, que es
quien nos pide, sin más menús, el nombre del fichero que editar.
Tras la edición de un diccionario, se verificará automáticamente la corrección de su
ordenamiento.
Recordar que las opciones de un menú que contengan una letra resaltada en mayúsculas
podrán ser escogidas sin más que presionarla en el teclado, estén o no bloqueadas las
mayúsculas, y que pulsando ESC volveremos al menú precedente, incluido el principal.
Los ficheros que realizan listados del disco duro, darán u mensaje de error "No se ha
encontrado ningún fichero" si su busca ha sido infructuosa.
VII.9.3 Finalizar
Para salirse del programa deberemos escoger esta opción (o pulsar ESC, 'f' o 'F') y
responder 's' o 'S' a la pregunta de si deseados realmente salir del programa.
VII.9.4 Opciones
Un menú nos permite variar :
-los colores
-las características del análisis o la compilación de reglas
-guardar la situación actual
de los parámetros variables en el fichero de configuración por defecto
VII.9.5 Mostrar reglas
Aparecerán las reglas extendidas de veinte en veinte. Moviendo la barra resaltada
recorreremos las reglas; para ver de qué regla no extendida proceden, pulsaremos F2.Las notas,
comentarios y ejemplos presentes en nuestro fichero .CMT se podrán ver por medio de F3.
Todas las convenciones de manejo de menús de barras son válidas aquí: tecla de Inicio,
tecla de Fin...
ESC nos hará pasar a ver las siguientes reglas, y con Pausa volveremos al menú
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
principal.
La velocidad, lenta, con la que se escriben en la pantalla las informaciones pedidas, se
debe achacar a la necesidad de leer los ficheros numerados (un número sin extensión) donde se
guarda la regla original y su información asociada. Las reglas creadas por el programa para
gestionar los símbolos acabados en '+' poseen comentarios también creados por programa.
ORACION=(SP Coma) OImperativa|OImperativa Coma SP
<< Las oraciones Imperativas admiten llevar "por favor"...
<< antepuesto o pospuesto.
ºº LA SEGUNDA ALTERNATIVA CARECE DE PARÉNTESIS PARA EVITAR
LA DUPLICACIÓN DE REGLAS
çç por favor , dame lo mío.
çç dame lo mío , por favor.
ºº
Ilustr. 20 Comentarios asociados a una regla.
VII.9.6 Mostrar símbolos
Permite ver, de veinte en veinte, los símbolos definidos por el usuario al escribir la
gramática y las categorías léxicas del diccionario. Seleccionando uno de ellos y pulsando F2,
para el símbolo seleccionado, una ventana nos mostrará de qué símbolos no terminales puede
ser nodo-hijo en un árbol sintáctico (eso quiere decir que, siguiendo al notación por niveles, si
Det aparece en una regla SN1=Det..., no será SN1 quien aparezca, sino SN, símbolo no
terminal visible). También se nos dirá cuáles son las categorías léxicas en las que admite debajo
(si editamos las categorías léxicas, la única información disponible será esta última invertida: en
qué categorías sintácticas terminales se puede convertir la seleccionada).
Las convenciones son las de siempre; pulsando ESC saltamos a los siguientes veinte
símbolos o categorías léxicas (éstas aparecen cuando se acaban los anteriores); la tecla Pausa
nos devuelve al menú principal.
VII.9.6 Analizar texto
Un menú de barras nos muestra los ficheros .TXT que tenemos en el directorio actual,
sin verificar si se trata de ficheros de auténticos ficheros de texto (las longitudes de línea
menores que el máximo permitido, no existencia de símbolos especiales como el tabulador...).
Frase a frase (una frase será cualquier secuencia de caracteres ASCII acabada con un
punto) se buscarán la palabras en el diccionario categorizado. Las que no se encuentren, serán
acumuladas en NuevaPal.DIC para que al acabar de analizar el texto se llame al editor Norton y
categorizar NuevaPal.DIC; al salir del editor se mezclará el fichero editado con el diccionario y
se ordenará; nos preguntará si deseamos o no repetir el análisis.
CAPITULO VII : EL ENTORNO PARA EL DESARROLLO DE GRAMÁTICAS
82
Si una línea del texto excede la longitud máxima, se nos indicará y finalizará el análisis.
CAPITULO VIII: LINGUISTICA APLICADA
101
CAPITULO VIII
LINGÜÍSTICA APLICADA
VIII.1 Los conceptos de oración y enunciado
Si se suele coincidir en la definición de enunciado como una cadena perteneciente al
habla situada entre dos pausas mayores (generalmente puntos), la definición del término oración
ha suscitado abiertas controversias.
Desde un enfoque semántico, la oración estaría constituida por uno o más enunciados
con sentido completo. La formalización del concepto de sentido completo es posible en
determinados entornos no completamente naturales (accesos a bases de datos,
fundamentalmente, donde cad enunciado debe corresponderse con una petición a la misma,
siendo inaceptables las peticiones cuya lógica no se ajuste al esquema conceptual de la base). En
ámbitos más generales y no tan restringidos, la formalización parece hallarse lejos y, en todo
caso, precisaría de la intermediación de la sintaxis.
Ante estas dificultades preferiremos el enfoque sintáctico-formal: para el generativismo,
la oración es el axioma del que se parte para analizar la lengua. Esta axiomatización no
presupone definición alguna: con una adecuada escritura de las reglas la oración puede variar
sustancialmente de contenido, desde la más complicada estructura subordinada al más simple
sintagma pasando por limitarse a las proposiciones dotadas de verbo en forma personal.
El enunciado será bien fragmentario bien oracional, y la oración podrá ser de posición
relativa (proposición inserta en otra de orden superior) o absoluta.
VIII.2 Sintaxis del enunciado fragmentario
Rapidez, emotividad o economía expresiva hacen que en diálogos, obras literarias,
publicidad... se pausen como enunciados algunos sintagmas que desde un punto de vista
formalista carecen de autonomía sintáctica. La entonación y el contexto lingüístico o
extralingüístico nos permiten asignar una significación a breves respuestas, exclamaciones,
títulos...
Con nuestro entorno sólo podremos estudiar su sintaxis, teniendo que pasar por alto
cómo la variación de la entonación convierte "¡Bien!" en una expresión irónica o de reproche
con significado opuesto al habitual.
CAPITULO VIII: LINGUISTICA APLICADA
101
Aunque desde posiciones generativistas (Hernanz[87], página 56) se ha criticado el
analizar como oraciones los simples fragmentos carentes de verbo en forma personal en torno al
cual ordenarse, o sin independencia sintáctica, el pragmatismo que nos guía hace aconsejable
tratar a la vez las oraciones formales y las "informales", aunque sin mezclarlas. Sin el estudio
sintáctico de los fragmentos no podremos abordar sistemas basados en diálogo de una mediana
complejidad, ni la comprensión de textos con pocas restricciones.
En esta recta final cambiaremos el nombre de nuestro axioma gramatical, que ya no será
la oración sino el enunciado, y distinguiremos entre oraciones formales y fragmentos (éstos no
serán susceptibles de aparecer en posiciones no absolutas: subordinaciones no entrecomilladas
por ser literales...).
Así nuestra gramática será más robusta frente a texto irrestringido, aunque sin que
pretendamos hacerla plenamente robusta, que acepte todo enunciado como correcto y le asigne
una estructura conocida o improvisada. En un entorno de reconocimiento de voz eso exigiría
una tasa de reconocimiento de palabras cercana a la infalibilidad, y eliminaría totalmente la
posibilidad de guiado por sintaxis48.
VIII.2.1 Fragmentos y elipsis verbal
Conviene diferenciar a los fragmentos de las proposiciones con elipsis verbal
recuperable a partir del contexto lingüístico oracional. En:
"el ganador recorrió 220 kilómetros y el segundo clasificado, la mitad"
no podemos considerar que "el segundo clasificado la mitad" constituya un fragmento
coordinado copulativamente con una proposición, ya que la pausa que antecede a "la mitad" nos
señala la ausencia del verbo, que, debido al paralelismo entre los sintagmas nominales,
fácilmente recuperamos de la primera proposición.
No obstante, la ausencia de antecedente en el interior del presente enunciado, si que dará
lugar a fragmento:
"el segundo clasificado, la mitad"
En la subordinada adverbial causal:
"porque él no quiso"
encontramos un verbo en forma personal articulando toda una proposición, pero ésta indica la
48En
sistemas de lectura o comprensión de texto escrito y
fiable,el análisis de fragmentos muy alejados del concepto
clásico de sintagma,una heurística de emergencia debería
intentar
,partiendo
de
los
constituyentes
mayores
o
estadísticamente
más
probables,usar
programación
dinámica...para construirles un árbol.Ver Russi[].
CAPITULO VIII: LINGUISTICA APLICADA
101
causa de un efecto no comprensible simplemente por el contenido del enunciado. Un "parser"
superior, de carácter semántico pragmático, debería enlazar nuestra subordinada con su
correspondiente principal, completando así el sentido del texto.
VIII.2.2 Clasificación pragmática de los fragmentos
-respuestas: ver el capítulo dedicado a la oración interrogativa.
-exclamativas: consultar "Las oraciones exclamativas"
-imperativas informales:
"Fuera"; "casa"
-descripciones rítmicas:
"el patio, con su fuente y sus rosales.La cocina, con su puchero y su
gazpacho.Todo era típico"
-títulos de todo tipo de obras, objetos...
"El sí de las niñas"
-refranes populares:
"perro labrador, poco mordedor"
-dichos y tópicos:
"un hombre, un voto"
-anuncios:
"consulta a las cinco"
-fragmentación retórica:
"nunca profeséis de gracioso.porque siempre hay ganas de reír.Aunque no falten
motivos para ello"
-fragmentos fáticos:
"hola"; "¿que tal?"
VIII.2.3 Clasificación sintáctica de los fragmentos
-proposición de infinitivo:
"No tener tanto que trabajar"
"a correr al patio hasta que os canséis"
-proposición de participio:
"marido cansado de esperar a su esposa"
"prohibido el paso"
CAPITULO VIII: LINGUISTICA APLICADA
101
-proposición de gerundio:
"jugador lanzando un golpe de castigo"
-otras subordinadas substantivas:
"que te digan a los sesenta que ya eres viejo..."
"¡que ya no sirves!"
-otras subordinadas adjetivas:
"que te quiere bien" (a modo de comentario)
-otras subordinadas adverbiales:
"a pesar de lo dicho"
-sintagmas nominales varios:
"papá y el periódico"
"peligro de muerte"
"silencio"
"última edición"
-sintagmas adjetivales varios:
"verde por fuera,rojo por dentro"
-sintagmas adverbiales varios:
"Bien"
"nunca más"
-sintagmas preposicionales:
"¡a mi edad!"
"¿para qué derramar más sangre?"
VIII.3 La oración formal
Para que un enunciado sea formalmente una oración completa, deberá tener un verbo en
forma personal (por elevación X con barra, un SintagmaVerbal).La misma caracterización de
ese verbo como personal implica la existencia explícita o implícita, de un sujeto concordante
con él. Aunque existen verbos que no admiten sujeto (meteorológicos como llover o
impersonales reflejos como en se come bien allí), la mayoría de las oraciones que en castellano
carecen de sujeto poseen desinencias verbales que nos permiten recuperarlo.
No consideraremos la flexión como constituyente inmediato de la proposición debido a
que ello supone una transformación en la estructura sintáctica por extracción de un elemento del
sintagma verbal para situarlo entre éste y el sujeto. Como nuestras reglas de contexto libre
impiden estos fenómenos, la flexión debe ser un rasgo que el sintagma verbal transmite al nivel
proposición, que será quien verifique la concordancia con el sujeto49.
49 En los casos de elisión de sujeto deberá descender al sujeto elidido y caracterizarlo para otras posibles concordancias o
determinaciones.
CAPITULO VIII: LINGUISTICA APLICADA
101
Pero la relación entre sujeto y verbo no se limita a la concordancia: pueden existir más
sintagmas nominales que concuerden con el verbo y no sean sujetos, incluso puede haber un
solo sintagma nominal que concuerde con el verbo y lo anteceda sin tener por ello que ser su
sujeto:
Propos[SN[las] SV[cogieron] SNSujeto[entre Juan y Pedro]]
La función de sujeto no se somete fácilmente a las reglas sintagmáticas y precisaría de
una determinación posterior si no queremos limitarnos a oraciones de estructura:
Proposición(SintagmaSujeto) SintagmaVerbal
o la muy ambigua:
ProposiciónSintagmaVerbal Sujeto
En el capítulo de líneas futuras veremos como otros módulos adicionales de "parsing"
podrían contemplar este caso y el de los constituyentes discontinuos:
Proposición[ SV[ transcurre diabólicamente] Sujeto[ el tiempo] SV[ SPrep[ con
lentitud propia de otras épocas ]]]
VIII.3.1 El sintagma nominal
En torno al sustantivo (al menos principalmente) se ordena uno de los dos constituyentes
inmediatos de la oración: el sintagma nominal50. Siguiendo la sintaxis X con barra, será la
proyección máxima del nombre, y en distintos niveles de ascensión se le irán añadiendo
determinantes, modificadores, la coordinación y la subordinación...
Aunque su papel temático o funcional varía (sujeto, objeto...), característica sintácticas
comunes a todos ellos los hacen perfectamente integrables en un análisis mediante ordenamientos. Como muestra compárese la estructura de "una fuerte tormenta de nieve" en:
"una fuerte tormenta de nieve azotó la comarca" (sujeto)
"los meteorólogos anuncian una fuerte tormenta de nieve (objeto directo)
"todos temen el inicio de una fuerte tormenta de nieve" (término de un sintagma
50En
Brucart[], al sintagma nominal y verbal se añade la
flexión,donde residirá la información de concordancia entre
ambos y que ,según los autores ,podrían ser considerado núcleo
de la oración.Como la flexión es parte del verbo,inseparable
sintácticamente de él,nuestro formalismo no podría interpretar
correctamente una gramática así.Los rasgos heredados por
elevación cumplirán un papel similar.
CAPITULO VIII: LINGUISTICA APLICADA
101
preposicional complemento de nombre)
"el invierno comenzó con una fuerte tormenta de nieve" (término de un sintagma
preposicional complemento del verbo)
VIII.3.1.2 Constituyentes del Sintagma Nominal
Tres tipos de elementos, con sintaxis muy particulares, pueden constituirse en núcleos
del sintagma nominal: el nombre común, le nombre propio y el pronombre personal.
VIII.3.1.2.1 El nombre propio
Destacar sólo, dado que le dedicaremos a continuación un capítulo entero, que el
analizador léxico debería tener un mecanismo de inducción ya que no se basan en morfología ni
son numerables, siendo desaconsejable la lista cerrada salvo en dominios semánticos muy
restringidos.
VIII.3.1.2.2 Los pronombres personales
Conservan restos del sistema de casos del latín: como sujeto sólo pueden usarse yo, tu...;
como complemento directo: la, lo...; como términos de una preposición no todos son factibles;
al ralizar funciones de complemnto directo equivalen a sintagmas con la preposición la...
Léxicamente presentan la particularidad de poder unirse al verbo y saltarse, al igual que
las contracciones, los espacios en blanco como delimitadores categoriales. Como los
pronombres no pueden ir tras el verbo de otro modo, la gramática será distinta si incluimos el
pronombre en el verbo o si los separamos.
Conviene categorizarlos por casos (sujeto, complemento directo...) y diferenciarlos para
limitar las posibilidades de coordinación y repetición (no es posible coordinar dos
complementos directos pronominales; raros son los casos de doble complemnto directo; no son
posibles las combinaciones le lo...).
En los casos de elipsis siempre es posible sustituir el verbo ausente por un pronombre
personal que concuerde con el verbo y realice las funciones del sujeto ausente.
VIII.3.1.1.3 El nombre común
Da lugar a la forma más general de sintagma nominal. Admite determinantes, sintagmas
adjetivos o preposicionales previos, aposiciones nominales adjuntas o explicativas, sintagmas
adjetivos y preposicionales posteriores, proposiciones de relativo con o sin preposición...
Las ambigüedades que pueden surgir de las reglas que contemplen tanta diversidad
suelen tener su origen en la rección prepositiva: si admitimos que cada nombre pueda tener
como complementos a sintagmas preposicionales sin restricción alguna, la presencia en el
sintagma nominal de varios complementos de ese tipo da lugar a, al menos, dos análisis: el
CAPITULO VIII: LINGUISTICA APLICADA
101
segundo sintagma como complemento del primero o como complemnto del núcleo. Si
admitimos complementos preposiconales dentro de sintagmas adjetivos o aque se encuentren
más allá de una proposición de relativo, las ambigüedades crecerán.
Para recortar su número, cada núcleo debe llevar codificada la información de
quépreposiciones pueden regirlo. El número de sílabas o palabras de los sintagmas intermedios
influye en la gramaticalidad de complementos lejanos, pero supone otra sencilla modificación
en el "parsing".
Los sitagmas preposicionales previos al núcleo son problemáticos. Su escaso uso
(generalmente por razones estéticas o de métrica) y la extrañeza que producen al oyente, nos
recomiendan su esclusión del patron más genérico del sintagma nominal.
VIII.3.1.3 ¿Nominalización o elipsis?
La ausencia de núcleo nominal en muchos sintagmas que pro su estructura deberían
tenerlo abunda en castellano. A lo largo de la historia de la lingüística se han sostenido diversas
hipótesis para su explicación:
-la nominalización del determinante: en sintagmas como un desesperado, este de verde,
mis viejos... la función de núcleo recaería sobre el artículo, el demostrativo, la familia léxixa de
ningún...
-la nominalización de los complementos: o sea, del adjetivo, el sintagma preposicional o
la proposición de relativo en: el que te pegó, los blancos, los de Pamplona...
-la elipsis del núcleo nominal, que deberíamos extraer del contexto lingüístico o de
situación. Hablando de fútbol, los de negro serían los señores de negro, los árbitros; en los de
Pamplona se sobreentiende el núcleo habitantes...
Si admitimos una de las opciones pronominalizadoras, podríamos incluir en el lexico la
categorización de los elementos nominalizables como sustantivos; así madrileño sería nombre
común gentilicio además de adjetivo relativo a Madrid. La naturaleza sintáctica del problema no
lo hace aconsejable: los elementos pronominalizados sólo funcionan como tales en estructuras
de sintagma nominal muy determinadas. Deberíamos crear reglas que traten dichas estructuras y
utilizar categorías intermedias AdjetivoPronominalizado, ArtículoNominalizado... para dejar
claro en nuestros árboles cuál es nuestro modo de abordar el problema.
Si optamos por la elipsis (algo muy común en el generativismo) usaremos una categoría
vacía NucleoNominal sub lambda que deje constancia de la ausencia del sustantivo51 y
permitirá a otros módulos semántico-pragmáticos su relleno.
Aunque el tema no admite un tratamiento homogéneo52 (el artículo nuetro sí parece
51 Si el método de parsing no admitiera la cadena vacía siempre podríamos marcar la regla como especial y posprocesar los árboles que
la contengan.
52
En Hallebeek[91] se puede hallar una pequeña gramática para este tipo de sintagmas.
CAPITULO VIII: LINGUISTICA APLICADA
101
realizar labores de núcleo al ir acompañado de adjetivos, sintagmas preposicionales o
proposiciones de relativo), las diferencias entre los diversos planteamientos expuestos son
mínimas al escribir las reglas sintácticas (no funcionales).
VIII.3.2 El sintagma verbal
La importancia del verbo queda ya reflejada en su etimología ( verbum, la palabra).
Aunque mucha gente asocia palabra con sustantivo, es el verbo la más característica de las
palabras de una oración gramaticalmente completa.
Ya hemos visto como el verbo concuerda con un elemento externo a su propio sintagma,
el sujeto. Sin embargo, la verdadera riqueza sintáctica asociada a él se da en las relaciones que
mantiene con sus otros complementos. La intimidad de trato que el verbo tiene con sus objetos
directo e indirecto fue señalada por la gramática tradicional, diferenciando así a estos
complementos de otros calificados como accesorios o circunstanciales.
Estos últimos complementos no subcategorizados gozan de una notable libertad de
movimientos que dificultan considerablemente el análisis automático. Ellos provocan los más
abundantes casos de relaciones lejanas intraoracionales y sintagmas discontinuos, provocando la
multiplicación del número de ambigüedades que ya causaban los sintagmas preposicionales en
el interior de los nominales.Como es necesario establecer marcos de subcategorización para los
verbos, será en líneas futuras donde se siga tratando esta cuestión53.
VIII.4 La coordinación y la yuxtaposición
Definiremos la coordinación y la yuxtaposición como la concatenación de dos sintagmas
u oraciones mediante nexos formales copulativos o yuxtapositivos, para formar un sintagma u
oración de nivel X-barra superior.
Bajo este paraguas aparentemente sencillo se cobijan gran diversidad de fenómenos:
oraciones asemánticas, jerarquías, subordinaciones sin nexo de subordinación tradicional,
cuestiones estilísticas, ambigüedad en el ámbito...
Desde un punto de vista tradicional, no deberíamos analizar la coordinación y la
yuxtaposición conjuntamente: la ausencia de nexo gramatical en la segunda las diferencia
claramente. Sin embargo, las relaciones tan estrechas que mantienen y sus características
formales comunes justificarán nuestra decisión (lo formal o estructural es lo que mejor podemos
tener en cuenta con las gramáticas de contexto libre).
Aunque lo semántico no es objeto principal de nuestro análisis, no se puede dejar de
señalar que el significado desempeña un papel crucial en su funcionamiento. Desde concatenación de oraciones no relacionadas:
Por esta misma razón en la gramática incremental que estamos desarrollando nos hemos centrado en la estructura del sintagma
nominal.
53
CAPITULO VIII: LINGUISTICA APLICADA
101
"Mis tíos se han ido de casa; el caballo parece mayor"
a la yuxtaposición con valor de coordinación:
"Comió peras, manzanas..."
o la subordinación consecutiva por medio de coordinación :
"fue empujado y cayó"
La independencia gramatical, y no la lógica, nos guiará a la hora de analizarlas: un
módulo semántico o pragmático debería estudiar la propiedad o no de las concatenaciones que
la sintaxis ha aceptado. Esa misma independencia las diferenciará de las subordinadas incluso
cuando todas ellas puedan ser funcionalmente equivalentes: las oraciones subordinadas se
integran en sus respectivas principales; las coordinadas y yuxtapuestas, no.
VIII.4.1 Paradigma transformacional
Al enfrentarnos a oraciones como:
"Juan comió y bebió todo lo que quiso"
ó
"Juan es el autor y director de la obra"
podíamos considerar que se han producido una serie de elisiones no particularmente complejas
a partir de:
"Juan comió todo lo que quiso y Juan bebió todo lo que quiso"
"Juan es el autor de la obra y Juan es el director de la obra"
Un enfoque radicalmente transformativo conlleva complicadas manipulaciones,
elisiones...:
"Juan y María fueron al parque"
que realmente, en la estructura profunda sería:
"Juan fue al parque y María fue al parque"
Otro ejemplo sobre la existencia de coordinación y yuxtaposición en niveles no
oracionales lo encontramos en:
"un capón y una perdiz fueron comidos por ellos durante el banquete"
CAPITULO VIII: LINGUISTICA APLICADA
101
VIII.4.1 Aritmética coordinativa
Hasta ahora la mayoría de los ejemplos vistos seguían las reglas habituales de la
aritmética:
singular+singular == plural
singular + plural == plural
plural + singular == plural
plural + plural == plural
Existen, sin embargo, casos donde la suma de números no se produce:
"la directora y autora de la obra fue llamada al orden"
aunque:
"directora y autora de la obra fueron llamadas al orden"
También:
"me gustó la chica flaca y joven"
pero:
"la flaca y la joven no me gustan"
Parece que la determinación desempeña un papel importante para no tener que admitir
ambigüedad en el número a la hora de analizar los sintagmas nominales:
SN[ Det[ la ] Núcleo[ directora y autora ]]
y
SN[ SN1[ directora ] y SN1[ autora ]]
Así mismo:
SN[ Det[ la ] Núcleo[ chica ] SAdj[ flaca y joven]]
y
SN[ SN1[ la flaca ] y SN1[ la joven ]]
VIII.4.2 Coordinación y elipsis
La fuerte relación entre elipsis y coordinación da lugar a abundantes ambigüedades:
CAPITULO VIII: LINGUISTICA APLICADA
101
"estos tres y aquellos cuatro maleantes..."
podría ser estructurado como:
SN[ Det[ estos tres y aquellos cuatro ] maleantes ]
o como:
SN[ SN1[ Det[ estos tres ] ] y SN1[ Det[ aquellos cuatro] maleantes ] ]
dependiendo del contexto extralingüístico en que sea enunciada (debe ser un módulo
superior el que desambigüe).
El análisis automatizado basado en ordenamientos encuentra más ambigüedades que las
reales, debido a la falta de información semántica, pragmática o de pausado. En:
"mujeres que van y vienen corriendo"
versus:
"mujeres que van | y vienen corriendo"
o:
"el ganado o los carros cavando las tierras o llevando en la cabeza las sellas del
agua o las cestas con fruta o pescado"
donde formalmente es posible la coordinación inverosímil:
"el ganado o los carros...o las cestas...o pescado"
VIII.4.3 Homogeneidad de coordinación
Habitualmente las estructuras coordinadas son del mismo tipo: sintagmas nominales,
sintagmas adjetivales, verbos... La regla general nos dice que es la función más que la
sintagmática la que rige la coordinación:
"el chico pelirrojo y de mirada tierna..."
"del amigo amable y que te asegura fidelidad eterna,
desconfía"
donde se coordinan diferentes sintagmas en función de modificador del sustantivo.
A pesar de esto el planteamiento sintáctico nos será útil sin más que permitir la
coordinación heterogénea en entornos delimitados, evitando aceptar ejemplos extremos
(gramaticales o no):
"comió lechuga y de pie"
CAPITULO VIII: LINGUISTICA APLICADA
101
VIII.4.4 Tipos de coordinación oracional y su prioridad
Tradicionalmente la coordinación se divide (por sus nexos y significación) en:
-copulativa : "ni corrió ni se cansó"
-disyuntiva : "lo mató o hizo algo parecido"
-adversativa : "es muy trabajador pero no le cunde"
-distributiva : "ora corre,ora anda: nunca está quieto"
-explicativa : "es gallego, o sea, es peligroso"
De ellas sólo la adversativa no admite ni estructuras bimembres ni recursión.
?"se comió el pastel entero, pero no le sentó mal; sin embargo fue al médico"
En las principales gramáticas consultadas no se analiza la combinación en una misma
proposición de distintos tipos de coordinaciones (posiblemente por su no existencia en los
textos literarios de donde suelen sacar los ejemplos):
"hombre y mujeres, niños desamparados, ancianos y ancianas..."
VII.5.La sintaxis X con barra
Es normal que las categorías léxicas se proyecten sintacticamente dando lugar a
sintagmas que lleven su nombre: (sintagmas verbal, nominal, preposicional...) porque, de algún
modo, esas categorías constituyen el nucleo que les da entidad.
Dicho camino de ascensión ha sido directo en la gramática tradicional, sin reflejar
subestructuras intermedias presentes en dichos sintagmas:
-la relación especial entre un sustantivo y sus modificadores o entre un verbo transitivo y
su complemento directo (al que va casi siempre adosado, sólo delante en las interrogativas...).
-la recursividad de un elemento (los varios adjetivos consecutivos que pueden anteceder
o suceder a un sustantivo...) no debe multiplicar la presencia de éste en el árbol, como lo harían
reglas como:
Install Equation Editor and doubleclick here to view equation.
donde se repite SintagmaAdjetival, un símbolo del cual no se puede prescindir en el
árbol
Con el fin de aumentar de un modo sencillo y sistemático las categorías clásicas,
Jackendoff propuso que cada una de ellas adoptara una estructura de niveles numerados que
toman su nombre del núcleo del sintagma y que se relacionan entre si de acuerdo con el patrón:
Install Equation Editor and doubleclick here to view equation.
CAPITULO VIII: LINGUISTICA APLICADA
101
En nuestro entorno no seguiremos de un modo purista la notación X con barra empleada
por los lingüistas y conservaremos la noción de Sintagma nominal sin considerarla simplemente
como la proyección máxima del nombre y así evitar que tengamos que definir un número
máximo o mínimo de proyección (cuestión siempre muy polémica). Como los niveles
intermedios, caracterizados por acabar en un número, no aparecerán en los árboles para evitar
que éstos sean excesivamente densos a la vista y aunque se usen en la estructuración de la
gramática, debemos cuidar especialmente la existencia de extremos dibujables, que no acaben
en número o comiencen por subrayado.
Como ejemplo de su uso encontramos en M. L. Gutiérrez[78], convenientemente
transformado a reglas sintácticas:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
CAPITULO IX
EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA :
EL NOMBRE PROPIO
Para explicar la metodología recomendada para construir una gramática que cubra
determinados aspectos del castellano natural, estudiaremos incrementalmente la del nombre
propio, generando un pequeño conjunto de reglas para los sintagmas nominales que tengan al
nombre propio como núcleo54.
Los manuales generales de gramática del español apenas tratan las estructuras de dichos
sintagmas (especialmente si se apoyan en textos literarios para dar ejemplos). Se justifica su
carácter de categoría léxico-sintáctico-semántica diferenciada apoyándose en que:
-se escriben con mayúsculas y muchas veces este hecho nos permite reconocerlos
-suelen carecer de morfemas (salvo casos de composición como en: calle de
"Rompeteelalma", donde se nominaliza y se hace propia una expresión...)
-no se hallan en los diccionarios sino en las enciclopedias porque carecen de semántica
connotativa; Luisa, Barcelona... no son definibles sino que simplemente denotan seres
humanos, entidades geográficas... concretas.
-la presencia de determinantes y complementos no es frecuentemente admisible o
supone una importante variación o matiz de significado; comunalización+vulgarismo ("el
Pepe"), temporalización ("la Marbella que tú conociste"), metonimia ("un Velázquez")...55
Normalmente el nombre propio se presentará solo, carente de complementos o
No entraremos en detalles sobre otro tipo de sintagmas
(aunque también sean nominales);los ejemplos analizados usarán
la gramática general que estamos desarrollando en su estado
actual;se
ha
procurado
evitar
interferencias
con
otros
problemas del castellano usando oraciones sencillas o sólo el
análisis principal.
54
La comunalización puede ser tal que haya duplicación:
"Mecenas",nombre
propio
latino;"mecenas",nombre
común
que
designa a un benefactor de artistas.
55
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
determinantes y rama única del nodo de un sintagma nominal (sujeto, complemento directo..).
Una sencilla regla:
Install Equation Editor and doubleclick here to view equation.
daría cuenta de ejemplos típicos del acceso a una base de datos o un libro de gramática:
"dame todos los vuelos del aeropuerto de Madrid hasta Barcelona"
"eran la flor de su pueblo de Vizcaya"
"Juan parece tonto pero no lo es"
ORACION
Proposición
SVAtrib
VerbCop
Atrib
SN
DET Nucl
SPdirecc
Det N PrepOrig
SNOrig
DET Nucl
Det N
eran la flor de
SPdeProp
PrepDe NombreProp
su pueblo de
Vizcaya
ORACION
OCompuesta
OCoordinada
OAdversativa
Proposición
SN
NexoAdversat
SVAtrib
NomProp VerbCop Atrib
Proposición
SVAtrib
AdvNegativo PronPreVerb VerbCop
SAdj
Adj
Juan parece tonto pero
no
lo
es
Como admite la coordinación con otros nombres propios o incluso otro tipo de
sintagmas nominales, no aparecerá directamente bajo SintagmaNominal, sino bajo
SintagmaNominal_1, su derivado para coordinación:
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
"No aparecieron ni Juan ni el alcalde de la ciudad"
"Juan y Pepe fueron los autores"
Install Equation Editor and doubleclick here to view equation.
En ese mismo nivel situaremos las aposiciones explicativas (las que van entre comas):
"Juan, que no parece fiable, será el jefe"
"Juan, rebelde hasta el extremo, no lo admitió"
ORACION
Proposición
SN
SN1
V
NexoMonoCop
NombrePropio
Juan
SAdv
SN1
Adv
NombrePropio
y
Pepe
corren más
ORACION
Proposición
SN
SN
SVAtrib
Coma
Aposición
NombrePropio
Coma VerbCop Atrib
ORelativo
SN
ORelativoSin
PronRelativo
DET Nucl
ORACION
Det N
Proposición
SVAtrib
AdvNegativo PronPreVerb VerbCop Atrib
SAdj
Adj
Juan
,
que
no
me
parece fiable , será el jefe
Para tratar los nombres compuestos de entidades geográficas (ciudades, ríos, macizos...)
que admiten o exigen artículos determinados, sintagmas preposicionales en "de"... (los Estados
Unidos deAmérica, La Coruña...), podemos optar por generar reglas sintácticas con una
categorización más fina:
SintNominal_1=NomGeoSinArt (SintPrepDE)
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
SintNominal_1=ArtDet NomGeoConArt (SintPrepDE)
SintNominal_1=NomPersona
o dejar que sea el analizador lexicográfico quien agrupe varias palabras bajo una misma
categoría (por ejemplo: NombrePropConArt o NombrePropSinArt).
Dado que nuestro entorno es léxicamente biunívoco (una palabra implica una categoría),
pero para evitar una engorrosa escritura, simularemos el comportamiento de un analizador
lexicográfico más complejo uniendo en una las diferentes palabras de un nombre compuesto:
"Felipe_VI_de_Borbón_y_Grecia"
"Maximiliano_Victor_Caramés_Bartolomé"
"Santiago_Cortizas_González-Criado"
y crearemos cinco categorías léxico-sintácticas:
-NomPersonaSimple: "Juan"...
-NomPersonaComp: "Juan_Carlos_I"...
-NomGeoSimple: "Madrid"...
-NomGeoCompConArt: "Cerro_de_los_Angeles"...
-NomGeoCompSinArt: "Villafranca_del_Bierzo"...
Agregando la posibilidad de que los nombres de persona lleven títulos delante ("santo",
"san", "don"...):
SintNominal_1=(Título) NomPersonaSimple
SintNominal_1=NomGeoSimple
SintNominal_1=(Título) NomPersComp
SintNominal_1=NomGeoCompSinArt
SintNominal_1=ArtDet NomGeoCompConArt
cubriremos los ejemplos:
"(Don) Juan"
"Barcelona"
"(Don) Juan_Carlos"
"Santiago_de_Compostela"
"el Cerro_De_Los_Angeles"
Las categorías léxicas multisintácticas (las familias de "otro", "demás", "mucho"...) se
diferencian de los adjetivos ordinarios en que no necesitan determinante:
"no hay otros Pirineos"
"busca otro Shakespeare porque éste no me vale"
"mucho Pérez veo por aquí suelto"
"conozco algún Javier que está loco por ti"
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
"Pepe es mucho Pepe"
ORACION
OCompuesta
OCoordinada
OAdversativa
Proposición
Proposición
NexoAdversat
V
SVAtrib
VerbCop
SN
AdjAntAlgún
Atrib
SPde
NomPersona
AdvNegativo
NomPersSimple
PrepDe AdvAutónomo
conozco
es
de
algún
aquí
Javier
pero
no
Si admitimos estas construcciones (que deberíamos marcar como a-normales dado su
fuerte grado de comunalización del nombre propio, las referencias contextuales que
conllevan...), escribiremos una regla para cada caso:
NomPropSinArt=NomPersonaComp|NomPersonaSimple|NomGeoSimple
|NomGeoCompSinArt
SintNominal_1=AdjALGUN (Titulo) NomPropSinArt (Compl)
SintNominal_1=(DET) AdjMUCHO (Titulo) NomPropSinArt (Compl)
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
SintNominal_1=(DET) AdjOTRO (Titulo) NomPropSinArt (Compl)


Para "mismo" y "tal" (mucho más comunes en combinación con nombres propios) es
fácil encontrar oraciones "normales":
"un tal Jiménez te llamó anoche"
"el mismísimo Balboa era quien conducía el timón"
Necesitan ir precedidos de determinante y permiten complementos pospuestos al
nombre propio:
"todos los tales Monteros eran gente de mal vivir"
"este mismo Pepe comía además de beber"
"tu misma Barcelona tampoco me parece una gran ciudad"
provisionalmente creamos las reglas:
SintNominal_1=DET AdjTAL NomPropSinArt (Compl)
SintNominal_1=DET AdjMismo NomPropSinArt (Compl)
SintNominal_1=NomProp AdjMismo
Los adjetivos que pueden anteceder al nombre (los llamaremos previos y no explicativos
por nuestro enfoque sintáctico no funcional) son poco compatibles con las categorías que
acabamos de mencionar en ausencia de más complementos:
* "una tal hermosa Isabel"
* "la misma hermosa Isabel"
La razón es el choque entre el carácter especificativo de unos y el explicativo de los
otros:
Para contemplar:
"tu bella Barcelona..."
"la desierta y desoladora Siberia..."
"este tan centrado Cerro_de_los_Angeles..."
"la siempre glacialmente provocadora Sharon"
"la misma magistral Michelle_Pfeiffer que asombró en..."
construiremos:
SintNominal_1=DET AdjMISMO SAdjPre NomPropSin Compl
SintNominal_1=DET SAdjPre NomPropSin (Compl)
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
Los posibles complementos pospuestos (sin contar con aposiciones adjuntas o
explicativas) son SintagmaAdjetvoPosterior , SintagmaPreposicional, ProposiciónDeRelativo.
"esa Sharon_Stone perfecta e impecable de aquella película no se repetirá"
ORACION
ORACION
Proposición
Proposición
SN
SVAtrib
SAdjPre
SN
DET
Det
NomPropSin
VerbCop
PronPreVerb
V AdvIns
SAdv
Adj
AdjMismo
SAdjPre Adv2NomPropSin
Adv1
Det
Adj
NomPersona
PronRelativo
la
Atrib
NomPersona
DET
SAdj
ORelativo
NomPersComp
SAdjConAdv
ORelativoSin
SAdv
Adj
NomPersComp
Adv2
ORACION
siempre glacialmente provocadora Sharon_Stone
era
demasiado peligrosa
Proposición
PronPreVerb V
ORACION
SN
DET NomPropSin
Prep
SN
DET
SAdjPost
Det NomPersona
Adj
SPde
NexoMonoCop
Adj
Det
NPrepDe
DET
aquella película nos cautiva ya
Det
e
impecable
de
Proposición
DET
SAdjPre
SVAtrib
NomPropSin
AdvNegativo VerbCop
Det SAdv Participio NomGeoSin
SP
Adv2
NomGeoCompSinArt
Prep
Atrib
SN
NomGeoSimple
este tan centrado CerroDeLosAngeles
no
está en
AdvNegativo PronPreVerb
Nucl
la misma
V
Madrid
magistral Michelle_Pfeiffer
que nos asombró en
N
aquella película
ORACION
SN
Nucl
SN
NomPersComp
esa Sharon_Stone perfecta
SP
Proposición
no
se
repetirá
CAPITULO IX : EJEMPLO DE DESARROLLO DE UNA GRAMÁTICA
115
CAPITULO X : INTEGRACIÓN...
122
CAPITULO X
INTEGRACIÓN DE LA SINTAXIS EN LOS SISTEMAS
DE RECONOCIMIENTO DE VOZ
X.1 Parsing de un lattice
Si dispone de una celosía de palabras detectadas en una serie de tramas de voz, de sus
tramas de comienzo y sus trama final, podemos aplicarle los algoritmos sintácticos para
encontrar la secuencia de palabras gramatical más probable.
X.1.1 CYK
Puede usarse el algoritmo de Ney que más adelante veremos, en su versión asíncrona,
con los mismos defecto que se reseñarán (Makino[91], Andry[91]).
X.1.2 Algoritmos predictivos
Con ellos tratamos de encontrar todos los caminos gramaticales presentes en el lattices,
compuestos de palabras compatibles por sus tramas de comienzo y terminación (permitiremos
cierto grado de solapamiento y pausas entre palabras).
-Inicialmente predecimos todas las posibles palabras que puedan ser principio de oración
(caminos activos iniciales: nº1)
-Recorremos las tramas de voz:
-si encontramos que en una de ellas se ha detectado el comienzo de una o más
palabras predichas en alguno de los caminos gramaticales activos y su comienzo es compatible
con el final de la última palabra de dicho camino, avanzamos el análisis hasta el final de la
palabra.
-si para un mismo camino activo hemos encontrado varias palabras con distinta
trama final, creamos una nueva rama activa para cada una menos la primera (que continuará por
la rama ya presente anteriormente)
La eliminación del "lattice" intermedio es teóricamente sencilla aunque en la práctica
CAPITULO X : INTEGRACIÓN...
122
delicada de implementar.
Ahora no disponemos de la probabilidad definitiva de que una palabra comience en una
trama determinada y finalice en otra dada: debemos ir continuamente actualizando la
información probabilístico-fonética hasta que, o bien sea muy reducida y nos sea posible podar
esa rama del análisis (lo que antes llamábamos pila por similitud con el algoritmo LR), o bien
hayamos procesado todas las tramas y tengamos los resultados no parciales sino absolutos.
Para evitar que la anchura de análisis (el número de pilas simultáneamente activas)
desborde la capacidad del sistema se debe establecer otro "pruning" (en Saito[89] se muestra la
dependencia que en la práctica puede tener una buena o mala política de poda y en Kita[91] otra
similar pero trabajando con fonemas en lugar de palabras).
CAPITULO X : INTEGRACIÓN...
122
Estructuras de datos:
struct TipoCélula
{
TipoPila PilaLR;
PROBABILIDADES Q[n];
BOOLEAN Aceptada;
} Célula;
Inicialización:
begin
C=CrearCélula()
C->Q[0]=1.0
for i=0 to N
C->Q[i]=0.0
MeteEnPila(C.PilaLR,EstadoInicial)
C.Aceptada=FALSE
end
Bucle:
while ()
begin
para cada célula C tal que C.Aceptada==FALSO
begin
s=CimaDeLAPila(C.PilaLR)
para cada símbolo terminal 'a' tal que
ACCION(s,a)!=ERROR
begin
si ACCION(s,a)=='dsh s2'
begin
for i=1 to N
Temp[i]=probabilidad del último estado de
Markov para la trama i
if (máximo(Q)>UMBRAL)
begin
C.Q=Temp
MeteEnLaPila(C.PilaLR,s2)
end
else
DestruyeCélula(C)
end
si ACCION(s,a)=="red a->B'
Reduce(C.PilaLR,A,B)
si ACCION(s,a)=='aceptac"
C.Aceptada=CIERTO
end
end
24 Algoritmo LR sin lattice intermedio.
CAPITULO X : INTEGRACIÓN...
122
EstadoAct[1]=0;
NumPilas=1
for TramaActual=0 to TramaFinal
begin
Palabras={palabras que comiencen en esta trama}
si cardinal(Palabras)==0
continue
for j=1 to NumPilas
begin
Expect(j)={categorías esperadas para el
estado actual de la pila j }
Si el cardinal de Expect(j)==0
begin
Realizar las posibles reducciones de
la
pila j
end
si no
begin
for k=1 to Cardinal(Palabras)
begin
si (no ha sido actualizada
temporalmente y UltimaPalabra(j) es compatible con
Palabras[k])
avanzar la pila temporalmente
si (fue actualizada temporalmente
y
UltimaPalabra
es
compatible
con Palabras[k])
crear
una
nueva
pila
dependiente
de la anterior...
end
end
end
end
25 Algoritmo de Tomita para parsing de lattices de palabras
mediante LR(0) extendido.
X.2 Integración síncrona
X.2.1 Integración de CYK con la programación dinámica
En 1987 Ney propone combinar el algoritmo sintáctico CYK con el fonético de
alineamiento temporal para habla continua, realizando simultáneamente el parsing y la
detección de límites de palabra sin necesidad de posproceso.
CAPITULO X : INTEGRACIÓN...
122
Utilizando la versión síncrona de CYK e incorporando a los símbolos guardados la
información de probabilidad y límites que el alineamiento temporal va calculando. Los dos
pasos del algoritmo serán las de la figura 26
for i=1 to I
begin
para cada palabra 'u' del vocabulario
Score[j][i][u]=score acústico en i-2*J...i
for j=i-1 to max(0,i-2*J)
para cada regla U->u
begin
si D[j][i][u]<Chart[j][i][U]
begin
Chart[j][i][U]=
Score[j][i][u]
B[j][i][U]=
NumRegla(U->u)
end
end
end
F[j][i][U]=0
for j=i-1 to 0
recorrer las reglas U->VW
for l=j+1 to i-1
begin
Aux=Chart[j][i][V]+Chart[l][i][W]
si (Aux<Chart[j][i][U])
begin
Chart[j][i][U]=Aux
B[j][i][U]=NumRegla
end
F[j][i][U]=l
end
26 Algoritmo de Ney.
,donde:
-el Chart es ahora tridimensional (no bidimensional con una pila en cada casilla) y
guarda en Chart[j][i][U] la probabilidad de que un símbolo No Terminal 'U' aparezca entre las
tramas 'i' y 'j'
CAPITULO X : INTEGRACIÓN...
122
-B[j][i][U] guarda cual ha sido la regla con 'U' en su parte izquierda, que ha dado mayor
probabilidad al ascender en el parsing
-F[j][i][U] contiene, si es que existe, la trama que separa los dos símbolos No
Terminales que el parsing ha unificado en 'U' al aplicar la regla B[j][i[U]
-el proceso de reconstrucción nunca será ambiguo al habernos quedado al ascender sólo
con las reglas que nos dan la mayor probabilidad parcial (en eso consiste la programación
dinámica)
El resultado es la secuencia de palabras más probable ateniéndose a las restricciones
impuestas por la gramática, aunque a expensas de un enorme coste computacional:
-para cada trama hay que realizar el alineamiento hacia atrás de todas las palabras del
vocabulario sin usar la información predictiva incluida en la gramática
-el Chart y las demás matrices son proporcionales en tamaño al número de tramas y no
al número de palabras como en el CYK convencional.
su-algoritmo
nº de operaciones
memoria usada
alineamiento temporal
2*J*J*I*Cardinal(u)
2*J*Card(u)
reglas U->u
2*J*I*Card(U->u)
3*I*I*Card(U->u)
reglas U->VW
I*I*I*Card(U->VW)/6
3*I*I*Card(U->VW)
X.2.2 Guiado del reconocimiento mediante predicción sintáctica
Más elegante es el tratamiento modular de Okada[91], que utiliza un autómata creciente
en el tiempo para guiar a un "one-pass": el algoritmo sintáctico(en su caso un "active chart",
aunque es perfectamente extensible al Earley) va creando el autómata (o simplemente un árbol,
si no deseamos autolazos en el autómata creciente):
CAPITULO X : INTEGRACIÓN...
122
Inicialización
Para cada regla del tipo S->A..B
incorporar a la agenda {S->A..B,0,0,[]}
Para cada regla A->C..D
si C es No Terminal
añadir a la agenda todas las reglas
{C->E..F,0,0,[]}
Para cada regla A->a..D
si 'a' es un símbolo Terminal
comunicar al reconocedor one-pass la
existencia de un nodo {'a',0,0[]}
Actualización del chart
mientras haya elementos activos en la agenda
begin
si el elemento no ha sido incorporado al chart
begin
Incorporarlo
si es del tipo {A->aB..,i,j,[o,p,...]}
begin
para cada B->C..D
incorporar {B->C..D,j,j,[]}
para cada {B->C..D,j,j,[]}
incorporar {C->E..F,j,j,[]}
para cada elemento del Chart
B->C..D..,j,k,[m,n,..]}
begin
Crear un vértice 'l' en el Chart
añadir a la agenda el elemento
{A->..B..,i,l,[k]}
end
para cada nuevo elemento
{C->..a..,j,j,[]}
Comunicar el nuevo nodo al 1-pass
end
si es del tipo B->..,i,j,[o,p,..]}
para cada {A->aB..,k,i,[m,n,...]}
begin
Crear un vértice 'l'
end
end
27 Chart Parsing de Okada.
Añadir {A->aB..,k,l,[j]}
end
CAPITULO X : INTEGRACIÓN...
122
El one-pass sólo ve la existencia en el Chart de nodos léxicos: aquellos que están
esperando la aceptación de una palabra o símbolo terminal, o aquellos que ya la han recibido.
Cuando la zona activa de una palabra esperada alcanza su estado final de Markov, la palabra es
aceptada y se comunica asíncronamente al Actualizador del Chart.
Los módulos sintáctico y acústico pueden ser implementados en procesadores diferentes
con comunicación asíncrona.
En número de operaciones es proporcional al número de trama de voz, la longitud media
de las zonas activas y el número medio de nodos.
CAPITULO XII : LÍNEAS FUTURAS
130
CAPITULO XI
LÍNEAS FUTURAS
Aunque las gramáticas de contexto libre tal cual están contempladas en nuestro entorno
nos proporcionan un aceptable marco para caracterizar una lengua natural como el castellano, la
muy detallada labor de categorización necesaria para cubrir la multitud de aspectos que
presentan las lenguas y la lentitud que para el "parsing" supone la generación de numerosas
estructuras intermedias finalmente carentes de utilidad, hace aconsejable una ampliación del
formalismo de escritura basándonos en rasgos.
La introducción de rasgos simples (género, número, persona...) no implica salirnos del
paradigma generativo: si permitimos que cada símbolo de la gramática pueda llevar asociadas
unas características que lo diferencien de otros del mismo nombre (por ejemplo
Sustantivo[+Masculino, +Plural]56), sólo tendremos que, por cada posible n-tupla
Símbolo[+Característica_1,... ,+Característica_n-1]
crearemos un nuevo símbolo terminal.
Por el número excesivo de reglas y símbolos a que dará lugar (cada
Sustantivo[+Característica_1,+Característica_2] supondrá la existencia de varios
SintagmaNominal_m[+Caract_1,+Caract_2]) preferiremos o bien el postproceso o bien el
"parsing" con rasgos incorporados:
-Si los árboles que nuestra gramática da para la mayoría de las oraciones son pocos, un
simple posproceso podrá verificar la concordancia entre los rasgos mediante una función
recursiva de recorrido de cada árbol: partiendo del nodo raíz bajará hasta las palabras y desde
allí elevará sus rasgos y comprobará su compatibilidad con los de los restantes constituyentes de
su nivel.
-conforme aplica las reglas gramaticales de contexto libre, el "parser" puede ir
chequeando las compatibilidades y evitando la aceptación de frases discordantes.
Rasgos más complejos que describan no sólo características de la palabra sino también
el contexto en el que puede o debe aparecer, podrían hacer imposible la tarea de hallar un
No confundir con el formalismo de las gramáticas
indexadas,donde entre corchetes hay una pila propia del
símbolo.
56
CAPITULO XII : LÍNEAS FUTURAS
130
algoritmo de "parsing" (Ver Shieber[86]).
Si nos limitamos a casos como el del verbo impersonal que exige ausencia de sujeto o
un sustantivo que no admite sintagmas preposicionales en "de", seguiremos teniendo la doble
posibilidad: posproceso o integración. Por ejemplo:
-el verbo impersonal elevará a sus categorías superiores el rasgo "no se admite la
presencia de sujeto". El "parser", cuando intente unificar un sintagma nominal con ese sintagma
verbal, no permitirá que al primero se le asigne la función de sujeto (podrá ser complemento
temporal o espacial no subcategorizado...).
Los mecanismos de herencia requerirán barreras que impidan su propagación más allá
de donde son necesarios o significativos. Que una proposición no pueda tener sujeto porque el
verbo es meteorológico (llover...) y le ha transmitido dicho rasgo por elevación57, no quiere
decir que proposiciones de nivel superior que contengan a la impersonal también sean
impersonales.
La elipsis, tan frecuente en castellano, podría suponer alteraciones de estos límites al
combinarse con la coordinación o la yuxtaposición. En:
"Juan comió y María cocinó spaguetis"
el carácter transitivo de la construcción verbal influye más allá de los límites de las
proposiciones coordinadas, alcanzando el ámbito oracional. Aunque podría considerarse que la
coordinación no es entre proposiciones sino entre fragmentos incompletos de proposiciones
("Juan comió" y "María cocinó"), más lógico es considerar que hay una elipsis en la primera
proposición y que el hueco es rellenado con un sintagma por el nivel superior (al unificar las
proposiciones coordinadas en una oración completa, el rasgo "falta un sintagma nominal
complemento directo" exige que dicho sintagma sea copiado desde la otra proposición o si no
que no se unifique).
Para reducir la memoria, los rasgos pueden no ser continuamente ascendidos sino que,
cuando es necesario comprobar una concordancia, se realiza una reconstrucción parcial para
extraer temporalmente dichos rasgos sólo presentes continuamente en el nivel de palabra. La
ralentización sería notable ya que la reconstrucción es mucho más lenta que el análisis simple.
Gazdar propone en su "Generalised Phrase Structure Gramar" que sustituyamos las
transformaciones (mecanismos conceptualmente elegantes, muy gráficos pero poco prácticos a
la hora de analizar) por un método doble:
-incluir dentro de las reglas sintácticas la posibilidad de emplear categorías derivadas
(las propias de las Gramáticas Categoriales) para dar que se puedan transmitir de un modo
sencillo las elipsis
57
Este concepto de elevación no implica que el algoritmo deba
de ser ascendente.Los algoritmos descendentes también pueden
emplear rasgos.
CAPITULO XII : LÍNEAS FUTURAS
130
-meta-reglas que alteren la estructura superficial que se va creando para que salga a la
luz la estructura de relaciones correcta
Bresnan, por su parte, creó junto a Kaplan el formalismo llamado "Lexical Functional
Gramar" donde realiza el "parsing" secuencialmente en dos niveles:
-el sintáctico, bastante laso y de contexto libre como los de este proyecto
-el funcional, basado en ir rellenando patrones desde el nivel terminal hasta el nivel
axiomático de los árboles sintácticos.
Para la oración:
"una niña le dió un regalo"
obtendríamos una estructura sintagmática simple (26).
ORACION
SintagmaNominal
Det
Núcleo
SintagmaVerbal
Núcleo
Prononbre
SintagmaNominal
VerboTransit
Det
El verbo, principal componente de la mayoría de las oraciones gramaticales, guiará el
análisis funcional:
Install Equation Editor and doubleclick here to view equation.
Unas reglas sintáctico-funcionales traducirán las categorías funcionales en categorías
sintácticas:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
Los posibles ordenamientos de las categorías funcionales también deberán ser
especificados:
Install Equation Editor and doubleclick here to view equation.
Install Equation Editor and doubleclick here to view equation.
CAPITULO XII : LÍNEAS FUTURAS
130


El resultado funcional será :
Install Equation Editor and doubleclick here to view equation.
Las distintas cadenas vacías :
CAPITULO XII : LÍNEAS FUTURAS
130
Install Equation Editor and doubleclick here to view equation.
CAPITULO XII : LÍNEAS FUTURAS
130
resultarían útiles al hacer el "parsing":su presencia indicaría al "parsing" funcional que debe
buscar más allá de los límites proposicionales lo que falta.
Las referencias pronominales podrían recibir un tratamiento similar.
Aunque con estos mecanismos nos salimos de la ortodoxia generativa, los estudios de
ésta sobre restricciones a la aplicación de transformaciones (ningún elemento puede ser extraído
de una proposición coordinada aunque sí puede ser copiado...), las reglas de elisión
(recuperabilidad gracias a la huella...), ... nos seguirán siendo útiles.
135
BIBLIOGRAFÍA
[Aho 72] A.V.Aho y J.D.Ullman, The theory of parsing, translation and compiling:
volume I: parsing, Ed. Prentice Hall, 1972.
[Alcina 75]J.Alcina y J.M.Blecua, Gramática española, Ed. Ariel, 1991.
[Andry 91] F.Andry y S.Thornton, "A parser for speech lattices using a Unification
Categorial Gramar", IEEE-ICASSP, pp.219-222, 1991.
[Ascen 93] Ascension Gallardo, Proyecto Fin de Carrera, ETSI Telecomunicación
(UPM), 1993.
[Dik 78] S.C.Dik, Gramática Funcional, Ed. Sociedad General Española de Librería
S.A., 1981.
[Dirksen 92] A.Dirksen, "PROS-3 Sintax and Prosody for text-to-speech", Polyglot,
1992.
[Earley 70] J.Earley, "An efficient context-free parsing algorithm", en Grosz [86],
pp.25-33.
[Edinburgh 89] "Edinburgh course on computational sintax".
[Esbozo 73] Comisión de gramática de la R.A.E., Esbozo de una nueva gramática
de la lengua española, Ed.Espasa-Calpe, 1991.
[Fissore 88] L.Fissore et al, "Interaction between fast lexical access and word
verification in large vocabulary continuous speech recognition", IEEE-ICASSP, pp.279-282,
1988.
[Fissore 89] L.Fissore et al, "A word hypothesizer for a large vocabulary continuous
speech understanding system", IEEE-ICASSP, pp.453-456, 1989.
[Fu ] K.Fu, "Syntactic approach to pattern recognition"
[Fu 85] K.Fu, "VLSI Architectures for recognition of context-free languages".
[Granda 90] J.S.Granda, "Clasificación del léxico para un algoritmo probabilístico de
etiquetado automático en microordenadores", Actas del VI Congreso de lenguajes naturales y
lenguajes formales, pp.949-970, 1991.
[Grosz 86] B.Grosz et al, Readings in Natural Language Processing, Ed. Morgna
Kaufmann, 1986.
[Gutiérrez 78] M.L.Gutiérrez, Estructuras sintácticas del español actual, Ed. Sociedad
General Española de Librería S.A., 1978.
135
[Hallebeek 90] J.Hallebeek, "Nominalización funcional y análisis sintáctico
automatizado", Actas del VI Congreso de lenguages naturales y lenguajes formales, pp.621-640,
1991
[Haller 91], "La ingeniería lingüística: un ejemplo de cooperación entre Universidad e
Industria", ASPLN, Barcelona, 1991
[Hernanz 87] J.M.Brucart y M.L.Hernanz, La sintaxis.Volumen 1: Principios
teóricos.La oración simple", Ed. Crítica, 1987.
[Leandro 89] M.A.Leandro, "Análisis semántico automático de la lengua española
aplicado al reconocimiento de habla", Proyecto Fin de Carrera DIE-ETSIT-UPM, 1989.
[Levinson 87] S.E.Levinson, "Continuous speech recognition of acoustic/phonetic
classification obtained from a Hidden Markov Model", IEEE-ICASSP, pp.93-96, 1987.
[Levinson 88] S.E.Levinson et al, "Large vocabulary speech recognition using a Hidden
Markov Model for acoustic/phonetic classification", pp.505508, 1988.
[Macías 92] J. Macías,Proyecto Fin De Carrera, DIE-ETSIT-UPM, 1992.
[Miller 88] L.G.Miller y S.E.Levinson, "Syntactic analysis for large vocabulary speech
recognition using a context-free covering gramar", pp.271-274, 1988
[Nakagawa 87] S.Nakagawa, "Spoken sentence recognition by time-synchronous
parsing algorithm of context-free gramar", IEEE-ICASSP, pp.829-832, 1987.
[Ney 87] H.Ney, "Dynamic programming speech recognition using a context-free
gramar, IEEE-ICASSP, pp.69-72, 1987.
[Niemann 86] H.Niemann et al, "Generating word hypotheses in continuous speech",
IEEE-ICASSP, pp.1565-1568, 1986.
[Okada 91] M.Okada, "A unification-gramar-directed One-Pass search algorithm for
parsing spoken language", pp.721-724, 1991.
[Pereira 87] F.C.N.Pereira y S.Shieber, Prolog and natural language analysis, Ed.
CLSI, 1987.
[Perrault 84] "On the mathematical properties of linguistic theories", en Grosz[86]
[Pieraccini 91] R. Pieraccini, E. Levin, "Stochastic representation of semantic structure
for speech understanding", IEEE-ICASSP, pp. 383-386 ,1991.
[Pieraccini 92] R. Pieraccini et al, "A speech understanding system based on statistical
representation of semantics", IEEE-ICASSP, pp.193-196, 1991
135
[Radford 81] A.Radford, Introducción a la sintaxis transformativa, Ed.Teide, 1988.
[Roe 91] Roe et al "Toward a spoken language translation for restricted-domain contextfree languages", IEEE-ICASSP, pp.1063-1066, 1991.
[Roe 92] Roe et al, "Efficient gramar processing for a spoken language translation
system", IEEE-ICASSP, pp.213-216, 1992.
[Russi 91] T.Russi, "Robust and efficient parsing for applications such as text-to-speech
conversion", IEEE-ICASSP, pp.775-778, 1991.
[Sager 91] "Panorama de aplicaciones de la lingüística computacional a problemas de
comunicación bilingüe", ASPLN, Barcelona, 1991
[Saito 89] H.Saito et al, "HMM continuous speech recognition using predictive LR
parsing", IEEE-ICASSP, pp.703-706, 1989.
[Seneff 92] S. Seneff, "Robust parsing for spoken languaje systems", IEEE-ICASSP, pp.
189-192, 1992
[Shieber 86] S.Shieber, An introduction to Unification-based aproaches to gramar,
CLSI Lecture Notes, 1986.
[Smaïli 90] K.Smaïli et al, "A continuous speech recognition approach for the design of
a dictation machine", IEEE-ICASSP, pp.953-956, 1990.
[Subirats 91] C.Subirats, "System of electronic dictionaries of Spanish", Congreso de
Barcelona, Septiembre 1991.
[Tomita 86a] M.Tomita, "An efficient word lattice parsing algorithm for continuous
speech recognition", IEEE-ICASSP, pp.1569-1562, 1986.
[Tomita 86b] M.Tomita, Efficient parsing for natural language.A fast algorithm for
practical systems, Ed. Kluger Academic Publishers, 1986.
[Vidal 90] E.Vidal y P.García, "Inference of k-testable languages in the strict sense and
application to syntactic pattern recognition", IEEE Transactions on Pattern Analysis and
Machine Intelligence, pp.920-925, Septiembre 1990.
[Vidal 91] E.Vidal y N.Prieto, "Learning language models through the EGGI method",
IEEE-ICASSP, pp.395-398, 1991.
[Waibel 92] A. Waibel et al, "Testing generality in Janus: a multilingual speech
translation system", IEEE-ICASSP, pp. 209-212, 1992
[Ward 91] W.Ward, "Incorporating LR parsing into SPHINX", IEEE-ICASSP, pp.269272, 1991.
135
[Willemse 90] R.Willemse, Wild Card Parser user manual.
[Winograd 83] T.Winograd, Language as a cognitive process. Volume I: Syntax, Ed.
Addison Wesley, 1983.
[Wirth 82] N.Wirth, Programación en Modula-2, Ed.El Ateneo, 1987.
[Young 91] S.Young y M.Matessa, "Using pragmatic and semantic knowledge to
correct parsing of spoken language utterances", IEEE-ICASSP, pp.223-227, 1991.