No estoy seguro de que esto te traiga más de lo que ya sabes. Pero entonces, es posible que no comprenda las razones que lo hacen preguntarse sobre la reescritura de términos. Sí ayuda.
Como sabrán, las gramáticas son sistemas de reescritura de cadenas. En la parte superior de la jerarquía de Chomsky, tiene gramáticas de tipo 0, que definen los ángulos recursivamente enumerables (RE), y tiene el poder computacional de las máquinas de Turing.
Eso te dice que los sistemas de reescritura en general tienen mucho que ver con algoritmos de expresión.
El problema con las cadenas en general es que no hay una forma obvia de unirles la semántica. Es una especie de reescritura amorfa.
Lo que a la gente generalmente le interesa es expresar algoritmos en dominios específicos que tienen estructura y propiedades. Dichos dominios a menudo se definen a partir de entidades elementales (atómicas) y se cierran mediante diversas operaciones, posiblemente citadas por relaciones de equivalencia, etc. A menudo se llaman álgebras.
Estos dominios son a menudo abstractos. Pero los cálculos sobre sus elementos solo pueden expresarse en representaciones concretas. Los términos son una represión natural de estos elementos, ya que expresan cómo pueden obtenerse elementos para otros elementos mediante la aplicación de operaciones, recurrentemente hacia elementos atómicos (aunque las propiedades generales no siempre tienen que ir hacia abajo). Los términos son un tipo de sintaxis de estructura de árbol que se puede manipular para expresar algoritmos (como para cadena). Pero la estructura de términos del operador operando también permite asociarles semántica en algún dominio abstracto por medio de homomorfismos.
En lugar de tener una visión muy formal de Wikipedia y muchos textos sobre este tema, solo considere los programas. Por lo general, se reconoce que una representación sintáctica conveniente de los programas es lo que se llama Árbol de sintaxis abstracta (AST). Pero un AST es solo un término para representar un objeto de programa. La semántica denotacional es una forma de definir dominios abstractos y asociar valores de estos dominios a AST (o subárboles de AST) por medio de homomorfismos. Los programas en formato AST pueden transformarse u optimizarse aplicando reglas de reescritura (no estoy afirmando que todas las optimizaciones puedan o deban hacerse de esa manera).
La transformación de expresiones algebraicas para diversos fines puede expresarse mediante la reescritura de términos. Por ejemplo, la simplificación de algunas expresiones. Varios tipos de cálculos también pueden expresarse naturalmente como reescritura de términos, como el cálculo de derivados. La reescritura de términos también se usa a veces para definir formas canónicas en álgebras, cuando la misma entidad semántica puede tener varias representaciones sintácticas.
Le sugiero que mire el artículo de Wikipedia sobre este tema .
