Existe uma alternativa para o Flex / Bison que é utilizável em sistemas embarcados de 8 bits?

Estou escrevendo um pequeno interpretador para uma linguagem simples como o BASIC como um exercício em um microcontrolador AVR em C usando o conjunto de ferramentas avr-gcc. No entanto, eu estou querendo saber se existem quaisquer ferramentas de código aberto que poderiam me ajudar a escrever o lexer e parser.

Se eu escrevesse isso para rodar na minha checkbox Linux, eu poderia usar flex / bison. Agora que me limitei a uma plataforma de 8 bits, tenho que fazer tudo manualmente ou não?

Eu implementei um analisador para uma linguagem de comando simples direcionada para o ATmega328p . Este chip tem 32k ROM e apenas 2k de RAM. A RAM é definitivamente a limitação mais importante – se você ainda não estiver preso a um chip em particular, escolha um com o máximo de RAM possível. Isso tornará sua vida muito mais fácil.

No começo eu considerei usar flex / bison. Eu decidi contra esta opção por duas razões principais:

  • Por padrão, o Flex & Bison depende de algumas funções de biblioteca padrão (especialmente para E / S) que não estão disponíveis ou não funcionam da mesma maneira no avr-libc. Tenho certeza de que existem soluções suportadas, mas isso é um esforço extra que você precisará levar em conta.
  • AVR tem uma arquitetura de Harvard . C não é projetado para explicar isso, portanto, variables ​​constantes são carregadas na RAM por padrão . Você tem que usar macros / funções especiais para armazenar e acessar dados em flash e EEPROM . O Flex & Bison cria algumas tabelas de consulta relativamente grandes, e elas consomem rapidamente sua memory RAM. A menos que eu esteja enganado (o que é bem possível), você terá que editar a fonte de saída para aproveitar as interfaces especiais Flash e EEPROM.

Depois de rejeitar o Flex & Bison, fui procurar outras ferramentas geradoras. Aqui estão alguns que eu considerei:

  • LIMÃO
  • Ragel
  • re2c

Você também pode querer dar uma olhada na comparação da Wikipedia .

Por fim, acabei codificando manualmente o lexer e o parser.

Para análise usei um analisador descendente recursivo. Eu acho que Ira Baxter já fez um trabalho adequado de cobrir este tópico, e há muitos tutoriais online.

Para o meu léxico, eu escrevi expressões regulares para todos os meus terminais, diagramação da máquina de estado equivalente, e implementei como uma function gigante usando goto ‘s para saltar entre os estados. Isso foi tedioso, mas os resultados funcionaram muito bem. Como um aparte, o goto é uma ótima ferramenta para implementar máquinas de estado – todos os seus estados podem ter labels claros ao lado do código relevante, não há chamada de function ou sobrecarga de variável de estado e é o mais rápido possível. C realmente não tem uma construção melhor para construir máquinas de estado estático.

Algo para se pensar: os lexers são apenas uma especialização de analisadores. A maior diferença é que as gramáticas regulares geralmente são suficientes para a análise lexical, enquanto a maioria das linguagens de programação tem (na maior parte) gramáticas livres de contexto. Portanto, não há nada que impeça você de implementar um lexer como um analisador de descendência recursivo ou usar um gerador de analisador para escrever um léxico. Normalmente, não é tão conveniente quanto usar uma ferramenta mais especializada.

Se você quiser uma maneira fácil de codificar analisadores, ou se estiver com pouco espaço, você deve codificar manualmente um analisador descendente recursivo; estes são essencialmente parsers LL (1). Isso é especialmente eficaz para idiomas que são tão “simples” quanto Basic. (Eu fiz vários destes anos nos anos 70!). A boa notícia é que estes não contêm nenhum código de biblioteca; apenas o que você escreve.

Eles são muito fáceis de codificar, se você já tem uma gramática. Primeiro, você precisa se livrar das regras recursivas à esquerda (por exemplo, X = XY). Isso é geralmente muito fácil de fazer, então eu deixo como um exercício. (Você não precisa fazer isso para regras de formação de lista; veja a discussão abaixo).

Então, se você tem a regra BNF do formulário:

  X = ABC ; 

