Como escrever um interpretador / analisador de comandos?

22

Problema: Execute comandos na forma de uma sequência.

  • exemplo de comando:

    /user/files/ list all; equivalente a: /user/files/ ls -la;

  • outro:

    post tw fb "HOW DO YOU STOP THE TICKLE MONSTER?;"

equivalente a: post -tf "HOW DO YOU STOP THE TICKLE MONSTER?;"

Solução atual:

tokenize string(string, array);

switch(first item in array) {
    case "command":
        if ( argument1 > stuff) {
           // do the actual work;
        }
}

Os problemas que vejo nesta solução são:

  • Nenhum erro de verificação além de ifs aninhado em cada caso. O script se torna muito grande e difícil de manter.
  • Comandos e respostas são codificados.
  • Não há como saber se os sinalizadores estão corretos ou faltando parâmetros.
  • Falta de inteligência para sugerir "você pode querer executar o comando $".

E a última coisa que não consigo abordar são sinônimos em diferentes codificações, por exemplo:

case command:
case command_in_hebrew:
    do stuff;
break;

O último pode ser trivial, mas bem, o que eu quero ver são os sólidos fundos desse tipo de programa.

Atualmente, estou programando isso em PHP, mas pode fazê-lo em PERL.

alfa64
fonte
Não vejo como isso se relaciona especificamente ao PHP. Já existem muitos tópicos neste intérprete / compilador-tópico no SO e no SE.
Raffael
3
Ninguém mencionou o getopt?
Anton Barkovsky
@AntonBarkovsky: Eu fiz. Veja meus links. Acho que respostas como a de Ubermensch são muito complicadas demais para o que o OP está tentando fazer.
você está
1
Também citei uma abordagem simples usando o RegExp. A resposta também é atualizada
Ubermensch 22/12
Não mencionou nenhum programa específico. lang. você pode adicionar uma tag "c", "ruby", "php", talvez exista uma biblioteca de código aberto, uma biblioteca padrão ou "comumente usada, ainda não uma biblioteca padrão". para o seu progr. lang.
umlcat

Respostas:

14

Permitam-me admitir francamente que a construção de analisador é um trabalho tedioso e chega perto da tecnologia do compilador, mas a construção de um acabaria sendo uma boa aventura. E um analisador vem com intérprete. Então você tem que construir os dois.

Uma rápida introdução ao analisador e intérpretes

Isso não é muito técnico. Para que os especialistas não se preocupem comigo.

Quando você alimenta alguma entrada em um terminal, o terminal divide a entrada em várias unidades. A entrada é chamada expressão e as várias unidades são chamadas tokens. Esses tokens podem ser operadores ou símbolos. Portanto, se você digitar 4 + 5 em uma calculadora, essa expressão será dividida em três tokens 4, +, 5. O sinal de mais é considerado um operador com 4 e 5 símbolos. Isso é passado para um programa (considere isso como um intérprete) que contém a definição para os operadores. Com base na definição (no nosso caso, add), ele adiciona os dois símbolos e retorna o resultado ao terminal. Todos os compiladores são baseados nessa tecnologia. O programa que divide uma expressão em vários tokens é chamado de lexer e o programa que converte esses tokens em tags para processamento e execução adicionais é chamado de analisador.

Lex e Yacc são as formas canônicas para a construção de lexers e analisadores baseados na gramática BNF em C e é a opção recomendada. A maioria dos analisadores é um clone de Lex e Yacc.

Etapas na construção de um analisador / intérprete

  1. Classifique seus tokens em símbolos, operadores e palavras-chave (as palavras-chave são operadores)
  2. Crie sua gramática usando o formulário BNF
  3. Escreva funções de analisador para suas operações
  4. Compile uma execução como um programa

Portanto, no caso acima, seus tokens de adição teriam qualquer dígito e um sinal de mais com a definição do que fazer com o sinal de mais no lexer

Notas e dicas

  • Escolha uma técnica de analisador que avalie da esquerda para a direita LALR
  • Leia este livro sobre dragões em Compiladores para ter uma idéia. Eu pessoalmente não terminei o livro
  • Esse link daria uma visão super rápida sobre Lex e Yacc em Python

Uma abordagem simples

Se você precisar apenas de um mecanismo de análise simples com funções limitadas, transforme seu requisito em uma Expressão Regular e crie um monte de funções. Para ilustrar, assuma um analisador simples para as quatro funções aritméticas. Então você chamaria primeiro o operador e depois a lista de funções (semelhante ao lisp) no estilo (+ 4 5)ou(add [4,5]) então poderia usar um RegExp simples para obter a lista de operadores e os símbolos a serem operados.

