0

几周以来，我一直在用 flex 和 bison 编写一个解析器，但由于双重递归而停了下来，前几条规则的定义是相似的。Bison 总是在某个特定阶段选择错误的路径并崩溃，因为语法不合适。野牛代码看起来有点像这样：

set : 
TOKEN_    /* token */
QString
QString
Integer  /* number of descrs (see below) */
M_op     /*'M' optional*/
alts;

和

alts  :
alt | alts alt ;

alt   :
QString
pName_op   /* empty | TOKEN1 QString */
deVal_op    /* empty | TOKEN2 Integer */
descrs
;

和

descrs  :   
descr | descrs descr ;
descr :
QString
QString_op   /* optional qstring */
Integer
D_op         /* optional 'D' */

Bison 停留在descrs递归中，永远不会退出它进入下一个alt。descr然而，在初始块中读入的整数告诉我们将要出现多少个实例。所以我的问题是：

有没有办法为特定数量的递归实例准备野牛，以便他可以退出这个递归并进入“上面”的递归？我可以在 C 代码中访问这个整数，但我不知道所说移动的语法，比如 a descrs : {for (int i=0;i<n;++i){descr}}（我知道这可能看起来很荒谬）

如果做不到这一点，有没有其他方法可以解决这个问题？

任何输入将不胜感激。提前致谢。

4

1 回答 1

1

上下文无关语法不能依赖于语义信息。然而，这正是您所寻求的：您希望在表达式的语法中考虑数字标记的值。

作为请求，这不是不合理或不道德的；它完全超出了上下文无关语法的范围。并且bison旨在为上下文无关语法创建解析器。所以它根本不是解决这个问题的正确工具。

话虽如此，如果您使用的是相当近的版本，其中包括对 GLR 语法的支持，则可以以这种方式使用野牛。bisonBison 的 GLR 支持包括使用语义谓词来控制解析的选项。（有关详细信息，请参阅野牛手册。）基于该机制的解决方案是可能的，并且可能不太复杂。

更容易——如果语法允许的话——使用自顶向下的解析器。例如，在递归下降解析器中解析一个数字，然后解析该数量的descrs 将是微不足道的。

语法中非终结符的自由使用FOO_op表明自上而下的解析不会有问题，但是如果没有看到整个语法就不可能肯定地说。人工非终结符（如FOO_op）通常会导致 LR(1) 语言中的移位归约冲突，因为它们会强制立即做出移位/归约决策。在 LR(1) 语言中，形式的产生式：A → ω B? χ 通常会呈现为一对产生式A → ω B χ; A → ω χ，而不是替换Bop → B | ε; A → ω Bop χ，以避免与形式C → ω ζwhere的其他产生式发生冲突FIRST(ζ) ∩ FIRST(B ∪ ω) ≠ ∅。

于 2015-03-24T20:37:08.203 回答