yacc 中的 Lisp 语法

Question

我正在尝试构建 Lisp 语法。容易，对吧？显然不是。

我呈现这些输入并收到错误...

( 1 1)
23 23 23 
ui ui

这是语法...

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

据我所知，我需要一个定义为程序的非终端，整个解析树都可以卡在上面。但是我试了一下，好像不行。

编辑 - 这是我的“顶级终端”方法:

program: slist;

slist: slist sexpr | sexpr;

但它允许出现如下问题:

( 1 1 

Edit2:FLEX 代码是...

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

过度匹配的例子...

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

这里有什么错误？

编辑:错误在词法分析器中。

Answer 1

Lisp文法不能表示为上下文无关文法，yacc也不能解析所有的lisp代码。这是因为 lisp 具有读取评估和可编程读取器等功能。因此，为了阅读任意 lisp 代码，您需要运行完整的 lisp。这不是一些晦涩难懂、未使用的功能，而是实际使用的功能。例如，CL-INTERPOL、CL-SQL。

如果目标是解析 lisp 的一个子集，那么程序文本就是一个 sexprs 序列。