Os casos mais comuns poderiam ser facilmente resolvidos por essa abordagem. A desvantagem é que você não pode ter muitas expressões aninhadas com uma sintaxe clara e não pode ter funções fáceis de ordem superior.

Ubermensch
fonte
2
Essa é uma das maneiras mais difíceis possíveis. Separar passagens de lexing e de análise, etc. - provavelmente é útil para implementar um analisador de alto desempenho para uma linguagem muito complexa, mas arcaica. No mundo moderno, a análise sem lexer é uma opção padrão mais simples. A análise de combinadores ou eDSLs é mais fácil de usar do que pré-processadores dedicados como o Yacc.
SK-lógica
Concordei com a SK-logic, mas como uma resposta geral detalhada é necessária, sugeri Lex e Yacc e algumas noções básicas sobre o analisador. getopts sugeridos por Anton também são uma opção mais simples.
Ubermensch
foi o que eu disse - lex e yacc estão entre as maneiras mais difíceis de analisar, e nem genéricas o suficiente. A análise sem Lexer (por exemplo, packrat ou Parsec simples) é muito mais simples para um caso geral. E o livro Dragon não é mais uma introdução muito útil para analisar - está muito desatualizado.
SK-logic
@ SK-logic Você pode recomendar um livro melhor atualizado. Parece cobrir todos os princípios básicos para uma pessoa que tenta entender a análise (pelo menos na minha percepção). Em relação ao lex e ao yacc, embora difícil, ele é amplamente utilizado e muitas linguagens de programação fornecem sua implementação.
Ubermensch
1
@ alfa64: não se esqueça de nos avisar, em seguida, quando você realmente codificar uma solução com base nesta resposta
Quentin-starin
7

Primeiro, quando se trata de gramática ou como especificar argumentos, não invente a sua. O padrão no estilo GNU já é muito popular e conhecido.

Segundo, como você está usando um padrão aceito, não reinvente a roda. Use uma biblioteca existente para fazer isso por você. Se você usa argumentos no estilo GNU, quase certamente já existe uma biblioteca madura no seu idioma preferido. Por exemplo: c # , php , c .

Uma boa opção para analisar a biblioteca imprimirá até ajuda formatada nas opções disponíveis.

EDIT 12/27

Parece que você está tornando isso mais complicado do que é.

Quando você olha para uma linha de comando, é realmente bastante simples. São apenas opções e argumentos para essas opções. Existem muito poucos problemas complicadores. A opção pode ter aliases. Argumentos podem ser listas de argumentos.

Um problema com sua pergunta é que você realmente não especificou nenhuma regra para qual tipo de linha de comando você gostaria de lidar. Sugeri o padrão GNU, e seus exemplos se aproximam disso (embora eu realmente não entenda seu primeiro exemplo com o caminho como o primeiro item?).

Se estamos falando do GNU, qualquer opção única pode ter apenas uma forma longa e uma forma curta (caractere único) como alias. Qualquer argumento que contenha um espaço deve estar entre aspas. Várias opções de formato curto podem ser encadeadas. As opções de formato curto devem ser processadas por um único traço, o formato longo por dois traços. Somente a última das opções de forma abreviada encadeada pode ter um argumento.

Tudo muito direto. Tudo muito comum. Também foi implementado em todos os idiomas que você pode encontrar, provavelmente cinco vezes mais.

Não escreva. Use o que já está escrito.

A menos que você tenha algo em mente além dos argumentos padrão da linha de comando, use uma das MUITAS bibliotecas testadas já existentes que fazem isso.

Qual a complicação?

quentin-starin
fonte
3
Sempre, sempre aproveite a comunidade de código aberto.
Spencer Rathbun
você já experimentou o getoptionkit?
Alfa24
Não, eu não trabalho em php há alguns anos. Pode muito bem haver outras bibliotecas php também. Eu usei a biblioteca de analisador de linha de comando c # à qual vinculei.
você precisa
4

Você já tentou algo como http://qntm.org/loco ? Essa abordagem é muito mais limpa do que qualquer ad hoc manuscrita, mas não exige uma ferramenta de geração de código independente como o Lemon.

EDIT: E um truque geral para lidar com linhas de comando com sintaxe complexa é combinar os argumentos novamente em uma única sequência separada por espaços em branco e analisá-los corretamente como se fosse uma expressão de alguma linguagem específica de domínio.

SK-logic
fonte
+1 link legal, gostaria de saber se está disponível no github ou outra coisa. E quanto aos termos de uso?
hakre
1

Você não deu muitos detalhes sobre sua gramática, apenas alguns exemplos. O que posso ver é que existem algumas strings, espaços em branco e uma (provavelmente, seu exemplo é indiferente na sua pergunta) com aspas duplas e depois uma ";" no fim.

