利用递归文法+可以用什么？

来源：蜘蛛抓取(WebSpider) 时间：2022-05-30 03:13 标签： 利用递归方法求5

一直以来，在递归下降解析方法下，左递归文法都是不好处理的硬骨头，因为简单处理会导致函数的无限递归调用。因为这个原因，现在主流的解析器以采用LR系列方法为多，利用lex/yacc, bison之类的工具产生解析器。而有的语言虽然采用了递归下降解析方法，不得不限制语法构造，或者使得语法规则体系不必要地复杂化。

昨天晚上，终于找到了在递归下降方法中对左递归的简单优雅的处理办法了。历经将近5年，经过三四十次不断的尝试与失败，终于有了一个漂亮的结果。感觉非常爽。再一次体验到坚持不懈直到成功之后的愉快。

得到的这个方法有以下的特点：
1. 能处理左递归，包括间接左递归。
2. 简单直观，解析程序可读性好。
3. 时间效率高。对现有的LL(k), LR方法能处理达到线性时间复杂度的语法，此方法也可以同样达到。
4. 空间效率高。因为不需要自底向上类型方法（LR系列）所需要的转移表，也不需要象传统递归下降方法（比如peg/packrat)为了实现线性时间而设置的整体性memo。
5. 易学易用，学习曲线平坦。
6. 可以实现无扫描解析。不需要独立的词法器。
7. 灵活，适应性强。可以根据需要在解析程序中简单方便得添加前看（lookahead)或者回溯(backtracking), 因此可以任意地适应不同类型的语法。
8. 动态性好。因为不需要从定义解析器产生阶段，因此可以实现动态修改语法规则。

以下描述算术表达式的LL(1)文法的递归下降分析程序构造 G[E]: E→TE′ E′→+TE′|ε T→FT′ T′→*FT′|ε F→(E)|i 说明：终结符号i为用户定义的简单变量,即标识符的定义。 要求具有如下功能： 1)从终端输入表达式 2)总控函数分析算术表达式； 3)根据分析结果正误，分别给出不同信息

我要回帖

更多关于 利用递归方法求5 的文章

 

随机推荐