解析 Bison 中的 While 循环 [英] Parsing a While Loop in Bison

问题描述

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

What is the best way to implement a simple while loop in Bison? If it makes a difference, I am using C, but I can use C++ as well.

推荐答案

您的问题并不适合 Stack Overflow 的答案.它非常详细，已经写了很多关于它的书.

What you're asking doesn't really fit into a Stack Overflow answer. It's pretty detailed, and many books have been written about it.

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

The basic answer is that you don't implement while loops in Bison. Bison is not a language in that sense. Bison builds a parser from a grammar and actions that are associate with rules in that grammar.

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

A parser is a pushdown automaton, which is a state machine with a stack attached. It takes a linear sequence of tokens and detects when rules in the grammar have been satisfied (or if there's an error). When a rule has been satisfied, the parser will execute the action attached to that rule. Here, tokens are (typically) integer values that correspond to keywords, identifiers, and literals in the language. Parsers written with Bison usually rely on a separate routine, called a lexical scanner, to translate input text into tokens.

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

Nothing in this machinery will directly allow you to implement a while loop. Instead, the actions are used to build an internal representation of the input that can be further processed. For grammars that are complicated enough to have while loops, this representation usually takes the form of a tree, and is commonly called an abstract syntax tree (AST). To be more concrete, given the input text:

while (i < n) { ... }

相应的 AST 可能如下所示:

a corresponding AST might look like this:

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

while 节点需要两个子树:一个对应于 continue 条件的表达式子树(i )，和一个对应于块的块子树({ ... }).

The while node expects two subtrees: an expression subtree corresponding to the continue condition (i < n), and a block subtree corresponding to the block ({ ... }).

为 while 循环提供适当的 AST，通过处理 AST 的节点并结合一些处理标识符和变量值的机制来实现循环相当简单.

Given a proper AST for the while loop, it's reasonably straightforward to implement the loop by processing the nodes of the AST, in combination with some machinery for handling identifiers and variable values.

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

If you give Bison a proper grammar (ie: suitable for LALR(1) parsing) and actions that build an AST, you'll get a routine that will convert a stream of tokens into an AST. Executing the loop from that AST is outside the scope of Bison.

这篇关于解析 Bison 中的 While 循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！