INTRODUCCIÓN AL LENGUAJE DE PROGRAMACIÓN CONVERT

Vista previa del material en texto

ACTA MEXICANA DE CIENCIA Y TECNOLOGIA 
Vol. Ill, No. 9, Enero-Marzo, 1985 
págs. 65-74 
INSTRUMENTACION 
INTRODUCCIÓN AL LENGUAJE DE PROGRAMACIÓN CONVERT 
GERARDO CISNEROS 
Sección de Graduados, Escuela Superior de Ingeniería Mecánica y Eléctrica (ESIME) 
Instituto Politécnico Nacional, 07738 México, D.F. 
HAROLD V. McINTOSH 
Departamento de Aplicación de Microcomputadoras, Instituto de Ciencias, 
Uruvers1dad Autónoma de Puebla, Apdo. Postal 461, 72000 Puebla, Puebla 
Resumen: Se presenta una descripción introductoria del lenguaje de programación Convert, aplicable a 
problemas de manipulación simbólica cuya solución pueda formularse en términos de reglas de transfor-
mación. Se discute la experiencia obtenida con el uso del lenguaje y se mencionan algunas aplicaciones fu-
turas. 
INTRODUCI'ION TO THE PROGRAMMING LANGUAGE CONVERT 
Altstnct: We presentan introductory description of Convert, a programming language applicable to sym-
bolic manipulation problems whose solution may be expressed in terms of transformation rules. W e dis-
cuss the experience derived from our use of the language and mention sorne future applications. 
INTRODUCCIÓN 
Convert es un lenguaje de programación que fun-
ciona a base de reconocimiento de patrones y de sus-
titución de cadenas, que originalmente fue diseñado 
como interpretador basado en el lenguaje LISP por 
Guzmán y Mclntosh. 1, 2 El compilador actual de 
Convert está escrito en REC, 3, 4 transforma progra-
mas de Convert a REC (que posteriormente REC 
compila a código de máquina y ejecuta). Funciona en 
microcomputadoras cuyo procesador central es el cir-
cuito Intel 8080 u 8086 (o compatibles, como Zilog 
Z80 o Intel 8088) junto con el sistema operativo 
CPIM. 
La idea central en el funcionamiento de un progra-
ma en Convert es identificar y aislar segmentos de 
65 
una cadena de caracteres ya sea porque satisfacen al-
gún requisito (p. ej. que una cadena conste de exacta-
mente S caracteres) o porque están situados en un en-
torno prescrito (p. ej una cadena delimitada por pa-
réntesis). Los segmentos identificados de este modo 
pueden usarse para generar un texto nuevo, de pref e-
rencia con la ayuda de funciones y estructuras de 
control muy generales. 
Un programa en Convert es una lista cuyos ele-
mentos son cuatro listas: 
- Una lista de definiciones de patrones 
(Sección 2). 
- Una lista de definiciones de esqueletos 
(Sección 3). 
- Una lista de variables, y 
- Una lista de reglas (Sección 4). 
66 G. CISNEROS Y H. V. MclNTOSH 
Cada una de estas listas se encierra entre paréntesis 
y a su vez las cuatro listas se delimitan con otro par 
de paréntesis. Cualquiera de las listas puede ser nula, 
de hecho, la cadena (( )( )( )( )), en la que las cuatro 
listas son nulas, es un programa completo en Con-
vert, con las siguientes características: 
- No define patrones. 
- No define esqueletos. 
- No declara variables. 
- No tiene reglas (por lo cual no hace nada, es de-
cir, si se le hiciera actuar sobre un texto no le 
haría ningún cambio). 
Todo programa o subrutina en Convert tiene a su 
disposición una área de trabajo cuyo contenido ini-
cial es el texto cuya transformación se desea que el 
programa efectúe (texto que podría ser la cadena nu-
la). La transformación de dicho texto se efectúa por 
las reglas y cada una de ellas consta a su vez de un 
patrón y un esqueleto. Los patrones son predicados 
(es decir, entidades que pueden ser verdaderas o fal-
sas) que determinan si el texto tiene cierta forma o 
no. Los esqueletos son entidades cuyo valor es una 
cadena de texto, pero que pueden además realizar 
otras funciones, como abrir, cerrar, leer o escribir 
archivos de disco. Las variábles se identifican simple-
mente mediante números enteros del O al 30 (aunque 
esto puede parecer restrictivo, pocos programas re-
quieren más de seis variaNes, la mayoría utiliza una o 
dos y es posible tener programas que no usan va-
riables). Las variables pueden hacer las veces de 
patrones o esqueletos, según el contexto en el que 
aparezcan. 
2. PATRONES 
Como se mencionó antes, un patrón es un predica-
do que especifica la forma de alguna cadena de texto, 
es decir, constituye una proposición lógica que resul-
ta verdadera o falsa según el texto analizado tenga o 
no la forma especificada (esto es, según el patrón 
"case" o "no case" con el texto). Hay patrones pri-
mitivos y patrones compuestos. Como ejemplos de 
patrones primitivos se pueden mencionar las cons-
tantes, que sólo casan con una subcadena idéntica del 
texto, y las variables, que casan con porciones diver-
sas del texto según el contexto en que aparezcan. 
Ejemplos de patrones compuestos lo son la concate-
nación de patrones y las combinaciones booleanas. 
Todo patrón, para casar, debe casar mínimamente 
con alguna porción contigua del texto que inicie en el 
extremo izquierdo del mismo. Ciertos patrones, co-
mo se verá más adelante, sólo son verdaderos cuando 
se establece la correspondencia con la totalidad del 
texto. 
A continuación se da una lista de los patrones bási-
cos de Convert. En dicha lista, las letras griegas a y (J 
denotan cadenas de caracteres ASCII (Código Normal 
Americano para Intercambio de Información), la le-
tra griega n se usa para denotar a un patrón y la letra 
griega o representa a un esqueleto. 
Patrón 
a 
< ( > 
<)> 
( <) 
( >) 
<' > 
<' > 
< " > 
(QUO/al) 
Descripción 
Constante. La cadena a puede 
contener cualquier carácter impri-
mible ASCII excepto los parénte-
sis redondos [ ( y ) ] , los paréntesis 
angulares [< y> ], la coma [ , ], 
el apóstrofo [ ' ] y las comillas 
[ " ] . La cadena a casa con una 
subcadena idéntica en el texto 
analizado. 
Constante. Casa con un parénte-
sis izquierdo. 
Constante. Casa con un parénte-
sis derecho. 
Constante. Casa con un parénte-
sis angular izquierdo. 
Constante. Casa con un parénte-
sis angular derecho. 
Constante. Casa con una coma. 
Constante. Casa con un apóstro-
fo. 
Constante. Casa con una instan-
cia del carácter "comillas". 
Constante. La cadena a no de-
be incluir a los delimitadores 
"/"; casa con una cadena idénti-
ca a la cadena a. Por ejemplo 
(QUO=(ab)=) es idéntico al 
patrón < ( > ab< )>, que casa 
con la cadena de cuatro caracte-
res (ab). Nótese que se puede usar 
como delimitador cualquier ca-
rácter ASCII que no forme parte 
de la cadena a. 
Constante. a es una cadena de ca-
racteres ASCII cuyos valores es-
(/VL, a, (J,) 
LENGUAJE DE PROGRAMACION CONVERT 
tán entre 64 y 95 (@, A, B, ... , 
z, [,\,],"y_). Cada carácter 
de la cadena a se mapea a un ca-
rácter de control ASCII restándo-
le 64 a su valor, y casa sólo con el 
carácter de control correspon-
diente. (Los caracteres de control 
tienen valores entre O y 31.) Por 
ejemplo, ("MJ) casa con los ca-
racteres ASCII CR (retorno de 
carro) y LF (avance de línea), en 
ese orden. 
Intervalo lexicográfico, a y /J son 
cadenas ASCII que no contienen 
a los delimitadores "," Este 
patrón casa con la subcadena más 
corta del texto (llamémosla T ), 
que satisfaga la desigualdad a<; T 
<; /J, donde "<; " es la relación de 
orden lexicográfico inducida por 
el código ASCII. Si la cadena a es 
nula, casa trivialmente con la ca-
dena nula; si (J es la cadena nula, 
el patrón se interpreta de modo 
que sólo se requiere la desigual-
dad a <T. Por ejemplo, 
(IVL/ A/Z/) casa con cualquier 
letra mayúscula (una sola). Al 
igual que en el caso de QUO, los 
delimitadores pueden ser cual-
quier carácter ASCII no conteni-
do en las cadenas delimitadas. El 
orden lexicográfico se define co-
mo sigue: una cadena de m carac-
teres es igual a una de n caracte-
res si y sólo si n = m y ambas 
cadenas constan de la misma su-
cesión de caracteres; una cadena 
de n caracteres es mayor que otra 
de m caracteres si existe un entero 
k entre 1 y el menor de m y n tal 
que las cadenas coinciden en los 
primeros k - 1 caracteres y el k-
ésimo carácter de la primera ca-
dena es mayor que el correspon-
diente de la segunda, y una cade-na de n caracteres es mayor que 
una de m caracteres si n > m y los 
primeros m caracteres de la pri-
mera cadena son idénticos a los 
caracteres correspondientes de la 
<()> 
< [a]> 
<--> 
<> 
< :a:> 
<a> 
67 
segunda. 
Nido de paréntesis. Este patrón pri-
mitivo casa con una cadena que co-
mienza con un paréntesis izquierdo 
y termina con el paréntesis de-
recho que lo equilibra, y que pue-
de contener otros caracteres. Por 
ejemplo, < ( )> casa con toda la 
cadena ((a+ b) + c-(d!(e-j))), 
pero sólo casa con los prime-
ros seis caracteres de la cadena 
(()())( ). 
Cadena de longitud fija. a es una 
cadena de dígitos ASCII (que 
representa a un entero) o un es-
queleto cuyo valor es una cadena 
que representa a un entero. Si el 
entero representado es n, casa 
con los primeros n caracteres del 
texto con el que se compara; no 
casa si el texto tiene menos de n 
caracteres o si a es un esqueleto 
cuyo valor no resulta en un en-
tero. 
Cadena indefinida. Casa con 
cualquier cadena; por lo general 
se emplea concatenado con otros 
patrones. Por ejemplo,<--> ab 
casa con cualquier texto que con-
tenga a la cadena ab; en particu-
lar, casa con ab, xab, y 0123ab. 
Fin del texto. Casa únicamente 
con la cadena nula en el extremo 
derecho del texto. Por ejemplo, 
< --> a casa con cualquier texto 
que contenga a la letra a, mien-
tras que<--> a<> sólo casa 
con textos cuyo último carácter es 
la letra a. 
Referencia a un patrón definido. 
Este patrón representa al patrón' 
definido con el nombre a en la lis-
ta de definiciones de patrones; a 
puede ser cualquier carácter alfa-
numérico ASCII ( dígito o letra 
mayúscula o minúscula). 
Variable. a es un entero entre O y 
31. Una variable no ligada (es de-
cir, una a la que no se le ha asig-· 
68 
(and, ff 1, ••• , nn) 
G. CISNEROS Y H. V. McINTOSH 
nes n 1 , . . . , n n casan todos con 
la misma porción del texto. Si el 
primer patrón, n 1 , casa, queda 
decidida con ello la longitud de la 
subcadena con la que deben casar 
los demás patrones. (and, n) es 
equivalente a n y (an<I) siempre 
casa con la cadena nula. 
nado un valor) casa con la subca-
dena de menor longitud posible 
que haga que case el patrón ente-
ro en el que aparece, excepto cuan-
do la variable es la última compo-
nente del patrón, en cuyo caso ca-
sa con todo el texto restante hasta 
el extremo derecho. Si la variable 
está ligada, casa sólo con un texto 
idéntico al valor que tiene asigna-
do. En particular, si la misma va-
riable aparece dos o más veces en 
el mismo patrón, debe casar en 
cada instancia con la misma sub-
cadena. Por ejemplo, el patrón 
< O> aislado casa con el texto 
completo; < O> ab casa con cual-
quier cadena que contenga a la 
subcadena ab y asocia a la va-
riable O con el texto que haya a la 
izquierda de ab (que puede ser la 
cadena nula) y < O> :< O> casa 
con cadenas en las que el mismo 
texto aparece a la izquierda y a la 
derecha del símbolo " : " y asigna 
dicha cadena a la variable O. En 
cambio~ <O>:< 1 > casa con 
cualquier cadena que contenga 
al símbolo ": " y liga a las va-
riables O y 1 con las cadenas que 
aparezcan a la izquierda y a la de-
recha del " : ", respectivamente; 
como ejemplo final, el patrón 
(AND, n1 , ••• , nn) 
< O.> < 1 > casa con cualquier tex-
to, la variable O casa con la cade-
na nula (que es la menor posible) 
y la variable 1 casa con el resto 
del texto. 
Concatenación. La concatena-
ción de n patrones casa con un 
texto T si cada patrón n; casa con 
una subcadena T; de T y T se puede 
expresar como una concatena-
ción T=T¡T2 ... TnTn+1,dOnde 
T n + 1 es un residuo (posiblemente 
nulo) que no hace falta analizar 
para que el patrón entero case. 
Conjunción booleana. n,, ... , 
nn son patrones; el patrón com-
puesto casa si y sólo si los patro-
(OR, n 1 , ••• , nn) 
(NOT, n) 
Conjunción booleana. Su opera-
ción es enteramente análoga a la 
de and, excepto que si alguno de 
los patrones n; falla, AND desliga 
a las variables que pudieran ha-
ber ligado los patrones nk, k< i, 
mientras que and no lo hace. Esto 
sólo es importante cuando se usa 
la conjunción dentro de la nega-
ción booleana, (NOT, n). 
Disyunción booleana. Casa si al-
guno de los patrones que lista ca-
sa con el texto; la comparación de 
patrones con texto se hace de iz-
quierda a derecha, de modo que 
el orden en que se listan los patro-
nes es importante. El patrón (or) 
siempre es falso; si en una conca-
tenación de la forma (or, 
n 1 , ••• , nn) n alguno de los 
patrones n1 (i < n) casa y subse-
cuentemente el patrón n no casa, 
or no prosigue a probar el patrón 
n1 + 1 , sino que el patrón entero 
falla. 
Disyunción booleana. Análogo 
en operación al patrón or, pero sí 
continúa probando alternativas 
en el caso de la concatenación 
mencionada al final de la descrip-
ción precedente. 
Negación. Si el patrón n casa con el 
texto, (NOT, n) falla; en caso con-
trario, (NOT, n) casa con la cade-
na nula o con el resto del texto se-
gún aparezca o no otro patrón a la 
derecha de (NOT, n). Por ejemplo, 
el patrón (an<J< [1]>1, (NOT,A)) 
casa con una cadena de un carác-
ter que no case con la letra A. 
LENGUAJE DE PROGRAMACION CONVERT 69 
(ITR, n) 
(itr, n) 
<< a>> 
Iteración máxima. Casa con eJ 
máximo número de subcadenas 
contiguas del texto que casen 
(cada una por separado) con el 
patrón n. Por ejemplo, 
(ITR,(IVL,0,9,)) casa con cero o 
más digitos decimales, según el 
contenido del texto. 
Iteración mínima. Casa con el 
mínimo número de subcadenas 
contiguas del texto que casen (ca-
da una por separado) con el patrón 
n. Para que itr case con una cade-
na no nula, es necesario que apa-
rezca al menos en una concatena-
ción de la forma (itr, n)n,, de mo-
do que el patrón n, es el que deci-
de cuántas instancias de texto que 
case con n son necesarias para 
que el patrón entero case. 
Patrón nulo. a puede ser cual-
quier cadena de caracteres ASCII, 
incluyendo caracteres de control. 
Se usa para separar un patrón 
largo en dos o más renglones, de 
modo que el par "< < " apare-
ce al final de un renglón y el par 
"> > " se coloca al principio del 
siguiente. 
Para finalizar esta sección, mencionaremos que se 
cuenta en Convert con tres patrones para rastrear la 
ejecución de un programa: (PWS, a), que escribe en 
la consola el rótulo opcional a y el texto restante en el 
área de trabajo; (PVR, a), que despliega en la conso-
la el valor ligado a la variable a, y (HLT, a), que 
despliega el rótulo opcional a y detiene el proceso 
hasta que se oprime alguna tecla en la consola. 
3. ESQUELETOS 
Los esqueletos son las partes de las reglas que de-
terminan el nuevo contenido del área de trabajo una 
vez que queda decidida una transformación. Convert 
cuenta con esqueletos constantes, variables, funcio-
nales, condicionales e iterativos. 
Todo esqueleto tiene como valor alguna cadena de 
texto y deja en el área de trabajo dicho texto al ser 
ejecutado. A continuación se listan las diversas for-
mas que pueden tomar los esqueletos. 
Esqueleto Descripción 
a Constante. La cadena a puede contener 
cualquier carácter imprimible ASCII 
excepto los paréntesis redondos, los pa-
réntesis angulares, la coma, el apóstrofo 
y las comillas. Su valor es la misma cade-
na a. 
<(> 
<)> 
(<) 
(>) 
<,> 
<'> 
< "> 
Constante. Su valor es el paréntesis re-
dondo izquierdo. 
Constante. Su valor es el paréntesis re-
dondo derecho. 
Constante. Su valor es el paréntesis an-
gular izquierdo. 
Constante. Su valor es el paréntesis an-
gular derecho. 
Constante. Su valor es la coma. 
Constante. Su valor es el apóstrofo. 
Constante. Su valor es el carácter co-
millas. 
(QUO/a/) Constante. Su valor es la cadena a, 
que puede contener cualquier carácter 
ASCII excepto el delimitador "/". 
Por ejemplo, el esqueleto (QUO*(a,b)*) 
tiene el mismo valor que el esqueleto 
< ( > a< , > b< ) > . 
< a> 
< => 
(/) 
Constante. a es una cadena de caracteres 
ASCII cuyos valores están entre 64 y 95 
(@,A,B, ... , Z, [~ ,]," y _). El valor 
delesqueleto es una cadena de caracteres 
de control obtenida de la cadena a res-
tándole a cada carácter de ésta 64. Por 
ejemplo, el valor de("/) es el carácter HT 
(tabulador horizontal). 
Variable. a es un entero entre O y 31; su 
valor es el que haya sido ligado con ella 
durante la comparación patrón-texto. 
Variable. Su valor es la totalidad del tex-
to existente en el área de trabajo durante 
la última comparación patrón-texto; sólo 
se puede emplear en posiciones en las que 
el área de trabajo no ha sido modificada 
por otros esqueletos, luego de la compa-
ración aludida. 
Función sin argumento. El valor de este 
esqueleto es el que resulta de ejecutar la 
70 G. CISNEROS Y H. V. McINTOSH 
función de nombre/, que puede ser una 
subrutina definida en Convert, un es-
queleto incluido en la lista de defini-
ciones de esqueletos o una función inter-
na proporcionada por el compilador. En 
cualquier caso, la función/ recibe la ca-
dena nula en el área de trabajo. 
(/,o) Función con argumento. Similar al ante-
rior, pero la función/ recibe en el área de 
trabajo el texto que resulte de evaluar el 
esqueleto o. 
<<a>> Esqueleto nulo. a puede ser cualquier ca-
dena de caracteres ASCII, incluyendo 
caracteres de control. Se usa para sepa-
rar esqueletos largos en dos o más ren-
glones, de modo que el par " < < " 
aparece al final de un renglón y el par 
" > > " aparece al principio del siguien-
te. 
Para la discusión de los esqueletos condicionales e 
iterativos, se introduce la siguiente convención: los 
corchetes indicarán que la entidad sintáctica que en-
cierran puede presentarse en cero o más instancias, y 
los paréntesis cuadrados se usarán para indicar aque-
llas entidades de las que pueda aparecer cero o una 
instancia. Por entidad sintáctica se quiere decir la 
concatenación completa de comas, patrones o es-
queletos contenida en los corchetes o paréntesis cua-
drados. De este modo, { ,n,o 1 ,o2 } indicará que se 
pueden escribir en el esqueleto correspondiente y en 
el lugar indicado, cero o más ternas patrón-
esqueleto-esqueleto con comas en los lugares indica-
dos, mientras que [,o] indica que en el lugar que esto 
ocurre se puede escribir opcionalmente una coma se-
guida de un esqueleto. 
Los esqueletos condicionales son los siguientes: 
(if, 01, n1 ,o,1{ ,o;, n;, o,¡} [,o1]) 
(/F,(w),01 ,n1 ,o,1 { ,o;, n;,o,¡} [,o1]) 
(n/,o1 ,n1 ,o,1 { ,o;, n;,o,1 } [,o1]) 
(NF,(w),o1 ,n1 ,o,1{ ,o;,ff;,o,) [,o1]) 
en donde (w) es una lista de variables (cero o más nú-
meros entre O y 31, con un espacio en blanco entre ca-
da par), las o representan esqueletos y las n represen-
tan patrones. En el esqueleto if, se compara el texto 
generado por 0 1 con el patrón n, . Si casan, el texto fi-
nal resultante es el valor de o,1 • En caso contrario, se 
procede de manera similar con cada terna esqueleto-
patrón-esqueleto; si todas las comparaciones fallan, 
el valor del esqueleto if es el valor del esqueleto o1 , a 
menos que éste no aparezca, en cuyo caso el valor es 
el del último esqueleto evaluado para una compara-
ción (el primero de la última terna). Cada esqueleto 
ok sólo se evalúa si la comparación previa entre ºk- J y 
nk-, falla. 
El esqueleto IF opera de modo enteramente análo-
go al if, pero en aquél, los patrones nk pueden ligar a 
las variables de la lista (w) para ser utilizadas en los 
esqueletos correspondientes o,k. Las variables 
quedan desligadas (indefinidas) al principio de cada 
comparación que sea necesario efectuar. Si el es-
queleto inicial 0 1 contiene variables, se entiende que 
éstas representan a variables definidas y ligadas afue-
ra del esqueleto IF, independientemente de las va-
riables indicadas en la lista (w). 
El esqueleto nf es similar al if, pero la compara-
ción se hace de modo negativo: el resultado es o,k si nk 
no casa con ºk• es decir, se deja o,k a menos que nk ca-
se con ok; si todos los patrones nk casan con los textos 
generados por los esqueletos respectivos ok, el resul-
tado es el valor de o1 , o del último ok en caso de omi-
tirse o1. Finalmente, NF tiene operación idéntica a la 
de nf, pero con uso de variables, como se describe en 
el párrafo referente al esqueleto /F. 
Como ejemplo de esqueleto condicional, considé-
rese el esqueleto 
(if,(0/oR),(A'Z),< => (0/ot,Fin dedatos),(%T,< =>)) 
en el que la función (UJoR) tiene como valor una línea 
leída del teclado de la consola, (0/ot,o) escribe en la 
consola el valor del esqueleto o y su valor es la cadena 
nula y (o/o T, o) escribe en la consola el texto dado por 
o y su valor es ese mismo texto. El esqueleto if se eva-
lúa como sigue: se lee una línea y se compara con el 
patrón (" Z); si casan, se deja en el área de trabajo la 
línea leída y se escribe en la consola la cadena "Fin de 
datos", en caso contrario la línea leída se escribe y se 
deja en el área de trabajo. 
Para terminar esta sección se da la descripción de 
los esqueletos iterativos, son los siguientes: 
(while, o1, n,, o, ,o,1{, n¡, o;,o,;} [, op]) 
(WHILE,(w),o1,n1 ,o1 ,o,1{ ,n¡,o1,o,;} [,op]) 
(until, o1, n, ,o, ,o,, {, n1, o1, o,1 } [, op]) 
(UNTIL,(w),o1,n1 ,o1,o,1{, n1,o1,o,;} [,op]) 
LENGUAJE DE PROGRAMACION CONVERT 71 
donde, al igual que en los esqueletos condicionales, 
las o representan esqueletos, las n representan patro-
nes y (w) representa una lista de variables. WHILE 
opera igual que while y UNTIL opera igual que until, 
excepto que los patrones de WHILE y UNTIL 
pueden ligar las variables de la lista (w). Describimos 
el esqueleto while en detalle y until en términos de és-
te. 
En el esqueleto while: 
(i) Se coloca el valor del esqueleto inicial 01 en el 
área de trabajo. 
(ii) Si el patrón n1 casa con el texto, se evalúa 0 1 y su 
valor queda como parte del valor final en lugar 
del texto usado en la comparación; el esqueleto 
o,1 se evalúa y el texto resultante se usa en una 
nueva comparación con el patrón n1 • Este paso 
se repite hasta que n1 ya no casa con el texto que 
se le presente. 
(iii) El último texto generado por 0,1 en el paso (ii) 
(o el generado por o1 si n1 no casó desde el pri-
mer intento) se usa como texto inicial para com-
parar con el patrón siguiente, y ocurre una ite-
ración como la del paso (ii) sobre la terna pa-
trón-esqueleto-esqueleto correspondiente. 
(iv) Se ejecutan iteraciones similares para cada ter-
na; cuando el último patrón, nn, deja de casar 
con el texto con el que se le compara, su último 
residuo o queda como parte del texto final, a 
'n 
menos que esté presente el esaueleto final oF, en 
cuyo caso su valor sustituye al texto que no casó 
por última vez. 
Por lo anterior, el valor del esqueleto while es una 
concatenación de cero o más instancias de 0 1, 
o2, ••• , on y el valor de oF o el último de o,n; el núme-
ro de instancias de cada ok depende del número de ite-
raciones que ocurran en cada terna. 
El esqueleto until opera de manera similar al while, 
excepto que la iteración continúa en tanto el pa-
trón no case con el texto. En los esqueletos WHILE y 
UNTIL las variables quedan libres (indefinidas) al 
principio de cada iteración para que el patrón pueda 
ligarlas a valores nuevos. 
Un ejemplo de esqueleto iterativo es el siguiente: 
( WHILE,(0),(0/oR),(NOT, < -- > (" Z)), << 
>> < =>,(0/oR),<O>("Z),<O> ,) 
Este esqueleto lee una o más lineas de la consola y las 
deja concatenadas en el área de trabajo hasta en-
contrar una que contenga el carácter control-Z, de la 
cual deja la porción que preceda a dicho carácter. 
4. REGLAS DE TRANSFORMACION Y 
EJEMPLOS 
La parte medular de un programa en Convert es la 
lista de reglas. Una regla consiste de un patrón y un 
esqueleto separados por una coma y encerrados en 
paréntesis, y va seguida por el carácter punto y coma 
(;) o el carácter dos puntos (: ), que indica que la 
regla es terminal o repetitiva, respectivamente. La 
aplicación de las reglas se puede tipificar mediante la 
frase "si se ve esto, hágase esto otro", es decir, se 
compara el texto del área de trabajo con el patróncontenido en la regla, y si el texto tiene la forma des-
crita por el patrón (es decir, si el patrón "casa" con 
el texto), se sustituye el esqueleto en lugar del texto 
(es decir, se evalúa el esqueleto y su valor queda en 
lugar del texto original); en este caso, el símbolo que 
sigue a la regla (: o ;) determina si se debe repetir la 
aplicación de las reglas (desde el principio) sobre el 
texto nuevo o si se debe terminar, respectivamente. Si 
el patrón no casa con el texto, se procede a aplicar la 
siguiente regla (es decir, a verificar si el patrón de la 
siguiente regla casa con el texto), y si no hay más re-
glas, el programa termina y el texto permanece sin 
cambio. 
Como ejemplo de programación en Convert, con-
sidérese la función de la figura 1, que ilustra algunas 
rfp liu: características más importantes del lenguaje. 
[invierte una cadena] 
(()()(0 1)( 
( ( and , < [ 1 ] > , < O> ) < 1 > , ( u , < 1 > ) < O> ) 
) ) u 
Fig.1. 
En esta función, cuyo nombre, u, aparece en seguida 
de su definición, se tiene: 
- Una lista nula de definiciones de patrones, 
- Una lista nula de definiciones de esqueletos, 
- Una lista en la que se declaran dos variables: O 
y 1, 
- Una lista de reglas que contiene una sola regla, 
en la que el patrón es (and,< [l]> ,<O>)< 1> 
y el esqueleto es (u,< 1> )< O> . 
El texto encerrado en paréntesis cuadrados es un 
comentario que se incluye únicaipente con propósitos 
de documentación y no afecta la compilación ni la 
ejecución del programa. 
Procedemos ahora a analizar el patrón. 
(and, < [ 1 ]> t:, O> ) es un ejemplo de patrón boolea 
72 G. CISNEROS Y H. V. McINTOSH 
no, que en este caso específico se trata de un patrón 
que casa con el texto o una subcadena del mismo si y 
sólo si los dos patrones < [ 1 ]> y < O> casan con la 
misma subcadena. A su vez< [I]> es un patrón que 
casa con una cadena de longitud 1 (es decir, casa 
exactamente con un carácter) y< O> es el patrón va-
riable O, que, si no ha sido ligado previamente a una 
cadena (lo cual corresponde al caso que estamos ana-
lizando) casa con la subcadena de menor longitud po-
sible que haga que el patrón entero del que forma par-
te también case, o casa con todo el resto del texto si es 
el último componente del patrón en que se encuentra. 
De este modo, en el patrón (and, < [ 1] > , < O> ), el 
patrón< O> es el único y último componente del se-
gundo patrón incluido en la combinación booleana 
and, de modo que al no estar ligado casará con el 
mismo texto que el patrón < [l] > (una cadena de 
longitud 1). El patrón,< I> , al ser el último compo-
nente del patrón de la regla estudiada y no estar ligado a 
un valor (no puede estarlo ya que no aparece pre-
viamente en el mismo patrón), casará con el resto 
del texto, es decir, con el texto que siga al carácter 
que casa con el patrón and. El patrón completo 
(and, < [I]> ,<O>)< I> sólo falla cuando el texto 
contenido en el área de trabajo es nulo, porque sólo 
entonces falla el patrón < [Í] > y con él, el patrón 
and y el patrón completo. 
Pasamos ahora al análisis del esqueleto, 
(u,< l > )< O> . Este indica que el nuevo texto que 
ocupará el área de trabajo se forma concatenando las 
cadenas de texto representadas por (u,< I>) y 
< O> . < O> como esqueleto es simplemente el texto 
que se asoció con la variable O al verificarse la corres-
pondencia entre patrón y texto. (u,< l >) es un es-
queleto cuyo valor es el texto resultante de aplicarle 
la función u al valor de la variable 1. Nótese que este 
es un ejemplo de programación recursiva, en el que la 
solución del problema "invertir una cadena" se des-
cribe como sigue: "Sea x una cadena den caracteres. 
Si n> O, entonces x = yz, donde y es una cadena de l 
carácter y z tiene n-1 caracteres; luego la cadena x in-
vertida es la cadena z invertida seguida de la cadena 
y. Si n = O, la cadena x invertida es la misma cadena x 
(la cadena nula)". 
La recursividad implica que cada invocación de 
una función causa que se creen nuevas instancias de 
las variables que la función declara. En el ejemplo 
que nos ocupa, si el texto inicial es abcd, las llama-
das sucesivas a u (incluyendo la primera) asignarán a 
< O> los valores a, b, e y d, y a< 1> los valores bcd, 
cd, d y la cadena nula, con lo que los esqueletos en 
llamadas sucesivas serán (u,bcd)a, (u,cd)b, (u,d)c y 
(u,)d, de donde se puede sustituir en reversa: (u,)= la 
cadena nula, y por tanto (u,d)=(u,)d=d, 
(u,cd)=(u,d)c=dc, (u,bcd)=(u,cd)b=dcb y 
(u,abcd) = (u,bcd)a = deba. 
[programa principal: lee líneas, las in-
vierte y las escribe, hasta encontrar 
una que comienza con el carácter "con-
trol-Z"] 
(()()()( 
(("Z),)¡ 
(, (%t, (u,<=>)) (%R)): 
) ) 
Flg. 2. 
Convert requiere que exista un programa principal 
para poder ejecutar un proceso. Para nuestro ejem-
plo, el programa principal podría ser el que se 
muestra en la figura 2. El programa principal se dis-
tingue por ser el último en ser presentado al compila-
dor y por no tener asignado un nombre (el cual, co-
mo se mencionó antes, aparecería enseguida del pa-
réntesis derecho final). En el programa de la figura 2 
la primera regla es terminal ( el programa para si el 
primer carácter del texto es el carácter "control-Z", 
representado por el patrón (AZ}) y la segunda regla es 
repetitiva; en ésta el patrón es nulo y por ello casa 
con cualquier texto, que a su vez es asignado como 
valor del esqueleto < = > . Como en la segunda regla 
el patrón siempre casa, el esqueleto correspondiente 
es evaluado: (u,< => ) invierte el texto representado 
por < = > , (O'/ot,(u, < = > )) escribe en la consola 
el resultado de evaluar la función u con argumento 
< => y deja la cadena nula, y (O'/oR) lee de la consola 
una línea, dejándola en el área de trabajo; sobre el 
texto leído se repite la acción del conjunto de reglas. 
Como último ejemplo se presenta el programa de 
la figura 3, que constituye una aplicación sencilla pe-
ro no trivial de Convert. Este programa encuentra to-
das las trayectorias que no tienen ciclos cerrados en-
tre un par dado de nodos de un laberinto, es decir, de 
una gráfica en la que no hay más de un arco entre cual-
quier par de nodos de la misma 5• El programa lee y 
verifica los datos, que deben tener la forma (i f e), 
donde i es el identificador del nodo inicial,/ el del no-
do final y e es una lista de conexiones de la forma (na 
(nal . . . nak) . .. nz(nzl . .. nZ'.))), donde na, nz, 
etc., son identificadores de nodos del laberinto, nal, 
. . . , nak son los nodos conectados por arcos con na 
y nzl, . . . , n~ son los nodos que tienen conexiones 
con nz en el laberinto. La subrutina M resuelve el 
problema recursivamente: Se. listan las trayectorias 
del nodo inicial a sus primeros vecinos junto con las 
trayectorias desde éstos hasta el nodo final. La condi-
LENGUAJE DE PROGRAMACION CONVERT 
ción terminal ocurre cuando se está ya en el nodo fi-
nal. Se evitan los ciclos retirando de la lista de cone-
xiones las conexiones de los nodos ya considerados. 
La figura 4 muestra un laberinto en el que el nodo 
inicial se denota por A y el nodo final por B; la figura 
S muestra el mismo laberinto expresado en la forma 
requerida por el programa de la figura 3 y la figura 6 
muestra el resultado producido por el programa. 
[TRAYEC.CNV) 
[G. Cisneros, 6.6.84) 
[Exclude ALL) 
[ [ 
Fig. 4. 
rrayectorias de un laberinto: 
(ni nf (na (nal na2 ••• nak) nz ( nz 1 • . • nz j) ) ) ) ] 
[calcula las trayectorias) 
( () () (O 1 2 3 4) ( 
(<(>(and,<:n:>,<O>) <O> <-->/<l>,<l> <O><)>); 
(<(>(and,<:n:>,<O>) (and,<:n:>,<l>) <2><< 
>>(or, <0>,<0>) <(><3><)>(or, ,)<4>,<< 
;>;>(WHILE, (5 6) ,<3>, (and,<:n:>,<5>) (or, ,)<6>,<< 
2 
>>(if, (M,<(><5> ~l> <2><4>(if,<0>,<9><>,, )<O>),$,),<< 
>><6>)); 
( , $) ; 
)) M 
[verifica datos, llama a M) 
(( [lista de definiciones de patrones) 
( (or, (IVL,A,Z,), (IVL,a,z,), (IVL,0,9,))) a 
( < : a:> ( ITR, < : a:>) ) n 
( < ( > ( or, < : n: > ( ITR, < : n: >) , ) <) >) 1 
(<:n:> <:l:>) p 
) () (O 8 9) ( 
[lista de reglas)(("Z),); 
((and,<(>(and,<:n:>,<9>) (and,<:n:>,<8>)<< 
> > < ( > < : p: > ( ITR, < : p: >) <) > <) >,<O>) , < < 
>>(%t,Inicial: <9>; Final: <8>)<< 
>>(%t,(WHILE,(1 2),<< 
>>< (> (if, (M,<0>/< (>) ,$,) <) >,<< 
>>(and,<[65)><--><)>,<1>)<2>,<< 
»<l> ("MJ) ,<2>,<=> ("MJ))) (%R)): 
(<>, (%R)): 
(,(%t,no es laberinto) (%Q) (%R)): 
)) 
[alfanurn) 
[nombre) 
[lista de nodos) 
[nodo y vecinos) 
Fi1. 3. 
Fig. S. (A B (A ( 1 2 3) 1 (A 2 3 B) 2 (A 1 3 B) 3 (A 1 2 B) B ( 1 2 3) ) ) 
( (A 1 2 3 B) (A 1 2 B) (A 1 3 2 B) (A 1 3 B) (A 1 B) (A 2 1 3 B) (A 2 1 B) 
(A 2 3 1 B) (A 2 3 B) (A 2 B) (A 3 1 2 B) (A 3 1 B) (A 3 2 1 B) (A 3 2 B) 
(A 3 B)) Fig. 6., 
73 
8 
74 G. CJSNEROS Y H. V. McINTOSH 
5. DISCUSION Y CONCLUSIONES 
Entre las aplicaciones más sobresalientes de la ver-
sión actual de Convert se encuentran los siguientes 
programas: 
- Diversos ejemplos pedagógicos, v. gr., compila-
dores de algoritmos de Markov, de máquinas de 
Turing, de sistemas de producción de Post y del 
lenguaje de programación C. 6 
- 80T86, un traductor automático de programas 
escritos en lenguaje ensamblador del procesa-
dor 8080 a ensamblador del procesador 8086. 
- XREF, un generador de listados de interrefe-
rencias, auxiliar para el desensamblado de pro-
gramas. 
- HAMEL, un sistema de 18 programas para ma-
nipulaciones y reducciones algebraicas que ob-
tiene de manera simbólica elementos de matriz 
del problema mecanocuántico de la interacción 
de configuraciones 7• 
En cuanto a la eficiencia de Convert en su forma 
presente, el programa 80T86 permite establecer una 
comparación entre un proceso expresado en Convert 
y el mismo proceso escrito en ensamblador. Después 
de usar la versión en Converf durante varios meses, 
se escribió una versión en ensamblador; ésta requirió 
1/20 de la memoria y correr 10 veces más rápidamen-
te que aquélla. No obstante, el programa en Convert 
fue escrito en pocas horas y proporcionó una expe-
riencia que resultó de gran valor al momento de in-
tentar escribir el mismo programa en lenguaje de má-
quina. Además, se puede afirmar que si en la traduc-
ción de código efectuada por 80T86 se intentara lle-
var a cabo un análisis de más de una instrucción a la 
vez, sería mucho más fácil escribir dicho análisis en 
Convert que en lenguaje de máquina. 
El hecho de que la rapidez y facilidad de progra-
mación resulte proporcional a la memoria requerida 
y al tiempo de ejecución, no es privativo de Convert, 
sino que se observa también en comparaciones entre 
programas expresados en otros lenguajes de alto ni-
vel y los mismos programas escritos en lenguaje de 
máquina. Específicamente se ha observado un factor· 
de magnitud similar en programas escritos en C o 
Pascal. 
Se espera usar Convert para escribir, entre otros 
programas, compiladores de FORTRAN y C que pue-
dan aprovechar las arquitecturas de procesadores 
aritméticos existentes, como el Intel 8087 y el 
Amd9511, y generadores de programas en FORTRAN 
para producción de gráficas con superficies ocultas, 
aprovechando las subrutinas del paquete PLOT84. 
Agradecimientos 
Uno de los autores (G.C.) agradece al Departamento 
de Aplicación de Microcomputadoras del Instituto de 
Ciencias de la Universidad Autónoma de Puebla las 
facilidades brindadas durante el ejercicio de su año 
sabático, del cual surgió este trabajo. El mismo autor 
agradece el apoyo recibido de la Comisión de Opera-
ción y Fomento de Actividades Académicas del IPN 
a través de su programa de becas por exclusividad, y 
del Sistema Nacional de Investigadores, al cual perte-
nece. 
REFERENCIAS 
l. Guzm,n A., and Mclnto8b H. V.: "CONVERT", Comm. 
ACM!>: 604 (1%6). 
2. Guzmu A. A.: CONVERT, Tesis profesional, ESIME, IPN 
(196S). 
3. Mclntosb, H. V.: "A CONVERT compiler of REC for the 
PDP-8", Acta Mex. de Ciencia y Tecnol., 2: 33 (1968). 
4. Clsneros, G.: "A FORTRAN-coded Regular Expression Com-
piler for the IBM 1130 Computing System", Acta Mex. de 
Ciencia y Tecnol., 4: 30 (1970). 
S. Guzmu A. and Mclntosb H. V.: "Comments on 'Ali paths 
through a maze' ", Proc. IEEE, SS: 1S2S (1967). 
6. Kernlgban B. W. and Rltcble D. M.: The C Programming Lan-
gua,e (Englewood Cliffs: Prentice-Hall, 1978). 
7. Clsneros, G., Bunae C. F. and Mclntosb H. V.: "Automatic 
Generation of Configuration lnteraction Hamiltonian Matrix 
Elements", /ni. J. Quantum Chem. 518: 683 (1984).