标签: compiler-theory

什么被认为是对复杂单元(如编译器)进行单元测试的最佳方法？

多年来我写了一些编译器和解释器,我发现这种代码很难以一种好的方式进行测试.

如果我们采用类似抽象语法树生成的东西.你会如何使用TDD测试？

小结构可能很容易测试.例如:

string code = @"public class Foo {}";
AST ast = compiler.Parse(code);

因为那不会产生很多ast节点.

但是,如果我真的想测试编译器可以为类似方法生成AST:

[TestMethod]
public void Can_parse_integer_instance_method_in_class ()
{
   string code = @"public class Foo {  public int method(){ return 0;}}";
   AST ast = compiler.Parse(code);

你会断言什么？手动定义代表给定代码的AST,并断言生成的AST符合手动定义的AST看起来非常简洁,甚至可能容易出错.

那么像这样的TDD复杂场景的最佳策略是什么？

我试图了解 LR1 解析器的工作原理，但我想到了一个奇怪的问题：如果语法包含 Epsilons 怎么办？例如：如果我有语法：

S -> A
A -> a A | B
B -> a

很清楚如何开始：

S -> .A
A -> .a A 
A -> .B

... 等等

但我不知道如何为这样的语法做到这一点：

S -> A
A -> a A a | \epsilon

这样做是否正确：

S -> .A
A -> .a A a
( A -> .\epsilon )

然后让 DFA 中的这个状态接受？

任何帮助将不胜感激！

我应该写一个程序来做 2 + 2 = 4 和 2.2 + 2 = 4.2。

我已经这样做了，因此它将所有内容都视为浮点数，但这是“错误的”。我必须区分它们。这是我到目前为止所拥有的：

%{
#include <stdio.h>
#include <ctype.h>
%}

%token <dval> FLOAT
%token <ival> INTEGER

%union
{
   float dval;
   int ival;
}

%type <dval> command exp term factor

%%

command : exp           {printf("%f\n",$1);}
    ;

exp : exp '+' term      {$$ = $1 + $3;}
    | exp '-' term      {$$ = $1 - $3;}
    | term          {$$ = $1;}
    ;

term    : term '*' factor   {$$ = $1 * $3;}
    | …

我正在使用flex,byacc(用于词法和解析)和C++开发一个类似语言的小python,但我有一些关于范围控制的问题.

就像python一样,它使用白色空格(或制表符)进行缩进,不仅如此,但我想实现索引破坏,例如,如果你在while循环中键入"break 2",那么在另一个while循环中它不仅会从最后一个,但也来自第一个循环(因此在休息后的数字2),依此类推.

例:

while 1
    while 1
        break 2
        'hello world'!! #will never reach this. "!!" outputs with a newline
    end
    'hello world again'!! #also will never reach this. again "!!" used for cout
end
#after break 2 it would jump right here

但由于我没有"反"制表符来检查作用域何时结束(例如C,例如我只使用'}'字符)我想知道这种方法是否最好:

我将在我的yacc文件中定义一个全局变量,如"int tabIndex",我将使用extern在我的lex文件中访问.然后每当我在我的lex文件中找到一个制表符时,我会将该变量增加1.当我在yacc文件上解析时,如果我找到一个"break"关键字,我会减去它从tabIndex变量后面输入的数量,以及我编译后达到EOF并且我得到一个tabIndex!= 0我会输出编译错误.

现在的问题是,最好的方法是查看缩进是否减少,我应该从lex读取\ b(退格)字符然后减少tabIndex变量(当用户不使用break时)？

另一种实现这个的方法？

另外一个小问题,我希望每个可执行文件都有一个名为start()的函数的起点,我应该将其硬编码到我的yacc文件中吗？

对不起,长期以来,我们非常感谢任何帮助.如果有人可以为python提供yacc文件,那么作为指南很好(尝试在谷歌上看,没有运气).

提前致谢.

谁能告诉我如何在C#中实现Call By Name？

我现在正在使用编译器类,我们正处于构建CFG以实现优化的程度.我无法弄清楚的一件事是一个程序有多少CFG？我见过的每个例子似乎都是简单代码段的CGF.所以,如果你有一个程序说三个功能.你是否为每个功能都有一个单独的CFG,或者整个程序有一个大的CFG？

可能重复:
学习编写编译器

我需要提出一种类似于SQL的虚拟语言,其功能非常有限.我之前从未做过任何编译或解析.任何人都可以让我知道一个好的开始点可能是一个链接或相同的例子.我很无能为力.

我将使用这种虚拟语言和C/C++作为我的主要语言.

谢谢

这不完全是家庭作业,但它与我的研究有关:

例如语法就像:

E - > E + E | E*E | -E |(E)| id

消除歧义后,它变为(从最低优先级运算符开始)

E->-F|F
F->F+G|G
G->G*H|H
H->(E)|id

在删除左递归并留下因子(在这种情况下不需要)之后,最终的LL1语法是:

E->-F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

这给出了一个无错误的解析器表,工作正常.现在关于我面临的问题,假设语法是这样的:

E - > E + E | E*E | id = E |(E)| id

现在我无法生成没有冲突的解析表,这意味着我的最终语法不是LL1.以下是步骤:

消除歧义后:

E->id=F|F
F->F+G|G
G->G*H|H
H->(E)|id

删除左递归并保留左因子后,语法变为:

E->id=F|F
F->GF'
F'->+GF'|e
G->HG'
B->*HG'|e
H->(E)|id

但是Parser表中存在一个我无法删除的冲突,这意味着我已经错过了一些步骤,或者在我无法找到的步骤中存在一些错误.请告诉我我做错了什么,以及如何解决这个问题.我一直在研究这个问题很长一段时间了.

首先，这个问题纯粹是理论性的。我不是在寻找解决方案（我已经知道了），我只是在寻找解释。

以下代码无法编译：

struct foo {};
void a(foo) {}
namespace foobar {
    void a(foo) {}
    void b(foo f) {a(f);}
}
int main() {return 1;}

MSVC++：

1>c:\projects\codetests\main.cpp(7) : error C2668: 'foobar::a' : ambiguous call to overloaded function
1>        c:\projects\codetests\main.cpp(4): could be 'void foobar::a(foo)'
1>        c:\projects\codetests\main.cpp(2): or       'void a(foo)' [found using argument-dependent lookup]
1>        while trying to match the argument list '(foo)'

G++：

main.cpp: In function 'void foobar::b(foo)':
main.cpp:5:20: error: call of overloaded 'a(foo&)' is ambiguous
main.cpp:5:20: note: candidates are:
main.cpp:4:7: note: void …

我正在为一个宠物项目编写解析器，出于教育目的，我想手工而不是使用解析器生成器。不幸的是，许多在线资源（以及我在大学上的编译器课程）都采用某种 LL(k) 语法。我不想保留语法因素，因为左递归非终结符，例如

E ::= E * E
    | E / E
    | E + E
    | E - E
    | ...

这在类似野牛的解析器生成器中是可能的，这似乎大大简化了语法。

手动解析这种语法的最简单方法是什么？到目前为止，我的研究告诉我，由于这里解释的原因，递归下降不是一种选择，并且使用递归上升的 LR 解析可能是一个不错的选择，尽管有几个站点停下来提到它不直观。