2

处理需要使用 flex 和 bison 来检查给定字符串是否为某种语言的作业。这只有在看到基本示例之后才会出现，其中使用 flex 基本上吐出读入的内容。

例如，格式为 {a^nb^nc^n} 且 n > 0 的字符串将在该语言中。所以字符串 aabbcc 是有效的。

flex 有没有办法计算读取的特定字符？例如，如果给定字符串 aaabbbcc，它将计算 3 个 a、3 个 b 和 3 个 c？或者我应该简单地使用 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

2

为了完整起见，向 bison 添加计数检查很简单。这是一个简单的例子（它识别或抱怨输入行，以便更容易玩）：

我省略了大部分样板文件，包括 amain和yyerror函数。但我确实加入了一些弹性选项。用来'a'表示“任意数量的as”正在扩展边界；最好定义名为As,Bs和的标记Cs，然后将 flex 规则拆分为五个不同的规则，等等。这样更短。:)

野牛

%{
#include <stdio.h>
%}
%%
start: line
     | start line
     ;

line: 'a' 'b' 'c' '\n' { if ($1 == $2 && $2 == $3)
                           fputs("Good!\n", stderr);
                         else
                           fputs("Bad!\n", stderr);
                       }

弹性：

%{
extern int yylval;
%}
%option noyywrap noinput nounput    
%%
"a"+|"b"+|"c"+|.|\n { yylval = yyleng; return *yytext; }
于 2013-09-16T05:09:14.877 回答
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"+然后逐个字符地遍历字符串，但这使得使用 flex 过大了。

有关状态的更多信息，请参见此处：http: //aquamentus.com/flex_bison.html#17 `

于 2013-09-16T02:05:21.497 回答
1

字符串a n b n c n既不是常规的也不是上下文无关的。字符串只能由 aContext Sensitive Grammar或 an生成，Unrestricted Grammar具体取决于 n 的值。因此无法使用Flex或Bison检查字符串。Flex 是一个扫描器生成器，它只能检查正则表达式。Bison 是一个解析器生成器，它只能检查上下文敏感语言。

于 2013-09-15T18:30:32.680 回答