Un predicado sintáctico especifica la validez sintáctica de la aplicación de una producción en una gramática formal y es análogo a un predicado semántico que especifica la validez semántica de la aplicación de 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ían aparecer en el borde izquierdo de una producción. La condición sintáctica requerida α podría ser cualquier fragmento gramatical válido libre de contexto.
De manera más formal, un predicado sintáctico es una forma de intersección de producción , utilizada en especificaciones de analizadores sintácticos o en gramáticas formales . En este sentido, el término predicado tiene el significado de una función indicadora matemática . 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 de conjuntos.
Tal como se definen o implementan normalmente, los predicados sintácticos ordenan implícitamente las producciones de modo que las producciones predicadas especificadas antes tengan mayor precedencia que las producciones predicadas especificadas después dentro de la misma decisión. Esto transmite una capacidad para desambiguar producciones ambiguas porque el programador puede especificar simplemente qué producción debe coincidir.
Las gramáticas de expresión de análisis sintáctico (PEG), inventadas por Bryan Ford, extienden estos predicados simples al permitir "predicados no" y permitir que un predicado aparezca en cualquier lugar dentro de una producción. Además, Ford inventó el análisis sintáctico de Packrat para manejar estas gramáticas en tiempo lineal mediante el empleo de la memorización , a costa del espacio de almacenamiento dinámico.
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 basta con una implementación más eficiente de la búsqueda anticipada. Este enfoque se implementa en la versión 3 de ANTLR , que utiliza autómatas finitos deterministas para la búsqueda anticipada; esto puede requerir probar un predicado para elegir entre transiciones del DFA (denominado análisis sintáctico "pred-LL (*)"). [1]
El término predicado sintáctico fue acuñado por Parr y Quong y diferencia esta forma de predicado de los predicados semánticos (también analizados). [2]
En diversas publicaciones, los predicados sintácticos se denominan coincidencia de múltiples pasos , restricciones de análisis y simplemente predicados (consulte la sección Referencias a continuación). En este artículo se utiliza el término predicado sintáctico a lo largo del texto para mantener la coherencia y distinguirlos de los predicados semánticos.
Bar-Hillel et al. [3] muestran que la intersección de dos lenguajes regulares también es un lenguaje regular, lo que quiere decir que los lenguajes regulares están cerrados bajo la intersección .
La intersección de un lenguaje regular y un lenguaje libre de contexto también es 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 aaabbccc , 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 aaabbccc .
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 es ordenada. Por ejemplo, utilizando 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::= a XX::= Y PREDZY ::= a+ BNCNZ::= ANBN c+BNCN ::= b [BNCN] cANBN ::= a [ANBN] b
Dada la cadena aaaabbbccc , en el caso en que Y debe satisfacerse primero (y asumiendo una implementación voraz), S generará aX y X a su vez generará aaabbbccc , generando así aaaabbbccc . En el caso en que Z debe satisfacerse primero, ANBN no generará aaaabbb , y por lo tanto aaaabbbccc no es generado por la gramática. Además, si Y o Z (o ambos) especifican alguna acción a tomar tras la reducción (como sería el caso en muchos analizadores sintácticos), el orden en que coinciden estas producciones determina el orden en que ocurren esos efectos secundarios. Los formalismos que varían con el tiempo (como las gramáticas adaptativas ) pueden depender de estos efectos secundarios .
Parr y Quong [5] dan este ejemplo de un predicado sintáctico:
stat : ( declaración ) ? declaración | expresión ;que tiene como objetivo satisfacer las siguientes restricciones de C++ establecidas informalmente [6] :
En la primera producción de la 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 la producción tenga éxito. Podemos interpretar el uso de (declaración)? como "No estoy seguro de si la declaración coincidirá; déjame probarla y, si no coincide, probaré la siguiente alternativa". Por lo tanto, cuando se encuentre una declaración válida, la declaración de la regla se reconocerá dos veces: una como predicado sintáctico y otra durante el análisis real para ejecutar acciones semánticas.
Lo que cabe destacar en el ejemplo anterior es el hecho de que cualquier código activado por la aceptación de la producción de declaración solo ocurrirá si se cumple el predicado.
El lenguaje se puede representar en varias gramáticas y formalismos de la siguiente manera:
S ← & ( A ! b ) a + B ! c A ← a A ? b B ← b B ? cUsando un predicado enlazado :
S → {A} BA → X 'c+'X → 'a' [X] 'b'B → 'a+' YY → 'b' [Y] 'c'
Usando dos predicados libres :
A → <'a+'> a <'b+'> b Ψ( a b ) X <'c+'> c Ψ( b c ) Y
X → 'a' [X] 'b'Y → 'b' [Y] 'c'
(Nota: el siguiente ejemplo en realidad genera , pero se incluye aquí porque es el ejemplo dado por el inventor de las gramáticas conjuntivas. [7] ):
S → AB y DCA → aA | εB → bBc | εC → cC | εD → aDb | ε
regla S { <antes de <A> <!antes de b>> a+ <B> <!antes de c> } regla A { a <A>? b } regla B { b <B>? c }Aunque no es de ninguna manera una lista exhaustiva, los siguientes analizadores sintácticos y formalismos gramaticales emplean predicados sintácticos:
<before ...>" o " <!before ...>" (es decir: " no antes"). Perl 5 también tiene este tipo de búsqueda anticipada, pero sólo puede encapsular las características de expresiones regulares más limitadas de Perl 5.