词法分析,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表达式的文件。这样就基本满足转换功能了。
本文地址:http://com.8s8s.com/it/it31441.htm