去括号！！！！！！！！！！！！！

p4apple

你这个问题很奇怪.

要是想进行表达式计算：看编译原理

想要简化表达式：可以用栈的方式。把计算改为输出
（a + (b + c )）+e  ==>  
1.b+c
2.b+c ()
3.b+c () + a
4.b+c () +a ()
5.b+c () +a () +e   // 把括号去掉
6.b+c +a +e


想不改变运算表达式的书写顺序的情况下，去掉括号。


根据 p4apple 公式 嘻嘻
设 集合p 是"最内部括号"的最小运算符的集合
当：
条件1 ：
p > "最内部括号"前面的符号。
或  p == "最内部括号"前面的符号级别 and    "最内部括号"前面的符号是+ ；
或  p == "最内部括号"前面的符号级别 and   "最内部括号"前面的符号是*；
条件2:
p >= "最内部括号"后面的符号。
条件 1，2 都满足的括号可以去掉。

原因：
  a - b ==> a + ( -b )     // 减法是加发的一个特例
   a / b ==> a * ( 1 / b)   // 除法是乘法的一个特例
  + * 符合 结合率  - / 不符合 结合率 。

没有解决的问题如 ： a - （b - c + c ）

[ 本帖最后由 p4apple 于 2008-2-17 00:58 编辑 ]

zszyj

原帖由 Wind-Son 于 2008-2-16 23:16 发表


好歹也要知道我在说什么吧, 我只不过是建议楼主使用现成的工具而已. 你举的例子不管用哪种方法都是要处理的.
正题:
第一 你好像不太了解分析树和语法树的区别,编译器一般会生成比分析树更紧凑的语法树, 像 ...

Wind-Son兄此言差矣! 您所说的细节, 其实才是解题的关键, 因为此题答案的核心, 是在于定义:什么才是多余的括号? 而不是什么"分析树"/"语法树"(按照您的术语).
之前大家都将焦点放在建立语法树的过程上(包括出栈/入栈其实就是手工建立语法树的过程)的表象上,其实这是本末倒置. 而我提出的问题,其实就是在提醒大家,我们该注意的是识别出多余括号的语法模式,只有列全了多余括号的语法模式, 才可以找出正确而快速的实现方法.

按照大家从我列举的几种模式中总结的规律, 就是'+'和"*"符合结合律,可以去掉括号,那么只要从小学数学书中找出符合四则运算结合律的所有数学表达式模式,用YACC列出这两条结合律等式, 直接将括号去掉，问题就得解, 完全是没有必要操作什么语法树的,直接用ＹＡＣＣ语法解决就是：

expr:
    expr '+' '(' expr ')' { output expr '+' expr; };  //结合律一
   expr '*' '(' expr '*' expr  ')' { output expr '*' expr '*' expr; }; //结合律二
　expr '-' '(expr '*' expr ')' { output expr '-' expr '*' expr; }; //优先级
　expr '-' '(expr '/' expr ')' { output expr '-' expr '/' expr; }; //优先级



而正因为您没捉住了重点,因此即使是最后提出的算法,很遗憾仍然是有错误的，看伪代码的最后一行判断：

else if (父节点为-或/)
         对右子节点加括号

为什么错，我就不再说了，按照上述判断操作，大家看个例子就明白,原式： a-b-c, 加括号后a-(b-c).　也不要以为简单把第一个判断表礞式从"子＜父＂改为＂子＜＝父＂就解决，为什么？自已想想就明白．

ＬＺ的问题讨论完了，题外再向Wind-Son请求几个问题吧，由于我一直是拿ＹＡＣＣ来开发脚本解释器的，因此确实并没试过拿它来只生成语法树，然后再对该树来操作．有几点不明白之处，希望能指导：
１．ＹＡＣＣ和ＬＥＸ，分别是词法分析和语法分析，生成的结果就是一个ＬＲ算法的语法分析树，由于'('，肯定是两个token，因此必然也会是语法分析树的一个结点．按照您的定义，这只是一个分析树，而不是语法树？　但ＹＡＣＣ里面，并没有两种树的概念之分，那么不含括号结点的语法树（按照您的定义的那种）如何生成出来呢？　请赐教．

２．ＹＡＣＣ工作的原理，是通过不断地shift/reduce的方式来工作的，而我们的操作是在不断的reduce过程中嵌入操作的．如何才能不在reduce过程中操作，而是在生成完全的语法分析树后才操作？请赐教，并请举个简单例子．谢谢！

[ 本帖最后由 zszyj 于 2008-2-17 12:55 编辑 ]

Wind-Son

原帖由 zszyj 于 2008-2-17 12:53 发表


