Análise Sintática • Capítulo 6

polish man

Nobre polonês • Típico usuário de notação polonesa

Notação Polonesa


Para testar a mpc vamos implementar uma gramática simples que lembra um subconjunto do nosso Lisp. Ela é chamada de Notação Polonesa e é uma notação para aritmética onde o operador vem antes dos operandos.

Por exemplo...

1 + 2 + 6é+ 1 2 6
6 + (2 * 9)é+ 6 (* 2 9)
(10 * 2) / (4 + 2)é/ (* 10 2) (+ 4 2)

Precisamos arranjar uma gramática que descreva essa notação. Podemos começar descrevendo-a textualmente e em seguida formalizar nossos pensamentos.

Para começar, observamos que na notação polonesa o operador sempre vem antes numa expressão, seguido por números ou outras expressões entre parênteses. Isso significa que podemos dizer "um programa é um operador seguido de uma ou mais expressões," onde "uma expressão é ou um número, ou, entre parênteses, um operador seguido de uma ou mais expressões.

Mais formalmente...

Programo começo da entrada, um Operator, uma ou mais Expression, e o fim da entrada.
Expressionou um Number ou '(', um Operator, uma ou mais Expression, e um ')'.
Operator'+', '-', '*', ou '/'.
Numberum - opcional, e um ou mais caracteres entre 0 e 9

Expressões Regulares


Devemos ser capaz de codificar a maior parte das regras acima usando coisas que já sabemos, mas Number e Program podem representar algum problema. Essas regras contêm algumas construções que ainda não aprendemos como expressar. Não sabemos como expressar o começo ou o fim da entrada, caracteres opcionais, ou uma faixa de caracteres.

Elas podem ser expressas, mas requerem uma coisa chamada Expressão Regular. Expressões regulares são uma maneira de escrever gramáticas para pequenas porções de texto como palavras ou números. Gramáticas escritas usando expressões regularas não podem consistir de múltiplas regras, mas dão controle preciso e conciso sobre o que está sendo casado e o que não. Eis aqui algumas regras básicas para escrever expressões regulares.

.É esperado algum caractere qualquer.
aÉ esperado o caractere a.
[abcdef]É esperado algum caractere do conjunto abcdef.
[a-f]É esperado algum caractere na faixa de a a f.
a?O caractere a é opcional.
a*Zero ou mais do caractere a são esperados.
a+Um ou mais do caractere a são esperados.
^O começo da entrada é esperado.
$O fim da entrada é esperado.

Estas são todas as regras de expressões regulares que vamos precisar por enquanto. Há livros inteiros sobre o assunto de aprender expressões regulares. Para os curiosos, mais informações podem ser achadas online ou dessas fontes. Vamos usá-las em próximos capítulos, então algum conhecimento básico será necessário, mas você não precisa dominá-las por enquanto.

Em uma gramática mpc nós escrevemos expressões regulares colocando-as entre barras /. Usando o guia acima a nossa regra Number pode ser expressa como uma expressão regular usando a string /-?[0-9]+/.

Instalando mpc


Antes de trabalharmos na escrita dessa gramática precisamos primeiro incluir os cabeçalhos da mpc, e então vincular a biblioteca mpc, da mesma forma que fizemos para editline no Linux e Mac. Começando com seu código do capítulo 4, você pode renomear o arquivo para parsing.c e baixar mpc.h e mpc.c do repositório mpc. Ponha estes no mesmo diretório que seu código fonte.

Para incluir mpc coloque #include "mpc.h" no topo do arquivo. Para vincular à mpc coloque mpc.c diretamente no comando de compilação. No Linux você também precisa ligar às bibliotecas de matemática adicionando a opção -lm.

No Linux e Mac

cc -std=c99 -Wall parsing.c mpc.c -ledit -lm -o parsing

No Windows

cc -std=c99 -Wall parsing.c mpc.c -o parsing

