grammaire Lisp yacc

Question

Je suis en train de construire une grammaire Lisp. Facile, non? Apparemment pas.

Je vous présente ces entrées et une erreur de réception ...

( 1 1)
23 23 23 
ui ui

Ceci est la grammaire ...

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

Pour autant que je peux dire, j'ai besoin d'un seul non terminal défini comme un programme, sur lequel l'ensemble arbre d'analyse syntaxique peut se bloquer. Mais je l'ai essayé et il ne semble pas fonctionner.

modifier - ce fut mon approche "terminal haut":

program: slist;

slist: slist sexpr | sexpr;

Mais il permet des problèmes tels que:

( 1 1 

Edit2: Le code FLEX est ...

%{
    #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 exemple de plus en correspondance ...

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

Quelle est l'erreur ici?

edit: L'erreur était dans le lexer

.

Answer 1

L'erreur est vraiment dans le lexer. Vos parenthèses finissent comme le dernier « » dans le lexer, et ne se présentent pas comme entre parenthèses dans l'analyseur.

Ajoutez des règles comme

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

à l'analyseur syntaxique et changer toutes les occurrences de ( ',') respectivement à LPAREN et RPAREN dans l'analyseur syntaxique. (, Vous devez également #define LPAREN et RPAREN où vous définissez votre liste de jetons)

Note: Je ne suis pas sûr de la syntaxe, pourrait être les anti-slash sont erronés

.

Answer 2

grammaire Lisp ne peut pas être représentée comme la grammaire hors-contexte, et yacc ne peut pas analyser tout le code Lisp. Il est à cause de caractéristiques telles que Lisp-évaluation lire et lecteur programmable. Donc, pour juste lire un code arbitraire Lisp, vous devez avoir une course pleine Lisp. Ce n'est pas une caractéristique obscure, non utilisé, mais il est effectivement utilisé. Par exemple, CL-INTERPOL, CL-SQL.

Si l'objectif est d'analyser un sous-ensemble de Lisp, le texte du programme est une séquence de sexprs.

Answer 3

Vous avez raison dans ce que vous devez définir un non-terminal. Ce serait défini comme un ensemble de SEXPR. Je ne suis pas sûr de la syntaxe YACC pour cela. Je suis partie à ANTLR pour les générateurs d'analyseur et la syntaxe serait:

program: sexpr*

Indiquant 0 ou plus SEXPR.

Mise à jour avec la syntaxe YACC:

program :  /* empty */
        | program sexpr
        ;

Non YACC, mais pourrait être utile de toute façon, voici une grammaire complète dans ANTLR v3 qui fonctionne pour les cas que vous avez décrit (exclut les chaînes dans le lexer parce qu'il n'a pas d'importance pour cet exemple, utilise également la sortie de la console C # parce que ce que je testé avec):

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

Cela ne fonctionne pas exactement comme il est en YACC parce que YACC génère et analyseur LALR en ANTLR est une descente récursive modifiée. Il y a un objectif de sortie de C / C pour ANTLR si vous voulez aller dans ce sens.

Answer 4

Avez-vous besoin d'un neccesarily yacc / analyseur de bison? Un « lit un sous-ensemble de la syntaxe Lisp » lecteur est pas difficile à mettre en œuvre en C (en commençant par une fonction read_sexpr, envoi à un read_list quand vous voyez un « ( », qui à son tour crée une liste de sexprs contenus jusqu'à ce qu'un ' ) » est vu;. sinon, appeler un read_atom qui recueille un atome et il retourne quand elle ne peut plus lire les caractères constituant-atome)

Cependant, si vous voulez être en mesure de lire arbritary Common Lisp, vous devrez (au pire) mettre en œuvre un Common Lisp, comme CL peut modifier le lecteur run-time (et même basculer entre les différentes tables de lecture la gestion du temps sous le contrôle du programme;. tout à fait à portée de main lorsque vous êtes désireux de charger le code écrit dans une autre langue ou le dialecte de Lisp)

Answer 5

Il a été longtemps que je travaille avec YACC, mais vous avez besoin d'un haut niveau non-terminal. Pourriez-vous être plus précis sur « essayé » et « il ne semble pas fonctionner »? Ou, pour cette question, ce sont les erreurs?

Je pense que aussi YACC peut-être trop pour un tel langage de syntaxe de lumière. Quelque chose plus simple (comme la descente récursive) pourrait mieux fonctionner.

Answer 6

Vous pouvez essayer cette grammaire .

Answer 7

Je viens d'essayer, ma "grammaire yacc lisp" fonctionne très bien:

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

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