META II - META II
META II é uma linguagem de programação específica de domínio para escrever compiladores . Foi criado em 1963–1964 por Dewey Val Schorre na UCLA . META II usa o que Schorre chamou de equações de sintaxe . Seu funcionamento é simplesmente explicado como:
Cada equação de sintaxe é traduzida em uma sub-rotina recursiva que testa a string de entrada para uma estrutura de frase particular e a apaga se encontrada.
Os programas Meta II são compilados em uma linguagem de código de bytes interpretada. Os compiladores VALGOL e SMALGOL que ilustram suas capacidades foram escritos na linguagem META II, VALGOL é uma linguagem algébrica simples projetada com o propósito de ilustrar o META II. SMALGOL era um subconjunto bastante grande do ALGOL 60 .
Notação
META II foi escrito pela primeira vez em META I, uma versão compilada à mão de META II. A história não está clara se o META I foi uma implementação completa do META II ou um subconjunto da linguagem META II necessária para compilar o compilador META II completo.
Em sua documentação, o META II é descrito como semelhante ao BNF , que hoje é explicado como uma gramática de produção. META II é uma gramática analítica. No documento TREE-META , essas línguas foram descritas como gramáticas redutivas.
Por exemplo, em BNF, uma expressão aritmética pode ser definida como:
<expr> := <term> | <expr> <addop> <term>
As regras BNF são hoje regras de produção que descrevem como as partes constituintes podem ser montadas para formar apenas construções de linguagem válidas. Um analisador faz o oposto separando as construções de linguagem. META II é uma linguagem de programação analisadora funcional baseada em pilha que inclui diretiva de saída. No META II, a ordem dos testes é especificada pela equação. META II, como outras linguagens de programação, iria estourar sua pilha tentando recursão à esquerda. META II usa um operador de sequência $ (zero ou mais). A equação de análise expr escrita em META II é uma expressão condicional avaliada da esquerda para a direita:
expr = term
$( '+' term .OUT('ADD')
/ '-' term .OUT('SUB'));
Acima, a equação expr é definida pela expressão à direita de '='. Avaliando da esquerda para a direita de '=', o termo é a primeira coisa que deve ser testada. Se o termo retornar falha, expr falha. Se um termo foi reconhecido com sucesso, então inserimos o loop indefinido $ zero ou mais onde primeiro testamos um '+' se falhar, a alternativa '-' é tentada e, finalmente, se um '-' não for reconhecido, o loop termina com expr retorno do sucesso tendo reconhecido um único termo. Se um '+' ou '-' for bem-sucedido, o termo será chamado. E se for bem-sucedido, o loop se repetirá. A equação expr também pode ser expressa usando agrupamento aninhado como:
expr = term $(('+' / '-') term);
Os elementos de produção de código foram deixados de fora para simplificar o exemplo. Devido ao conjunto limitado de caracteres dos primeiros computadores, o caractere / foi usado como o operador alternativo ou. O $ operador de loop é usado para corresponder a zero ou mais de algo:
expr = term $( '+' term .OUT('ADD')
/ '-' term .OUT('SUB')
);
O texto acima pode ser expresso em inglês: Um expr é um termo seguido por zero ou mais de (mais ou menos). Schorre descreve isso como um auxílio à eficiência, mas, ao contrário de um compilador descendente recursivo ingênuo , também garantirá que a associatividade das operações aritméticas esteja correta:
expr = term $('+' term .OUT('ADD')
/ '-' term .OUT('SUB')
);
term = factor $( '*' factor .OUT('MPY')
/ '/' factor .OUT('DIV')
);
factor = ( .ID
/ .NUMBER
/ '(' expr ')')
( '^' factor .OUT('EXP')
/ .EMPTY);
Com a capacidade de expressar uma sequência com um loop ou recursão à direita ("cauda"), a ordem de avaliação pode ser controlada.
As regras de sintaxe parecem declarativas, mas na verdade são obrigatórias por suas especificações semânticas.
Operação
META II produz código de montagem para uma máquina de pilha. Avaliar isso é como usar uma calculadora RPN .
expr = term
$('+' term .OUT('ADD')
/'-' term .OUT('SUB'));
term = factor
$('*' factor .OUT('MPY')
/ '/' factor .OUT('DIV'));
factor = (.ID .OUT('LD ' *)
/ .NUM .OUT('LDL ' *)
/ '(' expr ')')
( '^' factor .OUT('XPN'/.EMPTY);
No .ID e .NUM acima são reconhecedores de tokens integrados. * nas referências de produção de código .OUT o último token reconhecido. Ao reconhecer um número com as saídas .NUM .OUT ('LDL' *), a instrução literal de carga segue o número. Uma expressão:
- (3 * a ^ 2 + 5) / b
irá gerar:
LDL 3
LD a
LDL 2
XPN
MPY
LDL 5
ADD
LD b
DIV
META II é a primeira versão documentada de um metacompilador , pois compila o código de máquina para uma das primeiras instâncias de uma máquina virtual .
O papel em si é uma joia maravilhosa que inclui vários exemplos excelentes, incluindo o bootstrapping do Meta II em si (tudo isso foi feito em um 1401 de 8K (bytes de seis bits)!). "- Alan Kay
O artigo original não está disponível gratuitamente, mas foi reimpresso no Doctor Dobb's Journal (abril de 1980). O código-fonte transcrito foi disponibilizado em vários momentos (possivelmente pelo Grupo de Usuários CP / M). O documento incluía uma lista da descrição do Meta II, que poderia, em princípio, ser processada manualmente para produzir um programa interpretável em opcodes de máquina virtual; se ele foi executado e produziu uma saída idêntica, a implementação estava correta.
META II foi basicamente uma prova de conceito. Uma base para trabalhar.
META II não se apresenta como uma linguagem padrão , mas como um ponto de partida a partir do qual um usuário pode desenvolver sua própria " linguagem " META .
Muitas "linguagens" META se seguiram. Schorre foi trabalhar para a System Development Corporation, onde foi membro do projeto Compiler for Writing and Implementing Compilers (CWIC). A linguagem SYNTAX da CWIC construída em META II adicionando um operador alternativo de retrocesso, operadores de antecipação positivos e negativos e equações de token programadas. As operações .OUT e .LABEL removidas e as operações de transformação da pilha :<node> e !<number> adicionadas. A linguagem GENERATOR baseada no LISP 2 processou as árvores produzidas pela linguagem de análise sintática SYNTAX. Para gerar o código, uma chamada a uma função geradora foi colocada em uma equação SYNTAX. Essas linguagens foram desenvolvidas por membros do subgrupo LA ACM SIGPLAN em Syntax Directed Compilers. É notável como Schorre pensou a linguagem META II:
O termo META "linguagem" com META em letras maiúsculas é usado para denotar qualquer-escrevendo compilador linguagem tão desenvolvido.
Schorre explica o META II como uma base a partir da qual outras "linguagens" do META podem ser desenvolvidas.