最近,我正在考虑一个由我自己构造的算法。我称之为替换编译。它的工作如下:
定义语言及其运算符的优先级,例如
(1) store <value> as <id>, replace with: var <id> = <value>, precedence: 1
(2) add <num> to <num>, replace with: <num> + <num>, precedence: 2接受输入行,如store add 1 to 2 as a;
标记它:<kw,store><kw,add><num,1><kw,to><2><kw,as><id,a><EOF>;
然后扫描所有令牌,直到到达文件末尾,找到优先级最高的操作,然后“打包”操作:
<kw,store>(<kw,add><num,1><kw,to><2>)<kw,as><id,a><EOF>用定义的替换替换“子语句”(括号中的表达式):
<kw,store>(1 + 2)<kw,as><id,a><EOF>重复,直到不再有声明为止:
(<kw,store>(1 + 2)<kw,as><id,a>)<EOF>
(var a = (1 + 2))然后用内置函数eval()计算代码。
eval("var a = (1 + 2)")那么我的问题是:这个算法会起作用吗?这个算法在简单语言上更有效吗?
发布于 2020-06-10 10:32:59
这不能按原样工作,因为无法确定操作和关键字的优先级,但您实际上已经定义了解析(并在最后抛出了一个解释步骤)。这看起来非常接近运算符优先分析,但我可能在你的愿景的细节上错了。分析算法的真正关键在于它读取代码的方向/优先级,决策是自上而下的(确定什么样的语句并应用规则)还是自下而上(将小块组装成更大的组件,直到语句的类型变得明显为止),以及语法是否编码为代码或通用解析器的数据。(我可能忽略了一些东西,但这应该给你一个起点,让你更好地理解进一步的阅读。)
更典型的情况是,代码通常使用LR技术(如果是自顶向下的话)进行解析,这种技术是从状态机驱动的,具有前瞻性和下一步信息,但您也可以找到偶尔的递归下降。因为它们都在做非常相似的事情(只是实现方式不同),所以您的粗略算法可能会被改进,看起来很像其中的任何一个。
对于大多数学习解析的人来说,递归下降是方法,因为一切都在代码中,而不是为状态机定义构建相当于解释器的东西。但是大多数解析器生成器都构建了LL或LR编译器。
我显然过于简化了这个领域,因为你可以在维基百科页面的底部看到一些相关的系统,这些系统部分地围绕着你现有的语法。但对于大多数语言来说,这是三大算法。
发布于 2020-06-10 11:41:37
您定义的是重写系统:https://en.wikipedia.org/wiki/Rewriting
您可以这样做一个编译器,但是它很辛苦并且运行缓慢,如果您在优化它方面做得很好,那么您将得到传统的表驱动解析器。最后,最好是先了解这些,然后从那里开始。
如果您真的不想使用解析器生成工具,那么手工为简单语言编写解析器的最简单方法通常是递归下降:解析器。
https://stackoverflow.com/questions/62300672
复制相似问题