标签: compiler-theory

你好伙伴堆栈流量成员.

我正在学习编译器类.我确实理解Top-Down Parser应该避免左递归,并转换为右递归方式.

问题是,

a)我理解正确的自上而下的解析器等于LL而自下而上的解析器等于LR？

b)我发现左递归是规则,自称为ex)Expr:== Expr'+'Term | 可能导致无限循环查找Expr的术语.但无论如何,在C或Java中考虑输入的任何示例代码？(我不想要解析器或扫描器代码)我需要的是具有句子形式的案例代码示例,它通过左递归发生无限循环.

c)在自上而下的解析器中使用右递归的方式实际上有什么不同？

ANS c)无需回溯.还有别的吗？

ANS b)x - 2 * y还有其他什么？因为这个用回溯方式解析.

我已经找到了非左递归和左递归的案例.

左递归语法

A -> Ax

非左递归语法

A -> Bx
B -> Ay

两者都进入无限循环.

谢谢你,感谢所有专家.

有没有人知道任何论文讨论内联算法？并且密切相关,父子图与调用图的关系.

背景:我编写了一个编译器,Ocaml其中积极地内联函数,主要是由于这个和其他一些优化,它为我的编程语言生成比许多其他情况(包括偶数C)更快的代码.

问题#1:算法在递归时遇到问题.为此,我的规则只是将子项内联到父项中,以防止无限递归,但这会阻止兄弟函数一次性内联.

问题2:我不知道优化内联操作的简单方法.我的算法对于函数体的可变表示是势在必行的,因为它甚至不可能实现有效的函数内联算法.如果调用图是一棵树,很明显自下而上的内联是最佳的.

技术信息:内联包含许多内联步骤.问题是步骤的顺序.

每个步骤的工作原理如下:

• 我们通过用参数替换类型参数和值参数来制作要内联和beta-reduce的函数的副本.
• 然后,我们将return语句替换为对新变量的赋值,然后跳转到函数体的末尾.
• 然后,该函数的原始调用将替换为该函数.
• 但是我们还没完成.我们还必须克隆函数的所有子函数,并将它们进行beta减少,并将克隆重新复制到调用函数.

克隆操作使得内联递归函数变得非常困难.保持已经在进行中的列表并且只是检查我们是否已经处理此调用的常用技巧不能以天真的形式工作,因为递归调用现在被转移到调整后的代码中.函数,递归目标可能已更改为克隆的子项.但是,该子进程在调用父进程时仍在调用调用其子进程的原始父进程,现在不会停止展开递归.如上所述,我通过仅允许对孩子进行递归调用来打破此回归,从而防止内联的兄弟递归.

由于需要garbage collect使用未使用的功能,因此内联成本更加复杂.由于内联可能具有指数性,因此这是必不可少的.如果对函数的所有调用都是内联的,那么如果尚未内联函数,我们应该删除该函数,否则我们将浪费时间内联到一个不再使用的函数中.实际上跟踪谁调用极其困难的东西,因为在内联时我们不使用实际的函数表示,而是"解开"的表示:例如,正在按顺序处理指令列表并构建新列表,并且在任何一个时间点可能没有连贯的指令列表.

在他的ML编译器中,Steven Weeks选择使用多次重复应用的小优化,因为这使得优化易于编写且易于控制,但不幸的是,与递归算法相比,这错过了许多优化机会.

问题3:内联函数调用何时安全？

一般来说解释这个问题:在一个懒惰的函数式语言中,参数包含在闭包中,然后我们可以内联一个应用程序; 这是Haskell的标准模型.然而,它也解释了为什么Haskell这么慢.如果参数已知,则不需要闭包,那么参数可以直接替换其出现的参数(这是正常的顺序beta-reduction).

但是,如果已知参数评估不是非终止的,则可以使用急切评估:为参数分配表达式的值一次,然后重复使用.这两种技术的混合使用闭包但将结果缓存在闭包对象中.尽管如此,GHC还没有成功地生成非常高效的代码:显然非常困难,特别是如果你有单独的编译.

在菲利克斯,我采取了相反的方法.通过证明优化保留语义,而不是要求正确性并逐步提高效率,我要求优化定义语义.这保证了优化器的正确操作,但代价是不确定某些代码将如何表现.我们的想法是为程序员提供一些方法,以便在默认优化策略过于激进时强制优化器符合预期的语义.

例如,默认参数传递模式允许编译器选择是将参数包装在闭包中,用参数替换参数,还是将参数赋值给参数.如果程序员想要强制关闭,他们就可以传递一个闭包.如果程序员想要强制进行评估,他们会标记参数var.

这里的复杂性比函数式编程语言要大得多:Felix是一个带变量和指针的过程语言.它还有Haskell风格的类型.这使得内联例程极其复杂,例如,类型类实例尽可能替换抽象函数(由于在调用多态函数时类型特化,在内联时可能会找到一个实例,所以现在我们有了一个新函数可以内联).

