编译原理

1 词法分析

1.1 概述

词法分析是编译原理的第一个阶段,词法分析的任务是读入源程序的输入字符,生成一个个的单词,其主要的功能是为语法分析提供词法单元

graph LR

S1((源程序))
S2[词法分析器]
S3[语法分析器]
S4((符号表))
S5[输出之语义分析]

S1-->S2-->S3-->S5

S3-->S2

S2-->S4
S4-->S2

S3-->S4
S4-->S3

1.2 正则表达式

• 对于给定的正则表达式 $\Sigma$={c1, c2, c3…cn}
• 归纳定义:
  • 对于空串是正则表达式$\epsilon$是正则表达式
  • 对于任何$c\in\Sigma$,$c$是正则表达式
  • 如果M和N都是正则表达式,那么下面的也是正则表达式
    • 选择: M | N = {M, N}
    • 连接: MN = {mn| m $\in$ M, n, $\in$ M }
    • 闭包: M* = {$\epsilon$, M, MM, MMMM….}

1.2.1 flex正则表达式

使用flex学习正则表达式

Flex由三部分组成

定义部分
%%
规则部分
%%
用户附加的C语言部分

%%
[+-]?[0-9]+ { /* Print integers */
  printf("%s\n", yytext);
}

\n { /* newline */
}

. { /* For others, do nothing */
}
%%

void main(){
    yylex();
}

int yywrap(){
    return 1;
}

编译指令

#!/bin/sh

# 生成c源程序
flex lex.l

# 执行程序编译
gcc lex.yy.c

1.3 有限状态自动机(FA)

graph LR

输入的字符串 --> 有限状态自动机
有限状态自动机 --> 判断结果["{Yes, No}"]

1.3.1 数学描述

M = ($\Epsilon$, $S$, $q0$, $F$, $\delta$)

• $\Epsilon$ 字母表
• $S$ 状态集
• $q0$ 初始状态
• $F$ 终止状态
• $\delta$ 转移函数

1.3.2 例子

• 下面什么样子的串可以接受

graph LR

状态1((0))
状态2((1))
状态3((2))

状态1--b-->状态1
状态1--a-->状态2

状态2--b-->状态2
状态2--a-->状态3

状态3--a,b-->状态3

• 转移函数
  • ($q0$, a) –> $q1$, ($q0$, b) –> $q0$,
  • ($q1$, a) –> $q2$, ($q1$, b) –> $q1$,
  • ($q2$, a) –> $q2$, ($q2$, b) –> $q2$,

1.4 自动生成

graph LR
RE[正则表达式]
NFA[非确定有限自动机]
DFA[确定有限状态自动机]
mDFA[最简有限状态自动机]
RE--Thompson-->NFA--子集构造-->DFA--Hopcroft-->mDFA

1.4.1 Thompson算法

1.4.1.1 解释

• 基于RE的结构进行归纳
  • 对基本的RE进行直接构造
  • 对于复合的RE进行递归构造
• 递归,容易实现
  • 代码实现较少

1.4.2 例子

$a(b|c)*$

1.4.3 子集构造算法

1.4.4 Hopcroft算法

2 语法分析

2.1 自顶向下

• 递归下降
• 预测分析LL(1)

2.1.1 LL(1)分析文法

鉴于自定向下分析法存在回溯的问题,对于现代编译器设计是不可以接受的;由此提出了LL(1)分析文法

2.1.1.1 LL(1)文法概述

给出文法

0: S -> N V M
1: N -> s
2:   | t
3:   | g
4:   | w
5: V -> e
6:   | d

那么同时给出LL(1)分析表

那么在分析g d w语句的时候,可以得到如下的分析

解析算法

tokens[];  // all tokens
i = 0;
stack = [S]  // S 是开始符号
while(stack[] != [])
    if(stack[top] is a terminal t)
        if(t == tokens[i++])
            pop();
        else
            error(...);
    else if(stack[top] is a nonterminal T)
             pop();
             push(table[T, tokens[i]])

2.1.1.2 LL(1)一般步骤

如何判断文法是LL(1)文法 求出该文法的first集、follow集和select集， 通过select集之间的关系进行判断

graph TB
S0{判断是否是LL1文法}
S1[消除文法左递归]
S2[消除文法的回溯]
S3[计算所有非终结符的FIRST集]
S4[计算所有非终结符的FLLOW集]
S5[根据FIRST和FLLOW集生成分析表]
S6[进行LL1分析]

SA((开始))
SS((结束))

SA-->S0
S0--是-->S1
S0--否-->SS
S1-->S2-->S3-->S4-->S5-->S6-->SS

2.1.1.3 如何生成LL(1)分析表

那么就可以得到一个没有回溯的分析算法,但是怎么得到这个分析表呢？

2.1.1.3.1 FIRST集

2.1.1.3.2 FOLLOW集

2.1.1.3.3 SELECT集

2.1.2 分析流程

2.2 自底向上

2.2.1 LR(0)分析算法

移进-规约算法

2.2.2 点记号

.为了方便标记语法分析器已经读入可多少输入,我们可以引入一个点记号,来表示为读入的数据

2.2.3 生成一个逆序的最右推导

• 需要两个步骤
  • 移进一个记号到栈顶上
  • 规约栈顶上的n个符号到左部的非终结符
    • 对于产生式 $A$ -> $\beta$1 … $\beta$n,如果可以推导,那么弹出$\beta$1 … $\beta$n,
    • 压入非终结符
• 如何确定移进-规约的时机

2.2.3.1 构造分析表

3 语义分析