lazyparser / becoming-a-compiler-engineer Goto Github PK

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是* 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」* 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)

书中提到了根据占位符的位置有三种情况，分别在产生式的前、中、后，但是没有提到前瞻符号a可以取哪些。我的理解是可以让占位符往下移动的终结符或者eof。但是看书中给到的括号语法的例子，感觉有几个LR(1)项应该不可能让占位符往下移动：

[Pair -> ( • Pair ), eof] // 如果在 '(' 后面结束了，肯定是一个不合法的语句
[Pair -> ( • Pair ), )] // • 后面的Pair只可能是 '(' 开始的，不可能接着 ')' 才对，这种情况下只有[Pair -> ( • ), )]才能接 ')' 吧

bace-lecture-01.pdf 下次课程内容页面， 4个链接点击后 弹出浏览器地址栏中?变化为%3F

https://github.com/wenwensong114/homework

您看要是没什么问题我就PR到可以参考的学生作业

https://github.com/wenwensong114/scanner

https://github.com/wenwensong114/homework/tree/master/grammar%20tree

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)

应该是Brzozowski

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是* 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」* 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)

测试用例是：

请问Cooper的以下课程资料有开源或可执行文件的公开下载吗？

1. 官方的ILOC simulator
2. Lab 1的reference implementation
3. 如果有lab test codes就更好了:)

PPT地址：https://www.clear.rice.edu/comp412/Lectures/L08Parsing-1.pdf

希望后续课程能更多得像03课程一样，注重实操，确实是其他课程都无法达到的效果。

A ——> Aα | β 转换为
A ——> β A'
A' ——> α A'
原句型Aα，α在后， 变为α A'后，疑惑这个满足交换律吗

29949@DESKTOP-CDVLE4T MINGW64 /f/gittest/bace03/src (master)
$ vi scanner.l

29949@DESKTOP-CDVLE4T MINGW64 /f/gittest/bace03/src (master)
$ flex scanner.l
bash: flex: command not found

在PL/I中，通过在一行连续写两个引号，可以向字符串中插入一个引号字符。因而下诉字符串
The code, " , should be typed
在PL/I中将写作
"The code," ",should be typed"

这道题是《编译设计》中第二章的一道题，我应该怎样设计RE和FA来识别？假定字符串以引号开始和结束，只包含取字字母表集中的符号。

Fall 2020 Edition of COMP 412
COMP 412 is being taught online in the Fall Semester of 2020. It will no longer use this web site.
Canvas is the offical course repository.
The course syllabus may be found on either the Canvas site or on Esther (official long-term repository for course syllabi).

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是* 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」* 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)

C/C++定义的代码如下：
#ifdef _WIN32
#define DLLEXPORT __declspec(dllexport)
#else
#define DLLEXPORT
#endif
extern "C" DLLEXPORT void foo(int a){
printf("in foo: %d\n", a);
}

在LLVM中创建foo函数的声明如下：
vector<Type *> argTypes(1, Type::getInt32Ty(TheContext));
FunctionType *fooType = FunctionType::get(Type::getVoidTy(TheContext), argTypes, false);
Function *foo = Function::Create(fooType, Function::ExternalLinkage, "foo", TheModule.get());

创建函数调用IR的代码如下：
Value *value = ConstantInt::get(TheContext, APInt(32, 2, true));
vector<Value *> ArgsV;
ArgsV.push_back(value);
Builder.CreateCall(foo, ArgsV, "calltmp2");

在通过JIT来执行上述函数调用的时候，总是报错，原因是无法找到foo函数。

我的LLVM版本是llvm-11
操作系统是：ubuntu-20.04

如果上下文无关语法定义中存在ε的话，书中提供LR(1)算法我觉得是没有办法处理这种情况。这时有两种处理方法。

方法一：通过修改语法定义移除ε，比如PL/0语法（完整语法我贴在了最下面）：

Program -> Block "."
Block -> Assign Declare Procedure Statement
Assign -> "const" ident "=" number AssignRest ";"
       |  ε
...

改写为：

Program -> Block "."
Block -> Assign Declare Procedure Statement
      |  Declare Procedure Statement
Assign -> "const" ident "=" number AssignRest ";"
...

虽然通过这种方式可以去掉ε，但是改写起来非常麻烦而且不直观。所以这里给出我在跟着书中的算法手写LR(1)时，想到的对ε的处理，非常简单就可以支持到对ε的引入。

