如何在 lex 和 yacc 中实现本练习的语法

Question

Exercise

我正在尝试使用 lex 和 yacc 实现本练习的语法，但它引发了冲突：警告：5 shift/reduce 冲突 [-Wconflicts- sr] 并将每个字符串视为无效，我认为它必须具有优先级：它应该接受如下字符串： ba#ababadada#bad#dabbada 并拒绝：爸爸#ad#abaadad#badadbaad 这是我试过的：

%{
#include <stdio.h>
int flag=0;
%}
%{
void yyerror();
%}

%token A B D NL
%%
str1        :   Oracion NL      { printf("\n Sequence accepted");return(0);}
        ;
Oracion     :   Oracion '#' Parrafo     { }
        |   Parrafo         { }
        ;
Parrafo     :   Silaba Parrafo Silaba           { }
        |   Silaba              { }
        ;
Silaba      :   Explosion Alto      { }
        |   A Explosion             { }
        |   A Alto          { }
        |   Explosion           { }
        ;
Explosion   :   Alto A              { }
        ;
Alto        :   B               { }
        |   D               { }
        ;   
%%
void main()
{
    printf("\n write a sequence\n");
    yyparse();
    if(flag == 0)
        printf("\n Valid sequence");
}
void yyerror()
{
    printf("\n Invalid Sequence\n\n");
    flag=1;
}

Answer 1

该语法允许四个音节（忽略b和d之间的非句法区别）：

ba
bab
ab
aba

单词是包含奇数个音节的序列。由于音节边界没有以任何方式标记，因此音节的划分是不明确的，这就是野牛报告冲突的原因。例如，babab 可以解析为

ba-bab  (Explosión / Explosión Alto)
bab-ab  (Explosión Alto / "a" Alto)

在少数情况下，单词必须由奇数个音节组成的事实可以消除解析歧义。比如bababa只能分解为ba-ba-ba（Explosión/Explosión/Explosión），因为bab-aba（Explosión Alto / "a" Explosión）只有两个音节，是偶数个。特别是，这意味着贪婪的解决方案——总是使用尽可能长的音节——有时会产生不正确的解析。此外，如果没有任意前瞻，您无法保证正确的解析，这使得 LR 解析器不合适。考虑以下两个词：

abababbabbabbabbabbabbab
abababbabbabbabbabbabbabbab

双辅音是一个明确的音节分隔符，因此唯一有歧义的分隔符是在前六个字符中，如上所述，它可以是两个或三个音节。纵观整个单词，就会清楚这些选择中的哪一个导致了一个音节数为奇数的单词。但是在看到整个单词之前，解析器无法知道。特别是，在看到首字母 ab 后，它必须决定是将其解析为 a Alto 形式的音节，还是将后面的 a 移动以将其解析为 [=22] =].但任何固定的前瞻限制都不足以在所有情况下做出此决定。

我想这个练习旨在帮助您理解这种歧义（除非练习的内容比您在问题中展示的内容更多）。我不确定你还被要求做什么。如果您想使用 bison 来实际生成解析树，则必须以某种方式处理歧义，这可能意味着使用 GLR parser.

如何在 lex 和 yacc 中实现本练习的语法

How to implement the grammar for this exercise in lex & yacc

grammar

yacc

lex