Wind-Son兄此言差矣! 您所说的细节, 其实才是解题的关键, 因为此题答案的核心, 是在于定义:什么才是多余的括号? 而不是什么"分析树"/"语法树"(按照您的术语).
之前大家都将焦点放在建立语法树的过程上(包 ...

我没有说一定要生成语法树，也没有说一定要用ＹＡＣＣ，就是给楼主个选择和提示而已嘛。

对非线性结构的分析本质上就是语法分析，但是否生成语法树就看情况。一般，如果一遍遍历可以完成所有操作，则不必真正生成语法树，如编译器中的递归下降分析。前面说过楼主的问题可以通过递归栈解决，我赞成，那本质上就是在逻辑上遍历语法树。

你给的文法是有问题的，如(a+(((b+c))))有些括号你就去不了，因为你的文法递归不完全。又如，a-((((b-c))))你也去不全。如果你不重新规划你的文法，恐怕你就只有穷举了。再如，如果原表达式括号匹配有错，你可能给出一个完全错误的结果，而不能进行容错处理。

还有，你举的例子是不对的。“为什么错，我就不再说了，按照上述判断操作，大家看个例子就明白,原式： a-b-c, 加括号后a-(b-c).　也不要以为简单把第一个判断表礞式从"子＜父＂改为＂子＜＝父＂就解决，为什么？自已想想就明白．”a-b-c生成语法树应该是：
              －
            /     \
          －     c
        /    \      
      a      b   

而不是：
              －
            /     \
          a       －
                 /   \
                b     c


最后，你的两个问题。利用YACC生成语法树不必在所有的reduce中都需要调用mknode()。语法树和分析树只是概念上的，只在必须的地方才调用mknode就生成所谓语法树。

[ 本帖最后由 Wind-Son 于 2008-2-17 14:11 编辑 ]

zszyj

原帖由 Wind-Son 于 2008-2-17 14:03 发表

我没有说一定要生成语法树，也没有说一定要用ＹＡＣＣ，就是给楼主个选择和提示而已嘛。

对非线性结构的分析本质上就是语法分析，但是否生成语法树就看情况。一般，如果一遍遍历可以完成所有操作，则不必真 ...

多重括号很好解决,只要增加一个不作输出的递归替代模式就行,如下:
expr:
  
  '(' '(' expr ')' ')' :  yytext =  '(' expr ')';
.... // 其它部分照抄前面;

而我之所以举上一个贴子的例子a-b-c, 是因为它确实是有问题的,因为并不一定是'-'和'/'就必须对右结点加括号. 即使按照你的说法, 右子结点只有一个 'c', 那么按照你的判断语句,生成的就是a-b-(c),一样是有问题,这不是LZ所要的.

因此, 我的意见仍然是,不管你是否生成了语法树, 用的是加括号法还是减括号法, 都无法用一两个简单判断规则就完成, 仍然是需要总结数学表达式的结构, 并转换成相应的判断规则语法(不管是用if, 还是用yacc里面的patten,都是一样的).

不过,这都不重要了,现在原题的答案已经很明了, 不管谁喜欢用什么办法,都不难,只要自已熟悉就行.

我现在比较感兴趣的是, 如何将YACC自已解析语法过程中使用的语法树直接完整生成出来, 因为我觉得这个功能确实很有用, 我在使用yacc过程中,从来是YACC调用我的代码,而我无法调用它的代码,例如你说的mknod. 所以还是请你再辛苦一下,举个简单例子, 让我们学习一样怎么使用这个功能, 不一定是YACC,bison也行. 请不吝赐教.

[ 本帖最后由 zszyj 于 2008-2-17 22:15 编辑 ]

Wind-Son

怎么生成个a-b-(c)? 叶节点(终结符)直接跳过不就行了?
yacc创建节点的例子参看gcc里c-parse.y,不过比较复杂

zszyj

原帖由 Wind-Son 于 2008-2-18 01:10 发表
怎么生成个a-b-(c)? 叶节点(终结符)直接跳过不就行了?
yacc创建节点的例子参看gcc里c-parse.y,不过比较复杂

这个文件我看了一下,虽然比较复杂,但其原理与我写的脚本解释器本质没两样,只不过我是将脚本代码边解释边执行,完结后就是得到所有代码执行完毕后的结果. 而c_parse.y, 则是边解释边转换, 到了stmt节点,就要进行reduce, 然后调用default_conversion 转换成目标代码写入文件. 而我们希望得到的, 在解释过程中形成的与源代码等价的语法树, 并没有存在.我看对于编译形的应用,也根本不可能会形成这么一棵树的,因为如果一个源代码行数很多,那么这棵树会很巨大,根本是无法保存在内存中的. 事实上,我看到过的所有解释器或者编译器的语法规则源码,都是边扫描边reduce边计算/输出, 而没有见到过不做reduce而只生成一颗完整的树,再一次性遍历这个树后才得出计算结果/输出的例子. 真很想找个这种例子看看. YACC/bison的工作原理都是生成树的部分,计算部分,释放部分,周而复始完成整个扫描的, 不过,如果有什么开关,能够将这个树在整个内存中保存下来,可以留待以后使用的话,那将是很有用的功能.

Wind-Son

我现在手头没有源码，记得里面有个build_binary_op，你自己找吧
编译原理和实践里有利用YACC生成语法树的介绍，参考附录有个tiny.y
google: http://blog.csdn.net/liwei_cmg/archive/2007/05/21/1618822.aspx
另外一个源码文件就算变态到上万行，形成的语法树能有多大让内存装不下？