Gramática Lisp en yacc

grammar

Question

Estoy tratando de construir una gramática Lisp. Fácil, ¿verdad? Aparentemente 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");}
    ;
%%

Por lo que puedo decir, necesito un único no terminal definido como un programa, sobre el cual se puede colgar todo el árbol de análisis sintáctico. Pero lo intenté y no pareció funcionar.

editar - este fue mi enfoque de "terminal superior":

program: slist;

slist: slist sexpr | sexpr;

Pero permite 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 exceso de coincidencia ...

(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 lexer.

Answer 1

Ha pasado mucho tiempo desde que trabajé con YACC, pero necesitas un no terminal de alto nivel. ¿Podría ser más específico acerca de "lo probé" y "no pareció funcionar"? O, para el caso, ¿cuáles son los errores?

También sospecho que YACC podría ser excesivo para un lenguaje tan ligero como la sintaxis. Algo más simple (como el descenso recursivo) podría funcionar mejor.

Answer 2

La gramática de Lisp no se puede representar como gramática libre de contexto, y yacc no puede analizar todo el código de lisp. Se debe a las funciones de lisp, como la evaluación de lectura y el lector programable. Entonces, para poder leer un código de lisp arbitrario, necesita tener un lisp completo en ejecución. Esta no es una función oscura y no utilizada, pero en realidad se usa. Por ejemplo, CL-INTERPOL, CL-SQL.

Si el objetivo es analizar un subconjunto de lisp, el texto del programa es una secuencia de sexprs.

Answer 3

Podrías probar esta gramática aquí .

Answer 4

¿Necesitas necesariamente un analizador de yacc / bison? Un lector "lee un subconjunto de sintaxis lisp" no es tan difícil de implementar en C (comienza con una función read_sexpr, envía a read_list cuando ves un ''('', que a su vez crea una lista de sexprs contenidos hasta que '' ) ''se ve; de ​​lo contrario, llame a read_atom que recopila un átomo y lo devuelve cuando ya no puede leer los caracteres que constituyen el átomo).

Sin embargo, si desea poder leer Common Lisp arbritary, necesitará (en el peor de los casos) implementar Common Lisp, ya que CL puede modificar el tiempo de ejecución del lector (e incluso cambiar entre diferentes tablas de lectura en tiempo de ejecución) bajo control de programa, bastante útil cuando quieres cargar código escrito en otro idioma o dialecto de ceceo).

Answer 5

El error está realmente en el lexer. Tus paréntesis terminan como el último "." en el lexer, y no aparecen como paréntesis en el analizador.

Agregue reglas como

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

al lexer y cambie todas las ocurrencias de ''('', '')'' a LPAREN y RPAREN respectivamente en el analizador. (también, necesitas #define LPAREN y RPAREN donde defines tu lista de tokens)

Nota: No estoy seguro acerca de la sintaxis, podría ser que las barras invertidas son incorrectas.

Answer 6

Tiene razón en que necesita definir un terminal no terminal. Eso se definiría como un conjunto de sexpr. No estoy seguro de la sintaxis de YACC para eso. Soy parcial a ANTLR para los generadores de analizadores y la sintaxis sería:

program: sexpr*

Indicando 0 o más sexpr.

Actualización con sintaxis YACC:

program :  /* empty */
        | program sexpr
        ;

No en YACC, pero podría ser útil de todos modos, aquí hay una gramática completa en ANTLR v3 que funciona para los casos que describes (excluye cadenas en el lexer porque no es importante para este ejemplo, también usa salida de consola C # porque eso es lo que probé 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 en YACC porque YACC genera y el analizador LALR mientras que ANTLR es un descenso recursivo modificado. Hay un objetivo de salida de C / C ++ para ANTLR si quisiera ir por ese camino.

Answer 7

Lo probé, mi "gramática de yac lisp" funciona bien:

%start exprs

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

list:
    ''('' exprs '')''
    ;

expr:
    atom
    | list
    ;

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