在北美野牛解析一个while循环

Question

在Bison中实现简单while循环的最佳方法是什么？如果它有所不同,我使用C,但我也可以使用C++.

Answer 1

你问的问题并不适合Stack Overflow的答案.它非常详细,很多书都是关于它的.

基本答案是你没有在Bison中实现while循环.在这个意义上,野牛不是一种语言.Bison根据语法和与该语法中的规则相关联的动作构建解析器.

解析器是一个下推自动机,它是一个附加堆栈的状态机.它需要一个线性的令牌序列,并检测何时满足语法规则(或者是否存在错误).满足规则后,解析器将执行附加到该规则的操作.这里,标记(通常)是整数值,对应于语言中的关键字,标识符和文字.用Bison编写的解析器通常依赖于一个单独的例程,称为词法扫描程序,将输入文本转换为标记.

此机器中的任何内容都不会直接允许您实现while循环.相反,这些操作用于构建可以进一步处理的输入的内部表示.对于复杂到足以具有while循环的语法,这种表示通常采用树的形式,通常称为抽象语法树(AST).更具体的是,给定输入文本:

while (i < n) { ... }

相应的AST可能如下所示:

                        [while node]
                   _____/          \_____
             _____/                      \____
            /                                 \
       [operator <]                     [block subtree]
       /          \
      /            \
  [ID: i]        [ID: n]

while节点需要两个子树:对应于continue条件(i < n)的表达式子树,以及对应于块({ ... })的块子树.

给定while循环的适当AST,通过处理AST的节点以及处理标识符和变量值的一些机制来实现循环是相当简单的.

如果你给Bison一个正确的语法(即:适合LALR(1)解析)和构建AST的动作,你将获得一个将令牌流转换为AST的例程.从该AST执行循环超出了Bison的范围.