Infix->Postfix

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

词法分析,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表达式的文件。这样就基本满足转换功能了。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航