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

エラーは実際にはレクサーにあります。括弧は最後の「。」になります。パーサーでは括弧として表示されません。

のようなルールを追加します。

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

パーサーで「(」、「)」のすべての出現箇所をそれぞれ LPAREN および RPAREN に変更します。(また、トークン リストを定義する LPAREN と RPAREN を #define する必要があります)

注：構文についてはわかりません。バックスラッシュが間違っている可能性があります。

于 2009-02-06T13:22:40.330 に答える
12

Lisp 文法は文脈自由文法として表すことはできず、yacc はすべての Lisp コードを解析することはできません。これは、読み取り評価やプログラマブル リーダーなどの Lisp 機能によるものです。したがって、任意の Lisp コードを読み取るだけでも、完全な Lisp を実行する必要があります。これは、あいまいで使用されていない機能ではありませんが、実際に使用されています。例: CL-INTERPOL、CL-SQL。

目的が Lisp のサブセットを解析することである場合、プログラム テキストは一連の sexprs です。

于 2009-02-05T18:46:04.873 に答える
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();};

ANTLRは修正された再帰下降であるのに対し、YACCはLALRパーサーを生成するため、これはYACCの場合とまったく同じようには機能しません。そのようにしたい場合は、ANTLRのC /C++出力ターゲットがあります。

于 2009-02-05T18:29:02.897 に答える
2

必ず yacc/bison パーサーが必要ですか? 「lisp構文のサブセットを読み取る」リーダーは、Cで実装するのはそれほど難しくありません（read_sexpr関数で開始し、「（」が表示されたときにread_listにディスパッチします。これにより、含まれるsexprのリストが「それ以外の場合は、アトムを収集する read_atom を呼び出し、アトム構成文字を読み取ることができなくなったときにそれを返します)。

ただし、任意の Common Lisp を読み取れるようにしたい場合は、(最悪の場合) Common Lisp を実装する必要があります。これは、CL がリーダー ランタイムを変更できるため (さらに、異なる読み取りテーブル ランタイム間で切り替えることさえできるからです)。プログラムの制御下で; 別の言語または Lisp の方言で書かれたコードをロードしたい場合に非常に便利です)。

于 2009-02-06T13:48:10.873 に答える
1

YACC を使用してから長い時間が経ちましたが、トップレベルの非端末が必要です。「試してみた」と「うまくいかなかったようだ」について、より具体的に教えていただけますか？または、さらに言えば、エラーは何ですか?

また、YACC は、このようなシンタックスの軽い言語にはやり過ぎではないかと思います。もっと単純なもの (再帰的降下など) の方がうまくいくかもしれません。

于 2009-02-05T18:32:33.653 に答える
1

試してみたところ、「yacc lisp grammar」は正常に動作します。

%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 に答える
1

ここでこの文法を試すことができます。

于 2009-02-05T18:49:07.037 に答える