2

特定の文字列が言語に含まれているかどうかを確認するために flex と bison を使用する必要がある課題に取り組んでいます。これは、読み込まれたものを基本的に吐き出すために flex が使用された基本的な例を見た後にのみ発生します。

たとえば、{a^nb^nc^n} 形式で n > 0 の文字列は言語に含まれます。したがって、文字列 aabbcc は有効です。

フレックスが読み取った特定の文字をカウントする方法はありますか? 例として、文字列 aaabbbcc が指定されている場合、a が 3 つ、b が 3 つ、c が 3 つカウントされますか? または、単純に flex を使用して入力文字列が適切な形式であることを確認し、bison で文法規則を使用して言語であるかどうかを確認する必要がありますか?

編集
私はしばらくそれに取り組んできましたが、半作業バージョンがあるようです。私が現在直面している問題は、yyparse() が終了しないように見え、無効な​​文字列が指定されると構文エラーが発生することです。例として:
文字列「aabbcc」は、L2 と呼んでいるものにあるはずです。次の出力が得られます。 

grammar recognizer result:  
L2 recognized

その後、停止し、完了しません。さらに、文字列「hjnkll」は認識されないはずですが、そのようなものを入力すると構文エラーが発生するだけです。
フレックス 

...  
A [a]*
B [b]*
C [c]*
D [d]*
E [e]*
Z [^a-e\n][.]*
%%
{A} {a = yyleng;} return A;
{B} {b = yyleng;} return B;
{C} {c = yyleng;} return C;
{D} {d = yyleng;} return D;
{E} {e = yyleng;} return E;
{Z} {z = yyleng;} return Z;
\n return NL;
%%

バイソン スニペット 

%token A
%token B
%token C
%token D
%token E
%token Z
%token NL

%%
/*grammer rules*/
transunit: L1 | L2 | L5 | L6
    {
    printf("\n*****Congratulations; Parse Successful*****\n");
    }
;
L2: A B C NL
    {
    /*Language 2 : L(G2) = {a^nb^nc^n} with n > 0*/
    if(a==b && b==c && d==0 && e==0 && a!=0 && z==0){
        printf("\nLG2 recognized\n");
    } else {
        printf("\nSorry language not recognized\n");
    }
    }
;
/*None of the above : not recognized*/
L6: Z NL
    {
    printf("\nSorry language not recognized\n");
    }
;
4

3 に答える 3

1

特定の例では、a+b+c+状態を使用して一致させることができます。その後、a、b、c の出現回数をチェックし、それらがすべて等しいことを確認します。ただし、このソリューションは、言語に 2 つまたは 3 つ以上のルールがある場合、急激に複雑になります。

%{
int a = 0, b = 0, c = 0;
%}
%x Bstate Cstate
%%
"a"+                { a = yyleng; BEGIN(Bstate);           }
.                   { /* not in language; error! */        }
<Bstate>"b"+        { b = yyleng; BEGIN(Cstate);           }
<Bstate>.           { /* not in language; error! */        }
<Cstate>"c"+        { c = yyleng; 
                      if(a != b || a != c) { 
                          /* not in language; error! */
                      }
                      BEGIN(INITIAL);                      }
<Cstate>.           { /* not in language; error! */        }
%%

逆に、マッチするように flex に指示してから"a"+"b"+"c"+、文字列を 1 文字ずつ反復処理することもできますが、これでは flex を使いすぎてしまいます。

状態の詳細については、こちらを参照してください: http://aquamentus.com/flex_bison.html#17 `

于 2013-09-16T02:05:21.497 に答える
1

文字列a n b n c nは、通常でも文脈自由でもありません。文字列は、n の値に応じてaContext Sensitive Grammarまたは anによってのみ生成できます。そのため、 FlexやBisonUnrestricted Grammarを使用して文字列をチェックすることはできません。Flex はスキャナー ジェネレーターであり、正規表現のみをチェックできます。Bison はパーサー ジェネレーターであり、状況依存言語のみをチェックできます。

于 2013-09-15T18:30:32.680 に答える