Gramática Lisp en yacc

Question

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

Hasta donde puedo decir, que necesito un solo no terminal definido como un programa, sobre el cual todo el árbol de análisis puede colgar. Pero lo intenté y no pareció funcionar.

edición - 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 coincidencia excesiva ...

(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

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.

Añadir reglas como

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

al léxico y cambiar todas las apariciones de '(', ')' a LPAREN y RPAREN, respectivamente, en el analizador. (también, necesita #define LPAREN y RPAREN donde define su lista de tokens)

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

Answer 2

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 generadores de analizadores sintácticos y la sintaxis sería:

program: sexpr* 

Indicando 0 o más sexpr.

actualización 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, ya que no es importante para este ejemplo, también utiliza C# salida de la consola porque eso es lo que he comprobado 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. Hay un objetivo de salida de C/C++ para ANTLR si quisiera ir por ese camino.

Answer 3

Ha pasado mucho tiempo desde que trabajé con YACC, pero necesita 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 4

La gramática de Lisp no se puede representar como gramática sin contexto, y yacc no puede analizar todo el código de lisp. Es debido a las características 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, a continuación, el texto del programa es una secuencia de sexprs.

Answer 5

Usted podría intentar this grammar here.

Answer 6

¿Se necesita un neccesarily yacc/analizador de 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 una read_list cuando ves un '(', que a su vez crea una lista de sexprs contenidos hasta un ') 'se ve, de lo contrario, llame a read_atom que recoge 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 lecturas tablas en tiempo de ejecución bajo control de programa, bastante útil cuando se quiere cargar código escrito en otro idioma o dialecto de ceceo).

Answer 7

yo sólo lo han probado, 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 
    | '+' 
    | '-' 
    | '*' 
    | '^' 
    | '/' 
    ;