斯坦福cs231(编译原理)の 12 Conclusion

运行时和编译时的划分及概念（广义和狭义）？

compile: The instructions or source code written using high-level language is required to get converted to machine code for a computer to understand. During compile time, the source code is translated to a byte code like from .java to .class. During compile time the compiler check for the syntax, semantic, and type of the code.

Inputs and Outputs

Inputs and outputs during compile time are the following:

Inputs – Source code, dependent files, interfaces, libraries required for successful compilation of the code
Outputs – On successful compilation, a complied code (assembly code or relocatable object code), otherwise compile time error messages

Errors: During compile time errors occur because of syntax and semantic. The syntax error occurs because of the wrong syntax of the written code. Semantic errors occur in reference to variable, function, type declarations and type checking.

简单来说，就是把源代码编译成计算器可以理解的语言，就是编译，注意这里计算机可以理解的语言不一定是汇编和机器码什么的，也可以是与特定操作系统无关的中间语言(字节码)，这个时候可以把这些执行字节码的解释器或者虚拟机理解一个小型的操作系统。

Runtime:

A program’s life cycle is a runtime when the program is in execution. Following are the different types of runtime errors:

Division by zero – when a number is divided by zero (0)
Dereferencing a null pointer – when a program attempts to access memory with a NULL
Running out of memory – when a computer has no memory to allocate to programs

静态作用域和动态作用域的实现有什么不同？

静态类型检查和动态类型检查:

首先得先明确什么是编译时什么是运行时，

一般的运行时表示从上至下执行汇编代码，但还有些运行时包含中间代码执行时的运行时，举个例子：

Python => (编译) pyc(中间代码文件) => (解释器解释执行) 结果

这里的pyc => 结果就是运行时，这一步其实包含了把中间代码转为汇编or机器指令的过程，以及优化和类型检查，垃圾回收等，但其实用户感知不到这些过程，感觉好像字节码直接被运行了，所以这些也被包含在运行时里，

思考：编译+AI优化？

上下有关文法的理解，什么语言会用上下有关文法，上下无关文vs上下有关文法的比较，各有什么特点

题主的主要疑惑应该在于：什么是上下文，上下文在哪里？为什么说这个文法上下文无关？

答案就是：在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文。上下文无关的意思的，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导。（从形式上来看，就是产生式的左边都是单独一个非终结符，即形如 S-> ...，而不是非终结符左右还有别的东西，例如 aSb -> ...）

作者：Quokka 链接：https://www.zhihu.com/question/21833944/answer/307309365 来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这么描述有点儿抽象，我举一个自然语言的例子：

上下文无关文法：

产生式：

Sent -> S V O

S -> 人 | 天

V -> 吃 | 下

O -> 雨 | 雪 | 饭 | 肉

其中英文字母都是非终结符（SVO 分别表示主谓宾），汉字都是终结符。

这个文法可以生成如下句子（共 224=16 种组合，懒得写全了，简单写 7 种意思意思）：

｛人吃饭，天下雨，人吃肉，天下雪，人下雪，天下饭，天吃肉，……｝

可以看到，其中有一些搭配在语义上是不恰当的，例如“天吃肉”。其（最左）推导过程为：

Sent -> SVO -> 天VO -> 天吃O -> 天吃肉

但是上下文无关文法里，因为有“V -> 吃 | 下”这样一条产生式，V 就永远都可以推出“吃”这个词，它并不在乎应用“V -> 吃 | 下”这个产生式进行推导时 V 所在的上下文（在这个例子里，就是”天VO“中 V 左右两边的字符串”天“和”O“）。事实上，在 V 推出“吃”这一步，它的左边是“天”这个词，而”天“和”吃“不搭配，导致最后的句子读起来很奇怪。

那上下文有关文法呢？产生式可以定义为（其中前两条产生式仍是上下文无关的，后四条则是上下文有关的）：

Sent -> S V O

S -> 人 | 天

人V -> 人吃

天V -> 天下

下O -> 下雨 | 下雪

吃O -> 吃饭 | 吃肉

可以看到，这里对 V 的推导过程施加了约束：虽然 V 还是能推出”吃“和”下“两个词，但是仅仅当 V 左边是”人“时，才允许它推导出”吃“；而当 V 左边是”天“时，允许它推导出”下“。这样通过上下文的约束，就保证了主谓搭配的一致性。类似地，包含 O 的产生式也约束了动宾搭配的一致性。

这样一来，这个语言包含的句子就只有｛人吃饭，天下雨，人吃肉，天下雪｝这四条，都是语义上合理的。

以”人吃饭“为例，推导过程为：

Sent -> SVO -> 人VO -> 人吃O -> 人吃饭

其中第三步推导是这样的：非终结符 V 的上文是“人”，因此可以应用“人V -> 人吃”这条产生式，得到“人VO -> 人吃O”。第四步也类似。

而

@范彬

回答的是语法的歧义性，这和 CFG 无关。最简单的例子：

假设有如下上下文无关文法：

S -> S1 | S2
S1 -> ab
S2 -> AB
A -> a
B -> b

