Escrevendo um compilador em seu próprio idioma

Intuitivamente, parece que um compilador de linguagem Foonão pode ser escrito em Foo. Mais especificamente, o primeiro compilador para idioma Foonão pode ser escrito em Foo, mas qualquer compilador subsequente pode ser escrito Foo.

Mas isso é realmente verdade? Tenho algumas lembranças muito vagas de ler sobre uma linguagem cujo primeiro compilador foi escrito em "ele mesmo". Isso é possível e, em caso afirmativo, como?

Isso é chamado de "inicialização". Você deve primeiro criar um compilador (ou intérprete) para o seu idioma em algum outro idioma (geralmente Java ou C). Feito isso, você pode escrever uma nova versão do compilador na linguagem Foo. Você usa o primeiro compilador de autoinicialização para compilar o compilador e, em seguida, esse compilador compilado para compilar tudo o resto (incluindo futuras versões dele mesmo).

A maioria dos idiomas é realmente criada dessa maneira, em parte porque os designers de idiomas gostam de usar o idioma que estão criando e também porque um compilador não trivial geralmente serve como uma referência útil para o quão "completo" o idioma pode ser.

Um exemplo disso seria Scala. Seu primeiro compilador foi criado em Pizza, uma linguagem experimental de Martin Odersky. A partir da versão 2.0, o compilador foi completamente reescrito no Scala. A partir desse momento, o antigo compilador Pizza pode ser completamente descartado, devido ao fato de que o novo compilador Scala poderia ser usado para se compilar para iterações futuras.

Lembro-me de ouvir um podcast da Rádio de Engenharia de Software em que Dick Gabriel falou sobre a inicialização do intérprete LISP original, escrevendo uma versão básica no LISP no papel e montando manualmente no código da máquina. A partir de então, o restante dos recursos do LISP foram escritos e interpretados com o LISP.

Adicionando uma curiosidade às respostas anteriores.

Aqui está uma citação do manual Linux From Scratch , na etapa em que se começa a construir o compilador GCC a partir de sua origem. (Linux From Scratch é uma maneira de instalar o Linux radicalmente diferente de instalar uma distribuição, na qual você precisa compilar realmente cada binário do sistema de destino.)

make bootstrap

O destino 'bootstrap' não apenas compila o GCC, mas o compila várias vezes. Ele usa os programas compilados em uma primeira rodada para se compilar pela segunda vez e depois novamente pela terceira vez. Em seguida, compara essas segunda e terceira compilações para garantir que ela possa se reproduzir na perfeição. Isso também implica que foi compilado corretamente.

Esse uso do destino 'bootstrap' é motivado pelo fato de que o compilador usado para criar a cadeia de ferramentas do sistema de destino pode não ter a mesma versão do compilador de destino. Procedendo dessa maneira, é certo obter no sistema de destino um compilador que pode se compilar.

Quando você escreve seu primeiro compilador para C, você o escreve em outro idioma. Agora, você tem um compilador para C no, digamos, assembler. Eventualmente, você chegará ao local em que precisará analisar as strings, especificamente para escapar seqüências. Você escreverá um código para converter \no caractere com o código decimal 10 (e \r13, etc).

Depois que o compilador estiver pronto, você começará a reimplementá-lo em C. Esse processo é chamado " bootstrapping " ".

O código de análise de cadeia se tornará:

...
if (c == 92) { // backslash
    c = getc();
    if (c == 110) { // n
        return 10;
    } else if (c == 92) { // another backslash
        return 92;
    } else {
        ...
    }
}
...

Quando isso compila, você tem um binário que entende '\ n'. Isso significa que você pode alterar o código fonte:

...
if (c == '\\') {
    c = getc();
    if (c == 'n') {
        return '\n';
    } else if (c == '\\') {
        return '\\';
    } else {
        ...
    }
}
...

Então, onde estão as informações que '\ n' são o código para 13? Está no binário! É como o DNA: a compilação do código-fonte C com esse binário herdará essas informações. Se o compilador se compilar, ele passará esse conhecimento para sua prole. A partir deste ponto, não há como ver apenas a partir da fonte o que o compilador fará.

Se você deseja ocultar um vírus na fonte de algum programa, pode fazê-lo assim: Obtenha a fonte de um compilador, encontre a função que compila funções e substitua-a por esta:

