首页 > 代码库 > the science of programming BNF范式的优先级

the science of programming BNF范式的优先级

2024-08-04 13:18:03   217人阅读

the science of programming 的三点


1.关于一个数组的数学解析：数组就是一个函数，index->value的映射
2.BNF范式与正则表达式是不同的，之前一直搞混乱了。正则表达式是用来描述词法，BNF范式是用来描述语法的。
--------------------------------------------------------------------------------------------------
3.最大的收获是关于BNF范式如何写出带优先级的语法,这个问题一直很困扰人，因为之前面试的时候面试官让我
  写一个计算器，那计算器没有括号的标志符号，很难做抽象语法分析树，所以当时很猥琐的选了另外一个html
  源码词法分析的题目。
  那昨天在看the sicence of programming的时候，偶然发现里面如何写带优先级的BNF范式


  举一个我们每天都会看到的例子：  3-2-2*1*(2-1*1)
  如何在我们定义的代数空间中只有两个操作符号分别是：“-”和“*”，而且“*”的优先级大于“-”
  那如何用BNF范式定义这个优先级？
  先看结果再分析吧：

  1. <expr>:=<expr_imp>
  2.		|<exper>-<expr_imp>
  3. <expr_imp>:=<factor>
  4.		|<expr_imp>*<factor>
  5. <facotr>:=(<expr>)
  6.		|<identifer>





  这里的identifier可以是1~n的整数。
  如果用递归下降法来识别这个BNF范式，很容易
  下面的是随便写的可能会有点问题
  ---------------------------------------------
  testNext()测试当前字符的后一个是什么字符
  test()测试当前字符是什么
  
  matchExpr(){

	 while(testNext()=EOF){

		matchExper_imp() 
		if ! matchMinus()
		   return 
	 }
	 mathcExper_imp()
  }

  matchExpr_imp(){

	 while(testNext()=EOF){

		matchFactor() 
		if ! matchMulti()
			return
	 }
	 mathcFactor()
  }

 matchFactor(){
 
	 if test()=="("
		 matchLeftPar()
		 matchExpr()
		 mathcRightPar()
	 else if test() == number
		 matchIdenti()
	 else 
		 error
 
 }




可以对照着看如何解3-2-2*1*(2-1*1),
其实这种优先级的BNF是先写最低优先级的,依次写低优先级，像刚刚的例子就先写“-”语法，再写“+”语法，所以整个下来很容易
另外写递归下降的时候一定得注意，要消除左递归和右递归，上面的BNF范式就有左递归的情况，消除也很简单，就是用基本的
循环来替代递归！！！！

the science of programming BNF范式的优先级


联系
我们