Un predicado sintáctico especifica la validez sintáctica de aplicar una producción en una gramática formal y es análogo a un predicado semántico que especifica la validez semántica de aplicar una producción. Es un medio simple y eficaz de mejorar drásticamente la fuerza de reconocimiento de un analizador LL al proporcionar una búsqueda anticipada arbitraria. En su implementación original, los predicados sintácticos tenían la forma "(α)?" y solo podía aparecer en el borde izquierdo de una producción. La condición sintáctica requerida α podría ser cualquier fragmento de gramática libre de contexto válido.
Más formalmente, un predicado sintáctico es una forma de intersección de producción , que se utiliza en las especificaciones del analizador sintáctico o en las gramáticas formales . En este sentido, el término predicado tiene el significado de una función de indicador matemático . Si p 1 y p 2 son reglas de producción, el lenguaje generado tanto por p 1 como por p 2 es su intersección establecida.
Tal como se definen o implementan típicamente, los predicados sintácticos ordenan implícitamente las producciones de modo que las producciones predicadas especificadas anteriormente tengan mayor precedencia que las producciones predicadas especificadas posteriormente dentro de la misma decisión. Esto transmite la capacidad de eliminar la ambigüedad de las producciones ambiguas porque el programador puede simplemente especificar qué producción debe coincidir.
Las gramáticas de expresión analítica (PEG), inventadas por Bryan Ford, amplían estos predicados simples al permitir "no predicados" y permitir que un predicado aparezca en cualquier lugar dentro de una producción. Además, Ford inventó el análisis sintáctico packrat para manejar estas gramáticas en tiempo lineal mediante el empleo de memorización , a costa del espacio de almacenamiento .
Es posible admitir el análisis sintáctico en tiempo lineal de predicados tan generales como los permitidos por los PEG, pero reducir el costo de memoria asociado con la memorización al evitar el retroceso cuando es suficiente una implementación más eficiente de la búsqueda anticipada. Este enfoque es implementado por ANTLR versión 3, que utiliza autómatas finitos deterministas para la búsqueda anticipada; esto puede requerir probar un predicado para elegir entre las transiciones del DFA (llamado análisis "pred-LL (*)"). [1]
Descripción general
Terminología
El término predicado sintáctico fue acuñado por Parr & Quong y diferencia esta forma de predicado de los predicados semánticos (también discutidos). [2]
Los predicados sintácticos se han denominado coincidencia de varios pasos , restricciones de análisis y simplemente predicados en diversas publicaciones. (Consulte la sección Referencias a continuación). Este artículo utiliza el término predicado sintáctico en todo momento para mantener la coherencia y para distinguirlos de los predicados semánticos .
Propiedades de cierre formal
Bar-Hillel y col. [3] muestran que la intersección de dos idiomas regulares es también un idioma regular, lo que quiere decir que los idiomas regulares están cerrados bajo intersección .
La intersección de un lenguaje regular y un lenguaje libre de contexto también está cerrada, y se sabe al menos desde Hartmanis [4] que la intersección de dos lenguajes libres de contexto no es necesariamente un lenguaje libre de contexto (y por lo tanto no es cerrado). Esto se puede demostrar fácilmente utilizando el lenguaje canónico de Tipo 1 ,:
Dejar (Tipo 2)Dejar (Tipo 2)Dejar
Dadas las cadenas abcc , aabbc y aaabbbccc , está claro que la única cadena que pertenece tanto a L 1 como a L 2 (es decir, la única que produce una intersección no vacía ) es aaabbbccc .
Otras Consideraciones
En la mayoría de los formalismos que utilizan predicados sintácticos, la sintaxis del predicado es no conmutativa , es decir, la operación de predicación está ordenada. Por ejemplo, usando el ejemplo anterior, considere la siguiente pseudogramática , donde X :: = Y PRED Z se entiende que significa: " Y produce X si y solo si Y también satisface el predicado Z ":
S :: = una XX :: = Y PRED ZY :: = a + BNCNZ :: = ANBN c +BNCN :: = b [BNCN] cANBN :: = a [ANBN] b
Dada la cadena aaaabbbccc , en el caso de que Y deba satisfacerse primero (y asumiendo una implementación codiciosa), S generará aX y X a su vez generará aaabbbccc , generando así aaaabbbccc . En el caso de que Z deba satisfacerse primero, ANBN no generará aaaabbb y, por lo tanto, la gramática no generará aaaabbbccc . Además, si Y o Z (o ambos) especifican cualquier acción que se tomará tras la reducción (como sería el caso en muchos analizadores), el orden en que coinciden estas producciones determina el orden en el que se producen esos efectos secundarios. Los formalismos que varían con el tiempo (como las gramáticas adaptativas ) pueden depender de estos efectos secundarios .
Ejemplos de uso
- ANTLR
Parr y Quong [5] dan este ejemplo de un predicado sintáctico:
stat: (declaración)? declaración | expresión ;
que está destinado a satisfacer las siguientes restricciones [6] establecidas de manera informal de C ++ :
- Si parece una declaración, lo es; de lo contrario
- si parece una expresión, lo es; de lo contrario
- es un error de sintaxis.
En la primera producción de regla stat, ¿el predicado sintáctico (declaración)? indica que la declaración es el contexto sintáctico que debe estar presente para que el resto de esa producción tenga éxito. ¿Podemos interpretar el uso de (declaración)? como "No estoy seguro de si la declaración coincidirá; déjeme probarla y, si no coincide, probaré la siguiente alternativa". Por lo tanto, cuando se encuentra una declaración válida, la declaración de la regla se reconocerá dos veces: una como predicado sintáctico y una vez durante el análisis real para ejecutar acciones semánticas.
Cabe señalar en el ejemplo anterior el hecho de que cualquier código desencadenado por la aceptación de la producción de la declaración solo ocurrirá si se cumple el predicado.
Ejemplos canónicos
El idioma se puede representar en varias gramáticas y formalismos de la siguiente manera:
Análisis de gramáticas de expresión
S ← & ( A ! B ) a + B ! c A ← a A ? b B ← b B ? C
§-Cálculo
Usando un predicado enlazado :
S → {A} B
A → X 'c +'X → 'a' [X] 'b'B → 'a +' YY → 'b' [Y] 'c'
Usando dos predicados libres :
A → <'a +'> a <'b +'> segundo Ψ ( a b ) X <'c +'> c Ψ ( segundo c ) Y
X → 'a' [X] 'b'Y → 'b' [Y] 'c'
Gramáticas conjuntivas
(Nota: el siguiente ejemplo realmente genera , pero se incluye aquí porque es el ejemplo dado por el inventor de las gramáticas conjuntivas. [7] ):
S → AB&DCA → aA | εB → bBc | εC → cC | εD → aDb | ε
Reglas de Perl 6
regla S { > a + } regla A { a ? b } regla B { b ? c }
Analizadores / formalismos que utilizan alguna forma de predicado sintáctico
Aunque de ninguna manera es una lista exhaustiva, los siguientes analizadores sintácticos y formalismos gramaticales emplean predicados sintácticos:
- ANTLR (Parr y Quong)
- Como se implementó originalmente, [2] los predicados sintácticos se ubican en el borde más a la izquierda de una producción de tal manera que la producción a la derecha del predicado se intenta si y solo si el predicado sintáctico primero acepta la siguiente porción del flujo de entrada. Aunque ordenados, los predicados se comprueban primero, y el análisis de una cláusula continúa si y solo si se satisface el predicado, y las acciones semánticas solo ocurren en no predicados. [5]
- Coincidencia de patrones aumentada (Balmas)
- Balmas se refiere a los predicados sintácticos como "coincidencia de varios pasos" en su artículo sobre APM. [8] A medida que un analizador de APM analiza, puede vincular subcadenas a una variable y luego comparar esta variable con otras reglas, continuando el análisis si y solo si esa subcadena es aceptable para otras reglas.
- Análisis de gramáticas de expresión (Ford)
- Los PEG de Ford tienen predicados sintácticos expresados como el predicado y y el no predicado . [9]
- §-Cálculo (Jackson)
- En el §-Cálculo, los predicados sintácticos se denominan originalmente simplemente predicados , pero luego se dividen en formas limitadas y libres , cada una con diferentes propiedades de entrada. [10]
- Reglas de Raku
- Raku presenta una herramienta generalizada para describir una gramática llamada reglas , que son una extensión de la sintaxis de expresiones regulares de Perl 5. [11] Los predicados se introducen mediante un mecanismo de anticipación llamado antes , ya sea con "
" o "" (es decir: " no antes"). Perl 5 también tiene tal anticipación, pero solo puede encapsular las características de expresiones regulares más limitadas de Perl 5.
- ProGrammar (NorKen Technologies)
- El GDL (lenguaje de definición de gramática) de ProGrammar hace uso de predicados sintácticos en una forma llamada restricciones de análisis . [12] ATENCIÓN NECESARIA: ¡Este enlace ya no es válido!
- Gramáticas conjuntivas y booleanas (Okhotin)
- Las gramáticas conjuntivas, introducidas por primera vez por Okhotin, [13] introducen la noción explícita de conjunción -como-predicación. El tratamiento posterior de las gramáticas conjuntivas y booleanas [14] es el tratamiento más completo de este formalismo hasta la fecha.
Referencias
- ^ Parr, Terence (2007). La referencia definitiva de ANTLR: creación de lenguajes específicos de dominio . Los programadores pragmáticos . pag. 328. ISBN 978-3-540-63293-1.
- ^ a b Parr, Terence J .; Quong, Russell (octubre de 1993). "Adición de predicados sintácticos y semánticos al análisis de LL (k): pred-LL (k)". Centro de Investigación en Computación de Alto Rendimiento del Ejército Preprint No. 93-096: 263–277. CiteSeerX 10.1.1.26.427 . Cite journal requiere
|journal=
( ayuda ) - ^ Bar-Hillel, Y .; Perles, M .; Shamir, E. (1961). "Sobre las propiedades formales de las gramáticas de estructura de frase simple". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung . 14 (2): 143-172..
- ^ Hartmanis, Juris (1967). "Lenguajes libres de contexto y cálculos de máquina de Turing" . Actas de simposios en matemáticas aplicadas . Aspectos matemáticos de la informática. AMS. 19 : 42–51. doi : 10.1090 / psapm / 019/0235938 . ISBN 9780821867280.
- ^ a b Parr, Terence; Quong, Russell (julio de 1995). "ANTLR: un generador de analizador LL (k) predicado " (PDF) . Software: práctica y experiencia . 25 (7): 789–810. doi : 10.1002 / spe.4380250705 .
- ^ Stroustrup, Bjarne; Ellis, Margaret A. (1990). El Manual de referencia de C ++ anotado . Addison-Wesley.
- ^ Okhotin, Alexander (2001). "Gramáticas conjuntivas" (PDF) . Revista de Autómatas, Idiomas y Combinatoria . 6 (4): 519–535. Archivado desde el original (PDF) el 26 de junio de 2019.
- ^ Balmas, Françoise (20 a 23 de septiembre de 1994). Un comparador de patrones aumentado como herramienta para sintetizar descripciones conceptuales de programas . Actas de la Novena Conferencia de Ingeniería de Software basada en el conocimiento. Monterey, California. págs. 150-157. doi : 10.1109 / KBSE.1994.342667 .
- ^ Ford, Bryan (septiembre de 2002). Packrat Parsing: un algoritmo práctico de tiempo lineal con retroceso (tesis de maestría). Instituto de Tecnología de Massachusetts.
- ^ Jackson, Quinn Tyler (marzo de 2006). Adaptación a Babel: adaptabilidad y sensibilidad al contexto en el análisis . Plymouth, Massachusetts: Publicación de Ibis. CiteSeerX 10.1.1.403.8977 .
- ^ Wall, Larry (2002-2006). "Sinopsis 5: expresiones regulares y reglas" .
- ^ "Lenguaje de definición de gramática" . NorKen Technologies.
- ^ Okhotin, Alexander (2000). "Sobre el aumento del formalismo de gramáticas libres de contexto con una operación de intersección". Actas de la Cuarta Conferencia Internacional "Modelos discretos en la teoría de los sistemas de control" (en ruso): 106-109.
- ^ Okhotin, Alexander (agosto de 2004). Gramáticas booleanas: potencia expresiva y algoritmos (tesis doctoral). Kingston, Ontario: Escuela de Computación, Universidad de Queens.
enlaces externos
- Sitio ANTLR
- Página de gramáticas conjuntivas de Alexander Okhotin
- Página de gramáticas booleanas de Alexander Okhotin
- Página de gramática de expresiones de análisis y análisis de Packrat