Parsing a While Loop in Bison

问题:

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.

回答1:

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.

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.

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.

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) { ... }

a corresponding AST might look like this:

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

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

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.

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.