PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

胡谷
5 years ago
Views:

1 编译原理第三章词法分析方徽星扬州大学信息工程学院 (505) 2018 年春季学期

2 词法分析器与语法分析器的关系源程序词法分析器词法单元 (token) 取下一个词法单元语法分析器符号表

3 本章主要内容一. 正规文法与有限自动机正规文法正规式正规集确定的有限自动机 (DFA) 非确定的有限自动机 (NFA) NFA 的确定化 DFA 的简化正规式与有限自动机之间的关系正规文法与有限自动机之间的关系二. 词法分析程序的设计预处理与超前搜索扫描器的输出格式扫描器的设计

4 词法分析基本术语词法单元词法单元名 : 抽象符号用于区别不同种类的词法单元, 用于当作语法分析器的输入符号属性值 ( 可选 ): 指针或常量值 ( 由具体实现决定 ) 例 :position = initial + rate 60 的词法单元名和属性值 : id, 指向符号表中 position 条目的指针 assign _ op id, 指向符号表中 initial 条目的指针 add_op id, 指向符号表中 rate 条目的指针 mul_ op number, 整数值 60

5 词法分析基本术语模式 : 描述一个词法单元的词素可能具有的形式词素 : 源代码中的实际字符序列, 可与某词法单元模式相匹配, 可被词法分析器识别为一个词法单元实例例 : 词素示例词素 if, else 词法单元名 Keyword <=,!= CompOp index, score FloatNumber ID

6 第一节正规文法与有限自动机

7 1.1 正规文法正规式正规集由正规文法产生的语言称为正规集, 可以使用正规式来形式地表示正规集, 设非空有限字母表 A = a i i = 1,2,, n}, 则空串符号 ε 是正规式,L ε = {ε} 空集符号是正规式, L ε = {} a A 是正规式, L a = {a} 如果 α, β 是正规式, 则下面都是正规式 : α β, L α β = L α L(β) ( 或 ) α β, L α β = L α L(β) ( 连接 ) α 和 β,l α = (L α ) ( 闭包 ) 正规式扩展 :α +, L α + = (L α ) + ;α?, L α? = L α ε ;[a 1 a 2 a m ]= a 1 a 2 a m, [a-z]= a b z

8 1.1 正规文法正规式正规集正规式代数定律 : 如果 α,β,γ 是正规式, 则下述等式成立定律 α β = β α α β γ = α β γ α βγ = (αβ)γ α β γ = αβ αγ (α β)γ = αγ βγ εα = αε = α (α ) = α α = α + ε 描述交换律结合律分配律 ε 是连接的单位元 * 具有幂等性闭包中一定包含 ε

9 1.1 正规文法正规式正规集定理 1: 设 α,β,γ 是字母表 A 上的正规式, 则 α = β αγ 当且仅当 α = βγ α = β γα 当且仅当 α = γ β 由正规文法求解对应语言的正规式 : 首先由各个产生式写出对应的正规方程式, 获得联立方程组这些方程组中的变元是非终结符, 求解方程组得到一个关于开始符号的解

10 1.1 正规文法正规式正规集例 : 已知正规文法的产生式如下 : S as ab, B bb ba, A ca c 求出它所定义的正规式解 : 由产生式写出联立方程组 : S = as ab (1) B = bb ba (2) A = ca c (3) 由定理 1,(1) 的解为 S = a ab = a + B; 同理 (2) 的解为 B = b ba = b + A; 由 (3) 可得 A = c c = c + ; 最后解得正规式 S = a + b + c +

11 1.2 确定的有限自动机确定的有限自动机 (DFA: Deterministic Finite Automata)M=(S, Σ, f, s 0, Z), 其中 : S: 有限状态集,S 的每一个元素 s 称为状态 Σ: 有穷字母表,Σ 的每一个元素 σ 称为输入字符 f:s Σ S, 转换函数, 对于状态 s S 和输入符号 σ Σ 最多只有一条标号为 σ 的边离开状态 s s 0 S 是初始状态 Z S 是终止状态集, Z 为空集时, 该 DFA 不接受任何东西

12 1.2 确定的有限自动机例 :DFA M = ( 0,1,2,3, a, b, f, 0, {3}), 其中 S = 0,1,2,3, Σ = a, b, s 0 = 0, Z = {3} 转换图如下所示 : b a b b a a 此例中转换函数 f 是如何定义的? a 3 b