方法二：在构造LR(1)项时，如果占位符前面是ε，则占位符往前移动直到前面不是ε为止。因为ε前后的位置实际上都是一样的，但是需要保留最后一个，用于方便判断该项是否可以产生一个归约。比如前面提到的PL/0中的ε：

[Assign -> • ε, a]

可以等价转换为：

[Assign -> ε •, a]

代码上的实现大概是这样子：

const Spec::CFG<Symbol> PL0_CFG{
    ...
    // c++中表示Assign的语法，引入了EPSILON符号
    {
        Symbol(NonterminalSymbolType::Assign),
        {
            // Assign的第一个产生式
            {
                Symbol(TerminalSymbolType::keyword, "const"),
                Symbol(TerminalSymbolType::ident),
                Symbol(TerminalSymbolType::keyword, "="),
                Symbol(TerminalSymbolType::number),
                Symbol(NonterminalSymbolType::AssignRest),
                Symbol(TerminalSymbolType::keyword, ";")
            },
            // Assign的第二个产生式，只有EPSILON符号
            {
                Symbol(SymbolType::EPSILON)
            }
        }
    },
    ...
}
class LR1 {
  ...
  LR1Item makeLR1Item (const Symbol& nt, const Production& p, int pos, const Symbol& t) {
    // 跳过epsilon符号
    while (pos < p.size() && p[pos] == epsilon) {
      pos += 1;
    }
    return LR1Item{nt, p, pos, t};
  }
  ...
}

PS：当然如果不引入EPSILON符号，直接让产生式空着（比如改成下面的语法定义），就不存在我这里提到的问题了，但是阅读起来不是很直观：

const Spec::CFG<Symbol> PL0_CFG{
    ...
    // c++中表示Assign的语法，不引入了EPSILON符号
    {
        Symbol(NonterminalSymbolType::Assign),
        {
            // Assign的第一个产生式
            {
                Symbol(TerminalSymbolType::keyword, "const"),
                Symbol(TerminalSymbolType::ident),
                Symbol(TerminalSymbolType::keyword, "="),
                Symbol(TerminalSymbolType::number),
                Symbol(NonterminalSymbolType::AssignRest),
                Symbol(TerminalSymbolType::keyword, ";")
            },
            // Assign的第二个产生式
            {
                // 这里是空的一个产生式
            }
        }
    },
    ...
}

附录

下面是我根据wikipedia中的PL/0改写的完整PL/0语法，主要是使用更简单的语法书写：

Program -> Block "."
Block -> Assign Declare Procedure Statement
Assign -> "const" ident "=" number AssignRest ";"
       | ε
AssignRest -> "," ident "=" number AssignRest
           | ε
Declare -> "var" ident DeclareRest ";"
        | ε
DeclareRest -> "," ident DeclareRest
            | ε
Procedure -> "procedure" ident ";" Block ";" Procedure
          | ε
Statement -> ident ":=" Expression
          | "call" ident
          | "?" ident
          | "!" Expression
          | "begin" Statement StatementRest "end"
          | "if" Condition "then" Statement
          | "while" Condition "do" Statement
          | ε
StatementPre -> ";" Statement StatementRest
              | ε
Condition -> "odd" Expression
          | Expression RelationOp Expression
RelationOp -> "=" | "#" | "<" | "<=" | ">" | ">="
Expression -> Term ExpressionRest
            | Op1 Term ExpressionRest
ExpressionRest -> Op1 Term ExpressionRest
                | ε
Op1 -> "+" | "-"
Term -> Factor TermRest
TermRest -> Op2 Factor TermRest
          | ε
Op2 -> "*" | "/"
Factor -> ident | number | "(" Expression ")"

https://pandolia.net/tinyc/index.html
偏实战，用简单和易于实现的实例来描述基本的编译原理及过程

https://perso.esiee.fr/~najmanl/compil/Flex/flex_1.html

pros:

• 学习资料可以完整地在一起管理

cons:

• 视频（和代码相比）都比较大
• 国内很多地方ISP访问github并不流畅
• 可以考虑repo里只放链接，指向B站或者百度网盘？

Hi all

现在作业和练习题已经逐渐变难，完全自学开始有点吃力。按照我们的SSR培养方式，后续开始进行课堂讨论。目前构思和尝试的几种方式，要面对大家时间不确定的现状，目前采用的方式是 「视频课布置作业 --> GitHub issues 汇总作业 --> 视频课针对提交的作业进行讲解」 的方式。

后续，《现代编译原理》和《编译器设计》的课后习题，我们按照章节开issues，接收作业。

提交可以是某个单独的习题的答案，最好做了一点就上传一点。

也欢迎大家相互评论和提问 :-)