Espera aí, você não quer dizer #include <mpc.h>?

Existem duas maneiras de incluir arquivos em C. Uma delas é usando colchetes angulares <> como já vimos até agora, e a outra é usando aspas duplas "".

A única diferença entre as duas é que usando colchetes angulares procura os cabeçalhos nos diretórios do sistema primeiro, já as aspas duplas procuram no diretório atual primeiro. Por causa disso cabeçalhos do sistema como <stdio.h> são tipicamente usados com colchetes angulares, e cabeçalhos locais como "mpc.h" tipicamente são usados com aspas duplas.

Gramática para notação polonesa


Formalizando as regras acima ainda mais, e usando algumas expressões regulares, podemos escrever uma gramática final para a linguagem de notação polonesa como segue. Leia o código abaixo e verifique que ele fecha com o que tínhamos escrito textualmente, e nossas ideias de notação polonesa.

/* Cria Alguns Parsers */
mpc_parser_t* Number   = mpc_new("number");
mpc_parser_t* Operator = mpc_new("operator");
mpc_parser_t* Expr     = mpc_new("expr");
mpc_parser_t* Lispy    = mpc_new("lispy");

/* Define eles com a seguinte linguagem */
mpca_lang(MPCA_LANG_DEFAULT,
  "                                                     \
    number   : /-?[0-9]+/ ;                             \
    operator : '+' | '-' | '*' | '/' ;                  \
    expr     : <number> | '(' <operator> <expr>+ ')' ;  \
    lispy    : /^/ <operator> <expr>+ /$/ ;             \
  ",
  Number, Operator, Expr, Lispy);

Precisamos adicionar isso ao prompt interativo que começamos no capítulo 4. Coloque este código logo no começo da função main, antes de parte que mostra a informação de versão e como sair. Ao fim do nosso programa, também precisamos deletar os parsers quando não precisamos mais deles. Logo antes da main retornar nós devemos adicionar o código de limpeza a seguir.

/* Desfaz definicao e deleta nossos Parsers */
mpc_cleanup(4, Number, Operator, Expr, Lispy);