13 1.2 确定的有限自动机状态转换图用于表示词法分析器被语法分析器调用时, 词法分析器为返回下一个词法单元所做的动作开始识别词法单元时, 控制进入开始状态如果离开状态的某条边上的标记与当前输入字符匹配, 则进入目标状态, 否则识别过程失败由双圈表示的状态规定为接受状态, 控制进入该类状态则表示成功识别了一个词法单元接受状态可以有动作, 到达接受状态时执行该动作符号 *: 表示需要回退一个字符

14 1.2 确定的有限自动机状态转换图示例开始状态接受状态 4 return(compop, GE) > Other 1 2 = 词法单元名属性值 3 * return(compop, GT) 接受状态

15 1.2 确定的有限自动机 DFA 接受输入串 x, 当且仅当转换图中存在从开始状态到某个终止状态的路径, 使得该路径上各边上的标记组成 x DFA 模拟算法输入 : 一个以文件文件结束符 EOF 结尾的字符串 x. DFA M 的开始状态为 s 0, 终止状态集为 Z, 转换函数为 f 输出 : 如果 M 接受 x, 则回答 yes, 否则回答 no s = s 0 ; c = nextchar(); While(c EOF){ s = f s, c ; c = nextchar(); } If (s Z) return yes ; Else return no ;

16 1.3 非确定的有限自动机非确定的有限自动机 (NFA: Nondeterministic Finite Automata)M=(S, Σ, f,s 0, Z), 其中 : S: 有限状态集,S 的每一个元素 s 称为状态 Σ: 有穷字母表,Σ 的每一个元素 σ 称为输入字符 f:s Σ {ε} 2 S, 转换函数, 对于每个状态 s S 和每个输入符号 σ Σ 可能有多条标号为 σ 的边离开状态 s s 0 S 是初始状态 Z S 是终止状态集, Z 可为空集确定与非确定的有限自动机能识别的语言的集合是相同的, 且是能够用正规式描述的语言集合

17 1.3 非确定的有限自动机例 :NFA M = ( 0,1,2,3, a, b, f, 0, {3}), 其中 S = 0,1,2,3, Σ = a, b, s 0 = 0, Z = {3} 转换图如下所示 : a b a b b 此例中转换函数 f 是如何定义的? 3

18 1.4 NFA 的确定化将 NFA 转换为 DFA 子集构造算法 (Subset Construction): 输入 : 一个 NFA N = (S N, Σ N, f N,s 0 N, Z N ) 输出 : 一个 DFA D = (S D, Σ D, f D,s 0 D, Z D ) 基本方法 : 构造 D 的状态和转换函数, D 的每个状态对应 N 的一个状态集合, N 中每个状态集合的转换对应 D 中的一个状态转换

19 1.4 NFA 的确定化子集构造算法主体 : 一开始,ε-closure(s 0 N ) 是 S D 中的唯一状态, 且未加标记 ; While ( 在 S D 中有一个未标记的状态 T) { 给 T 加上标记 ; For ( 每个输入符号 a ) { U = ε-closure(move(t, a)); If (U 不在 S D 中 ) Then 将 U 加入到 S D 中, 且不加标记 ; f D T, a = U; } } 操作 ε-closure(s) ε-closure(t) move(t, a) 描述能够从 NFA 的状态 s 出发只通过 ε 转换到达的 NFA 状态集合能够从 T 中某个 NFA 的状态 s 出发只通过 ε 转换到达的 NFA 状态集合能够从 T 中某个 NFA 的状态 s 出发只通过 a 转换到达的 NFA 状态集合

20 1.4 NFA 的确定化例 : 下图给出了一个接受语言 (a b)*abb 的 NFA ε ε 0 1 ε ε 2 a b ε ε ε a ε 构造 DFA:DFA 的开始状态 A 为 ε-closure(0)={0,1,2,4,7} NFA 状态集 DFA 状态符号 a 符号 b {0,1,2,4,7} A move(a,a)={3,8} B=ε-closure({3,8}) ={1,2,3,4,6,7,8} {1,2,3,4,6,7,8} B?? b b 10 move(a,b)={5} C=ε-closure({5}) ={1,2,4,5,6,7}