crie uma sub-rotina para cada item na regra (X, A, B, C) que retorna um booleano dizendo “Eu vi a construção de syntax correspondente”. Para X, código:

 subroutine X() if ~(A()) return false; if ~(B()) { error(); return false; } if ~(C()) { error(); return false; } // insert semantic action here: generate code, do the work, .... return true; end X; 

Similarmente para A, B, C.

Se um token for um terminal, escreva o código que verifica o stream de input para a cadeia de caracteres que compõe o terminal. Por exemplo, para um número, verifique se o stream de input contém dígitos e faça avançar o cursor de stream de input pelos dígitos. Isso é especialmente fácil se você estiver analisando um buffer (para BASIC, você tende a obter uma linha no tempo) simplesmente avançando ou não avançando um ponteiro de varredura de buffer. Este código é essencialmente a parte lexer do analisador.

Se a regra da BNF for recursiva … não se preocupe. Apenas codifique a chamada recursiva. Isso lida com regras gramaticais como:

 T = '(' T ')' ; 

Isso pode ser codificado como:

 subroutine T() if ~(left_paren()) return false; if ~(T()) { error(); return false; } if ~(right_paren()) { error(); return false; } // insert semantic action here: generate code, do the work, .... return true; end T; 

Se você tiver uma regra da BNF com uma alternativa:

  P = Q | R ; 

em seguida, codifique P com opções alternativas:

 subroutine P() if ~(Q()) {if ~(R()) return false; return true; } return true; end P; 

Às vezes você encontrará listas formando regras. Estes tendem a ficar recursivos, e este caso é facilmente manipulado. Exemplo:

 L = A | LA ; 

Você pode codificar isso como:

 subroutine L() if ~(A()) then return false; while (A()) do // loop return true; end L; 

Você pode codificar várias centenas de regras gramaticais em um ou dois dias dessa maneira. Há mais detalhes para preencher, mas o básico aqui deveria ser mais do que suficiente.

Se você está realmente apertado no espaço, pode construir uma máquina virtual que implemente essas ideias. Foi o que fiz nos anos 70, quando as palavras de 8 bits e 16 bits eram o que você conseguia.


Se você não quiser codificar isso manualmente, poderá automatizá-lo com um metacompilador ( Meta II ) que produz essencialmente a mesma coisa. Estes são alucinantes e realmente fazem todo o trabalho de fazer isso, mesmo para grandes gramáticas.

Agosto de 2014:

Recebo muitas solicitações de “como construir um AST com um analisador”. Para obter detalhes sobre isso, que basicamente elabora essa resposta, veja minha outra resposta SO https://stackoverflow.com/a/25106688/120163

Julho de 2015:

Existem muitas pessoas que querem escrever um simples avaliador de expressões. Você pode fazer isso fazendo os mesmos tipos de coisas que o link “Construtor AST” sugere; apenas faça aritmética em vez de construir nós de trees. Aqui está um avaliador de expressões feito dessa maneira .

Você pode usar o flex / bison no Linux com seu gcc nativo para gerar o código que você irá compilar com seu gcc do AVR para o destino incorporado.

O GCC pode fazer uma compilation cruzada para uma variedade de plataformas, mas você executa flex e bison na plataforma em que está executando o compilador. Eles simplesmente cuspem código C que o compilador constrói. Teste para ver o tamanho do executável resultante. Note que eles têm bibliotecas de tempo de execução ( libfl.a etc.) que você também terá que cruzar a compilation para o seu destino.

Experimente o Boost :: Spirit. É uma biblioteca somente de header que você pode include e construir um analisador muito rápido e limpo completamente em C ++. Operadores sobrecarregados em C ++ são usados ​​em vez de um arquivo de gramática especial.

Em vez de reinventar a roda, dê uma olhada no LUA: http://www.lua.org . É uma linguagem interpretativa destinada a ser incorporada em outro software e usada em sistemas de pequena escala, como sistemas embarcados. Árvore de análise de syntax procedural integrada, lógica de controle, suporte a matemática e variável – não é necessário reinventar algo que milhares de outras pessoas já depuraram e usaram. E é extensível, o que significa que você pode adicionar à gramática adicionando suas próprias funções em C.