那么对于 "ab" 这个串，一种推倒方式是 S -> S1 -> ab，另一种是 S -> S2 -> AB -> aB -> ab。前一种要把 "ab" 合起来，后一种要分开，这只是说明该文法有歧义，而不能说这是一个上下文有关文法。事实上，还有一些上下文无关语言是固有歧义的（能产生该语言的每一种上下文无关文法都有歧义）。

上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符，比如：

S -> aSb

S -> ab

这个文法有两个产生式，每个产生式左边只有一个非终结符S，这就是上下文无关文法，因为你只要找到符合产生式右边的串，就可以把它归约为对应的非终结符。

比如：

aSb -> aaSbb

S -> ab

这就是上下文相关文法，因为它的第一个产生式左边有不止一个符号，所以你在匹配这个产生式中的S的时候必需确保这个S有正确的“上下文”，也就是左边的a和右边的b，所以叫上下文相关文法

在替换的时候，不是直接替换，还要考虑左边符号的左右环境

现代编译器和字节码？

typescript？

编译的概念是什么？

为什么正则语言不能用于文法解析？因为正则语言无法处理递归的嵌套结构，不信你用正则写一个嵌套任意层级的if-else试试？

为什么要有空转换：A -> epsilon ? 主要是未来消耗某个非终结符哈，以预测一个字符为例：

T[E, t] = a, t是一个预测字符，有一个特殊的情况，epsilon用于消耗某个非终结符，如X -> E | epsilon

LL和LR差异

什么是LL(1),是语言还是解析器？其性质是什么，什么样的文法才是LL(1)

如何避免左递归

名次辨识：语言，语法，production， item，viable prefix，handle，解析器

LL1指的是文法

language: 对于人类来说，符合一些既定规则（语法）的文本标记就是语言，语言通常是针对人来说的，而语义往往人类察觉不到，语法则是帮助人们理解语义的一座桥梁

grammar：语法是构成语义的重要组成部分，可以说两者是相辅相成的，语法 <=> 语义

semantics：编程语言里的语义是指组成句子的单元之间的关系，这个关系是结构化的，而每个单元也是可以结构化的

Production:

Handle: 句柄（handle）是一个来自编译原理的术语，指的是一个句子中最先被规约的部分，所以带有一个「句」字。

Viable prefix：:

Parser: 把序列文本转成结构化语义的分析器

Item:

(2 封私信 / 34 条消息) 运行时（runtime）是什么意思？应该怎样深入且直观地理解？ - 知乎 (zhihu.com)

运行时库不仅包含include的，也包含编译器自动插入的；

https://zhuanlan.zhihu.com/p/71718231

以类为例，大致的一个编译流程：

Class Student {
public:
	int a;
	int name;
	void print() {};
	Student(int name, int age) {
		a = age;
		name = name;
	}
}

s = new Student(2);
s.print();

编译类时：在Symbol Table里注册，并记录该类的信息：[Student, 16, a, name, ptr] // Student是标识符，a是其中一个属性, 8是该类的大小，同时有个指向代码段的指针ptr

编译new语句时，在Symbol中找到该类，找到后寻找第一个offset的值也就是类大小8，call，malloc 16 byte的空间， 第一个参数name，name的偏移量是8；处理第二个参数a偏移量是4。

编译S.print时，找到ptr指向的地址，编译对应的函数即可；如果函数里使用了变量，优先在参数和局部变量找（具体看怎么实施的），然后去当前的这个类里找；

1
2
3

a = [1,2]
b = [3, 4]
sum(a, b)

Runtime Error (NZEC)
Traceback (most recent call last):
  File "script.py", line 3, in 
    sum(a, b)
TypeError: can only concatenate list (not "int") to list

tupleconcat(PyTupleObject *a, PyObject *bb)
{
    Py_ssize_t size;
    Py_ssize_t i;
    PyObject **src, **dest;
    PyTupleObject *np;
    if (Py_SIZE(a) == 0 && PyTuple_CheckExact(bb)) {
        return Py_NewRef(bb);
    }
    if (!PyTuple_Check(bb)) {
        PyErr_Format(PyExc_TypeError,
             "can only concatenate tuple (not \"%.200s\") to tuple",
                 Py_TYPE(bb)->tp_name);
        return NULL;
    }
    PyTupleObject *b = (PyTupleObject *)bb;

    if (Py_SIZE(b) == 0 && PyTuple_CheckExact(a)) {
        return Py_NewRef(a);
    }
    assert((size_t)Py_SIZE(a) + (size_t)Py_SIZE(b) < PY_SSIZE_T_MAX);
    size = Py_SIZE(a) + Py_SIZE(b);
    if (size == 0) {
        return tuple_get_empty();
    }

    np = tuple_alloc(size);
    if (np == NULL) {
        return NULL;
    }
    src = a->ob_item;
    dest = np->ob_item;
    for (i = 0; i < Py_SIZE(a); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    src = b->ob_item;
    dest = np->ob_item + Py_SIZE(a);
    for (i = 0; i < Py_SIZE(b); i++) {
        PyObject *v = src[i];
        dest[i] = Py_NewRef(v);
    }
    _PyObject_GC_TRACK(np);
    return (PyObject *)np;
}