21 1.5 DFA 的简化任何一个正则语言都有一个唯一的状态数目最少的 DFA 从任意一个接受相同语言的 DFA 出发, 通过分组合并等价状态, 总可以构建得到该状态数最少的 DFA 如果分别从状态 s 和 t 出发, 沿着串 x 的路径到达的两个状态中只有一个是接受状态, 则串 x 区分状态 s 和 t 如果存在某个能够区分状态 s 和 t 的串, 则 s 和 t 是可区分的

22 1.5 DFA 的简化最小化 DFA 状态数量算法输入 :DFA D = (S,Σ,f,s 0,Z) 输出 : 最小化 DFA D 1. 首先构造包含两个组 Z 和 S Z 的初始分划 P, 分别是 D 的接受状态组和非接受状态组 ; 2. 构造新分划 Pn; 3. 若 Pn=P, 令 Pf=P 跳到步骤 4; 否则, 用 Pn 替换 P 并重复步骤 2; 4. 在分划 Pf 的每个组中选取一个代表, 则所有代表构成 D 的状态 : D 的开始状态是 D 的开始状态所在组的代表,D 的接受状态是那些包含了 D 的接受状态所在组的代表 ; 令 s 为某组代表, 且 s a t, 若 r 为 t 组的代表, 则 D 中有 s a r

23 1.5 DFA 的简化最小化 DFA 状态数量算法令 Pn = P; For (P 中的每个组 G) { 将 G 划分为更小的组, 使得两个状态 s 和 t 在同一个组中当且仅当对于所有的输入符号 a, 状态 s 和 t 在 a 上转换到 P 中的同一组里 ; } 在 Pn 中将 G 替换为对 G 进行划分得到的那些小组 ; 构造新分划 Pn

24 1.5 DFA 的简化例 : 将下图所示 DFA 最小化 b A b a a C B a b a b 第一次分划 : 非接受和接受第二次分划 :D 在 b 上不同于其他第三次分划 :B 在 b 上不同于其他 a D b {A, C} E 分划树 {A, B, C, D, E} {A, B, C, D} {A, B, C} {D} {B} {E} 最终 Pf={A,C}, {B}, {D}, {E}

25 1.6 正规式与有限自动机之间的关系定理 2: 字母表 Σ 上的 NFA M 所能识别的语言 L(M) 可以用 Σ 上的正规式表示定理 3: 对于 Σ 上的任何正规式 α, 存在一个 DFA M 使得 L(M)=L(α) 例 : 将下图所示的有限自动机使用正规式表示 a b c d 1 3 d a b 2 c ac 1 3 b ac 1 3 (b ac)(dc)* 1 3 dc dc 3 可消除状态正规式

26 1.6 正规式与有限自动机之间的关系由正规式构造 NFA 的 McMaughton-Yamada-Thompson 算法 : 沿着正规式的语法分析树自底向上递归地处理, 对于每个子表达式, 构造一个只有一个接受状态地 NFA 输入 : 字母表 Σ 上的一个正规式 γ 输出 : 一个接受 L(γ) 的 NFA N 方法 : 首先对 γ 进行语法分析, 分解出组成它的子表达式, 然后使用构造规则构造规则基本规则 : 处理不包含运算符的子表达式归纳规则 : 根据一个给定表达式的直接子表达式的 NFA 构造出这个表达式的 NFA

27 1.6 正规式与有限自动机之间的关系 McMaughton-Yamada-Thompson 算法基本规则对于表达式 ε, 构造下面的 NFA i ε f ( 其中状态 i,f 都是新状态 ) 对于字母表中的每个符号 a, 构造下面的 NFA i a f ( 其中状态 i,f 都是新状态 )

28 1.6 正规式与有限自动机之间的关系 McMaughton-Yamada-Thompson 算法归纳规则 : 假设正规式 s 和 t 的 NFA 分别是 N(s) 和 N(t), 则如果 γ = s t, 则 γ 的 NFA, 可以按照下图方式构造新开始状态 i ε ε N(s) N(s) 开始状态 N(t) 开始状态 N(t) N(s) 接受状态 N(t) 接受状态 ε ε f 新接受状态

29 1.6 正规式与有限自动机之间的关系 McMaughton-Yamada-Thompson 算法归纳规则 : 假设正规式 s 和 t 的 NFA 分别是 N(s) 和 N(t), 则如果 γ = st, 则 γ 的 NFA, 可以按照下图方式构造 N(s) 的开始状态 N(t) 的接受状态 i N(s) N(t) f 合并 N(s) 的接受状态与 N(t) 的开始状态