Parece que isso pode ser semelhante à sintaxe do PHP. Nesse caso, o PHP vem com um analisador, você pode reutilizar e validar mais concretamente. Finalmente, você precisa lidar com os tokens, mas parece que isso é simplesmente da esquerda para a direita; portanto, apenas uma iteração sobre todos os tokens.

Alguns exemplos para reutilizar o analisador de token do PHP ( token_get_all) são fornecidos nas respostas às seguintes perguntas:

Ambos os exemplos também contêm um analisador simples, provavelmente algo como esse é adequado ao seu cenário.

hakre
fonte
sim, eu apressei o material da gramática, vou adicioná-lo agora.
Alfa17
1

Se suas necessidades são simples, e vocês dois têm tempo e estão interessados ​​nisso, eu vou contra a corrente aqui e digo: não coíbe de escrever seu próprio analisador. É uma boa experiência de aprendizado, se nada mais. Se você tiver requisitos mais complexos - chamadas de funções aninhadas, matrizes etc. - esteja ciente de que isso pode levar um bom tempo. Um dos grandes pontos positivos de criar o seu próprio é que não haverá um problema de integração com seu sistema. A desvantagem é, obviamente, que todos os erros são sua culpa.

O trabalho contra tokens, no entanto, não usa comandos codificados. Então esse problema com comandos de som semelhantes desaparece.

Todo mundo sempre recomenda o livro do dragão, mas eu sempre achei "Compiladores e Intérpretes de Escrita", de Ronald Mak, uma introdução melhor.

GrandmasterB
fonte
0

Eu escrevi programas que funcionam assim. Um deles era um bot de IRC que possui sintaxe de comando semelhante. Há um arquivo enorme que é uma grande declaração de opção. Funciona - funciona rápido - mas é um pouco difícil de manter.

Outra opção, que tem mais rotação de OOP, é usar manipuladores de eventos. Você cria uma matriz de valores-chave com comandos e suas funções dedicadas. Quando um comando é dado, você verifica se a matriz possui a chave fornecida. Caso isso aconteça, chame a função Essa seria minha recomendação para um novo código.

Brigand
fonte
Eu li o seu código e é exatamente o mesmo esquema do meu código, mas como afirmei, se você quiser que outras pessoas usem, você precisará adicionar verificação de erros e outras coisas
alfa64
1
@ alfa64 Por favor, adicione esclarecimentos à pergunta, em vez de comentários. Não está muito claro o que exatamente você está pedindo, embora seja um pouco claro que você está procurando algo realmente específico. Se sim, diga-nos exatamente o que é isso. Eu não acho que é muito fácil ir I think my implementation is very crude and faultyda but as i stated, if you want other people to use, you need to add error checking and stuff... Conte-nos exatamente o que é bruto sobre isso eo que é deficiente, ele iria ajudá-lo a obter melhores respostas.
yannis
Claro, eu vou reformular a pergunta
alfa64
0

Sugiro usar uma ferramenta, em vez de implementar um compilador ou intérprete. O Irony usa C # para expressar a gramática do idioma de destino (a gramática da sua linha de comando). A descrição no CodePlex diz: "O Irony é um kit de desenvolvimento para implementar linguagens na plataforma .NET."

Consulte a página oficial da Irony no CodePlex: Irony - .NET Language Implementation Kit .

Olivier Jacot-Descombes
fonte
Como você o usaria com PHP?
SK-logic
Não vejo nenhuma tag PHP ou referência ao PHP na pergunta.
Olivier Jacot-Descombes
Entendo, costumava ser sobre PHP originalmente, mas agora reescrito.
SK-logic
0

Meu conselho seria o google para uma biblioteca que resolve seu problema.

Ultimamente tenho usado o NodeJS, e o Optimist é o que eu uso para o processamento da linha de comando. Convido você a procurar um que possa usar para o seu próprio idioma de escolha. Caso contrário, escreva um e abra o código-fonte: D Você pode até ler o código-fonte do Optimist e portá-lo para o idioma de sua escolha.

ming_codes
fonte
0

Por que você não simplifica um pouco seus requisitos?

Não use um analisador completo, é muito complexo e até desnecessário para o seu caso.

Faça um loop, escreva uma mensagem que represente seu prompt, pode ser o caminho atual.

Aguarde uma sequência, "analise" a sequência e faça algo dependendo do seu conteúdo.

A string pode "analisar" como esperar uma linha, na qual os espaços são os separadores ("tokenizer") e o restante dos caracteres são agrupados.

Exemplo.

O programa gera (e permanece na mesma linha): / user / files / O usuário grava (na mesma linha) lista tudo;

