bison和flex的基本原理

见图：

1. The parser will obtain the first token from the scanner — obtaining "The",an article. The parser will push the "The" on the stack (Figure 1-a).

parser得到“The”，它是个冠词，所以parser将它置入堆栈

2. The parser will obtain another token from the scanner — obtaining "man",a noun. Since there is an article on the stack,the parser will pop the article off the stack and replace it with a noun-phrase "The man" (Figure 1-b).
parser得到“man”，它是个名词，因为堆栈中有一个冠词，所以parser将这个冠词从堆栈中取出，和man合并后，放入堆栈
3. The parser will obtain another token from the scanner — obtaining "ate",a verb. There is no rule reducing "noun-phrase verb" so it pushes "ate" on the stack (Figure 1-c).
parser得到“ate”，它是个动词，因为这里没有规则来减少“名词短语 动词”，所以parser将ate压栈

4. The parser will obtain another token from the scanner — obtaining "a",an article. There is no rule reducing "noun-phrase verb article" and so it pushes the "a" on the stack (Figure 1-d).

parser得到“a”，它是个名词，因为这里没有规则来减少“名词短语 动词 冠词”，所以parser将a栈
5. The parser will obtain another token from the scanner — obtaining "worm",a noun. The parser can now reduce the "article noun" on the top of the stack to a noun-phrase and places the noun-phrase on the stack (Figure 1-e).
parser得到“worm”，它是个名词，因为这里有规则“冠词 名词”-->“名词短语”，所以parser将a出栈，和worm合并后压栈
6. The parser will obtain another token from the scanner — obtaining ".",a period. The parser can now reduce the "noun-phrase verb noun-phrase period" to a sentence and places this on the stack (Figure 1-f).

parser得到“.”，它是个分隔符，因为这里有规则“名词短语 动词 名词短语 分隔符”，所以parser将栈情况，在栈中放入一句话“The man ate a worm”

这里的合并被称为Reduce，入栈被称为Shfit。

其实bison中的parser是一个有限状态机，下面一句话是从gun网站上copy来的，很好的说明了这个原理。

Each time a lookahead（当前获得到的token） token is read,the current parser state together with the type of lookahead token are looked up in a table. This table entry can say,“Shift the lookahead token.” In this case,it also specifies the new parser state,which is pushed onto the top of the parser stack. Or it can say,“Reduce using rule number n.” This means that a certain number of tokens or groupings are taken off the top of the stack,and replaced by one grouping. In other words,that number of states are popped from the stack,and one new state is pushed.