30 1.6 正规式与有限自动机之间的关系 McMaughton-Yamada-Thompson 算法归纳规则 : 假设正规式 s 和 t 的 NFA 分别是 N(s) 和 N(t), 则如果 γ = s*, 则 γ 的 NFA, 可以按照下图方式构造 N(s) 的开始状态 i ε ε N(s) N(s) 的接受状态 ε f 新开始状态 ε 新接受状态如果 γ = (s), 则 L(γ)=L(s), 直接把 N(s) 当作 N(γ)

31 1.6 正规式与有限自动机之间的关系例 : 使用 McMaughton-Yamada-Thompson 算法为正规式 r=(a b)*abb 构造一个 NFA r11 r9 r10 r7 r8 b r5 r6 b r4 * a ( ) r3 (a b)*abb 的语法分析树 r1 a r2 b

32 1.7 正规文法与有限自动机之间的关系设 G = (V N, V T, P, S) 是正规文法, 则存在一个有限自动机 M = (Q, Σ, f, q 0, Z) 使得 L G = L(M) 右线性文法的自动机构造规则 : 令 M 中的 Q=V N {T}, 其中 T 是新增的接受状态 ; 令 Σ = V T,q 0 = S; 若 P 中含有产生式 S ε, 则 Z = {S, T}, 否则 Z = {T} 转换函数 f 构造如下对于 P 中每一条形如 A 1 aa 2 的产生式, 有 f A 1, a = A 2 对于 P 中每一条形如 A 1 a 的产生式, 有 f A 1, a = T 对于 Σ 上所有的 a 有 f T, a =, 在接受状态下自动机没有动作

33 1.7 正规文法与有限自动机之间的关系例 : 已知文法 G=({S,A,B}, {a,b,c}, P, S), 其中 P 定义如下 1. S -> as, 2. S -> ab, 3. B -> bb, 4. B -> ba, 5. A -> ca, 6. A -> c 试构造等价的自动机解 : 按照构造规则, 构造等价自动机为 : M=({S, A, B, T}, {a,b,c}, f, S, {T}) a S a b B b c A c 其中 f 定义如下 : 1. f(s, a) = S 2. f(s, a) = B 3. f(b, b) = B 4. f(b, b) = A 5. f(a, c) = A 6. f(a, c) = T T

34 1.7 正规文法与有限自动机之间的关系 G = (V N, V T, P, S), M = (Q, Σ, f, q 0, Z) 左线性文法的自动机构造规则 : 令 M 中的 Q=V N {q 0 }, 其中 q 0 是新增的初始状态 ; 令 Σ = V T ; 若 P 中含有产生式 S ε, 则 Z = {S, q 0 }, 否则 Z = {S} 转换函数 f 构造如下对于 P 中每一条形如 A 1 A 2 a 的产生式,f A 2, a = A 1 对于 P 中每一条形如 A 1 a 的产生式,f q 0, a = A 1

35 1.7 正规文法与有限自动机之间的关系例 : 构造左线性文法 G=({S,A,B}, {a,b}, P, S) 的相应的自动机, 其中 P 定义如下 : 1. S -> Sa Aa Bb 2. A -> Ba a 3. B -> Ab b 解 : 按照构造规则,M = ({S, A, B, q 0 }, {a, b}, f, q 0, {S}) 转换函数 f 定义为 : a q 0 b a A B b b a S a f(s, a) = S f(a, a) = S f(b, b) = S f(b, a) = A f(q 0, a) = A f(a, b) = B f(q 0, b) = B

36 第二节词法分析程序的设计

37 2.1 预处理与超前搜索预处理 : 包括对空白符跳格符回车符和换行符等编辑性字符的处理, 及删除注解, 识别标号区找出续行符连接成完整语句等超前搜索 : 当读到一个单词后, 不能确定该单词的作用, 要向前多读几个字符后才能确定 ; 在读到一个单词之后, 在缓冲区或扫描缓冲区上做标记, 然后继续先前读, 直到明确之后再退回标记处重新分析如算符的识别 C/C++, java 的 ++, --, >=,!=, == 等

