Lisp Grammatik in Yacc

Question

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

stelle ich diese Eingaben und Fehlermeldungen ...

(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 definiert als ein Programm, auf dem der ganze Parse-Baum hängen kann. Aber ich habe es versucht und es schien nicht zu funktionieren.

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

program: slist; 

slist: slist sexpr | sexpr; 

Aber es erlaubt Probleme wie:

(1 1 

Edit2: Die 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 Überdeckung ...

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

Was ist der Fehler hier?

edit: Der Fehler war im Lexer.

Answer 1

Der Fehler liegt wirklich im Lexer. Ihre Klammern enden als letztes "." im Lexer und erscheinen nicht als Klammern im Parser.

hinzufügen Regeln wie

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

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

Hinweis: Ich bin mir nicht sicher über die Syntax, könnte die Backslashes falsch sein.

Answer 2

Sie haben Recht, dass Sie ein Nicht-Terminal definieren müssen. Das würde als eine Reihe von Sexpr definiert werden. Ich bin mir der YACC-Syntax dafür nicht sicher. Ich bin teilweise zu ANTLR für Parser-Generatoren und die Syntax wäre:

program: sexpr* 

Anzeige 0 oder mehr sexpr.

Aktualisierung 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 nicht wichtig ist, für dieses Beispiel verwendet auch Konsolenausgabe C#, weil das ist, was ich mit) getestet:

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 und LALR Parser erzeugt, während ANTLR eine modifizierte rekursive Abstieg ist. Es gibt ein C/C++ - Ausgabeziel für ANTLR, wenn Sie diesen Weg gehen wollten.

Answer 3

Es ist schon lange her, dass ich mit YACC gearbeitet habe, aber Sie brauchen ein Non-Terminal der obersten Ebene. Könntest du etwas genaueres über "probier es" und "es scheint nicht zu funktionieren" sagen? Oder was sind die Fehler?

Ich würde auch vermuten, dass YACC für eine solche Sprache Syntax-Sprache übertrieben sein könnte. Etwas einfacheres (wie rekursiver Abstieg) könnte besser funktionieren.

Answer 4

Die Lisp-Grammatik kann nicht als kontextfreie Grammatik dargestellt werden und yacc kann den gesamten Lisp-Code nicht analysieren. Es ist wegen Lisp Funktionen wie Lese-Auswertung und programmierbaren Leser. Um also nur einen beliebigen Lisp-Code zu lesen, muss ein vollständiges Lispeln ausgeführt werden. Dies ist keine obskure, nicht verwendete Funktion, aber es wird tatsächlich verwendet. Z. B. CL-INTERPOL, CL-SQL.

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

Answer 5

Sie könnten versuchen this grammar here.

Answer 6

Benötigen Sie einen Yacc/Bison Parser? Ein "liest eine Teilmenge der Lisp Syntax" Leser ist nicht so schwer in C zu implementieren (starten Sie mit einer read_sexpr Funktion, Versand an eine read_list wenn Sie ein '(' sehen, das wiederum eine Liste von enthaltenen sexprs bis ein ') 'wird gesehen, andernfalls rufen Sie ein read_atom auf, das ein Atom sammelt und es zurückgibt, wenn es keine atomkonstituenten Zeichen mehr lesen kann.

Wenn Sie jedoch Arbitrary Common Lisp lesen möchten, müssen Sie (im schlimmsten Fall) ein Common Lisp implementieren, da CL die Reader-Laufzeit ändern kann (und sogar zwischen verschiedenen Lese- Tabellenlaufzeit unter Programmkontrolle; ziemlich praktisch, wenn Sie Code laden möchten, der in einer anderen Sprache oder einem anderen Dialekt von Lisp geschrieben wurde).

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 
    | '+' 
    | '-' 
    | '*' 
    | '^' 
    | '/' 
    ;