Lisp grammar in yacc

Question

J'essaie de construire une grammaire Lisp. Facile, non? Apparemment non.

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

(1 1) 
23 23 23 
ui ui 

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

autant que je peux dire, j'ai besoin d'un seul non terminal défini en tant que programme, sur lequel l'ensemble de l'arbre d'analyse peut se bloquer. Mais j'ai essayé et ça n'a pas l'air de marcher.

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 l'appariement ...

(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 n'apparaissent pas comme des parenthèses dans l'analyseur.

Ajouter des règles comme

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

au lexer et changer toutes les occurences de '(', ')' respectivement à LPAREN et RPAREN dans l'analyseur. (aussi, vous devez # définir LPAREN et RPAREN où vous définissez votre liste de jetons)

Remarque: Je ne suis pas sûr de la syntaxe, les barres obliques inverses sont peut-être incorrectes.

Answer 2

Vous avez raison de définir un terminal non-terminal. Cela 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 la suivante:

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 est pas important pour cet exemple, utilise également C# sortie de la console parce que ce que je l'ai 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 fonctionnera 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 une cible de sortie C/C++ pour ANTLR si vous voulez aller dans ce sens.

Answer 3

Ça faisait longtemps que je travaillais avec YACC, mais vous avez besoin d'un non-terminal de haut niveau. Pourriez-vous être plus précis sur "essayé" et "ça n'a pas l'air de marcher"? Ou, d'ailleurs, quelles sont les erreurs?

Je soupçonnerais également que YACC pourrait être exagéré pour un tel langage syntaxe-lumière. Quelque chose de plus simple (comme la descente récursive) pourrait mieux fonctionner.

Answer 4

La grammaire Lisp ne peut pas être représentée comme une grammaire sans contexte, et yacc ne peut pas analyser tout le code Lisp. C'est grâce aux fonctionnalités de LISP telles que la lecture-évaluation et le lecteur programmable. Donc, juste pour lire un code Lisp arbitraire, vous devez avoir un Lisp complet. Ce n'est pas une fonctionnalité obscure, non utilisée, mais elle est réellement utilisée. Par exemple, CL-INTERPOL, CL-SQL.

Si le but est d'analyser un sous-ensemble de lisp, alors le texte du programme est une séquence de sexprs.

Answer 5

Vous pouvez essayer this grammar here.

Answer 6

Avez-vous besoin d'un analyseur yacc/bison? Un lecteur "lit un sous-ensemble de syntaxe Lisp" n'est pas si difficile à implémenter dans C (commencez par une fonction read_sexpr, envoyez-le à read_list quand vous voyez un '(', qui construit une liste de sexprs contenus jusqu'à ') 'est vu, sinon, appelez un read_atom qui recueille un atome et le renvoie quand il ne peut plus lire les caractères atom-constituant. Cependant, si vous voulez être capable de lire Common Lisp arbritaire, vous devrez (au pire) implémenter un Common Lisp, car CL peut modifier l'exécution du lecteur (et même basculer entre différentes lectures). tables run-time sous le contrôle du programme, assez pratique lorsque vous voulez charger du code écrit dans une autre langue ou un dialecte de lisp).

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