Microsoft PowerPoint - 3-LexicalScanning.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - 3-LexicalScanning.ppt"

驾低禄
5 years ago
Views:

1 Compler8 LexclScnnng 第三章词法分析有限自动机词法分析器的设计与实现词法分析器的自动生成有限自动机确定有限自动机非确定有限自动机正规文法与确定自动有限自动机的等价性正规式与确定自动有限自动机的等价性确定自动有限自动机的化简作业 : P6-65:,6-9,-4,8*,* ( 九月二十二交 ) 上机 : () 编写识别 C 的数值型常数的扫描程序 () 用 LEX 自动产生一个指定语言的扫描程序 ( 上机时间由班级自行安排, 定了以后通知辅导老师 ) 正规式与正规集正规式和正规集的形式定义和 φ 都是字母表上的正规式, 它们所表示的正规集分别为 {} 和 φ ; 任何, 是上的一个正规式, 它所表示的正规集为 {}; 假定 U 和 V 都是上的正规式, 它们所表示的正规集分别记为 L(U) 和 L(V), 那么 (U V) (U V) 和 (U) * 也都是上的正规式, 而且它们所表示的正规集分别为 L(U) L(V) L(U) L(V) 和 L(U) * Σ={,}, 通过有限次使用上述三个步骤而得到的表达式是那么 *, ( )* 和 ( )*( )( )* 都是 Σ 上的正规式正规式由这些正规式所表示的符号串的集合是上的正是 (), 是 (), 是规集是 ()=>*( 是 ()=> 是 ( 是或 ( 或 )=>( )*( 闭包闭包 ) 是 ); 是 ; 是 ()=> 是 ()=> ( )* 是是 ( 连闭包 ), 是 ()=>* 是 ( 连接 ) ( 连接接 );) 是 ()=> 是 ( 连接 )=> ( )*( )( )* 是 ( 连接 ) 正规集 : 上所有以为首后跟到多个的符号串正规集 : Σ : 上所有以 Σ 上所有含有两个相继为首的符号串或两个相继的符号串例 : Σ={,}, 那么 *, ( )* 和 ( )*( )( )* 都是 Σ 上的正规式是 ()=>*( 闭包 ) 是, 是 ()=>* 是 ( 连接 ) 正规集 : Σ 上所有以为首后跟到多个的符号串是 (), 是 ()=> 是 ( 或 )=>( )*( 闭包 ) 是 ; 是 ()=> ( )* 是 ( 连接 ) 正规集 : Σ 上所有以为首的符号串是 (), 是 ()=> 是 ( 或 )=>( )*( 闭包 ) 是 ; 是 ()=> 是 ( 连接 ); 是 ()=> 是 ( 连接 )=> ( )*( )( )* 是 ( 连接 ) 正规集 : Σ 上所有含有两个相继或两个相继的符号串正规式和正规集举例令字母表 ={,}, 则 : 正规式表示集合 {, } 正规式 ( )( ) 表示集合 {,,, } 正规式 * 表示由到多个构成的符号串的集合正规式 ( )* 表示由到多个或构成的符号串的集合正规式 * 表示符号串以及由到多个后跟一个构成的符号串的集合正规式与正规集正规式 : 形式语言中确切定义一组合法的单词符号的字的规则构造这种规则采用如下三类运算符 : 连接 xy 选择 x y x 或 y 重复 x * x 重复到多次重复 x + x 重复到多次例 : 正规式 ( )* 表示的单词符号为 :,,,,,, 即由和组成的任意符号串这些符号串的全集叫正规集 < 整数 >:=< 数字 > < 整数 >< 数字 > ( )+ < 标识符 >:=< 字母 > < 标识符 >< 字母 > < 标识符 >< 数字 > ( c )+( c )* Ynlng Zho

2 Compler8 LexclScnnng 正规式的代数性质对于定义在字母表 {,} 上的语言, 分别给出下述正规集的正规式 : ) 所有以为开头和结尾的符号串 ( )* ) 第奇数位都是的所有符号串 ( )(( ))* ( )(( ))* c) 不具有任何两个连续的所有符号串 *(+)* *(+)* 若两个正规式 U 和 V 所表示的正规集相同, 则称为二者等价, 记为 U=V 例如, ()*=()* ( )*=(**)* 公理 U V = V U U (V W) = (U V) W (UV)W = U(VW) U(V W) = UV UW (U V)W = UW VW U = U U = U U** = U* 描述是可交换的是可结合的是可结合的对可分配是的衡等元素 * 是幂等的大写字母为正规式正规式的或运算正规式的连接运算 * 正规式的闭包运算正规定义字母表 Σ 上的正规定义形如 : d r d r d n r n 各个 d 的名字不同, 每个 r 是字母表 Σ {d, d,,d - } 上的正规式, 其中 =,,,n <> <s> <> + 引入的符号 <num> [+ -]<s><s>[e[+ -]<s>] Fnte-Stte Automt Alphet Set of sttes wth ntl nd ccept sttes Trnstons etween sttes, leled wth letters ( )*( )* 初态终态 Automton Acceptng Strng 例 Conceptully, run strng through utomton Hve current stte nd current letter n strng Strt wth strt stte nd frst letter n strng At ech step, mtch current letter gnst trnston whose lel s sme s letter Contnue untl rech end of strng or mtch fls If end n ccept stte, utomton ccepts strng Lnguge of utomton s set of strngs t ccepts 当前状态当前符号 Ynlng Zho

