作者：未知 来源：月光软件站 加入时间：2005-6-5　月光软件站

词法分析,lexical analysis属Compiler的front end部分，infix到postfix只是其中很小的一部分。

从infix转postfix的关键是写出它的Context Free Grammar，写出了Context Free Grammar算法也就实现了。

在转成代码的时候，和Context Free Grammar有细微的差别。我是用C#写的，lexer是用C写的，没有多大的出入。

红龙书上只给出了单个位数数字C代码，比如:90+45-65，就不行。不过,只要稍微改动一下它的Context Free Grammar就可以实现任意位数的postfix form。前面的章节让我很模糊，到了这里总算才和SE117联系起来。

下面给出postfix Context Free Grammar的定义，其实这个还是很容易写出来到的:

Expr->Num UnOpt

UnOpt->Num+UnOpt

         ->Num-UnOpt

         ->Num*UnOpt

         ->Num/UnOpt

         ->L(Null string)

Num->0Num

       ->1Num

       ->2Num

       ->3Num

       ->4Num

       ->5Num

       ->6Num

       ->7Num

       ->8Num

       ->9Num

       ->L(Null string)

Expr,Num,UnOpt为nonterminals。0-9,+-*/为terminals。可以进一步用Killing L(Null string)方法改写Context Free Grammar，因为实际写代码的时候用的是Killing L形式。

注意，如果Num和UnOpt同时生成L则该语法是接受的。但+-*\中任何一个开头都被视为错误,如果出现连续2个运算符也是错误的。写代码时避免这2种情况的发生。似乎这个Context Free Grammar还不是很完美。

比如:4+5-2+3的postfix form为45+2-3+。用上述Context Free Grammar来实现postfix form的步骤如下：

Expr->Num UnOpt

      ->4Num+Unopt

      ->45+Num-UnOpt

      ->45+2-Num+UnOpt

      ->45+2-3+L(null string.)

我在写代码的时候，事先写了个函数去除了空格键和跳格键，然后用StreamReader和StreamWriter把一个包含infix表达式的文件，转换成postfix表达式的文件。这样就基本满足转换功能了。

相关软件：