编译原理5-8节看不懂了

Question

java版。如何通过产生式写递归函数，从而将式子构建成抽象语法树，希望老师能举一个简单的例子。比如说不考虑优先级的情况，像上一节的simpleparse，如何用左递归的产生式来实现。还有一个ExprHOF接口的hoc（）方法，方法体一直没实现，不知返回的具体是啥

Answer 1

求老仙 2020-08-03 16:30:36

关于hoc那部分，java代码如果是最新版， 是有个一个interface在定义hoc的。 相当于把函数作为函数的参数。

• 求老仙 #1

  public interface ExprHOF {
  
      ASTNode hoc() throws ParseException;
  
  }
  这个接口不需要实例，这个是java的特性你搜下FunctionalInterface

• 提问者 weixin_慕田峪0187414 回复 求老仙 #2

  好的，谢谢老师

Answer 2

求老仙 2020-08-03 16:28:18

产生式如果不是左递归的，那么是可以解析出语法树的。 

你看比如 A -> xA|y 这种形式的产生式，如果你的函数这么写

parseA(input){

  if(input === y) {

     return new Node(y) 

     return

  }

  const x = new Node(x)

  const right = parseA(input)

  return new Node(x, right)

}

input代表输入流，按照上面的递归，是可以完整解析的。 如果你把 x A 看做一个节点的两个子节点，你就可以利用上面的过程收集并形成二叉树。 

Answer 3

提问者 weixin_慕田峪0187414 2020-08-03 19:02:54

好的，谢谢老师