21

我正在尝试构建 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

这里有什么错误？

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

4

7 回答 7

12

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

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

于 2009-02-05T18:46:04.873 回答
12

错误确实在词法分析器中。你的括号最终是最后一个“。” 在词法分析器中，并且不会在解析器中显示为括号。

添加规则如

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

到词法分析器，并在解析器中将所有出现的 '(', ')' 分别更改为 LPAREN 和 RPAREN。（此外，您需要在定义令牌列表的位置#define LPAREN 和 RPAREN）

注意：我不确定语法，可能是反斜杠错误。

于 2009-02-06T13:22:40.330 回答
4

您是正确的，因为您需要定义一个非终端。那将被定义为一组 sexpr。我不确定 YACC 的语法。对于解析器生成器，我偏爱ANTLR，语法为：

program: sexpr*

表示 0 个或多个 sexpr。

使用 YACC 语法更新：

program :  /* empty */
        | program sexpr
        ;

不在 YACC 中，但无论如何可能会有所帮助，这是 ANTLR v3 中的完整语法，适用于您描述的情况（不包括词法分析器中的字符串，因为它对本示例并不重要，也使用 C# 控制台输出，因为这是我测试过的):

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

这不会像在 YACC 中那样工作，因为 YACC 生成和 LALR 解析器，而 ANTLR 是修改后的递归下降。如果您想这样做，ANTLR 有一个 C/C++ 输出目标。

于 2009-02-05T18:29:02.897 回答
2

您是否需要一个 yacc/bison 解析器？“读取 lisp 语法的子集”阅读器在 C 中并不难实现（从 read_sexpr 函数开始，当你看到一个 '(' 时分派到一个 read_list，然后构建一个包含的 sexprs 的列表，直到一个 ' )' ；否则，调用一个 read_atom 来收集一个原子并在它不能再读取原子组成字符时返回它）。

但是，如果您希望能够阅读任意 Common Lisp，则需要（最坏的情况）实现 Common Lisp，因为 CL 可以修改阅读器运行时（甚至在不同的读取表运行时之间切换在程序控制下；当您想要加载用另一种语言或 lisp 方言编写的代码时非常方便）。

于 2009-02-06T13:48:10.873 回答
1

自从我与 YACC 合作以来已经很长时间了，但是您确实需要一个顶级的非终端。您能否更具体地说明“尝试过”和“它似乎没有用”？或者，就此而言，错误是什么？

我还怀疑 YACC 对于这种语法轻量级的语言来说可能是矫枉过正。更简单的东西（如递归下降）可能会更好。

于 2009-02-05T18:32:33.653 回答
1

你可以在这里试试这个语法。

于 2009-02-05T18:49:07.037 回答
1

我刚试过，我的“yacc lisp 语法”工作正常：

%start exprs

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

list:
    '(' exprs ')'
    ;

expr:
    atom
    | list
    ;

atom:
    IDENTIFIER
    | CONSTANT
    | NIL
    | '+'
    | '-'
    | '*'
    | '^'
    | '/'
    ;
于 2013-02-24T19:04:40.677 回答