38 2.2 扫描器的输出格式词法分析程序通常又叫作扫描器单词分类 (Pascal 语言为例 ) 关键字 : 具有特殊含义的标识符, 起分隔语法成分的作用, 如 :program var procedure begin end 标识符 : 用于表示各种名字, 如 : 变量名数组名函数名过程名运算符算术运算符 + 逻辑运算符 :and or not 关系运算符 :> >= < <= = 分界符 :, ; ( ) :

39 2.2 扫描器的输出格式扫描器的输出格式为二元式序列, 每个单词对应一个二元式 ( 类号, 内码 ) 类号用整数表示, 区分单词的种类, 方便程序处理每个关键字有一个类号, 编译程序内部通常有关键字表, 表中的编号可以用作类号, 而内码可以省略对于标识符, 内码用于区分标识符名, 把符号表中地址作为内码常量, 按不同类型分成相应类号, 将常量表中的地址作为内码分界符, 整型类号, 内码可省略

40 2.3 扫描器的设计用 Lex 建立词法分析器的步骤 Lex 源程序 lex.l lex.yy.c 输入流 Lex 编译器 C 编译器 a.out lex.yy. c a.out 结果序列词法分析器仅返回记号名 ( 代表词法单元的抽象名字 ) 给语法分析器记号的属性值通过共享整型变量 yylval 传递

41 2.3 扫描器的设计 Lex 程序包括三个部分声明 %% 翻译规则 %% 辅助过程 Lex 程序的翻译规则模式 { 动作 } p1 { 动作 1} pn { 动作 n} 每个模式是一个正规式每个动作描述该模式匹配词法单元时, 词法分析器应执行的程序段

42 2.3 扫描器的设计例声明部分 %{ /* 常量 LT, LE, EQ, NE, GT, GE, WHILE, DO, ID, NUMBER, RELOP 的定义, 用 C 的 #define 方式来写 */ %} /* 正规定义 */ delim [ \t \n ] ws {delim}+ letter [A Za z] digit [0 9] id {letter}({letter} {digit})* number {digit}+(\.{digit}+)?(e[+\ ]?{digit}+)?

43 2.3 扫描器的设计例翻译规则部分 {ws} {/* 没有动作, 也不返回 */} while {return (WHILE);} do {return (DO);} {id} {yylval = install_id ( ); return (ID);} {number} {yylval = install_num( ); return (NUMBER);} < {yylval = LT; return (RELOP);} <= {yylval = LE; return (RELOP);} = {yylval = EQ; return (RELOP);} <> {yylval = NE; return (RELOP);} > {yylval = GT; return (RELOP);} >= {yylval = GE; return (RELOP);}

44 2.3 扫描器的设计例辅助过程部分 int installid ( ) { /* 把词法单元装入符号表并返回指针 */ } int installnum ( ) { /* 类似上面的过程, 但词法单元不是标识符而是数, 并放入数表 */ } Lex 最初的作者 :Mike Lesk,Eric Schmidt ( 前谷歌 CEO)

45 2.3 扫描器的设计 /* recognize tokens for the calculator and print them out */ %{ enum yytokentype { NUMBER = 258, ADD = 259, SUB = 260, MUL = 261, DIV = 262, ABS = 263, EOL = 264 }; int yylval; %} %% "+" { return ADD; } "-" { return SUB; } "*" { return MUL; } "/" { return DIV; } " " { return ABS; } [0-9]+ { yylval = atoi(yytext); return NUMBER; } \n { return EOL; } [ \t] { /* ignore whitespace */ }. { printf("mystery character %c\n", *yytext); } %% int main(int argc, char **argv) { int tok; while(tok = yylex()) { printf("%d", tok); if(tok == NUMBER) printf(" = %d\n", yylval); else printf("\n"); } }

46 小结正规文法与有限自动机主要是 DFA NFA 及正规式正规文法词法分析程序的设计了解实现词法分析程序的技术

大侠素材铺

大侠素材铺编译原理与技术词法分析 Ⅱ 计算机科学与技术学院李诚 13/09/2018 主要内容记号 (token) 源程序词法分析器 getnexttoken 语法分析器符号表词法分析器的自动生成正则表达式 NFA DFA 化简的 DFA 词法分析器的生成器 Lex: flex jflex Fst lexicl nlyzer genertor 2/51 Regulr Expr to NFA 正则表达式