为算数表达式构造上下文无关文法

gta

一个算数表达式，由整数、小数、标识符、括号、加减乘除号(+ - * /)、求模号(%)、乘方号^以及正负号(+、－)组成。要为这种算数表达式构造无二义的上下文无关文法，该怎么做？

以下是这种算数表达式的一个例子

(-b+(b^2)-4*a*c)/2*a

mik

未明白楼主意思

gta

原帖由 mik 于 2007-6-9 21:36 发表于 2楼  
未明白楼主意思

以龙书2.9节的翻译器为例，它把中缀表达式翻译成后缀形式。但它只支持包含数字、标识符、和+、-、*、/、div、mod这几种操作符。其文法如下：
start-> list eof
list->expr;list | E

expr->expr + term
         | expr - term
         | term

term-> term * factor
          | term / factor
          | term div factor
          | term mod factor
          | factor

factor-> (expr)
             | id
             | num

其中，红字表示终结符，是由词法分析器提交给语法分析器的。我现在想扩展这个翻译器的功能，使其能支持正负号及乘方号，但不知怎样为这样的算数表达式构造无二义的上下文无关文法

mik

你看看 lex/yacc 方面的知识

http://linux.chinaunix.net/bbs/thread-885847-1-1.html

mik

http://linux.chinaunix.net/bbs/thread-896629-1-2.html

OpenPro

start-> list eof
list->expr;list | E

expr->expr + term
         | expr - term
         | term

term-> term * factor
          | term / factor_ultra
          | term div factor_ultra
          | term mod factor_ultra
          | term exp facor_ultra
          | factor_ultra

factor_ultra -> facor | unary-operator facor

unary-operator -> + | -

factor-> (expr)
             | id
             | num

其中term exp facor_ultra表示乘方，语义分析时可直接调用相关数学实现函数

bilbo0214

你要是用yacc，就无所谓非要写无二义的文法，只要指定如果处理冲突，一样可以实现的。《Lex and Yacc》中第三章就有这个例子呀。