Lisp Grammatik in yacc

Question

Ich versuche, eine Lisp Grammatik zu bauen. Einfach richtig? Offenbar nicht.

Ich stelle diese Eingänge und Empfangsfehler ...

( 1 1)
23 23 23 
ui ui

Dies ist die Grammatik ...

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

So nahe, wie ich sagen kann, ich brauche einen einzigen Nicht-Terminal als Programm definiert, auf das der gesamte Parsing-Baum hängen. Aber ich versuchte es und es scheint nicht zu arbeiten.

bearbeiten - das war mein "Top-Terminal" Ansatz:

program: slist;

slist: slist sexpr | sexpr;

Aber es erlaubt Probleme wie:

( 1 1 

Edit2: Der FLEX-Code ist ...

%{
    #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; }
.
%%

Ein Beispiel für die Übereinstimmungen ...

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

Was ist hier der Fehler?

edit: Der Fehler war in der Lexer

.

Answer 1

Der Fehler ist wirklich in der Lexer. Ihre Klammern am Ende als die letzten „“ in der Lexer, und zeigt nicht als Klammer im Parser auf.

Fügen Sie Regeln wie

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

zum Lexer und ändern Sie alle Vorkommen von '(', ')' zu LPAREN und RPAREN jeweils in den Parser. (Auch, müssen Sie LPAREN und RPAREN #define, wo Sie Ihre Token-Liste definieren)

Hinweis: Ich bin über die Syntax nicht sicher, könnte die Schrägstriche sind falsch

.

Answer 2

Lisp Grammatik nicht als kontextfreie Grammatik dargestellt werden, und yacc können nicht alle Lisp-Code analysieren. Es ist wegen der Lisp-Funktionen wie Lese Auswertung und programmierbarer Leser. Also, um einen beliebigen Lisp Code nur lesen können, benötigen Sie eine vollständige Lisp am Laufen haben. Das ist nicht irgendeine obskure, nicht genutztes Feature, aber es tatsächlich verwendet wird. Z. B. CL-INTERPOL, CL-SQL.

Wenn das Ziel eine Teilmenge von Lisp zu analysieren ist, dann wird der Programmtext ist eine Folge von sexprs.

Answer 3

Sie sind richtig, dass Sie einen nicht-Terminal definieren müssen. Das wäre als ein Satz von sexpr definiert werden. Ich bin die YACC Syntax für das nicht sicher. Ich bin teilweise zu ANTLR für Parser-Generatoren und die Syntax wäre:

program: sexpr*

Anzeige 0 oder mehr sexpr.

Update mit YACC Syntax:

program :  /* empty */
        | program sexpr
        ;

Nicht in YACC, aber vielleicht hilfreich sowieso sein, hier ist eine vollständige Grammatik in ANTLR v3, die für die Fälle, die Sie beschrieben (ausgenommen Strings in der Lexer funktioniert, weil es für dieses Beispiel nicht wichtig ist, verwendet auch die Konsolenausgabe C #, weil das ist, was ich getestet es mit):

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

Dies wird nicht genau arbeiten, wie in YACC ist, weil YACC erzeugt und LALR Parser während ANTLR eine modifizierte rekursive Abstieg ist. Es ist ein C / C ++ Ausgabeziel für ANTLR, wenn Sie diesen Weg gehen wollen.

Answer 4

Sie benötigen neccesarily einen yacc / Bison-Parser? A „liest eine Teilmenge von Lisp-Syntax“ Leser nicht so schwer ist in C (beginnen mit einer read_sexpr Funktion, Versand in einen read_list zu implementieren, wenn Sie ein ‚(‘ zu sehen, dass wiederum eine Liste der enthaltenen sexprs bis eine baut " ‚) zu sehen ist;. andernfalls eine read_atom aufrufen, die ein Atom sammelt und gibt es, wenn es nicht mehr atom konstituierenden Zeichen lesen kann)

Wenn Sie jedoch arbritary Common Lisp zu lesen in der Lage sein wollen, müssen Sie (im schlimmsten Fall) führen ein Common Lisp, als CL der Leser Laufzeit ändern kann (und schalten sogar zwischen verschiedenen Lese-Tabellen Laufzeit programmgesteuert;. ganz praktisch, wenn Sie wollen, Code laden, in einer anderen Sprache oder Dialekt von Lisp geschrieben)

Answer 5

Es ist schon eine lange Zeit, da ich mit YACC gearbeitet, aber Sie tun müssen, ein Top-Level nicht-Terminal. Könnten Sie etwas konkreter über „versucht, es“ zu sein und „es scheint nicht zu funktionieren“? Oder was das betrifft, was die Fehler sind?

Ich würde auch vermuten, dass YACC für eine solche Syntax-Licht Sprache Overkill sein könnte. Etwas einfacher ist (wie rekursive Abstieg) könnte besser funktionieren.

Answer 6

Sie könnten versuchen, diese Grammatik hier .

Answer 7

Ich habe gerade versucht, meine "yacc Lisp Grammatik" funktioniert:

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

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