3 Compler8 LexclScnnng 例例当前状态当前状态当前符号当前符号例例当前状态当前状态符号串被接受当前符号当前符号确定有限自动机 (DFA) 一个确定有限自动机 M 是一个五元式 M = (S, Σ, δ, s, F), 其中, S 是一个有限的状态集合 ; Σ 是有穷字母表, 它的每个元素称为一个输入字符 ; δ 是一个从 S 至 S 的单值部分映射 δ(s,)=s' 意味着 : 给定状态 s 和输入字符返回状态 s'; s S 是唯一的初态 ; F S 是一个终态集 ( 可空 ) M = ({,,, }, {, }, δ,, {}) 状态矩阵一个 DFA 可用一个矩阵表示, 该矩阵的行表示状态, 列表示输入字符, 矩阵元素表示 δ(s,) 的值 ( 转换的状态 ) 这个矩阵称为状态转换矩阵例 : 有 DFA 相应的状态转换矩阵如下表 : 其中 M = ({,,, }, {, }, δ,, {}) 其中 δ 为 : 输入符号 δ(,)= δ(,)= δ(,)= δ(,)= δ(,)= δ(,)= δ(,)= δ(,)= 状态矩阵元素 Ynlng Zho

4 Compler8 LexclScnnng 状态一个 DFA 也可用一张 ( 确定的 ) 状态转换图来表示假定 DFA M 含有 m 个状态和 n 个输入字符, 那么, 这个状态转换图含有 m 个状态结点, 每个结点顶多有 n 条箭弧射出和别的结点相连接, 整张图含有一个初态结点和若干个 ( 可以为 ) 终态结点 M = ({,,, }, {, }, δ,, {}) 图 5 状态转换图, 给定 DFA M = (S, Σ, δ, s, F), 对于 Σ* 中的任意符号串 α, 若存在一条从初态结点到终态结点的路径, 且这条路径上的所有弧的标记依次连接成一个符号串, 同时这个符号串等于 α 则称 α 可为 DFA M 所识别 ( 读出或接受 ) 给定 M = ({,,, }, {, }, δ,, {}) 有 : S = {,,, } = {, } *= {,,,,,,,,, }, 例如 : 对于 * 上的符号串 : 识别所有为 M 所识别的不识别 Σ* 中的符号串组成的集合称为识别 M 的语言, 记为 L(M) 识别不识别正规式和 DFA δ: ( ) ( )* s {,,,,4,5,6,7,8,9} 如果一个 DFA M 的输入字母表为 Σ (M 称为 Σ 上的一个 DFA), 则 Σ 上的一个字集 V Σ* 是正规的, 当且仅当存在 Σ 上的 DFA M 使得 V=L(M) nt {,,,,4,5,6,7,8,9} M = ({s,nt}, {,,,,4,5,6,7,8,9}, δ, s, {nt}) nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt nt <> <s> <> + <num> [+ -]<s><s>[e[+ -]<s>] [ ] E E 课堂练习 : 写出该状态转换图所对应的 DFA E E E-67 接受正则式 + * * 的正则集的 DFA 如下所示 : 例 -4: 串中只有一个被如下所示的 DFA 接受 : not not 例 -5: 包含最多一个的串被如下所示的 DFA 接受 : not not Ynlng Zho 4

