4

GLRパーサー、つまりあいまいな文法を処理できるパーサーを生成できると主張するいくつかの異なるパーサージェネレーター（Bison、DParserなど）を試しました。これは、私が話しているタイプの非常に単純なあいまいな文法です。

START: A | B;
A: C | D;
B: C | D;
C: T1 | T2;
D: T3 | T4;
T1: 't1';
T2: 't2';
T3: 't3';
T4: 't4';

パーサーを問題なく生成できますが、有効なはずのパーサー入力を与えると、「未解決のあいまいさ」エラーまたは完全なクラッシュが発生します。文法を明確なバージョンに変更しても、何の問題もありません。

GLR パーサーについて理解していないことは何ですか? 全体的なポイントは、あいまいな場合、可能なすべての解析がマージされるか行き止まりに達するまで追跡されるということだと思いました。必要なのは、入力の有効な解析があるかどうかを教えてくれるパーサーだけです。

助けてくれてありがとう。

編集：

これはイライラします。%dprec と %merge を使用して、Bison にあいまいなルールとターミナルを処理させることができましたが、処理が必要な種類の非常に単純だが非常に病理学的な疑似英語の文法が依然として詰まっています。

S: NP VP | NPA VP;
NPA: D N | NP PP;
NP: D N | NP PP | NPA;
VP: V NP | VP PP;
PP: P NP;
D: "the" | "a";
P: "in" | "with";
V: "saw";
N: "saw" | "girl" | "boy" | "park" | "telescope";

「a boy saw a girl」という入力に対して、Bison は解析できず、コード 1 を返します。一方、Tom は、この文法とこの入力文を完璧に処理し、未知の端末を可能な限りすべて割り当てるだけで自然に処理します。端末タイプ。しかし、Bison とは異なり、Tom は大きな文法で窒息します。（「チョーク」とは、さまざまな方法で失敗することを意味します。失敗モードが役立つ場合は、それらを報告できます。）

他にアイデアはありますか？

4

2 に答える 2

4

残念ながら、bison は (単一の) 解析を生成することを強く主張しているため、あいまいな解析をマージする方法を指定する必要があります。そうしないと、可能な解析が複数ある場合、bison の GLR パーサーは解析が曖昧であると文句を言うでしょう。

複数の解析のうちどれが受け入れられるかをあまり気にしないのであれば、bison を自分の意志に曲げるのはさほど難しくありません。%dprec最も簡単な方法は、あいまいな可能性のあるすべてのプロダクションに異なる を割り当てることです。その後、Bison は、たまたま優先順位が最も高い適用可能なプロダクションを選択します。

%merge単純な関数を使用して、bison に複数の解析について教えてもらうこともできます。バイソンのマニュアルに例があります。(この機能のドキュメントは良くありませんが、ニーズには十分かもしれません。そうでない場合は、お気軽に、より具体的な質問をしてください。)

私は DParser の経験があまりありませんが、マニュアルには、複数の可能な解析に直面したときの動作が似ていることが示されています: デフォルトは文句を言うことですが、独自の簡単なマージ機能を提供できます: 12、あいまいさ）

あいまいさは、優先順位と関連性に基づいて自動的に解決されます。さらに、他の解決手法が失敗した場合、ユーザー定義のあいまいさの解決が可能です。デフォルトのあいまい性ハンドラーは、未解決のあいまいさに対して致命的なエラーを生成します。この動作は、署名が で提供されているユーザー定義のリゾルバーに置き換えることができますdparse.h。

2 番目の例のバイソン GLR 文法の例を次に示します。私はレクサーを省略しましたが、これは実際には関係ありません (急いでいたので少し恥ずかしいです)。

%{
  int yylex();
  void yyerror(const char* msg);
%}

%error-verbose
%glr-parser

%token WORD_A "a"
%token WORD_BOY "boy"
%token WORD_GIRL "girl"
%token WORD_IN "in"
%token WORD_LIKED "liked"
%token WORD_PARK "park"
%token WORD_SAW "saw"
%token WORD_TELESCOPE "telescope"
%token WORD_THE "the"
%token WORD_WITH "with"

%%
S  : NP VP      {puts("S: NP VP");}     %dprec 1
   | NPA VP     {puts("S: NPA VP");}    %dprec 2
   ;
NPA: D N        {puts("NPA: D N");}     %dprec 3
   | NP PP      {puts("NPA: NP PP");}   %dprec 4
   ;
NP : D N        {puts("NP: D N");}      %dprec 6
   | NP PP      {puts("NP: NP PP");}    %dprec 7
   | NPA        {puts("NP: NPA");}      %dprec 10
   ;
VP : V NP       {puts("VP: V NP ");}    %dprec 11
   | VP PP      {puts("VP: VP PP");}    %dprec 12
   ;
PP : P NP       {puts("PP: P NP");}     %dprec 14
   ;
D  : "the"      {puts("D: the");}       %dprec 15
   | "a"        {puts("D: a");}         %dprec 16
   ;
P  : "in"       {puts("P: in");}        %dprec 17
   | "with"     {puts("P: with");}      %dprec 18
   ;
V  : "liked"    {puts("V: liked");}     %dprec 19
   | "saw"      {puts("V: saw");}       %dprec 20
   ;
N  : "girl"     {puts("N: girl");}      %dprec 21
   | "boy"      {puts("N: boy");}       %dprec 22
   | "park"     {puts("N: park");}      %dprec 23
   | "saw"      {puts("N: saw");}       %dprec 24
   | "telescope"{puts("N: telescope");} %dprec 25
   ;
%%

int main(int argc, char** argv) {
  printf("yyparse returned %d\n", yyparse());
  return 0;
}

コンパイル:

$ make ambig2
bison30 -v -d -o ambig2.c ambig2.y 
ambig2.y: warning: 6 shift/reduce conflicts [-Wconflicts-sr]
ambig2.y: warning: 10 reduce/reduce conflicts [-Wconflicts-rr]
gcc-4.8 -ggdb -Wall -D_POSIX_C_SOURCE=200809L -std=c99 -c -o ambig2.o ambig2.c
gcc-4.8   ambig2.o   -o ambig2
rm ambig2.o ambig2.c

サンプル解析:

$ ./ambig2 <<<"a boy saw a girl"
D: a
N: boy
NPA: D N
V: saw
D: a
N: girl
NPA: D N
NP: NPA
VP: V NP 
S: NPA VP
yyparse returned 0

$ ./ambig2 <<<"a saw saw the saw in a saw"
D: a
N: saw
NPA: D N
V: saw
D: the
N: saw
NPA: D N
NP: NPA
VP: V NP 
P: in
D: a
N: saw
NPA: D N
NP: NPA
PP: P NP
VP: VP PP
S: NPA VP
yyparse returned 0
于 2014-02-20T03:55:29.217 に答える