void compileFunction(char * name, char * filename, char * code) {
    if (strcmp("compileFunction", name) == 0 && strcmp("compile.c", filename) == 0) {
        code = A;
    } else if (strcmp("xxx", name) == 0 && strcmp("yyy.c", filename) == 0) {
        code = B;
    }

    ... code to compile the function body from the string in "code" ...
}

As partes interessantes são A e B. A é o código fonte para compileFunction incluir o vírus, provavelmente criptografado de alguma forma, para que não seja óbvio procurar no binário resultante. Isso garante que a compilação no compilador preservará o código de injeção de vírus.

B é o mesmo para a função que queremos substituir por nosso vírus. Por exemplo, poderia ser a função "login" no arquivo de origem "login.c" que provavelmente é do kernel do Linux. Poderíamos substituí-lo por uma versão que aceite a senha "joshua" para a conta root, além da senha normal.

Se você compilar isso e espalhá-lo como um binário, não haverá como encontrar o vírus olhando a fonte.

A fonte original da ideia: https://web.archive.org/web/20070714062657/http://www.acm.org/classics/sep95/

Você não pode escrever um compilador por si só porque não possui nada para compilar seu código-fonte inicial. Existem duas abordagens para resolver isso.

O menos favorecido é o seguinte. Você escreve um compilador mínimo no assembler (yuck) para um conjunto mínimo de idioma e, em seguida, usa esse compilador para implementar recursos extras do idioma. Construindo seu caminho até que você tenha um compilador com todos os recursos de idioma para si. Um processo doloroso que geralmente é feito apenas quando você não tem outra escolha.

A abordagem preferida é usar um compilador cruzado. Você altera o backend de um compilador existente em uma máquina diferente para criar uma saída que é executada na máquina de destino. Então você tem um bom compilador completo trabalhando na máquina de destino. O mais popular é a linguagem C, pois existem muitos compiladores existentes que possuem back-ends conectáveis ​​que podem ser trocados.

Um fato pouco conhecido é que o compilador GNU C ++ possui uma implementação que usa apenas o subconjunto C. O motivo é que geralmente é fácil encontrar um compilador C para uma nova máquina de destino que permita criar o compilador GNU C ++ completo a partir dele. Agora você se inicializou para ter um compilador C ++ na máquina de destino.

Geralmente, você precisa ter um corte funcional (se primitivo) do compilador trabalhando primeiro - então você pode começar a pensar em torná-lo auto-hospedado. Este é realmente considerado um marco importante em alguns idiomas.

Pelo que me lembro de "mono", é provável que eles precisem adicionar algumas coisas à reflexão para fazê-lo funcionar: a equipe mono continua apontando que algumas coisas simplesmente não são possíveis Reflection.Emit; é claro, a equipe do MS pode provar que estão errados.

