gramática Lisp em yacc

Question

Eu estou tentando construir uma gramática Lisp. Fácil, não é? Aparentemente não.

Eu apresento estas entradas e receber erros ...

( 1 1)
23 23 23 
ui ui

Esta é a gramática ...

%%
sexpr: atom                 {printf("matched sexpr\n");}
    | list
    ;
list: '(' members ')'       {printf("matched list\n");}
    | '('')'                {printf("matched empty list\n");}
    ;
members: sexpr              {printf("members 1\n");}
    | sexpr members         {printf("members 2\n");}
    ;
atom: ID                    {printf("ID\n");}
    | NUM                   {printf("NUM\n");}
    | STR                   {printf("STR\n");}
    ;
%%

tão perto quanto eu posso dizer, eu preciso de um único não-terminal definido como um programa, sobre o qual toda a árvore de análise pode pendurar. Mas eu tentei e não parece trabalho.

Editar - esta foi a minha abordagem "top terminal":

program: slist;

slist: slist sexpr | sexpr;

mas permite problemas, tais como:

( 1 1 

Edit2: O código FLEX é ...

%{
    #include <stdio.h>
    #include "a.yacc.tab.h"
    int linenumber;
    extern int yylval;
%}
%%
\n                         { linenumber++; }
[0-9]+                     { yylval = atoi(yytext); return NUM; }
\"[^\"\n]*\"               { return STR; }
[a-zA-Z][a-zA-Z0-9]*       { return ID; }
.
%%

Um exemplo do excesso de correspondência ...

(1 1 1)
NUM
matched sexpr
NUM
matched sexpr
NUM
matched sexpr
(1 1
NUM
matched sexpr
NUM
matched sexpr

O que é o erro aqui?

edit:. O erro foi no lexer

Answer 1

O erro é realmente no léxico. Seus parênteses acabar como o último "" no lexer, e não aparecem como parênteses no analisador.

Adicionar regras como

\)     { return RPAREN; }
\(     { return LPAREN; }

para o lexer e alterar todas as ocorrências de '(', ')' para LPAREN e RPAREN respectivamente no analisador. (Também, você precisa #define LPAREN e RPAREN onde você define a sua lista de token)

Nota:. Eu não tenho certeza sobre a sintaxe, poderiam ser as barras invertidas estão errados

Answer 2

Lisp gramática não pode ser representado como gramática livre de contexto, e yacc não pode analisar todo o código lisp. É por causa de lisp recursos como leitura-avaliação e leitor programável. Assim, a fim só para ler um código lisp arbitrária, você precisa ter um lisp funcionamento completo. Esta não é uma característica obscura, não utilizado, mas é realmente usado. Por exemplo, CL-INTERPOL, CL-SQL.

Se o objetivo é analisar um subconjunto de lisp, em seguida, o texto do programa é uma seqüência de sexprs.

Answer 3

Você está correto em que você precisa definir um não-terminal. Que pode ser definido como um conjunto de sexpr. Eu não tenho certeza da sintaxe YACC para isso. Eu sou parcial para ANTLR para geradores de analisador e a sintaxe seria:

program: sexpr*

Indicando 0 ou mais sexpr.

Atualização com a sintaxe YACC:

program :  /* empty */
        | program sexpr
        ;

Não no YACC, mas pode ser de qualquer maneira útil, aqui está uma gramática completa em ANTLR v3 que funciona para os casos que você descreveu (exclui cordas no lexer porque não é importante para este exemplo, também usa C saída # consola porque é isso que eu testei com):

program: (sexpr)*;

sexpr: list
    |  atom            {Console.WriteLine("matched sexpr");}
    ;

list:     
   '('')'              {Console.WriteLine("matched empty list");}
   | '(' members ')'   {Console.WriteLine("matched list");}

    ;

members: (sexpr)+      {Console.WriteLine("members 1");};

atom: Id               {Console.WriteLine("ID");}
    | Num              {Console.WriteLine("NUM");}
    ;


Num: ( '0' .. '9')+;
Id: ('a' .. 'z' | 'A' .. 'Z')+;
Whitespace : ( ' ' | '\r' '\n' | '\n' | '\t' ) {Skip();};

Isso não vai funcionar exatamente como está em YACC porque YACC gera e analisador LALR enquanto ANTLR é uma descida recursiva modificado. Há meta de produção de um C / C ++ para ANTLR se você queria ir por esse caminho.

Answer 4

Você neccesarily precisa de um yacc / parser bisonte? A "lê um subconjunto de sintaxe lisp" leitor não é tão difícil de implementar em C (começar com uma função read_sexpr, expedição para um read_list quando você vê a '(', que por sua vez cria uma lista de sexprs contidos até que um ' )' é visto;. Caso contrário, chamar um read_atom que recolhe um átomo e devolve-lo quando ele já não pode ler caracteres átomo-constituintes)

No entanto, se você quer ser capaz de ler arbritary Lisp comum, você precisa (no pior) implementar um Lisp comum, como CL pode modificar o leitor run-time (e até mesmo alternar entre diferentes de leitura-tables tempo de execução sob controle programa;. bastante útil quando você está querendo carregar código escrito em outro idioma ou dialeto do Lisp)

Answer 5

Tem sido um longo tempo desde que eu trabalhei com YACC, mas você precisa de um de nível superior não-terminal. Você poderia ser mais específico sobre "tentou fazê-lo" e "não parecem funcionar"? Ou, para essa matéria, o que os erros são?

Eu também suspeito que YACC pode ser um exagero para uma língua tão sintaxe-luz. Algo mais simples (como descendente recursivo) pode funcionar melhor.

Answer 6

Você poderia tentar essa gramática aqui .

Answer 7

Eu apenas tentei isso, meu "yacc lisp gramática" fino funciona:

%start exprs

exprs:
    | exprs expr
    /// if you prefer right recursion :
    /// | expr exprs
    ;

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

atom:
    IDENTIFIER
    | CONSTANT
    | NIL
    | '+'
    | '-'
    | '*'
    | '^'
    | '/'
    ;