Estou tendo o erro undefined reference to `mpc_lang'

O correto é mpca_lang, com um a no final!

Analisando a entrada


Nosso código cria um parser mpc para nossa linguagem Notação Polonesa, mas ainda precisamos usá-lo de verdade na entrada suprida pelo usuário cada vez que solicitamos. Precisamos editar nosso laço while para que em vez de simplesmente ecoar a entrada, ele realmente tente analisar a entrada usando nosso parser. Podemos fazer isso substituindo a chamada à printf com o seguinte código mpc, que faz uso do nosso parser de programa Lispy.

/* Tenta Parsear/Analisar a Entrada */
mpc_result_t r;
if (mpc_parse("<stdin>", input, Lispy, &r)) {
  /* Caso Successo, Imprime a AST */
  mpc_ast_print(r.output);
  mpc_ast_delete(r.output);
} else {
  /* Senao, Imprime o Erro */
  mpc_err_print(r.error);
  mpc_err_delete(r.error);
}

Esse código chama a função mpc_parse com nosso parser Lispy, e a string de entrada input. Ele copia o resultado da análise para r e retorna 1 caso teve sucesso ou 0 caso falhou. Nós usamos o operador de endereço & em r quando passamo-lo à função. Este operador será explicado em mais detalhes em capítulos posteriores.

No caso de sucesso, uma estrutura interna é copiada para r, no campo output. Nós podemos imprimir esta estrutura usando mpc_ast_print e deletá-la usando mpc_ast_delete.

Caso não, terá havido algum erro, que é copiado para r no campo error. Podemos imprimir o erro usando mpc_err_print e deletá-lo usando mpc_err_delete.

Compile essas atualizações, e bote o programa para rodar. Tente algumas entradas diferentes e veja como o sistema reage. Comportamento correto deve se parecer com o seguinte.

Lispy Version 0.0.0.0.2
Press Ctrl+c to Exit

lispy> + 5 (* 2 2)
>
  regex
  operator|char:1:1 '+'
  expr|number|regex:1:3 '5'
  expr|>
    char:1:5 '('
    operator|char:1:6 '*'
    expr|number|regex:1:8 '2'
    expr|number|regex:1:10 '2'
    char:1:11 ')'
  regex
lispy> hello
<stdin>:1:1: error: expected whitespace, '+', '-', '*' or '/' at 'h'
lispy> / 1dog
<stdin>:1:4: error: expected one of '0123456789', whitespace, '-', one or more of one of '0123456789', '(' or end of input at 'd'
lispy>

Estou tendo o erro <stdin>:1:1: error: Parser Undefined!.

Este erro é devido à sintaxe para sua gramática fornecida à mpca_lang estar incorreta. Veja se consegue descobrir qual parte da gramática está incorreta. Você pode usar o código de referência para este capítulo para ajudá-lo a descobrir isso, e verificar como a gramática deve ser.

Referência


#include "mpc.h"

#ifdef _WIN32

static char buffer[2048];

char* readline(char* prompt) {
  fputs(prompt, stdout);
  fgets(buffer, 2048, stdin);
  char* cpy = malloc(strlen(buffer)+1);
  strcpy(cpy, buffer);
  cpy[strlen(cpy)-1] = '\0';
  return cpy;
}

void add_history(char* unused) {}

#else
#include <editline/readline.h>
#include <editline/history.h>
#endif

int main(int argc, char** argv) {
  
  /* Create Some Parsers */
  mpc_parser_t* Number   = mpc_new("number");
  mpc_parser_t* Operator = mpc_new("operator");
  mpc_parser_t* Expr     = mpc_new("expr");
  mpc_parser_t* Lispy    = mpc_new("lispy");
  
  /* Define them with the following Language */
  mpca_lang(MPCA_LANG_DEFAULT,
    "                                                     \
      number   : /-?[0-9]+/ ;                             \
      operator : '+' | '-' | '*' | '/' ;                  \
      expr     : <number> | '(' <operator> <expr>+ ')' ;  \
      lispy    : /^/ <operator> <expr>+ /$/ ;             \
    ",
    Number, Operator, Expr, Lispy);
  
  puts("Lispy Version 0.0.0.0.2");
  puts("Press Ctrl+c to Exit\n");
  
  while (1) {
  
    char* input = readline("lispy> ");
    add_history(input);
    
    /* Attempt to parse the user input */
    mpc_result_t r;
    if (mpc_parse("<stdin>", input, Lispy, &r)) {
      /* On success print and delete the AST */
      mpc_ast_print(r.output);
      mpc_ast_delete(r.output);
    } else {
      /* Otherwise print and delete the Error */
      mpc_err_print(r.error);
      mpc_err_delete(r.error);
    }
    
    free(input);
  }
  
  /* Undefine and delete our parsers */
  mpc_cleanup(4, Number, Operator, Expr, Lispy);
  
  return 0;
}

Metas bônus


  • › Escreva uma expressão regular que case strings com tudo a ou b tais como aababa ou bbaa.
  • › Escreva uma expressão regular que case strings de a e b consecutivos, tais como ababab ou aba.
  • › Escreva uma expressão regular que case com pit, pot e respite mas não case com not peat, spit, ou part.
  • › Mude a gramática para adicionar um novo operador como o %.
  • › Mude a gramática para reconhecer operadores escritos em formato textual add, sub, mul, div.
  • › Mude a gramática para reconhecer números decimais como 0.01, 5.21, ou 10.2.
  • › Mude a gramática para fazer os operadores escritos convencionalmente, entre duas expressões.
  • › Use a gramática do capítulo anterior para analisar Doge. Você precisa adicionar começo e fim da entrada.

Navegação

‹ Linguagens

• Conteúdo •

Avaliação ›