grammatica Lisp in yacc

Question

Sto cercando di costruire una grammatica Lisp. Facile, no? A quanto pare no.

presento questi ingressi e ricevo errori ...

( 1 1)
23 23 23 
ui ui

Questa è la grammatica ...

%%
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");}
    ;
%%

Da quanto posso dire, ho bisogno di un singolo non terminale definito come un programma, su cui l'intero albero sintattico può appendere. Ma ho provato e non è sembrato funzionare.

modifica - questo è stato il mio approccio "stazione a monte":

program: slist;

slist: slist sexpr | sexpr;

Ma permette problemi come:

( 1 1 

Edit2: il codice 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; }
.
%%

Un esempio della over-matching ...

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

Qual è l'errore qui?

modifica: L'errore è stato nel lexer

.

Answer 1

L'errore è davvero nel lexer. I vostri parentesi finiscono come l'ultimo "" nel lexer, e non apparire come parentesi nel parser.

Aggiungi regole come

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

per il lexer e cambiare tutte le occorrenze di '(', ')' per LPAREN e RPAREN, rispettivamente, nel parser. (Anche, è necessario #define LPAREN e RPAREN dove si definisce la vostra lista di token)

Nota: Non sono sicuro sulla sintassi, potrebbero essere le barre inverse sono sbagliati

.

Answer 2

grammatica Lisp non può essere rappresentato come la grammatica context-free, e yacc non è in grado di analizzare tutto il codice Lisp. È a causa di caratteristiche lisp come lettura e valutazione lettore programmabile. Così, al fine solo per leggere un codice Lisp arbitrario, è necessario disporre di una completa esecuzione Lisp. Questo non è un oscuro, caratteristica non utilizzato, ma è effettivamente utilizzato. Per esempio, CL-INTERPOL, CL-SQL.

Se l'obiettivo è quello di analizzare un sottoinsieme di Lisp, quindi il testo del programma è una sequenza di sexprs.

Answer 3

Sei corretta in quanto è necessario definire un non-terminale. Questo sarebbe essere definito come un insieme di sEspr. Non sono sicuro della sintassi YACC per questo. Io ho un debole per ANTLR per i generatori di parser e la sintassi sarebbe:

program: sexpr*

Indicando 0 o più sEspr.

Aggiornamento con la sintassi YACC:

program :  /* empty */
        | program sexpr
        ;

Non in YACC, ma potrebbe essere utile in ogni caso, ecco una grammatica completa in ANTLR v3 che funziona per i casi descritti (esclude stringhe nel lexer perché non è importante per questo esempio, utilizza anche C # console di output perché è quello che ho testato con):

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();};

Questo non funziona esattamente come è in YACC perché YACC genera e LALR parser ANTLR, mentre è una discesa ricorsiva modificato. C'è un C / C ++ di destinazione di output per ANTLR se si voleva andare in quel modo.

Answer 4

Avete bisogno di un neccesarily Yacc / parser bisonte? A "si legge un sottoinsieme della sintassi Lisp" lettore non è così difficile da implementare in C (iniziare con una funzione di read_sexpr, la spedizione verso un read_list quando si vede un '(', che a sua volta crea un elenco di sexprs contenuti fino a quando un ' )' è visto,. in caso contrario, chiamare un read_atom che raccoglie un atomo e la restituisce quando non è più in grado di leggere i caratteri atomo-componente)

Tuttavia, se si vuole essere in grado di leggere arbritary Common Lisp, è necessario (nel peggiore dei casi) implementare un Common Lisp, come CL può modificare run-time il lettore (e anche commutare tra diversi lettura-tavoli run-time sotto il controllo del programma;. molto utile quando hai intenzione di caricare il codice scritto in un'altra lingua o dialetto Lisp)

Answer 5

E 'passato molto tempo da quando ho lavorato con YACC, ma avete bisogno di un livello superiore non terminale. Potrebbe essere più preciso circa "provato" e "non mi sembrava al lavoro"? Oppure, se è per questo, ciò che gli errori sono?

Mi piacerebbe anche il sospetto che YACC potrebbe essere eccessivo per un linguaggio come la sintassi-luce. Qualcosa di più semplice (come discesa ricorsiva) potrebbe funzionare meglio.

Answer 6

Si potrebbe provare a questa grammatica qui .

Answer 7

Ho appena provato, il mio "yacc lisca grammatica" funziona bene:

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

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