为了清楚起见,我必须添加一些注释.

内联和其他一些优化,例如用户定义的术语缩减,类型类实例化,线性数据流检查变量消除,尾部rec优化,都是在给定函数上同时完成的.

排序问题不是应用不同优化的顺序,问题是订购功能.

我使用脑死算法来检测递归:我建立了每个函数直接使用的所有内容的列表,找到闭包,然后检查函数是否在结果中.请注意,在优化过程中,使用集会多次构建,这是一个严重的瓶颈.

函数是否递归可能会发生变化.尾部优化后,递归函数可能变为非递归.但是有一个更难的情况:实例化类型类"虚拟"函数可以使看似非递归的递归.

至于兄弟调用,问题是给定f和g,其中f调用g和g调用f我实际上想要将f内联到g中,并将g内联到f ..一次.我的无限回归停止规则是只允许将f内联到g如果它们是相互递归的,如果f是g的子,则不包括内联兄弟.

基本上我想"尽可能"地"平掉"所有代码.

考虑一下简短的语法

S -> Bc | DB
B -> ab | cS
D -> d | epsilon

第一组是

FIRST(S) ={a,c,d}
FIRST(B) = { a,c }
FIRST(D)= { d, epsilon }

在它里面

Follow(S)={ Follow(B) }

和

Follow(B) ={ c , Follow(S) }

我的问题是如何解决这个循环依赖？

我更喜欢Haskell.

我已经知道如何使用Procedural Language创建自己的语言(例如:C,Java,Python等).

但是,我知道如何用功能语言创建我自己的语言(例如Haskell,Clojure和Scala).

我已经读过了:

互联网资源

1. 在48小时内为自己写一个计划
2. 真实世界Haskell - 第16章.使用Persec
3. 在Haskell中编写一个Lisp解释器
4. Parsec,一个快速的组合子解析器
5. 实现函数式语言:教程

图书

1. 简介使用Haskell第二版进行功能编程 - Haskell

StackOverflow(但使用过程语言)

1. 学习编写一个编译器
2. 创建我自己的编程语言

资源

1. 图书馆和工具/ HJS - Haskell

还有其他好的链接/来源吗？我想得到更多.

如何通过编译器(通常)完成语义分析？

我在上次考试时不得不回答这个问题,这对教授来说还不够.

我在答案中包含了BNF(带有一个例子)和语法卡片,他问我:"当编译器找到类似的语句时会发生什么int i;？"

在学校,我们被教导编译器将计算机程序编译为机器语言.我们还被告知机器语言包含对硬件的直接指令.然后,如何在具有不同硬件的多个计算机配置上运行相同的编译程序？

不耐烦的总结:我正在寻找关于为公共语言结构生成代码但不解析的好参考.

我对编程语言很感兴趣,并尝试尽可能多地阅读文献.但是大多数都是从功能和理论的角度来讨论这个话题,我觉得很难理解,更不用说实现这些想法了.

所以问题是; 您建议哪些资源以更加迫切和实用的方式涵盖主题的编程语言实现？

例如,我发现" Lua 5.0的实现 "论文非常有启发性.

请注意,我不是在寻找有关解析或标记的文章.

什么是运行时？我并不是说"在运行时"=因为程序/脚本正在运行.我的意思是

<your-interpret-language-here>运行时

可能重复:
为什么使用一组空括号来调用没有参数的构造函数是错误的？

我已经看到了关于嵌套构造函数调用和支撑的C++ FQA 条目,并且总是想知道C++解析器如何解析两个以及为什么解析器无法解析它.

所以我明白为什么foo xxx();是模棱两可的.然后foo x(bar());是什么使得模糊,因为它显然没有前瞻性声明.(即:应该有一个语法可以成功检测到这一点).

有人可以解释C++语法那部分的局限性和模糊性吗？

我无法使用包含 epsilon 产生式的语法为 LR(1) 解析器构建项目集的集合。例如，给定以下语法（其中 eps 代表 epsilon）

S -> a S U
U -> b
  |  eps

State0 将是

S' -> .S, $
S -> .a S U, $

从 State0 移动 'a' 将给出以下状态，我们称之为 State2

S -> a .S U, $
S -> .a S U, $/???

为了对 State2 的第二项进行前瞻，我需要计算 FIRST(U$)。我知道 FIRST(U) = {'b', eps}。我的第一个问题是：State2 的第二项的前瞻是 $ 和 'b'？由于 U 可以是 eps，我的大脑告诉我，我也可以将 $ 作为前瞻，而不仅仅是 'b'。如果 FIRST(U) 只是 {'b'}，它就只是 'b'。那是对的吗？

第二个问题：在某些时候，我会有一个状态如下

S -> a S .U, $
U -> .b, …