Seu programa irá gerar uma lista, coleção ou matriz como

list

all;

ou se ";" é considerado um separador como espaços

/user/files/

list

all

Seu programa pode começar esperando uma única instrução, sem "pipes" no estilo unix, nem redirecionamento no estilo windowze.

Seu programa pode criar um dicionário de instruções, cada instrução, pode ter uma lista de parâmetros.

O padrão de design do comando se aplica ao seu caso:

http://en.wikipedia.org/wiki/Command_pattern

Esse pseudocódigo "simples c" não foi testado ou finalizado, apenas uma idéia de como poderia ser feito.

Você também pode torná-lo mais orientado a objetos e, na linguagem de programação, desejar.

Exemplo:


// "global function" pointer type declaration
typedef
  void (*ActionProc) ();

struct Command
{
  char[512] Identifier;
  ActionProc Action; 
};

// global var declarations

list<char*> CommandList = new list<char*>();
list<char*> Tokens = new list<char*>();

void Action_ListDirectory()
{
  // code to list directory
} // Action_ListDirectory()

void Action_ChangeDirectory()
{
  // code to change directory
} // Action_ChangeDirectory()

void Action_CreateDirectory()
{
  // code to create new directory
} // Action_CreateDirectory()

void PrepareCommandList()
{
  CommandList->Add("ls", &Action_ListDirectory);
  CommandList->Add("cd", &Action_ChangeDirectory);
  CommandList->Add("mkdir", &Action_CreateDirectory);

  // register more commands
} // void PrepareCommandList()

void interpret(char* args, int *ArgIndex)
{
  char* Separator = " ";
  Tokens = YourSeparateInTokensFunction(args, Separator);

  // "LocateCommand" may be case sensitive
  int AIndex = LocateCommand(CommandList, args[ArgIndex]);
  if (AIndex >= 0)
  {
    // the command

    move to the next parameter
    *ArgIndex = (*ArgIndex + 1);

    // obtain already registered command
    Command = CommandList[AIndex];

    // execute action
    Command.Action();
  }
  else
  {
    puts("some kind of command not found error, or, error syntax");
  }  
} // void interpret()

void main(...)
{
  bool CanContinue = false;
  char* Prompt = "c\:>";

  char Buffer[512];

  // which command line parameter string is been processed
  int ArgsIndex = 0;

  PrepareCommandList();

  do
  {
    // display "prompt"
    puts(Prompt);
    // wait for user input
      fgets(Buffer, sizeof(Buffer), stdin);

    interpret(buffer, &ArgsIndex);

  } while (CanContinue);

} // void main()

Você não mencionou sua linguagem de programação. Você também pode mencionar qualquer linguagem de programação, mas preferencialmente "XYZ".

umlcat
fonte
0

você tem várias tarefas pela frente.

olhando para suas necessidades ...

  • Você precisa analisar o comando. Essa é uma tarefa bastante fácil
  • Você precisa ter uma linguagem de comando extensível.
  • Você precisa ter sugestões e verificação de erros.

A linguagem de comando extensível indica que uma DSL é necessária. Eu sugeriria não criar o seu próprio, mas usar JSON se suas extensões forem simples. Se eles são complexos, uma sintaxe de expressão s é boa.

A verificação de erros implica que o seu sistema também conheça os possíveis comandos. Isso faria parte do sistema pós-comando.

Se eu estivesse implementando esse sistema a partir do zero, usaria o Common Lisp com um leitor simplificado. Cada token de comando seria mapeado para um símbolo, que seria especificado em um arquivo RC de expressão s. Após a tokenização, ela seria avaliada / expandida em um contexto limitado, capturando os erros e quaisquer padrões de erro reconhecíveis retornariam sugestões. Depois disso, o comando real seria despachado para o sistema operacional.

Paul Nathan
fonte
0

Há um bom recurso na programação funcional que você pode estar interessado em examinar.

É chamado de correspondência de padrões .

Aqui estão dois links para alguns exemplos de correspondência de padrões no Scala e no F # .

Concordo com você que o uso de switchestruturas é um pouco tedioso, e eu particularmente gostei de usar a correspondência de padrões durante a implementação de um compilador no Scala.

Em particular, eu recomendo que você analise o exemplo de cálculo lambda do site da Scala.

Essa é, na minha opinião, a maneira mais inteligente de proceder, mas se você tiver que se ater estritamente ao PHP, ficará com a "velha escola" switch.

SRKX
fonte
0

Confira a Apache CLI , todo o seu objetivo parece estar fazendo exatamente o que você deseja fazer; portanto, mesmo que você não possa usá-lo, verifique sua arquitetura e copie-a.

Stephen Rudolph
fonte