5 Compler8 LexclScnnng 非确定有限自动机 (NFA) 一个非确定有限自动机 M 是一个五元式 DFA M = M (S, = (S, Σ, Σ, δ, δ, S s, F), 其中,, F) 的确定性表现在同 δ DFA 映射是一个单值函数 S 是一个有限的状态集合即对于任何状态 s S, 和输入符号 ; Σ, δ(s,) 唯一地确定了下一个状态 Σ 是有穷字母表, 它的每个元素称为一个输入字符 ; 当 δ δ(s,) 是一个从的值不唯一时 S Σ* 至 S 的映射 δ(s,α)=t 意味着 : 给定状态 s 和输入符号串 α 返回状态集合 T, 其中 T S; S S 是非空初态集 ; F S 是一个终态集 ( 可空 ) 每个箭弧上的输入是一个符号串 ( 含 ) 状态的迁移不再对于一个输入符号串是唯一的 ; 开始状态可以多个 NFA 接受输入串 α, 当且仅当转换图中存在从开始状态到终态的一条路径, 使得该路径中每条边的输入符号串依次连接成为 α 一个 NFA 也可用一张 ( 确定的 ) 状态转换图来表示假定 NFA M 含有 m 个状态, 每个结点可射出若干个箭弧与别的结点相连, 每个弧用 Σ* 中的一个字作为输入字整张图至少含有一个初态结点以及到多个终态结点 NFA 接受输入串 α, 当且仅当转换图中存在从开始状态到终态的一条路径, 使得该路径中每条边的输入字依次连接成为 α 对应的正则式为 * * M = ({,,, }, {, }, δ, {}, {}) 状态 {,} {} {,} {} φ {} {} {} φ {} {} {} φ φ {} {} 图状态转换图对应的正规式为 ( )* 4 图状态转换图练习 : 考虑以下 NFA 通过怎样的转换接受串 c: NFA 接受输入串 α, 当且仅当转换图中存在从开始状态到终态的一条路径, 使得该路径中每条边的输入字依次连接成为 α 4 c c 可接受的输入串为任意包含连续两个或连续两个的符号串 Σ={,} Ynlng Zho 5

