首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >编译器设计算法?

问编译器设计算法?
EN

Stack Overflow用户
提问于 2020-06-10 09:52:22
回答 2查看 153关注 0票数 2

最近,我正在考虑一个由我自己构造的算法。我称之为替换编译。它的工作如下:

定义语言及其运算符的优先级,例如

代码语言:javascript
复制
(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>;

然后扫描所有令牌,直到到达文件末尾,找到优先级最高的操作,然后“打包”操作:

代码语言:javascript
复制
<kw,store>(<kw,add><num,1><kw,to><2>)<kw,as><id,a><EOF>

用定义的替换替换“子语句”(括号中的表达式):

代码语言:javascript
复制
<kw,store>(1 + 2)<kw,as><id,a><EOF>

重复,直到不再有声明为止:

代码语言:javascript
复制
(<kw,store>(1 + 2)<kw,as><id,a>)<EOF>
(var a = (1 + 2))

然后用内置函数eval()计算代码。

代码语言:javascript
复制
eval("var a = (1 + 2)")

那么我的问题是:这个算法会起作用吗?这个算法在简单语言上更有效吗?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-06-10 10:32:59

这不能按原样工作,因为无法确定操作和关键字的优先级,但您实际上已经定义了解析(并在最后抛出了一个解释步骤)。这看起来非常接近运算符优先分析,但我可能在你的愿景的细节上错了。分析算法的真正关键在于它读取代码的方向/优先级,决策是自上而下的(确定什么样的语句并应用规则)还是自下而上(将小块组装成更大的组件,直到语句的类型变得明显为止),以及语法是否编码为代码或通用解析器的数据。(我可能忽略了一些东西,但这应该给你一个起点,让你更好地理解进一步的阅读。)

更典型的情况是,代码通常使用LR技术(如果是自顶向下的话)进行解析,这种技术是从状态机驱动的,具有前瞻性和下一步信息,但您也可以找到偶尔的递归下降。因为它们都在做非常相似的事情(只是实现方式不同),所以您的粗略算法可能会被改进,看起来很像其中的任何一个。

对于大多数学习解析的人来说,递归下降是方法,因为一切都在代码中,而不是为状态机定义构建相当于解释器的东西。但是大多数解析器生成器都构建了LL或LR编译器。

我显然过于简化了这个领域,因为你可以在维基百科页面的底部看到一些相关的系统,这些系统部分地围绕着你现有的语法。但对于大多数语言来说,这是三大算法。

票数 3
EN

Stack Overflow用户

发布于 2020-06-10 11:41:37

您定义的是重写系统:https://en.wikipedia.org/wiki/Rewriting

您可以这样做一个编译器,但是它很辛苦并且运行缓慢,如果您在优化它方面做得很好,那么您将得到传统的表驱动解析器。最后,最好是先了解这些,然后从那里开始。

如果您真的不想使用解析器生成工具,那么手工为简单语言编写解析器的最简单方法通常是递归下降:解析器。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62300672

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档