Vamos tentar escrever em Lisp ... um tradutor de uma linguagem imperativa simples. Não, não, não me enganei - é o tradutor. Será transmitido no código Lisp. E então esse código pode ser executado pelo sistema Lisp.
Aqui, o serviço inestimável será fornecido pelo fato de que no Lisp não há barreira entre código e dados (essa é uma propriedade rara de algumas linguagens de programação denominadas “homo-identidade”). Mas os recursos visuais do Lisp também terão um papel importante.
Como implementação, usarei o HomeLisp . Os interessados podem adaptar este projeto ao Common Lisp. Eu direi imediatamente - em relação ao problema em consideração, a diferença significativa entre o Common Lisp e o HomeLisp está apenas no processamento de linhas e arquivos.
Baixe uma versão portátil do HomeLisp aqui . A documentação também está localizada no mesmo site. Quem desejar pode copiar o código do artigo e verificar imediatamente o desempenho.
O tópico que chamou sua atenção serviu de base para minha oficina no famoso Novosibirsk LSHUP-2018 . Os resultados do workshop podem ser encontrados aqui . E então eu expus minha abordagem. Suponho que o leitor esteja familiarizado com a linguagem Lisp.
Descer
Vamos começar com a "linguagem imperativa simples" que transmitiremos no Lisp.
O idioma processará apenas dados numéricos. O código nesse idioma consiste em funções (procedimentos que retornam valores). Entre essas funções, uma deve ser chamada de principal. É com essa função que a execução do código começa. Embora por que se vincular assim? Nós escrevemos funções em uma linguagem imperativa, elas são transmitidas em Lisp e podem ser usadas junto com as funções Lisp. Mas não vamos nos antecipar ...
O conjunto de operadores de idiomas é usual: atribuição, ramificação, ciclo aritmético, saída antecipada do ciclo, entrada, saída e chamada de função. No entanto, sintaticamente uma chamada de função é executada como uma atribuição (resultado de uma chamada). Deixe os comentários conterem um asterisco na primeira posição da linha. A linguagem, é claro, deve fornecer a capacidade de criar funções recursivas. Para tornar mais claro, darei exemplos de código - imprimindo números ímpares sucessivos e calculando sua soma:
proc main() local s,n,k input n for i=1 to n k=2*i-1 print k s=s+k end_for print s end_proc
Em seu espírito, é uma linguagem básica. Vou chamá-lo de "mini-básico". Nosso tradutor deve converter o código fornecido para a seguinte função Lisp:
(defun main nil (let ((s 0) (n 0) (k 0)) (setq n (read)) (iter (for i from 1 to n) (setq k (- (* 2 i) 1)) (printline k) (setq s (+ sk))) (printline s)))
Eu realmente gosto do pacote iterado , que é implementado como uma macro nos pacotes profissionais do Common Lisp. No HomeLisp, a função iter (que implementa grande parte dos recursos da iteração de macro) está incluída no idioma principal. Foi meu vício em iter que fez com que os ciclos de nosso “mini-básico” fossem traduzidos em chamadas iter.
Por onde começar a implementação? Vamos começar selecionando o arquivo a ser transmitido e lendo e imprimindo esse arquivo linha por linha. Teremos que iniciar o tradutor muitas vezes, portanto, deixe isso começar desde o início, seja conveniente. Aqui está como essa função pode ser:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (let ((fi (gensym 'fi))) (when fname (filOpen fi fname _INPUT) (loop (getLine fi) (when (or *flagerr* (filEOF fi)) (return t))) (filClose fi) (when *flagerr* (printsline "**** ")))) (unset '*numline*) (unset '*flagerr*))
A função possui um parâmetro opcional fname - o nome do arquivo cujo conteúdo será transmitido. Ao inserir a função, duas variáveis globais são criadas: numLine, número da linha do arquivo de origem e flagerr , o sinalizador de status do erro. Antes de a função terminar, essas variáveis são destruídas (a função HomeLisp desabilita as variáveis globais).
Se o nome do arquivo de entrada for omitido, a caixa de diálogo padrão do Windows para selecionar o arquivo (sysGetOpenName) será chamada. O diretório atual (sysHome) é usado como o diretório inicial. Em seguida, um caractere exclusivo é criado para o manipulador de arquivos e o arquivo é aberto para leitura de texto. Então, em um loop sem fim, o arquivo é lido linha por linha (função getLine ). Após cada operação, é verificado se ocorreu um erro e se o final do arquivo foi atingido. Se ocorrer um erro ou o final do arquivo for corrigido, o ciclo será interrompido, o arquivo será fechado e, se houver erros, uma mensagem final será exibida.
Na verdade, a leitura do arquivo é realizada pela função getLine :
(defun getLine (fil) (let ((stri "")) (loop (when (filEof fil) (return "")) (setq *numline* (add1 *numline*)) (setq stri (filGetline fil)) (printsline (strCat (format *numline* "0000") " " (strRTrim stri))) (setq stri (strATrim stri)) (unless (or (eq "" stri) (eq "*" (strLeft stri 1))) (return stri)))))
Esta função aceita o identificador de um arquivo aberto e, em um loop infinito, executa as seguintes ações:
- verifica o final do status do arquivo. Nesse caso, o loop é interrompido e a função retorna uma string vazia;
- o contador de linhas de leitura aumenta em um;
- a próxima linha do arquivo é lida;
- a linha de leitura é impressa com a remoção de possíveis espaços à direita;
- se a linha de leitura não estiver vazia e não contiver um asterisco na primeira posição,
retorna da função;
Assim, todas as linhas do arquivo em sua forma original caem na listagem de saída.
Invadimos procedimentos
Agora vamos ensinar nosso código a dividir o fluxo de entrada em procedimentos separados. Primeiro, a string inserida precisará ser dividida em tokens (unidades lexicais de entrada indivisíveis). Esse processo é chamado de análise; nós temos que criar um analisador. Escrever analisadores é um tema clássico, existem bibliotecas de analisadores prontos e ferramentas especiais que permitem gerar o analisador necessário ... Vamos seguir nosso próprio caminho.
Antes de descrever o algoritmo do analisador, prestamos atenção ao fato de que todos os caracteres da sequência de entrada podem ser divididos em duas classes:
- Caracteres comuns;
- Caracteres separadores.
Portanto, no operador de atribuição "x = 15 + y ^ 2", os caracteres x, 1,5, ye 2 são caracteres comuns e os caracteres "espaço" , + , ^ são delimitadores. Qual a diferença entre um caractere normal e um separador? Separador - sempre separa um token do outro. Nosso operador de atribuição, sendo dividido em tokens, fica assim: “x”, “=”, ”15”, “y”, “^”, “2” .
Como você pode ver, nem todos os delimitadores se enquadram no resultado da análise (espaços, em particular, não caem). Vamos chamar separadores que não caem no resultado como separadores do primeiro tipo. Outros separadores serão chamados separadores do segundo tipo.
A entrada do analisador será uma sequência, a saída é uma lista de tokens de sequência. Como unidade, uma variável local será usada - a bateria. A bateria contém inicialmente uma corda vazia.
O algoritmo de análise pode ser o seguinte: lemos a linha de entrada caractere por caractere. Se você encontrar um caractere comum, concatene-o com a bateria. Se um delimitador for encontrado, então:
- Para o separador do primeiro tipo, redefinimos o valor da bateria (se não estiver vazio) na lista de saída, limpe a bateria e continue a ler o próximo caractere;
- Para o separador do segundo tipo, também despejamos o valor de uma bateria não vazia na lista de saída e depois inserimos o separador aceito do segundo tipo (como um token independente) na lista de saída, limpe a bateria e prossiga para ler o próximo caractere.
Aqui está o código do analisador:
(defun parser (txt &optional (d1 " ,") (d2 "()+-*/\^=<>%")) (let ((res nil) (lex "") ) (iter (for s in-string (strCat txt (strLeft d1 1))) (cond ((plusp (strInd d1 s)) (when (> (strLen lex) 0) (collecting lex into res)) (setq lex "")) ((plusp (strInd d2 s)) (when (> (strLen lex) 0) (collecting lex into res)) (collecting s into res) (setq lex "")) (t (setq lex (strCat lex s))))) res))
Além do parâmetro necessário, a função possui dois parâmetros opcionais: d1 contém uma cadeia de caracteres, cada caractere com um separador do primeiro tipo e a linha d2 contém separadores do segundo tipo.
A lógica do programa da função analisador é descrita acima. Deve-se observar apenas que, antes de iniciar o trabalho, um separador é anexado ao final da linha de entrada. Isso é feito para que o último token processado fique travado na bateria (a variável local lex desempenha o papel da bateria).
Vamos verificar nosso analisador "em ação":
(parser "x = 15 + y^2") ==> ("x" "=" "15" "+" "y" "^" "2")
Isso mesmo, não é? Mas trabalhar com listas de strings não é exatamente Lisp. Vamos passar da lista de strings para a lista de átomos. Para fazer isso, precisamos de uma função que ... cole todos os tokens novamente em uma linha longa (mas insira um espaço entre os tokens), cole o colchete de abertura no início desta linha, feche o colchete de fechamento no final ... e force Lisp a ler a lista:
(defun mk-intf (txt) (let ((lex (parser txt " ," "()+-*/\^=<>%")) (intf "")) (iter (for a in lex) (setq intf (strCat intf a " "))) (input (strCat "(" intf ")"))))
Agora, se enviarmos o operador de atribuição à entrada da função mk-intf, obtemos:
(mk-intf "x = 15 + y^2") ==> (X = 15 + Y ^ 2)
O que, você vê, é muito melhor.
Agora vamos mudar um pouco a função start: essa função terá que ler e processar procedimentos inteiros:
(defun start (&optional (fname nil)) (setq *numline* 0) (setq *flagerr* nil) (when (null fname) (setq fname (sysGetOpenName (sysHome) "-|*.mbs"))) (when fname (let ((fi (gensym 'fi))) (filOpen fi fname _INPUT) (loop (let ((curr-proc (action-proc fi))) (when (or *flagerr* (filEOF fi)) (return t)) (eval curr-proc))) (filClose fi)) (when *flagerr* (printsline "**** "))) (unset '*numline*) (unset '*flagerr*))
No corpo do loop, a função action-proc é chamada (para processar o procedimento), que formará o corpo do procedimento aceito já no Lisp. O corpo do procedimento, armazenado como uma expressão S na variável curr-proc , é então passado para a entrada de eval . E a função aceita é "reencarnada" no ambiente Lisp!
O que o action-proc deve fazer? Esta função recebe o identificador do arquivo aberto como um parâmetro. A função lê o arquivo linha por linha do arquivo, pula linhas e comentários vazios, analisa o restante das linhas, converte-o em um formulário de lista e gera o corpo do procedimento.
Gradualmente “aprenderemos” a geração de ação-processo . E vamos começar ensinando nossa função a reconhecer o início e o fim de um procedimento. Em um mini-básico, o início do procedimento é:
proc name(p1,p2,p3)
tente analisar uma linha como esta:
(mk-intf "proc name(p1,p2,p3)") ==> (PROC NAME (P1 P2 P3))
Como a função action-proc deve responder a essa entrada? Naturalmente, certificando-se de que o cabeçalho da lista seja um átomo PROC , é necessário considerar o segundo elemento da lista como o nome da função e o terceiro elemento como a lista de parâmetros. O nome e a lista de parâmetros devem ser armazenados em variáveis locais. Quando o operador end_proc é lido , é necessário formar um formulário com o corpo vazio (até o momento) do nome da função e da lista de parâmetros e retornar esse formulário como resultado. Aqui está o que parece:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm (quote OK))))
Para a formação final da cláusula defun , um bloqueio reverso é usado. Observe que o procedimento gerado retornará um átomo OK como resultado.
Agora podemos verificar nosso código em ação. Coloque o seguinte código no arquivo 0000.mbs:
proc f1(x,y) end_proc proc f2(x) end_proc
Execute o procedimento de início , selecione 0000.mbs e veja no console:
0001 proc f1(x,y) 0002 end_proc 0003 proc f2(x) 0004 end_proc
Se desejar, você pode garantir que a máquina Lisp agora tenha duas funções (até agora inúteis) f1 e f2 :
(getd 'f1) ==> (EXPR (XY) (QUOTE OK)) (getd 'f2) ==> (EXPR (X) (QUOTE OK))
Além disso! Eles já podem ser iniciados:
(f1 1 2) ==> OK (f2 2) ==> OK
Nosso tradutor respirou pela primeira vez ...
Variáveis de entrada, saída e locais
Agora é a hora de ensinar nosso tradutor recém-nascido a lidar com os operadores de entrada , impressão e local .
A maneira mais fácil de lidar com entrada e impressão. Ambos os operadores têm a mesma estrutura de sintaxe: palavra-chave e variável. A entrada do operador x deve se transformar em um formato Lisp (setq x (read)) . Assim, o operador de impressão x se transforma em um formulário (linha de impressão x) . Para armazenar esses formulários, você deve fornecer o corpo da variável local na função action-proc . Essa variável acumulará formulários que executam cálculos da função futura. Então tudo é bem simples:
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) `(defun ,proc-name ,proc-parm ,@body)))
Agora vamos preparar este código fonte em um mini-básico:
proc f1(x,y) print x print y end_proc proc f2(x) input x print x end_proc
e tente traduzi-lo ... Teremos duas funções Lisp f1 e f2 . Vamos examinar suas expressões definidoras e garantir que elas sejam geradas corretamente:
(getd 'f1) ==> (EXPR (XY) (PRINTLINE X) (PRINTLINE Y)) (getd 'f2) ==> (EXPR (X) (SETQ X (READ)) (PRINTLINE X))
Você pode chamar essas funções e garantir que elas funcionem exatamente como pretendido. Não incomodá-lo que inserimos o valor na variável de parâmetro - ainda não temos variáveis locais ... Vamos adicioná-las.
O operador local pode estar em qualquer lugar do procedimento e ocorrer mais de uma vez. Se o operador local for encontrado durante o processamento de um procedimento, você precisará pegar uma lista de variáveis e salvá-la em uma variável local. Depois que a instrução end_proc for atendida, você precisará gerar o formulário let e "incluir" todas as instruções executáveis nele (por enquanto, apenas entrada e impressão ). Aqui está como será o action-proc :
(defun action-proc (fi) (let ((stmt nil) (proc-name nil) (proc-parm nil) (loc-var nil) (lv nil) (body nil)) (loop (setq stmt (mk-intf (getLine fi))) (when (null stmt) (return t)) (cond ((eq (car stmt) 'proc) (setq proc-name (nth 1 stmt)) (setq proc-parm (nth 2 stmt))) ((eq (car stmt) 'end_proc) (return t)) ((eq (car stmt) 'print) (setq body (append body (list (cons 'printline (cdr stmt)))))) ((eq (car stmt) 'input) (setq body (append body (list (list 'setq (cadr stmt) (list 'read) ))))) ((eq (car stmt) 'local) (setq loc-var (append loc-var (cdr stmt)))) (t (printsline (strCat "**** " (output stmt) " ")) (setq *flagerr* t)))) (iter (for a in (setof loc-var)) (collecting (list a 0) into lv)) `(defun ,proc-name ,proc-parm (let ,lv ,@body))))
A lista de variáveis locais é acumulada na variável loc-var . Após a conclusão do processamento do procedimento, uma lista de pares do formulário (nome 0) é criada a partir dessa lista. Ao mesmo tempo, a duplicação de nomes idênticos é indesejável ... Como evitá-lo? Obviamente, é possível verificar em cada processamento do operador local se há nomes duplicados (se houver, forneça uma mensagem de erro). Mas, parece-me, é melhor simplesmente eliminar as repetições, que é o conjunto de chamadas . Agora vamos traduzir e executar este programa:
proc f1(x,y) local a,b,c print x print y input a print a end_proc
Garantimos que ele funcione exatamente como o algoritmo sugere. Mas tudo o mais interessante está à frente!
Aqui você pode baixar a versão final do que estamos fazendo w codificado ...
Para ser continuado!