6 Compler8 LexclScnnng 定理 : 对于每个 NFA M 存在一个 DFA M'' 使得 L(M)=L(M') 证明 : 假定 NFA M = (S, Σ, δ, S, F), 对 M 的状态转换图进行改变, 构造等价的 DFA M'' 第一步 : 由 NFA M 构造等价的 NFA M' 第二步 : 由 NFA M' 构造等价的 DFA M'' 引进新的初态结点 x 和终态结点 y, 从 x 到 S 中每一状态结点连一条输入符号为的箭弧 ; 从 F 中每一状态结点连一条输入符号为的箭弧 ; 重复进行如下图所示转换直到每条箭弧上的输入符号串的长度不大于为止 α β α β j j α β k j α β j α* j k j α 将最终得到的 NFA 记为 M, 且有 L(M)=L(M ) _CLOSURE(I) 的定义 DFA 是 NFA 的特例, 可以采用子集法将 NFA 确定化假定 I 是 NFA M 的状态集的一个子集, 我们定义 _CLOSURE(I) 为 : 若 s I, 则 s _CLOSURE(I); 若 s I, 那么从 s 出发经过任意条弧而能到达的任何状态 s 都属于 _CLOSURE(I) 状态集 _CLOSURE(I) 称为 I 的 _ 闭包 x _CLOSURE({x})={x,,,} _CLOSURE({})={,,} _CLOSURE({})={,y} _CLOSURE({4})={4,y} _CLOSURE({x,,})={x,,,,,y} _CLOSURE({,,4})={,,4,y} 4 y I 定义给定 NFA M = (S, Σ, δ, S, F), 假定 I S,, 定义 I =_CLOSURE(J), 其中, J 是那些可从 I 中的某一状态结点出发经过一条弧而到达的状态结点的全体 x y {4} {} =_CLOSURE({})={,y} =_CLOSURE({4})= {4,y} {x,} =_CLOSURE(φ)= φ {,} =_CLOSURE({4})= {4,y} 4 将 NFA 确定化为 DFA 的子集法表的初始化构造处理表的一行重复处理设 Σ={,, k } 先构造一张表, 该表的行数待定, 列数为 k+ 列然后置该表的首行首列为 _CLOSURE({x}) 如果某一行的第一列的状态子集已经确定, 例如记为 I, 那么, 依次求出 I,I,, I k 同时看它们是否已在表的第一列出现过, 将未出现的填入到后面空行的第一列重复上述过程, 直至所有第列和第 k+ 列的子集均已在第一列上出现了为止 Ynlng Zho 6

7 Compler8 LexclScnnng 确定化 : 由 NFA M' 构造 DFA M'' x 4 I I I {x,,} {,,} {,,} {,,} {,,,4,5,y} {,,} {,,} {,,} {,,,4,5,y} {,,,4,5,y} {,,,4,5,y} {,,,5,y} {,,,5,y} {,,,5,y} {,,,4,5,y} {,,,4,5,y} {,,,5,y} {,,,4,5,y} {,,,5,y} {,,,4,5,y} {,,,5,y} 5 y I=_CLOSURE ({x}) 为 {x,,} 从状态 I 出发经过一条弧而能到达的状态全体 J 为 {,}, 而 _CLOSURE(J )={,,} 从而 I ={,,} 把子集作为状态并命名 I {x,,} {,,} {,,} {,,,4,5,y} {,,,5,y} 4 {,,,4,5,y} 5 {,,,5,y} 6 该 DFA 接受的输入串同样为 ( )*( ) ( )* I {,,} {,,,4,5,y} {,,} {,,,4,5,y} {,,,5,y} 6 {,,,5,y} 6 {,,,4,5,y} I {,,} {,,} {,,,4,5,y} 5 {,,,5,y} 4 {,,,4,5,y} 5 {,,,4,5,y} 5 {,,,5,y} 到此我们将这个表作为状态转换矩阵就得到 DFA M = (S, Σ, δ, s, F ) 其中 δ 为通过子集算法构造的状态转换矩阵所表示的映射, 而 s 为 _CLOSURE({x}) 命名后的状态名例 : 考虑如下 NFA 转换为 DFA letter letter {} {,,4,5,7,} φ {,,4,5,7,} {4,5,6,7,9,} {4,5,7,8,9,} {4,5,6,7,9,} {4,5,6,7,9,} {4,5,7,8,9,} {4,5,7,8,9,} {4,5,6,7,9,} {4,5,7,8,9,} letter {4,5,6,7,9,} letter {} {,,4,5,7,} letter letter {4,5,7,8,9,} 4 型文法与有限自动机的等价性 Chomsky 文法 G = ( Vt, VN, S, P ) 型文法 ( αβ, ) P 有 : 型文法型文法型文法正规文法 α β, α ( V V ) ( V ), β ( V V ) * * * N T T N T G 的任何产生式 α β 均满足 α <= β, 仅 S 除外, 且 β 中不含 S; * A β, A VN, β ( VN VT) * A αb, 或, A α, 且 A, B V, α ( V ) N T 型文法有两种表示形式 : 左线性文法和右线性文法 G = ( V, V, S, P ) T N A Bα, 或, A α, 且 A, B V, α V A αb, 或, A α, 且 A, B V, α V N N * T * T Ynlng Zho 7

8 Compler8 LexclScnnng 定理 : 对于每一个右线性文法 G, 都存在一个有限自动机 M, 使得 L(M) = L(G) 对于型文法 ( 正规文法 ) G 和有限自动机 M, 如果 L(G)=L(M), 则称 G 和 M 是等价的关于型文法和有限自动机的等价性, 有以下结论 : 对于每一个型文法 G, 都存在一个有限自动机 M, 使得 L(M) = L(G) 对于每一个有限自动机 M, 都存在一个型文法 G, 使得 L(M) = L(G) G = ( V, V, S, P ) 作如下构造得到的 M 为一个 NFA T N 令 M=( V U{ f}, V, δ, S,{ f}), 其中 f V, 且 δ如下 : ) 若对于某个 A V 及 V U{} 有 ( A, ) P 则令 ( δ A, ) = f; N T N ) 对任意 A V 及 V U{}, 设 P 中左端为 A右端第一符号为的产生式形如 A A A A 则令 ( δ A, ) = { A,, A} N N k T T k 定理 : 对于每一个有限自动机 M, 都存在一个右线性文法 G, 使得 L(M) = L(G) DFA M = ( S, Σ, δ, s, F) 做如下构造得到右线性文法 G DFA M=({A,B,C,D},{,},δ, A, {B}) G L =({,},{B,C,D,f}, f, P) B f C B C C B D C D D B ) 若 s F, 令 G = ( Σ, S, s, P ), 其中 P构造如下 : 对于任何 Σ及 A, B S, 若有 δ ( A, ) = B, 则 : ) 当 B F时, 令 A B ) 当 B F时, 令 A B ) s F, 因为 δ( s, ) = s, 所以 L( M), 从而 LG ( ) = LM ( ) { } 因此令 G' = ( Σ, SU{ s }, s, P U{( s, s ),( s, )}) 其中 s S 最后令 G=G' ' ' ' ' ' A C D B, A f G R =({,},{A,B,C,D}, A, P) A B D B D C C B D D D D D, NFA M'=({A,B,C,D,f},{,},δ, A, {f}) C 5 正规式与有限自动机的等价性关于正规式和有限自动机的等价性, 有以下结论 : 对于任何有限自动机 M, 都存在一个正规式 R, 使得 L(R) = L(G) 对于任何正规式 R, 都存在一个有限自动机 M, 使得 L(M) = L(R) 令每条弧以正规式作标记 ; 在图中加进 X 和 Y 两个结点, 从 X 用弧连接到 M 的所有初态结点, 从 M 的所有终态结点用弧分别连接到 Y; 将 X 作为初态,Y 作为终态构成新的一个 NFA M' 且 L(M)=L(M') 采用图示替换规则消去 M 中所有结点, 只剩下 X 和 Y, 则 X 到 Y 的弧的标记就是 R α k β j αβ j 定理 : 对于任何有限自动机 M, 都存在一个正规式 R, 使得 L(R) = L(M) 对 Σ 上的 NFA M 构造 Σ 上的正规式 R 使得 L(R)=L(M) α β β k α γ j j α β j βα*γ j Ynlng Zho 8