Isso tem algumas vantagens reais : é um teste de unidade bastante bom para iniciantes! E você só precisa se preocupar com um idioma (ou seja, é possível que um especialista em C # possa não conhecer muito C ++; mas agora você pode consertar o compilador de C #). Mas eu me pergunto se não há uma quantidade de orgulho profissional no trabalho aqui: eles simplesmente querem que seja auto-hospedado.

Não é um compilador, mas recentemente trabalhei em um sistema que é auto-hospedado; o gerador de código é usado para gerar o gerador de código ... então, se o esquema mudar, eu simplesmente o executo: nova versão. Se houver um erro, volto para uma versão anterior e tento novamente. Muito conveniente e muito fácil de manter.

Atualização 1

Acabei de assistir este vídeo de Anders na PDC, e (cerca de uma hora), ele fornece razões muito mais válidas - tudo sobre o compilador como um serviço. Apenas para o registro.

Aqui está um despejo (tópico difícil de pesquisar, na verdade):

• Conversa fiada

• C

Essa também é a idéia do PyPy e Rubinius :

(Acho que isso também se aplica a Forth , mas não sei nada sobre Forth.)

O GNAT, o compilador GNU Ada, exige que um compilador Ada seja totalmente construído. Isso pode ser difícil ao transportá-lo para uma plataforma onde não há um binário GNAT prontamente disponível.

Na verdade, a maioria dos compiladores são escritos no idioma que compilam, pelas razões expostas acima.

O primeiro compilador de inicialização é geralmente escrito em C, C ++ ou Assembly.

O compilador C # do projeto Mono é "auto-hospedado" há muito tempo, o que significa é que ele foi escrito no próprio C #.

O que eu sei é que o compilador foi iniciado como código C puro, mas depois que os recursos "básicos" do ECMA foram implementados, eles começaram a reescrever o compilador em C #.

Não conheço as vantagens de escrever o compilador no mesmo idioma, mas tenho certeza de que isso tem a ver pelo menos com os recursos que o próprio idioma pode oferecer (C, por exemplo, não suporta programação orientada a objetos) .

Você pode encontrar mais informações aqui .

Eu escrevi o SLIC (Sistema de Idiomas para Implementar Compiladores) em si mesmo. Em seguida, compilou manualmente na montagem. Há muito no SLIC, pois era um compilador único de cinco sub-idiomas:

• Linguagem de Programação SYNTAX Parser PPL
• Idioma de geração de código PSEUDO de rastreamento de árvore baseado em GENERATOR LISP 2
• Sequência ISO, código PSEUDO, idioma de otimização
• PSEUDO Macro como código de montagem que produz linguagem.
• Linguagem de definição de instruções da máquina de montagem MACHOP.

O SLIC foi inspirado no CWIC (Compilador para Escrever e Implementar Compiladores). Diferentemente da maioria dos pacotes de desenvolvimento de compiladores, o SLIC e o CWIC tratavam da geração de código com idiomas especializados, específicos do domínio. O SLIC estende a geração de código CWICs, adicionando os sub-idiomas ISO, PSEUDO e MACHOP, separando as especificações da máquina de destino do idioma do gerador de rastreamento de árvores.

Árvores e listas do LISP 2

O sistema de gerenciamento de memória dinâmica da linguagem do gerador baseado em LISP 2 é um componente essencial. As listas são expressas no idioma entre colchetes, seus componentes separados por vírgulas, ou seja, uma lista de três elementos [a, b, c].

Árvores:

     ADD
    /   \
  MPY     3
 /   \
5     x

são representados por listas cuja primeira entrada é um objeto de nó:

[ADD,[MPY,5,x],3]

As árvores geralmente são exibidas com o nó separado antes das ramificações:

ADD[MPY[5,x],3]

Cancelar a análise com as funções do gerador baseadas em LISP 2

Uma função geradora é um conjunto nomeado de (unparse) => action> pairs ...

<NAME>(<unparse>)=><action>;
      (<unparse>)=><action>;
            ...
      (<unparse>)=><action>;

Expressões não analisadas são testes que correspondem aos padrões de árvore e / ou aos tipos de objetos, separando-os e designando essas partes à variável local a ser processada por sua ação processual. Como uma função sobrecarregada, recebendo diferentes tipos de argumentos. Exceto que os testes () => ... são tentados na ordem codificada. O primeiro desemparar com êxito executando sua ação correspondente. As expressões unparse são testes de desmontagem. ADD [x, y] corresponde a uma árvore ADD de dois ramos atribuindo seus ramos às variáveis ​​locais x e y. A ação pode ser uma expressão simples ou um bloco de código delimitado .BEGIN ... .END. Eu usaria blocos estilo {...} hoje. Regras correspondentes à árvore, [], unparse podem chamar geradores passando o (s) resultado (s) retornado (s) para a ação:

expr_gen(ADD[expr_gen(x),expr_gen(y)])=> x+y;

Especificamente, o expr_gen unparse acima corresponde a uma árvore ADD de dois ramos. Dentro do padrão de teste, um único gerador de argumento colocado em um galho de árvore será chamado com esse galho. Sua lista de argumentos, porém, são variáveis ​​locais atribuídas a objetos retornados. Acima do unparse, especifica que uma ramificação com dois ramos é a desmontagem da árvore ADD, pressionando recursivamente cada ramo para expr_gen. O retorno do ramo esquerdo é inserido nas variáveis ​​locais x. Da mesma forma, o ramo direito passou para expr_gen com y o objeto de retorno. O acima pode fazer parte de um avaliador de expressão numérica. Havia recursos de atalho chamados vetores, e acima da cadeia de nós, um vetor de nós poderia ser usado com um vetor de ações correspondentes:

expr_gen(#node[expr_gen(x),expr_gen(y)])=> #action;

  node:   ADD, SUB, MPY, DIV;
  action: x+y, x-y, x*y, x/y;

        (NUMBER(x))=> x;
        (SYMBOL(x))=> val:(x);

O avaliador de expressão mais completo acima atribui o retorno do ramo esquerdo expr_gen para x e o ramo direito para y. O vetor de ação correspondente executado em x e y retornou. Os últimos pares de ação => unparse correspondem aos objetos numéricos e de símbolo.

Símbolo e atributos de símbolo

Os símbolos podem ter atributos nomeados. val: (x) acesse o atributo val do objeto de símbolo contido em x. Uma pilha de tabela de símbolos generalizada faz parte do SLIC. A tabela SYMBOL pode ser pressionada e exibida, fornecendo símbolos locais para funções. Os símbolos recém-criados são catalogados na tabela de símbolos superior. A pesquisa de símbolo pesquisa a pilha da tabela de símbolos da tabela superior primeiro para trás na pilha.

Gerando código independente da máquina

A linguagem geradora do SLIC produz objetos de instrução PSEUDO, anexando-os a uma lista de códigos de seções. Um .FLUSH faz com que sua lista de códigos PSEUDO seja executada, removendo cada instrução PSEUDO da lista e chamando-a. Após a execução, uma memória de objetos PSEUDO é liberada. Os órgãos procedimentais das ações PSEUDOs e GENERATOR são basicamente a mesma linguagem, exceto pelo resultado. O PSEUDO deve atuar como macros de montagem, fornecendo seqüencialização de código independente da máquina. Eles fornecem uma separação da máquina de destino específica da linguagem do gerador de rastreamento de árvore. Os PSEUDOs chamam funções MACHOP para produzir o código da máquina. Os MACHOPs são usados ​​para definir pseudo ops de montagem (como dc, definir constante etc) e instruções de máquina ou uma família de instruções formatadas semelhantes usando entrada vetorial. Eles simplesmente transformam seus parâmetros em uma sequência de campos de bits que compõem a instrução. As chamadas MACHOP devem parecer com montagem e fornecer formatação de impressão dos campos para quando a montagem é mostrada na lista de compilação. No código de exemplo, estou usando comentários no estilo c que podem ser facilmente adicionados, mas não estavam nos idiomas originais. Os MACHOPs estão produzindo código em uma memória endereçável de bits. O vinculador SLIC lida com a saída do compilador. Um MACHOP para as instruções do modo de usuário DEC-10 usando a entrada vetorial: Os MACHOPs estão produzindo código em uma memória endereçável de bits. O vinculador SLIC lida com a saída do compilador. Um MACHOP para as instruções do modo de usuário DEC-10 usando a entrada vetorial: Os MACHOPs estão produzindo código em uma memória endereçável de bits. O vinculador SLIC lida com a saída do compilador. Um MACHOP para as instruções do modo de usuário DEC-10 usando a entrada vetorial:

.MACHOP #opnm register,@indirect offset (index): // Instruction's parameters.
.MORG 36, O(18): $/36; // Align to 36 bit boundary print format: 18 bit octal $/36
O(9):  #opcd;          // Op code 9 bit octal print out
 (4):  register;       // 4 bit register field appended print
 (1):  indirect;       // 1 bit appended print
 (4):  index;          // 4 bit index register appended print
O(18): if (#opcd&&3==1) offset // immediate mode use value else
       else offset/36;         // memory address divide by 36
                               // to get word address.
// Vectored entry opcode table:
#opnm := MOVE, MOVEI, MOVEM, MOVES, MOVS, MOVSI, MOVSM, MOVSS,
         MOVN, MOVNI, MOVNM, MOVNS, MOVM, MOVMI, MOVMM, MOVMS,
         IMUL, IMULI, IMULM, IMULB, MUL,  MULI,  MULM,  MULB,
                           ...
         TDO,  TSO,   TDOE,  TSOE,  TDOA, TSOA,  TDON,  TSON;
// corresponding opcode value:
#opcd := 0O200, 0O201, 0O202, 0O203, 0O204, 0O205, 0O206, 0O207,
         0O210, 0O211, 0O212, 0O213, 0O214, 0O215, 0O216, 0O217,
         0O220, 0O221, 0O222, 0O223, 0O224, 0O225, 0O226, 0O227,
                           ...
         0O670, 0O671, 0O672, 0O673, 0O674, 0O675, 0O676, 0O677;

O .MORG 36, O (18): $ / 36; alinha o local a um limite de 36 bits, imprimindo o endereço de $ / 36 local de 18 bits em octal. O opcd de 9 bits, o registro de 4 bits, o registro indireto e o índice de 4 bits são combinados e impressos como se fosse um único campo de 18 bits. O endereço de 18 bits / 36 ou o valor imediato é emitido e impresso em octal. Um exemplo MOVEI imprime com r1 = 1 er r2 = 2:

400020 201082 000005            MOVEI r1,5(r2)

Com a opção de montagem do compilador, você obtém o código de montagem gerado na lista de compilação.

Vincule-o

O vinculador SLIC é fornecido como uma biblioteca que lida com as resoluções de link e símbolo. A formatação do arquivo de carregamento de saída específico do destino, porém, deve ser gravada para as máquinas de destino e vinculada à biblioteca da biblioteca do vinculador.

A linguagem do gerador é capaz de gravar árvores em um arquivo e lê-las, permitindo a implementação de um compilador de várias etapas.

Curto verão de geração e origens de código

Analisei primeiro a geração de código para garantir que se entendesse que o SLIC era um verdadeiro compilador de compiladores. O SLIC foi inspirado no CWIC (Compilador para Escrever e Implementar Compiladores), desenvolvido na Systems Development Corporation no final dos anos 60. O CWIC tinha apenas idiomas SYNTAX e GENERATOR produzindo código de bytes numéricos fora do idioma GENERATOR. O código de bytes foi colocado ou plantado (o termo usado na documentação dos CWICs) nos buffers de memória associados às seções nomeadas e gravados por uma instrução .FLUSH. Um artigo da ACM sobre CWIC está disponível nos arquivos da ACM.

Implementando com sucesso uma linguagem de programação importante

No final da década de 1970, o SLIC foi usado para escrever um compilador cruzado COBOL. Concluído em cerca de 3 meses, principalmente por um único programador. Trabalhei um pouco com o programador, conforme necessário. Outro programador escreveu a biblioteca de tempo de execução e os MACHOPs para o mini-COMPUTADOR TI-990 de destino. Esse compilador COBOL compilou substancialmente mais linhas por segundo que o compilador COBOL nativo do DEC-10 escrito em assembly.

Mais para um compilador, então geralmente falamos sobre

Uma grande parte da escrita de um compilador do zero é a biblioteca de tempo de execução. Você precisa de uma tabela de símbolos. Você precisa de entrada e saída. Gerenciamento dinâmico de memória etc. Pode ser mais trabalhoso escrever a biblioteca de tempo de execução para um compilador do que escrever o compilador. Porém, com o SLIC, essa biblioteca de tempo de execução é comum a todos os compiladores desenvolvidos no SLIC. Observe que existem duas bibliotecas de tempo de execução. Um para a máquina de destino do idioma (COBOL, por exemplo). A outra é a biblioteca de tempo de execução dos compiladores do compilador.

Acho que estabeleci que esses não eram geradores de analisadores. Portanto, agora, com um pouco de compreensão do back-end, posso explicar a linguagem de programação do analisador.

Linguagem de programação do analisador

O analisador é escrito usando a fórmula escrita na forma de equações simples.

<name> <formula type operator> <expression> ;

O elemento de idioma no nível mais baixo é o caractere. Os tokens são formados a partir de um subconjunto dos caracteres do idioma. As classes de caracteres são usadas para nomear e definir esses subconjuntos de caracteres. O operador que define a classe de caracteres é o caractere de dois pontos (:). Os caracteres que são membros da classe são codificados no lado direito da definição. Os caracteres imprimíveis são colocados em seqüências de caracteres simples de primos. Caracteres não imprimíveis e especiais podem ser representados pelo seu ordinal numérico. Os alunos são separados por uma alternativa | operador. Uma fórmula de classe termina com um ponto e vírgula. As classes de caracteres podem incluir classes definidas anteriormente:

/*  Character Class Formula                                    class_mask */
bin: '0'|'1';                                                // 0b00000010
oct: bin|'2'|'3'|'4'|'5'|'6'|'7';                            // 0b00000110
dgt: oct|'8'|'9';                                            // 0b00001110
hex: dgt|'A'|'B'|'C'|'D'|'E'|'F'|'a'|'b'|'c'|'d'|'e'|'f';    // 0b00011110
upr:  'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|
      'N'|'O'|'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z';   // 0b00100000
lwr:  'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'|'i'|'j'|'k'|'l'|'m'|
      'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'z';   // 0b01000000
alpha:  upr|lwr;                                             // 0b01100000
alphanum: alpha|dgt;                                         // 0b01101110

O skip_class 0b00000001 é predefinido, mas pode estar em excesso definindo um skip_class.

Em resumo: Uma classe de caractere é uma lista de alternativas que só podem ser uma constante de caractere, um ordinal de um caractere ou uma classe de caractere definida anteriormente. Como implementei classes de caracteres: A fórmula da classe recebe uma máscara de bits de classe. (Mostrado nos comentários acima) Qualquer fórmula de classe com qualquer caractere literal ou ordinal faz com que um bit de classe seja alocado. Uma máscara é criada usando as máscaras de classe da (s) classe (s) incluída (s) juntamente com o bit alocado (se houver). Uma tabela de classe é criada a partir das classes de caracteres. Uma entrada indexada pelo ordinal de um caractere contém bits indicando as associações de classe do personagem. O teste de classe é feito em linha. Um exemplo de código IA-86 com o ordinal do caractere em eax ilustra o teste de classe:

test    byte ptr [eax+_classmap],dgt

Seguido por:

jne      <success>

ou

je       <failure>

Exemplos de código de instrução IA-86 são usados ​​porque acho que as instruções IA-86 são mais conhecidas hoje. O nome da classe que avalia sua máscara de classe é AND não destrutivamente com a tabela de classes indexada pelos caracteres ordinal (em eax). Um resultado diferente de zero indica associação à classe. (EAX é zerado, exceto por al (os 8 bits baixos de EAX) que contém o caractere).

Os tokens eram um pouco diferentes nesses compiladores antigos. Palavras-chave não foram explicadas como tokens. Eles simplesmente foram correspondidos por constantes de seqüência de caracteres citadas na linguagem do analisador. As strings entre aspas normalmente não são mantidas. Modificadores podem ser usados. A + mantém a string correspondente. (ou seja, + '-' corresponde a um caractere - mantendo o caractere quando for bem-sucedido) A operação, (ou seja, 'E') insere a sequência no token. O espaço em branco é tratado pela fórmula do token, ignorando os principais caracteres SKIP_CLASS até que uma primeira correspondência seja feita. Observe que uma correspondência explícita de caracteres skip_class interromperá o salto, permitindo que um token comece com um caracter skip_class. A fórmula do token de string ignora os caracteres skip_class principais que correspondem a um caractere entre aspas simples ou uma string entre aspas duplas. De interesse é a correspondência de um "caractere dentro de uma sequência" citada:

string .. (''' .ANY ''' | '"' $(-"""" .ANY | """""","""") '"') MAKSTR[];

A primeira alternativa corresponde a qualquer caractere entre aspas simples. A alternativa correta corresponde a uma string entre aspas duplas que pode incluir caracteres de aspas duplas usando dois caracteres "juntos para representar um único" caractere. Esta fórmula define as seqüências de caracteres usadas em sua própria definição. A alternativa interna direita '"' $ (-" "" ".ANY |" "" "" "", "" "") '"' corresponde a uma cadeia de caracteres entre aspas duplas. Podemos usar um caractere entre aspas simples para corresponder a um caractere "aspas duplas". No entanto, na sequência de aspas duplas "se desejarmos usar um caractere", precisamos usar dois "caracteres para obter um. Por exemplo, na alternativa interna esquerda que corresponde a qualquer caractere, exceto uma citação:

-"""" .ANY

uma espiada negativa à frente - "" "" é usada quando, quando bem-sucedida (não corresponde a um caractere "), corresponde ao caractere .ANY (que não pode ser um" caractere porque - "" "" eliminou essa possibilidade). A alternativa certa é assumir - "" "" combinar um caractere "e falhar foram a alternativa certa:

"""""",""""

tenta corresponder dois "caracteres substituindo-os por um único duplo" usando "" "" "para inserir o caractere" único. As duas alternativas internas que falham no caractere de citação da string de fechamento são correspondidas e MAKSTR [] chamado para criar um objeto de string. O $ Se o loop for bem-sucedido, o operador é usado para fazer a correspondência de uma sequência.Fórmula de token pular caracteres de classe de pular principais (com espaço em branco) Depois que uma primeira correspondência é feita, o skip_class skip está desativado. Podemos chamar funções programadas em outros idiomas usando []. MAKSTR [], MAKBIN [], MAKOCT [], MAKHEX [], MAKFLOAT [] e MAKINT [] são funções de biblioteca fornecidas que convertem uma sequência de token correspondente em um objeto digitado. A fórmula numérica abaixo ilustra um reconhecimento de token bastante complexo:

number .. "0B" bin $bin MAKBIN[]        // binary integer
         |"0O" oct $oct MAKOCT[]        // octal integer
         |("0H"|"0X") hex $hex MAKHEX[] // hexadecimal integer
// look for decimal number determining if integer or floating point.
         | ('+'|+'-'|--)                // only - matters
           dgt $dgt                     // integer part
           ( +'.' $dgt                  // fractional part?
              ((+'E'|'e','E')           // exponent  part
               ('+'|+'-'|--)            // Only negative matters
               dgt(dgt(dgt|--)|--)|--)  // 1 2 or 3 digit exponent
             MAKFLOAT[] )               // floating point
           MAKINT[];                    // decimal integer

A fórmula do token numérico acima reconhece números inteiros e de ponto flutuante. As alternativas sempre são bem-sucedidas. Objetos numéricos podem ser usados ​​em cálculos. Os objetos de token são empurrados para a pilha de análise no sucesso da fórmula. O lead do expoente em (+ 'E' | 'e', ​​'E') é interessante. Desejamos sempre ter um E maiúsculo para MAKEFLOAT []. Mas permitimos que um 'e' minúsculo o substitua usando 'E'.

Você pode ter notado consistências de classe de caractere e fórmula de token. A fórmula de análise continua a adicionar alternativas de retorno e operadores de construção de árvores. Os operadores alternativos de retorno e não retorno não podem ser misturados em um nível de expressão. Você pode não ter (a | b \ c) mixando não-backtracking | com a alternativa \ backtracking. (a \ b \ c), (a | b | c) e ((a | b) \ c) são válidos. Uma alternativa \ backtracking salva o estado de análise antes de tentar sua alternativa esquerda e, em caso de falha, restaura o estado de análise antes de tentar a alternativa correta. Em uma sequência de alternativas, a primeira alternativa bem-sucedida satisfaz o grupo. Outras alternativas não são tentadas. O fatoramento e o agrupamento fornecem uma análise de avanço contínuo. A alternativa de retorno cria um estado salvo da análise antes de tentar sua alternativa esquerda. O retorno é necessário quando a análise pode fazer uma correspondência parcial e depois falhar:

(a b | c d)\ e

Acima, se uma falha de retorno, o CD alternativo é tentado. Se c retornar a falha, a alternativa de retorno será tentada. Se a for bem-sucedido e b falhar, a análise será retornada e tentada. Da mesma forma, a falha c é bem-sucedida eb falha, a análise é retornada e a alternativa é tomada. O retorno não é limitado a uma fórmula. Se alguma fórmula de análise fizer uma correspondência parcial a qualquer momento e falhar, a análise será redefinida para a trilha de retorno superior e sua alternativa adotada. Uma falha de compilação pode ocorrer se o código tiver sido emitido no sentido em que o retorno foi criado. Um retorno é definido antes de iniciar a compilação. Retornar a falha ou voltar atrás para ela é uma falha do compilador. As trilhas de retorno estão empilhadas. Podemos usar negativo - e positivo? espie / observe os operadores para testar sem avançar na análise. sendo teste de cadeia de caracteres é uma espiada adiante, necessitando apenas do estado de entrada salvo e redefinido. Um olhar à frente seria uma expressão de análise que faz uma correspondência parcial antes de falhar. Um olhar à frente é implementado usando o retorno.

O idioma do analisador não é um analisador LL ou LR. Mas uma linguagem de programação para escrever um analisador decente recursivo no qual você programa a construção de árvores:

:<node name> creates a node object and pushes it onto the node stack.
..           Token formula create token objects and push them onto 
             the parse stack.
!<number>    pops the top node object and top <number> of parstack 
             entries into a list representation of the tree. The 
             tree then pushed onto the parse stack.
+[ ... ]+    creates a list of the parse stack entries created 
             between them:
              '(' +[argument $(',' argument]+ ')'
             could parse an argument list. into a list.

Um exemplo de análise comumente usado é uma expressão aritmética:

Exp = Term $(('+':ADD|'-':SUB) Term!2); 
Term = Factor $(('*':MPY|'/':DIV) Factor!2);
Factor = ( number
         | id  ( '(' +[Exp $(',' Exp)]+ ')' :FUN!2
               | --)
         | '(' Exp ')" )
         (^' Factor:XPO!2 |--);

Exp e Term usando um loop cria uma árvore para canhotos. O fator que usa recursão à direita cria uma árvore destra:

d^(x+5)^3-a+b*c => ADD[SUB[EXP[EXP[d,ADD[x,5]],3],a],MPY[b,c]]

              ADD
             /   \
          SUB     MPY
         /   \   /   \
      EXP     a b     c
     /   \
    d     EXP     
         /   \
      ADD     3
     /   \
    x     5

Aqui está um pouco do compilador cc, uma versão atualizada do SLIC com comentários no estilo c. Os tipos de função (gramática, token, classe de caractere, gerador, PSEUDO ou MACHOP são determinados por sua sintaxe inicial, seguindo seu ID. Com esses analisadores de cima para baixo, você começa com uma fórmula de definição de programa:

program = $((declaration            // A program is a sequence of
                                    // declarations terminated by
            |.EOF .STOP)            // End Of File finish & stop compile
           \                        // Backtrack: .EOF failed or
                                    // declaration long-failed.
             (ERRORX["?Error?"]     // report unknown error
                                    // flagging furthest parse point.
              $(-';' (.ANY          // find a ';'. skiping .ANY
                     | .STOP))      // character: .ANY fails on end of file
                                    // so .STOP ends the compile.
                                    // (-';') failing breaks loop.
              ';'));                // Match ';' and continue

declaration =  "#" directive                // Compiler directive.
             | comment                      // skips comment text
             | global        DECLAR[*1]     // Global linkage
             |(id                           // functions starting with an id:
                ( formula    PARSER[*1]     // Parsing formula
                | sequencer  GENERATOR[*1]  // Code generator
                | optimizer  ISO[*1]        // Optimizer
                | pseudo_op  PRODUCTION[*1] // Pseudo instruction
                | emitor_op  MACHOP[*1]     // Machine instruction
                )        // All the above start with an identifier
              \ (ERRORX["Syntax error."]
                 garbol);                    // skip over error.

// Observe como o ID é fatorado e mais tarde combinado ao criar a árvore.

formula =   ("==" syntax  :BCKTRAK   // backtrack grammar formula
            |'='  syntax  :SYNTAX    // grammar formula.
            |':'  chclass :CLASS     // character class define
            |".." token   :TOKEN     // token formula
              )';' !2                // Combine node name with id 
                                     // parsed in calling declaration 
                                     // formula and tree produced
                                     // by the called syntax, token
                                     // or character class formula.
                $(-(.NL |"/*") (.ANY|.STOP)); Comment ; to line separator?

chclass = +[ letter $('|' letter) ]+;// a simple list of character codes
                                     // except 
letter  = char | number | id;        // when including another class

syntax  = seq ('|' alt1|'\' alt2 |--);

alt1    = seq:ALT!2 ('|' alt1|--);  Non-backtrack alternative sequence.

alt2    = seq:BKTK!2 ('\' alt2|--); backtrack alternative sequence

seq     = +[oper $oper]+;

oper    = test | action | '(' syntax ')' | comment; 

test    = string | id ('[' (arg_list| ,NILL) ']':GENCALL!2|.EMPTY);

action  = ':' id:NODE!1
        | '!' number:MAKTREE!1
        | "+["  seq "]+" :MAKLST!1;

//     C style comments
comment  = "//" $(-.NL .ANY)
         | "/*" $(-"*/" .ANY) "*/";

É importante notar como a linguagem do analisador lida com comentários e recuperação de erros.

Eu acho que respondi a pergunta. Tendo escrito uma grande parte do sucessor dos SLICs, a linguagem cc em si aqui. Ainda não existe um compilador para ele. Mas eu posso compilá-lo manualmente em código de montagem, funções asm c ou c ++ nuas.

Sim, você pode escrever um compilador para um idioma nesse idioma. Não, você não precisa de um primeiro compilador para esse idioma inicializar.

O que você precisa para iniciar é uma implementação da linguagem. Isso pode ser um compilador ou um intérprete.

Historicamente, os idiomas eram geralmente considerados como idiomas interpretados ou compilados. Os intérpretes foram escritos apenas para o primeiro e os compiladores foram escritos apenas para o último. Portanto, normalmente, se um compilador fosse escrito para um idioma, o primeiro compilador seria escrito em outro idioma para inicializá-lo e, opcionalmente, o compilador seria reescrito para o idioma do assunto. Mas escrever um intérprete em outro idioma é uma opção.

Isso não é apenas teórico. Eu atualmente estou fazendo isso sozinho. Estou trabalhando em um compilador para uma linguagem, Salmon, que me desenvolvi. Primeiro criei um compilador Salmon em C e agora estou escrevendo o compilador no Salmon, para que ele possa funcionar sem precisar de um compilador para o Salmon escrito em qualquer outro idioma.

Talvez você possa escrever um BNF descrevendo o BNF.