Skip to main content
A cup of beer
  1. Posts/

编译原理-Week1

·151 words·1 min

编译器的结构 #

  • 词法分析

    • 例如给定语句 if x=y then z=1;else z=2;,则可以分析得到分解树,他的根是 if-then-else;下分 predicate then else三个孩子。这三个孩子分别都能解析成三个语句,分别是 relation 和两个assign,他们又分别能分解成 语句前部、后部。
    • 可见,这种分析是一种递归的过程。
  • 类型转换

  • 语义分析

    • 计算机很难做到这一点。

    • 例如 Jack said Jerry left his homework at home.那么到底是Jack的作业,还是Jerry的作业,还是其他人的作业呢?不知道。

    • 这种只有能通过上下文才能得到的分析,就是语义分析。一般情况下,例如变量的类型分析就是这样得来。

    • 因此,编程语言一般对可能导致模棱两可的情况进行非常谨慎的处理。例如C++中变量的作用域。

    • int main(){
        int test=3;
      	while(true){
      		int test=4;
      		cout<<test;
      	}
      }
      //这里,就是对test变量进行了严格的作用域限制。
      
  • 优化

    • 一个优化错误的例子:X=Y*0X=0在浮点的情况下是不等价的。因为纯0代表NaN。这样就导致Y*0=NaN
  • 代码生成

词法分析 #

Token Classes和Token #

  • 编程语言的Token Classes,也就是一个字符串扮演的角色情况。不同的Token Class就相当于英语中不同的语法成分,例如主谓宾。
    • Identifier标识符
      • 非数字开头的字符串
    • Number数字
    • Operator操作符
    • Keyword关键词
      • 例如if else
    • WhiteSpace空格
      • 例如空格、换行符\n、tab符 \t等。
  • 词法分析器Lexical Analysis的作用:Tokenize
    • 处理各字符串,并分别构成字符串+Token Class的二元组,传递给下一级。其中,这个二元组叫做Token,它携带了这个字符串的内容和他是什么成分这两种信息。

正则语言 - Regular Languages #

  • 元素的基本定义
    • 字符集 $\sum$:是一些字符构成的集合。可以用其中的字符来构成字符串,从而生成语法。一定要注意它是字符的集合,不是字符串。
    • 单字符:例如字符c,就代表了一个表示为{c}的字符集。
    • 空:记作 $\epsilon$. 代表了一个表示为 {}的字符串。
    • 并(加):例如A={a}.B={b,c}.则A+B={a,b,c}.
    • 连接(积):定义是 $AB={ab|a\in A\and b\in B}$.
    • 闭包(迭代):$A^*=\sum A^i(i\in[0,\inf))$.
      • 注意,i可以取到0,这就意味着 $A^*=\epsilon+A+A^2+…$.
    • 排0闭包: $A^+=AA^*$.
    • 可选A,记作 $A?$,表示为 $A?=A^++\epsilon$.
    • 范围表示,${0,1,2,3,4,5,6,7,8,9} =[0-9]$.
    • 范围补集,${0,1,2,3,4,5,6,7,8,9} $补集=[^0,9].
  • 例子
    • 设$\sum={0,1}$,则有 $1^*={\epsilon,1,11,111,…}$.
    • 此外,有 $(0+1)^={0,1}^=\sum^*=\epsilon+(0+1)+(0+1)^2+…+(0+1)^i$.
      • 注意,这就看出递归定义了。因为只要是 $(0+1)$出现的地方,实际上就是 ${0,1}$,也就是它可以由0或1中的任意一个字符代替。所以,它递归定义了这个01字符集上的任意字符串。
      • 而且,可以看出,因为 $(0+1)^$和 ${0,1}^$是一个意思,所以同一种grammer的表示方法并不唯一。

语言到语义的映射 #

  • 语言到语义是多对一映射。比如2+3和1+4表示的结果是一样的。又比如II和2表达的意思是一样的,又比如 $(0+1)^*={0,1}$.
  • 但是注意,不可能存在一对多的情况,否则程序就会出现未定义行为。

使用正则语言表达任意的需要匹配的模式(例) #

  • 首先方便起见,定义:
    • $digit={0,1,2,3,4,5,6,7,8,9} =[0-9]$.
    • $digits=digit^+$.
    • $letter={a,b,…,z,A,B,…,Z} =[a-z]+[A-Z]$.
  • 表达标识符:要求以字母开头,之后可以是字母或数字。
    • $letter\times (digit+letter)^*$.
  • 表达电子邮件:要求xxx@xxx.xxx。
    • $(letter+digit)^+\times @\times (letter+digit)^+\times . \times letter^+$,简记作 $(letter+digit)^+@ (letter+digit)^+.letter^+$.(即:可以不把乘号写出来。)
  • 总结
    • 可以空,则用闭包即可生成集合上的任意字符串,**或者可以用除零的闭包加上 $\epsilon$ ;**否则如果要求非空,就要用除零闭包去生成集合上的任意字符串。
    • 如果要连接字符串(即模式中的不同组成部分),则用乘法;如果要描述集合的字符组成范围,则用加法。

正则表达式匹配模式的原则 #

  • 首先,把这个编程语言所有的正确的模式的正则都进行相加,得到一个大的正则。于是,只要是与这个正则相匹配的输入就必然是没有问题的。
  • 接受了输入x1…xn,从左往右扫描,只要其中有x1…xi匹配成功,就把x1…xi从原输入中剔除,并把剩余部分重新作为输入。重复这个过程,直到都匹配完成。这样一来,就完成了词法分析。
  • 几个问题
    • 遇到非法输入,如何报错?如果存在非法输入,按照上面的规则,不就卡住了吗?因为不可能匹配,所以算法不可能退出。解决方式是:把这个编程语言的所有非法输入也做成一个大的正则,然后把这个正则放到优先级最低的位置。这样,只要前面那些正确的正则没匹配成功,才来匹配这个错误的。于是就匹配成功,就给出报错。
    • 如何区分 ===?当有多个模式可以匹配时,采取最长匹配原则。
    • 如何区分标识符和关键字?例如if为什么不被Tokenize成标识符?解决方式仍然可以采用优先级匹配原则,让关键字的优先级大于标识符即可!