9 Compler8 LexclScnnng 对 Σ 上的正规式 r 构造 Σ 上的 NFA M 使得 L(M)=L(r) 续对 Σ 上的正规式 R 构造 Σ 上的 NFA M 使得 L(M)=L(R) r= r=r q r q q f r=φ q q f q M f q f r= q q f q M f L(r)=L(M ) L(M ) 续对 Σ 上的正规式 R 构造 Σ 上的 NFA M 使得 L(M)=L(R) r=r r 续对 Σ 上的正规式 R 构造 Σ 上的 NFA M 使得 L(M)=L(R) r=r * q M f q M f q q M f f L(r)=L(M ) L(M ) L(r)=L(M ) * 结论正规文法正规式确定有限自动机非确定有限自动机在接受语言能力上等价 6 确定有限自动机的化简一个确定有限自动机 M 的化简是指 : 寻找一个状态数比 M 少的 DFA M, 使得 L(M)=L(M ) 一个 DFA M 的状态最少化过程旨在将 M 的状态集分割成一些不相交的子集, 使得任何不同的两个子集中的状态都是可区别的, 而同一子集中的任何两个状态都是等价的最后, 在每个子集中选出一个代表, 同时消去其它等价状态 M 的两个状态 s 和 t 是等价的 : 当且仅当分别从二者出发至终态均能够读出同一字 M 的两个状态 s 和 t 是可区别的 : 当且仅当二者不等价 Ynlng Zho 9

