gramática Lisp en yacc

Question

Estoy tratando de construir una gramática Lisp. Fácil, ¿verdad? Al parecer, no.

presento estas entradas y recibo errores ...

( 1 1)
23 23 23 
ui ui

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

Lo más cerca que puedo decir, que necesito un solo no terminal se define como un programa, en la que todo el árbol de análisis sintáctico puede colgar. Pero lo probé y no me parece funcionar.

editar - esta fue mi enfoque "terminal":

program: slist;

slist: slist sexpr | sexpr;

Pero permite que los problemas tales como:

( 1 1 

Edit2: El código FLEX es ...

%{
    #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 ejemplo de la coincidencia de más de ...

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

¿Cuál es el error aquí?

editar: El error estaba en el léxico

.

Answer 1

El error es realmente en el analizador léxico. Sus paréntesis, terminan como el último "" en el léxico, y no se mostrará como paréntesis en el analizador.

Añadir reglas como

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

a la lexer y cambiar todas las apariciones de '(', ')' a LPAREN y RPAREN, respectivamente, en el analizador. (También, es necesario #define LPAREN y RPAREN donde se define la lista de token)

Nota: No estoy seguro acerca de la sintaxis, podría ser la barras invertidas son mal

.

Answer 2

gramática Lisp no puede ser representada como la gramática libre de contexto, y yacc no puede analizar todo el código Lisp. Es debido a características tales como Lisp-evaluación leer y lector programable. Por lo tanto, con el fin sólo para leer un código Lisp arbitraria, es necesario tener una ejecución completa Lisp. Esto no es una característica oculta, no usado, pero se utiliza realmente. Por ejemplo, CL-INTERPOL, CL-SQL.

Si el objetivo es analizar un subconjunto de Lisp, a continuación, el texto del programa es una secuencia de sexprs.

Answer 3

Tiene usted razón en que es necesario definir un no terminal. Que se definiría como un conjunto de sexpr. No estoy seguro de la sintaxis YACC para eso. Soy parcial a antlr para generadores de analizadores sintácticos y la sintaxis sería:

program: sexpr*

Indicando 0 o más sexpr.

Actualizar con la sintaxis YACC:

program :  /* empty */
        | program sexpr
        ;

No en YACC, pero podría ser útil de todos modos, aquí está una gramática completa en la versión 3 antlr que funcione para los casos que se describe (cadenas excluyen en el léxico, porque no es importante para este ejemplo, también utiliza C # salida de la consola porque eso es lo que yo probado 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();};

Esto no funcionará exactamente como está en YACC porque YACC genera y analizador LALR mientras antlr es un descenso recursivo modificado. No es un objetivo de producción de C / C ++ para antlr si quería ir en esa dirección.

Answer 4

¿Necesita un neccesarily yacc / analizador de Bison? Un "lee un subconjunto de la sintaxis Lisp" lector no es tan difícil de implementar en C (comenzar con una función read_sexpr, envío a un read_list cuando se ve un '(', que a su vez crea una lista de contenidos sexprs hasta que un ' )' se ve;. de lo contrario, llamar a un read_atom que recoge un átomo y lo devuelve cuando ya no puede leer caracteres de átomos-componente)

Sin embargo, si usted quiere ser capaz de leer arbritary Common Lisp, tendrá que (en el peor) implementar un Common Lisp, como CL puede modificar el lector de tiempo de ejecución (e incluso cambiar entre diferentes lecturas en las tablas en tiempo de ejecución bajo control del programa;. bastante útil cuando se está queriendo cargar el código escrito en otro idioma o dialecto de Lisp)

Answer 5

Ha sido un largo tiempo desde que trabajé con YACC, pero sí es necesario un alto nivel no terminal. Podría ser más específico acerca de "probado" y "no parecía que trabajar"? O, para el caso, lo que los errores son?

También me sospecho que YACC podría ser excesiva para un idioma tan-sintaxis de luz. Algo más simple (como descendente recursivo) podría funcionar mejor.

Answer 6

Usted podría intentar esta gramática aquí .

Answer 7

he intentado, mi "gramática yacc Lisp" funciona bien:

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

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