10 Compler8 LexclScnnng 状态集 S 的划分步骤 : () 基本划分 { 终结状态集, 其他状态集 } 是一个划分 Π ; () 对于当前划分 Π={I (),,I (m) }, m>=; 进行如下处理 : 对于每个 Σ, 若 I () 分别与 Π 的 n 个不同块相交不为空 ( 其中 <=n<=m), 则将 I () 划分成 n 个不相交的子集, 使得每个子集 J 的 J 包含于 Π 的某个块然后将每个 J 加入 Π 并删除 I () () 重复上述过程 () 直至 Π 不再变化为止 Π= { X, L, X }, X X, = Lm, m X X = ϕ, U X = X m m j = 例 : 考虑下图所示 DFA 的化简 : Step: Π={{,4,5,6}, {,,}} Step: Π={{,4,5,6}, {}, {,}} Step:Π={{,4,5,6}, {}, {},{}} 把 M 的状态分为组 : 终态组 {,4,5,6}, 非终态组 {,,} 考察 {,4,5,6}, 由于 {,4,5,6} 和 {,4,5,6} 都包含于 {,4,5,6}, 所以它不能再划分考察 {,,}, 由于 {,,} ={,}, 分别与 {,4,5,6 和 {,,} 相交不空, 故进行划分因 δ(,)= 且 δ(,)=δ(,)=, 故将 {,,} 分成 {}, {,} 考察 {,}, 由于 {,} = {,5}, 与上述块中的块相交不为空, 故划分成 {},{} 当前 Π 不能再划分, 最后重新命名状态, 其中新状态代表 {,4,5,6}, 把原来射入,4,5,6 的弧改为射入新状态词法分析器的设计与实现 Introducton to Lexcl Anlyzer Introducton Desgn Issues Exmples Genertors Error Messge Error Processng Chrcter Strem (Grmmr) Lexcl Anlyzer (Automt) Token Strem Input Strem Output Strem Chrcter Strem Source Code Progrmmng Lnguges Scrpt Lnguges (HTML,XML) Others Grmmr Alphet Producton rules Token Strem Ctegory Vlue Symol Tle Other Tles Lexcl Anlyzer Genertor Error Lexcl Messge Anlyzer Lexcl Anlyzer Genertor (Regexp) Ynlng Zho

11 Compler8 LexclScnnng Desgn Issues on Lexcl Anlyzer 单词符号的分类及表示 Token 的表示全体一种一字一种词法分析器与语法分析器的关系单独一遍作为语法分析器的子程序输入缓冲区的控制预处理超前搜索 DFA 的表示 Mtrx Cse 语句关键字 : 由程序语言定义的具有固定意义的标识符也可称为保留字或基本字例如 :Pscl 中的 egn,end,f 等它是确定的标识符 : 用来表示各种名字, 如变量名数组名过程名等它是不限的常数 : 常数的类型一般有整型实型布尔型文字型等它是不限的运算符 : 如 + - * / 等它是确定的界符 : 如逗号分号括号 /*,*/ 等它是确定的 Token 的表示用二元组表示 : < 种别, 属性值 > 种别 : 采用整数表示常量表示或者特殊标识符表示属性值 : 对于常数采用内部表示 ; 标识符 ( 变量常量数组名函数名等 ) 采用符号表入口, 等等种别的确定 : 主要取决于实现上的方便, 例如 : 标识符一般同归为一种常数宜按类型 ( 整实布尔 ) 分关键字可以将其全体视为一种, 也可一字一种运算符可采用一符一种, 但也可把具有一定共性的视为一种界符则一般采用一符一种若是一符一种分种, 单词自身值就不需要了例 :FORTRAN 编译程序的词法分析器在扫描输入串 IF (5 EQ M) GOTO 后, 它输出的单词符号流是 : 逻辑 IF (4,_) 左括号 (,_) 整常数 (, 5 的二进制表示 ) 等号 (6,_) 标识符 (6, M ) 右括号 (6,_) GOTO (,_) 标号 (9, 的二进制表示 ) 例 :C++ 代码段 :whle ( >= j ) --; 经词法分析器处理以后, 它将被转换为如下的单词符号流 : ( whle,_ ) ( (,_ ) ( d, 指向的符号表指针 ) ( >=,_ ) ( d, 指向 j 的符号表指针 ) ( ),_ ) ( d, 指向的符号表指针 ) ( - -,_ ) ( ;,_ ) 词法分析器与语法分析器的关系源程序语法分析器词法分析器词法分析器 Tokens 语法分析器 Token 作为不同的遍源程序作为子程序调用 Ynlng Zho

12 Compler8 LexclScnnng 预处理子程序输入输入缓冲区扫描缓冲区列表预处理部分 : 把 scnner 作为一个独立的子程序 ; 词法分析器的任务为输出单词符号超前搜索问题若识别输入语句 IF (5EQM) GOTO, 若缓冲区情况如下所示 : IF (5EQM) GO 起点指示器搜索指示器扫描器单词符号语法分析器扫描器输入缓冲区图词法分析器结构若识别输入语句 IF (5EQM) GOTO, 若缓冲区情况如下所示 : 扫描缓冲区的结构 : 缓冲区大小 : 个字符采用两个指示器 : 起点指示器搜索指示器两个互补区 TO IF (5EQM) GO 起点指示器搜索指示器 TO IF (5EQM) GO 输入缓冲区搜索指示器个字符起点指示器两个互补输入缓冲区例 : 关键字识别中的超前搜索 : 例如 : 在标准 FORTRAN 中 DO99K =, IF(5EQM)I = DO99K = 4 IF(5) = 55 其中的 DO IF 为关键字其中的 DO IF 为标识符的一部分标识符的识别多数语言的标识符是字母开头的字母 / 数字串, 而且在程序中标识符的出现后都跟着算符或界符因此, 不难识别常数的识别对于某些语言的常数的识别也需要使用超前搜索算符和界符的识别对于诸如 C++ 语言中的 , 这种复合成的算符, 需要超前搜索 Ynlng Zho

13 Compler8 LexclScnnng 4 状态转换图的实现 ch 字符变量, 存放最新读进的源程序字符 TOKEN 字符数组, 存放构成单词的字符串 GETCHAR 过程, 将下一输入字符读入 ch, 搜索指示器前移一个字符 4 GETBC 过程, 检查 ch 中的字符是否为空白若是, 则调用 GETCHAR 直至 CHAR 中进入一个非空白字符 5 CONCAT 过程, 把 ch 中的字符连接到 TOKEN 之后 6 IsLetter 布尔函数过程, 它们分别判断 ch 中的字符是数字或是字母, IsDgt 从而给出真假值 TRUE FALSE 7 Reserve 整型函数过程, 用 TOKEN 中的字符串查保留字表, 若是一个保留字则给予编码, 否则回送值 ( 假定不是保留字的编码 ) 8 Retrct 过程, 把搜索指示器回调一个字节, 把 ch 中的字符置为空白 9 InsertID 插入符号表, 返回入口 ( 指针 ) InsertConst 插入常数表, 返回入口 ( 指针 ) Exmples C 程序 ( 作为子程序 ) whtechr letter * { } ( ) ;, e letter 其它其它 d 非 * / f * 4 E e E e 9 c + - 其它其它非 * 非 / * g h 6 7 n 8 非非 * * / 符号表 struct entry { struct entry *next; /* lnked lst mplementton */ chr *nme; /* the user-defned nme of the dentfer */ nt type; /* ts type */ nt lockno; /* scopng nformton */ nt ddr; /* ddress ssgned y code genertor */ }; z /* constnts for our scnner */ #defne LPAREN '(' /* sngle chr tokens */ #defne RPAREN ')' #defne COMMA ',' #defne GREATER > #defne LESS < #defne ASSIGN = #defne WHILE 57 /* reserved words */ #defne PRINT 58 #defne RETURN 59 #defne IF 6 #defne VARIABLE 68 /* other tokens */ #defne INTEGER 69 #defne TEXT 7 #defne EOF 7 /* end of fle */ #defne UNKNOWN 7 /* don't recognze */ /* some glols */ nt ch; /* next chr */ nt ntvl; /* nteger lexeme */ chr textvl[55]; /* text strng lexeme */ vod nt() { /* set up lookup tle for reserved words */ crete_reserved_tle(); nsert_reserved(while, "WHILE") nsert_reserved(print, "PRINT") nsert_reserved(return, "RETURN") /* get the frst chrcter */ ch = getchr(); } Ynlng Zho

$Compler8 LexclScnnng nt scnner(){ swtch(ch){ cse ' ': /* whte spce */ cse '\n': cse '\t': whle (sspce(ch = getchr())); /* get rd of the whte */ return scnner(); cse '/': /* check for comment or$

14 Compler8 LexclScnnng nt scnner(){ swtch(ch){ cse ' ': /* whte spce */ cse '\n': cse '\t': whle (sspce(ch = getchr())); /* get rd of the whte */ return scnner(); cse '/': /* check for comment or DIVIDE opertor */ ch = getchr(); f (ch!= '/') return DIVIDE; /* code to skp over comment */ cse '(': cse ')': cse ',': /* nd ny other sngle chr tokens */ ntvl = ch; ch = getchr(); return ntvl; cse 'A': /*ssume reserved words re cps, vrles lower cse*/ cse 'B': cse 'C': /* reserved words */ textvl[] = ch; for ( = ; supper(ch = getchr()); textvl[++] = ch) ; textvl[++] = \ ; return lookup_reserved(textvl); cse '': cse '': cse 'c': /* vrles */ textvl[] = ch; for ( = ; slower(ch = getchr()); textvl[++] = ch); textvl[++] = \ ; f (lookup_symt(textvl) == UNKNOWN) dd_symt(textvl); return VARIABLE; cse '': cse '': /* nteger */ ntvl = ch - ''; /* convert to numer */ whle (s(ch = getchr()) ntvl = ntvl * + ch - ''; return INTEGER; cse EOF: return EOF; defult: ntvl = ch; ch = getchr(); return UNKNOWN; } } 4 词法分析器的自动产生 Lex 源程序 Lexl lexyyc 输入流 Lex 编译器 C 编译器 out lexyyc out Token 流 < 程序 > =< 程序首部 >;< 分程序 > < 程序首部 > =progrm< 标识符 > < 分程序 > =< 复合语句 > < 复合语句 > =egn< 语句序列 >end < 语句序列 > =< 语句 >{;< 语句 >} < 语句 > =< 赋值语句 > < 复合语句 > < 条件语句 > lex 与 ycc( 第二版 ) 作者 : John R Levne,Tony Mson,Doug Brown 著杨作梅, 张旭东, 等译出版 : 年月书号 : 页数 : 9 定价 : 45 元 < 赋值语句 > =< 标识符 >:=< 表达式 > < 条件语句 > =f < 布尔表达式 > then < 语句 > else < 语句 > < 表达式 > =< 项 >{(+ -)< 项 >} < 项 > =< 因式 >{(* /)< 因式 >} < 因式 > =< 标识符 > < 无正负号常量 > ( < 表达式 > ) < 布尔表达式 > =< 表达式 >< 关系运算符 >< 表达式 > < 关系运算符 > = = < <= > >= <> < 标识符 > =< 字母 >{< 字母 > < 数字 >} < 无正负号常量 > =< 数字 >{< 数字 >}[< 数字 >{< 数字 >}] < 字母 > = c d e f g u v w x y z < 数字 > = 输入以 # 为结束符 Ynlng Zho 4

15 Compler8 LexclScnnng Lex 程序结构 A-Z, -9, -z - 构成了部分模式的字符和数字匹配任意字符, 除了 \n 用来指定范围例如 :A-Z 指从 A 到 Z 之间的所有字符 [ ] 一个字符集合匹配括号内的任意字符如果第一个字符是 ^ 那么它表示否定模式例如 : [C] 匹配,, 和 C 中的任何一个声明 %% 翻译规则 %% 辅助过程变量常量和正规定义正规式 { 动作 } 正规式 { 动作 } * +? $ { } \ ^ 匹配个或者多个上述的模式匹配个或者多个上述模式匹配个或个上述模式作为模式的最后一个字符匹配一行的结尾指出一个模式可能出现的次数例如 : A{,} 表示 A 可能出现次或次用来转义元字符同样用来覆盖字符在此表中定义的特殊意义, 只取字符的本意否定表达式间的逻辑或 "< 一些符号 >" 字符的字面含义元字符具有 / 向前匹配如果在匹配的模版中的 / 后跟有后续表达式, 只匹配模版中 / 前的部分如 : 如果输入 A, 那么在模版 A/ 中的 A 是匹配的 ( ) 将一系列常规表达式分组 %{ 常量定义 %} delm [ \t\n] ws {delm}+ letter [A-Z-z] [-9] d {letter}({letter} {})* numer {}+(\{}+)?(E[+\-]?{}+)? %% {ws} {} f then else {d} {return(if);} {return(then);} {return(else);} {yylvl=nstll_d();return(id);} {yylvl=nstll_num();return(number);} {numer} < {yylvl=lt;return(relop);} %% nstll_d() { 单词装入符号表并返回指针 ; } 上机实验 A 见 ftp 上的编译原理专题实验目录, 根据给定的 C 语言的文法, 采用 Lex 或者编写程序构造词法分析器上机时间第四周第五周 : 计算机 4,4,4, 44 安排在同一时间由班级负责同学到计算机系实验中心登记, 定了以后通知辅导老师实验部分以当时上机情况和提交的报告进行评分, 占本课程成绩 % 实验题目 ftp 上的编译原理专题实验目录内容 : ftp 759 用户名和密码均为 prllel 实验 A: 构造词法分析器, 采用 Lex 生成, 或者编程实现实验 B: 构造语法分析器, 采用 Ycc 生成, 或者编程实现实验 C: 产生中间代码, 具体内容另给实验 I: 借助 Lex 和 Ycc 进行词法语法分析实验一 lex 与 ycc 的使用 doc 实验 II: 用 C 或 Jv 编写词法分析器实验二词法分析器 doc 实验 III: 用 C 或 Jv 编写语法分析器实验三语法分析 doc C 语法 progrm { vr-declrton fun-declrton } vr-declrton nt ID {, ID } fun-declrton ( nt vod ) ID ( prms ) compoundstmt prms nt ID {, nt ID } vod empty compound-stmt { { vr-declrton } { sttement } } sttement expresson-stmt compound-stmt f-stmt whle-stmt return-stmt expresson-stmt [ expresson ] ; Ynlng Zho 5

16 Compler8 LexclScnnng C 语法 ( 续 ) f-stmt f( expresson ) sttement [ else sttement ] whle-stmt whle( expresson ) sttement return-stmt return [ expresson ] ; expresson ID = expresson smple-expresson smple-expresson ddtve-expresson [ relop ddtve-expresson ] C 语法 ( 续 ) relop < <= > >= ==!= ddtve-expresson term [( + - ) term ] term fctor [ ( * / ) fctor ] fctor ( expresson ) ID cll NUM cll ID( rgs ) rgs expresson {, expresson } empty ID ; 参见 C 语言标识符定义 NUM ; 参见 C 语言数的定义报告提交实验报告应该按照格式填写报告中写明程序设计思想及简要设计方案, 代码简要描述, 运行测试情况, 体会一共提交个报告, 分别对应实验 A,B,C 提交方式 : 作为附件 eml 到指定邮箱, 若天内得到回复确认表示提交成功指定邮箱为 :ynlng_zho@6com 附件命名格式 : 姓名学号班级实验 Xrr 附件 (rr) 中含有 : 源程序测试数据结运行结果报告其他辅助文件 ( 若有 ) 报告提交例子赵银亮 9544 软件 9 实验 Arr 该文件中包括 : 实验报告, 代码, 数据等 Ynlng Zho 6

Microsoft PowerPoint - 3-LexicalScanning12.ppt [兼容模式]

Microsoft PowerPoint - 3-LexicalScanning12.ppt [兼容模式] CompilerLexiclScnning Yinling Zho ( 赵银亮 ) Xi n Jiotong Universiy 本章内容第三章词法分析有限自动机词法分析器的设计与实现词法分析器的自动生成 Yinling Zho Xi n Jiotong University. 有限自动机确定有限自动机非确定有限自动机正规文法与确定自动有限自动机的等价性正规式与确定自动有限自动机的等价性确定自动有限自动机的化简..