Lecture 3: Lexical Analysis (Part II) Xiaoyuan Xie 谢晓园 xxie@whu.edu.cn 计算机学院 E301
回顾 编译器 把高级语言翻译成目标(机器)语言 几步 如何定义语言 语言定义在字母表上L( ) 字母表 定义了语言中允许出现的全部符号(有 穷集合) L( )规定了词法(三型文法) 语法(二型文法) 语义
回顾 如何定义文法 词法 语法都是这样定义的 文法(G, Grammar): 四元组G = (VN,VT, S, P ) 其中 VN 一个非空有限的非终结符号集合 它的每个元素称为非终结符 一般用大写字母表 示 它是可以被取代的符号 VT 一个非空有限的终结符号集合 它的每个元素称为终结符 一般用小写字母表示, 是 一个语言不可再分的基本符号 --- 来自于 S 一个特殊的非终结符号 称为文法的开始符号或识别符号 S VN 开始符号S必须 至少在某个产生式的左部出现一次 P 产生式的有限集合 所谓的产生式 也称为产生规则或简称为规则 是按照一定格式 书写的定义语法范畴的文法规则 G1 ({S},{a,b}, S,P) 设V是文法G的符号集 则有 V = VN VT VN VT = (0) S as (左线性 递归) (1) S a b (一定要有递归出口)
回顾 词法分析 词素 e.g. valu#e 当前语言对词法的规定 回忆一下 C语言 对变量名的规定 对函数名的规定 Comply with valu#e = initial + rate * 60 RE 产生式P e.g. id的re为letter(letter digit)* RE等价于正规文法 三型 用L(RE)表示 正规文法的能力足以描述词法规定
回顾 熟悉字符串的操作符 括号(r) 不改变r表示 主要是用于确定运算优先关系 或运算 表示 或 关系 连接运算 表示连接 经常省略 如r s也可表示为rs *运算 r*表示对r所描述的文本进行0到若干次循环连接 [ ] 任选符号: [ab] 等价于 (a b)
回顾 定义RE( 为字母表) 原子正则表达式(atomic regular expressions) 和 是 上的正则表达式 它们所表示的正则集分别为L(ε)={ε} L( )={}. 对任何a,a 是 上的正则表达式 它所表示的正则集L(a)={a}; 归纳步骤 若r和s都是 上的正则表达式 它们所表示的正则集分别为L(r)和L(s),则 (r)也是 上的正则表达式--- 在这里是操作符 r s也是 上的正则表达式 r s也是 上的正则表达式 r*也是 上的正则表达式 识别RE- 怎么自己写一个RE 有限次使用上述3条规则构成的表达式称为 上的正则表达式 --- 上述操作可以满足三型文法 (证明 http://tutorialspoint.howtolib.com/automata_theory/regular_sets.htm)
回顾 练习 设字母表 ={0 1},试写正则表达式 所有 上定义的串 [01]*, 或 (0 1)* 表示二进制数 特点 以0开头后面不接任何数 以1开头后面可接任何数 0 1[10]*, 或 0 1(0 1)* 能被2整除的二进制数 特点 以0结尾 0 1(0 1)*0
回顾 练习 为自然语言构造RE All strings of lowercase letters that contain the five vowels in order. S -> other* a (other a)* e (other e)* i (other i)* o (other o)* u (other u)* other -> [bcdfghjklmnpqrstvwxyz] 自己写一个RE 给定RE 怎么描述出它定义的字符串?
回顾 练习 下列正则表达式定义了什么语言 a(a b)*a (( a)b*)* 由a, b组成的 并由a开头和结尾的字符串 ( b* ab*)* (b* ab*)* 空串或所有由a, b组成的字符串 ((( a)b)*)* (( a)b)* ( b ab)* (b ab)* b/ab b/ab b/ab b/ab 空串 或 任意个b组成的字符串 两个b之间隔着0-1个a
回顾 练习 下列正则表达式定义了什么语言 b*(ab*ab*)* 空串 或 由偶数个a和任意个b组成的字符串 c*a(a c)*b(a b c)* c*b(b c)* a(a b c)* 由a,b,c组成 至少包含一个a和一个b的串 给定RE 描述出它定义的字符串
回顾 产生式 词法分析只考虑三型文法, 而三型文法一般用 RE 表示就足够了, 一般不需要用与 RE 等价的产生式来表示 暂时不做回顾, 到上下文无关文法时再回顾
回顾 词法分析 如何实现匹配过程 --- FM 状态控制器 读头 输出 输入带 1 0 1 1 0
回顾 FA 转换图 v.s. 转换矩阵 DFA M=( {S0, S1, S2, S3}, {a,b}, f, S0, {S3}), 其中 f 定义为 f (S0, a )=S1 f (S2, a )=S1 S1 a f (S0, b )=S2 f (S2, b )= S3 f (S1, a )= S3 f (S3, a )= S3 a b S0 a a,b S 3 f (S1, b )= S2 f (S3, b )= S3 a b 0+ 1 2 1 3 2 2 1 3 3-3 3 b S2 b
回顾 词法分析 FA接受的字符串 输出为终结状态 状态控制器 读头 输入带 1 0 1 1 0 # FA 和 RE 的关系
回顾 L(RE) FA 例1中自动机 0 a 1 a b 2 a 接受的语言是L(aba(a b)*) 3 b 例2中自动机 接受的语言是L((ab*da ca d)c*) b a S0 d c S2 S1 d a S3 c
回顾 L(RE) FA 自动机的设计是一个创造过程 没有固定的算法和过程 语法设计也如此 例1 = {a,b},构造自动机识别由所有奇数个a和奇数个b组成的字符串 b S奇a,偶b S奇a,奇b a a b b S偶a,奇b a S偶a,偶b b a 关键 不需要记住所看到的整个字符 串 只需记住至此所看到的a和b 的个数是奇数还是偶数
回顾 L(RE) FA 例2 设计有限自动机M 识别{0,1}上的语言 L = {x000y x,y {0 1}*} 分析 该语言的特点是每个串都包含连续3个0的子串 自动机的任务就是识别/检查 000 的子串 0 1 0 0 0 q0 q2 q3 1 q1 1 1
回顾 L(RE) FA 例3 设计有限自动机M 识别{0,1,2}上的语言 每个字符串代表的数字能整除3 分析: (1) 一个十进制数除以3 余数只能是0,1,2 (2) 被3整除的十进制数的特点 十进制数的所有位数字的和能整除3 0 0 0 1 q0 1 q1 2 2 1 2 q2
回顾 L(RE) FA 例5 使用DFA定义程序设计语言的标识符 x, Xy, x123, xyz 接受 23x, 12_x _x 拒绝 letter q0 letter q1 digit
回顾 L(RE) FA 例6 使用DFA定义程序设计语言的保留字 {if, else, while, for} w f i f e l s i h o e l r e
回顾 FA: DFA v.s. NFA DFA NFA 初始状态 一个初始状态 初始状态集合 边 不允许 允许 (S, a) S or {S1,, Sn} or 实现 容易 有不确定性
回顾 FA: DFA v.s. NFA DFA/NFA接受的字符串(可以等价) 输出为终结状态 状态控制器 读头 输入带 1 0 1 1 0 # 意味着读头不动 但是状态依旧发生转换
回顾 NFA DFA 子集法 输入 一个NFA N = {, SS, SS0,, TS} 输出 一个接受同样语言的DFA D = {, SS,S0,, TS } 方法 为D构造一个转换表Dtran D的每个状态是一个NFA状态集合 构造 Dtran使得D可以模拟N在遇到一个给定输入串时可能执行的所有动作 消除不确定性 合并所有 转换的状态 合并所有相同字符转换的状态 Tip: 把N中的状态集合 看做 D中的一个状态
回顾 NFA DFA 子集法 一些基本操作 核心思想 找出当N读入某个输入串之后可能位于的所有状态集合
回顾 NFA DFA 子集法 对于NFA N中的给定状态集合T和符号 a, Move(T, a) = {s 对于状态集T 中的一个状态si, 如果A中存在一条从si到s的a转换边} S a S2 SS S1 S3 a a S S Move({S1,S2,S3},a) = {S, S, S }
回顾 由NFA构造DFA (子集法) 构造Dtran 我们需要找出当N读入了某个输入串之后可能位于的所 有状态集合 首先 在读入第一个输入符号之前 N可以位于集合εclosure(s0)中的任何状态上 其中s0是N的开始状态 下面进行归纳定义 假定N在读入输入串x之后可以位于集合T中的状态上 如果下一 个输入符号是a 那么N可以立即移动到move(T,a)中的任何状态 然而 N可以在读入a后再执行几个ε转换 因此N在读入a之后可 位于ε-closure(move(T,a))中的任何状态上
回顾 由NFA构造DFA (子集法)例1 r=(a b)*abb的nfa to DFA 首先 NFA的开始状态A是ε-closure(0) 即A={0 1 2 4 7} NFA的输入字母表是{a,b} Dtran[A,a]=ε-closure(move(A,a))=ε-closure({3,8})={1,2,3,4,6,7,8}, 令B=Dtran[A,a] Dtran[A,b]=ε-closure(move(A,b))=ε-closure({5})={1,2,4,6,7}, 令C=Dtran[A,b] Dtran[B,a]=ε-closure(move(B,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B Dtran[B,b]=ε-closure(move(B,b))=ε-closure({5,9})={1,2,4,5,6,7,9}, 令D=Dtran[B,b]
回顾 由NFA构造DFA (子集法) 例1 r=(a b)*abb的nfa to DFA Dtran[C,a]=ε-closure(move(C,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B Dtran[C,b]=ε-closure(move(C,b))=ε-closure({5})={1,2,4,6,7}=C Dtran[D,a]=ε-closure(move(D,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B Dtran[D,b]=ε-closure(move(D,b))=ε-closure({5,10})={1,2,4,5,6,7,10}, 令E=Dtran[D,b] Dtran[E,a]=ε-closure(move(E,a))=ε-closure({3,8})={1,2,3,4,6,7,8}=B Dtran[E,b]=ε-closure(move(E,b))=ε-closure({5})={1,2,4,6,7}=C
回顾 由 NFA 构造 DFA ( 子集法 ) 例 1:r=(a b)*abb 的 NFA to DFA
回顾 作业 教材 P78:3.3.2, 3.3.5 ( 有一定难度 ) 教材 P86:3.4.1,3.4.2 ( 基础题,not covered) 教材 P96:3.6.3,3.6.4,3.6.5 ( 基础题 ) 教材 P105:3.7.1( 基础题 )
Transformation
对 上的每一个正则表达R 存在一个 上的非确定有限自 动机N 使得 L(N) = L(R) N可以通过子集法得到与之等价的确定有限自动机D NFA 子集法 DFA 正则表达式
从RE生成FA 用来模拟RE的实现 方法一 RE NFA DFA 最小DFA (***) 方法二 RE DFA 最小DFA (*) 方法三 RE NFA, 然后直接模拟 (模拟算法见教材P99 算法 3.22)
从RE生成FA 用来模拟RE的实现 方法一 RE NFA DFA 最小DFA 方法二 RE DFA 最小DFA 方法三 RE NFA 然后直接模拟 模拟算法见教材P99 算 法3.22
从RE生成FA 用来模拟RE的实现 方法一 由RE构造NFA (Thompson算法) 输入 字母表 上的一个正则表达式r 输出 一个接受L(r) 的NFA N 基本规则 又是递归 r由sub-r递归构成 N(r)也由N(sub-r)递归构成 对于字母表中的原子表达式a, 构造下面的NFA 对于表达式 构造右边的NFA
从RE生成FA 用来模拟RE的实现 方法一 由RE构造NFA (Thompson算法) 归纳规则 假设正则表达式s和t的NFA分别为N(s)和N(t) 对于r = s t 构造如下NFA 这里i和f都是新状态 分别是N(r)的开始状态和接受 状态 从i到N(s)和N(t)的开始状态各有一个 转换 从N(s)和N(t)到接受状态f也各 有一个 转换
从RE生成FA 用来模拟RE的实现 方法一 由RE构造NFA (Thompson算法) 归纳规则 假设正则表达式s和t的NFA分别为N(s)和N(t) 对于r=st 构造下面的NFA N(s)的开始状态变成了N(r)的开始状态 N(t)的接受 状态成为N(r)的唯一接受状态 N(s)的接受状态和N(t)的开始状态合并为一个状态 合并后的状态拥有原来进入和离开合并前的两个状态的全部转换
从RE生成FA 用来模拟RE的实现 方法一 由RE构造NFA (Thompson算法) 归纳规则 假设正则表达式s和t的NFA分别为N(s)和N(t) 对于r=s* 构造下面的NFA i和f是两个新状态 分别是N(r)的开始状态和唯一接受状态 要从i 到达f 我们可以沿着新引入的标号为 的路径前进 该路径对应于L(s)的一个串 我们也可以达 到N(s)的开始状态 然后经过该NFA 零次或多次从它的接受状态回到它的开始状态并重复上述 过程
由RE构造NFA (Thompson算法) 为r=(a b)*abb构造nfa 为表达式r1 = a r2=b构造nfa 为表达式r3 = r1 r2构造nfa
由RE构造NFA (Thompson算法) 为r=(a b)*abb构造nfa 为表达式r5 = r3*构造nfa 为表达式r6 = a构造nfa
由RE构造NFA (Thompson算法) 为r=(a b)*abb构造nfa 为表达式r7 = r5r6构造nfa
由RE构造NFA (Thompson算法) 为r=(a b)*abb构造nfa 同理 最终得到 (a b)*abb 的NFA
从RE生成FA 用来模拟RE的实现 方法一 生成NFA后 继续使用子集法构造与NFA等价的DFA 然后最小化DFA to be discussed later
从RE生成FA 用来模拟RE的实现 方法一 RE NFA DFA 最小DFA 方法二 RE DFA 最小DFA 方法三 RE NFA 然后直接模拟 模拟算法见教材P99 算 法3.22
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 首先先构造语法分析树 并标记位置 (a b)*abb (a b)*abb# 增广正则表达式 (r)#
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA NFA的重要状态 NFA状态有一个标号非 的离开转换 则称该状态为重要状 态(important state) --- 子集法在计算move(T, a)的时候 只使用了重要状态 计算四个函数nullalbe, firstpos, lastpos, followpos
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA nullable(n) returns true or false 表示以n为根结点推导出的句子集合是否包 括空串 是 则nullable(n)=true 否 则nullable(n)=false firstpos(n)定义了以结点n为根推导出的某个句子的第一个符号的位置集合 lastpos(n)定义了以结点n为根推导出的某个句子的最后一个符号的位置集合--规则在本质上和计算firstpos的规则相同 但是在针对cat结点的规则中 左右 子树的角色要对调
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 小例子 nullable(n) = false firstpos(n)={1,2,3} lastpos(n) = {3}
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 计算nullalbe, firstpos, lastpos
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA firstpos, lastpos for (a b)*abb (a b)*abb#
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA followpos(p)定义了一个和位置p相关的 抽象语法树中某些位置的集合 positions q is in followpos(p) iff 存在L((r)#) 中的某个串x=a1a2 an 是的我 们在解释为什么x属于L((r)#) 可以将x中某个ai和抽象语法树中的位置p匹配 并将位置ai+1和位置q匹配 语法树上 pq 两个位置的值 就是 aiai+1 aiai+1是re可以接受字符串的一个子串
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 计算followpos 只有下面两种情况会使得RE中一个位置跟在另一个位置之后 当n是一个cat结点 且其左右子树分别为c1 c2 那么对于lastpos(c1)中的所有 位置i firstpos(c2)中的所有位置都在followpos(i)中 当n是一个star结点 且i是lastpos(n)中的一个位置 那么firstpos(n)中的所有位置 都在followpos(i)中
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA followpos(p)
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA followpos(p)
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 首先 DFA的开始状态定义为根节点n0的 firstpos(n0)={1,2,3} 标记为A
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA 从DFA的开始状态 A=firstpos(n0)={1,2,3},起 we have Dtran[A,a]=followpos(1) U followpos(3)= {1,2,3,4}=B Dtran[A,b]=followpos(2)={1,2,3}=A
从RE生成FA 用来模拟RE的实现 方法二 由RE直接构造DFA Dtran[B,a]=followpos(1) U followpos(3)=b Dtran[B,b]=followpos(2) U followpos(4)={1,2,3,5}=c
DFA的最小化 NFA转换成的DFA 有时候会有一些等价状态 这些等价状态会 使分析效率降低 因此应合并 1 a d 2 5 b b 3 6 1 c 4 c 7 a d 2 b 3 c 4
最小DFA定义 如果DFA M 没有无关状态 也没有等价状态 则称M为最小(最 简)自动机 无关状态 从开始状态没有到S的通路 或S到任意终止状态无通路 a a 称S为M的无关状态 0 0 2 2 b 1 b 1 等价状态 对DFA中的两个状态S1和S2 如果将它们看作是初始状 态 所接受的符号串相同 则定义S1和S2是等价的
所以自动机最小化就是两个问题 一个是合并可以合并的等价状态 比较麻烦 一个是删去无用的无关状态 直接删除
两个状态S1和S2等价的条件 一致性条件 S1和S2同时为可接受状态或不可接受状态 蔓延性条件 S1和S2对所有输入符号必须都要转换到等价状态里 DFA终止状态和非终止状态是不等价的 DFA终止状态和非终止状态是不等价的
DFA化简的两种方式 合并等价状态; (状态合并法) 分离不等价状态;(状态分离法)
状态分离法化简DFA 输入 一个DFA D 其状态集合为S 输入字母表为 开始状态为s0 接受状态为F 输出 一个DFA D' 它和D接受同样的语言 且状态数最少 Notation: Π 即DFA状态的一个划分{S1, S2, }和S-{S1, S2, } 方法 1)首先构造包含两个组F和S-F的初始划分Π 这两个组分别是D的接受状态组和非接受状态组 2)用下面的构造新的分划Πnew 分割原则 分离出不等价状态
状态分离法化简DFA 方法 3)如果Πnew= Π,令Πfinal= Π并接着执行步骤 4) 否则 用Πnew替换II并重 复步骤2) 4)在分划Πfinal的每个组中选取一个状态作为该组的代表 这些代表构成了状 态最少DFA D'的状态 持续更新 直至无法继续分割为止 (即 该状态子集中的状态都为等价)
DFA D=({0,1,2,3,4,5}, {a,b}, δ, 0, {0,1}),其中δ见表 状态 a b 0 1 2 1 1 2 状态 类别 a b 0 A 1(A) 2(B) 4 1 A 1(A) 4(B) 1 3 2 B 1(A) 3(B) 3 3 2 4 0 5 3 B 3(B) 2(B) 5 5 4 4 B 0(A) 5(B) 5 B 5(B) 4(B) Step 1:根据一致性条件 A={0,1} B={2,3,4,5}
DFA D=({0,1,2,3,4,5}, {a,b}, δ, 0, {0,1}),其中δ见表 状 态 类别 a b 0 A 1(A) 2(B) 1 A 1(A) 4(B) 状态 a b 2 B 1(A) 3(B) 0 1 2 1 1 4 2 1 3 3 B 3(B) 2(B) 4 B 0(A) 5(B) 5 B 5(B) 4(B) 状 Step2: 根据蔓延性条件 态 对状态进行再分类 不可再分 类别 a b 0 A 1(A) 2(B) 1 A 1(A) 4(B) 2 B 1(A) 3(C) 3 3 C 3(C) 2(B) 3 2 4 0 5 4 B 0(A) 5(C) 5 5 4 5 C 5(C) 4(B)
DFA D=({0,1,2,3,4,5}, {a,b}, δ, 0, {0,1})最小化为 DFA D'=({A,B,C}, {a,b}, δ A {A}) 其中δ见表 状态 a b A A B B A C C C B
对r=(a b)*abb的 DFA化简 首先初始划分包括两个组{A,B,C,D},{E}, 分别是非接受状态组和接受状态组 构造Πnew时 考虑这两个组和输入符号a和b 因为组{E}只包含 一个状态 不能再被分割 所以{E}被原封不动的保留在Πnew中 对于{A,B,C,D} 是可以被分割的 因此我们必须考虑各个输入符 号的作用 在输入a上 这些状态中的每一个都转到B 因此使用 以a开头的串无法区分这些状态 但对于输入b 状态A B C都转换到{A,B,C,D}的某个成员上 而D转到另一组中的成员E上 因此在Πnew中 {A,B,C,D}被分割 成{A,B,C} {D} 现在IInew中有{A,B,C} {D} {E}
对r=(a b)*abb的 DFA化简 对于{A,B,C} 在输入b上 A和C都到达{A,B,C}中的元素 B却到达D 上 所有Πnew有{A,C},{B},{D},{E},对于{A,C}无法在分割 所有最后有{A,C},{B},{D},{E} 构造如下的DFA
状态分离法化简DFA D'的其他部分按如下步骤构建 (a)d'的开始状态是包含了d的开始状态的组的代表 (b)d'的接受状态是那些包含了d的接受状态的组的代表 (c)令s是πfinal中某个组g的代表 并令DFA D中在输入a上离开s的转换到达状态t 令r 为t所在组H的代表, 那么在D'中存在一个从s到r在输入a上的转换
例 1: {0,1,2,3} 和 {4} {0,1,3},{2} 和 {4} {0,3},{1},{2} 和 {4} 0 a 1 a 2 b a b b 3 4 b b a a 0 1 2 b b b 4 b
例2 {0 1 2 3} {4} {0 2} {1 3} {4} 1 a 0 b b a 4 a b 2 {0} {2} {1 3} {4} a 3 b 1 a 0 b a b b 4 a 2 a b a b
RE DFA(NFA) L(RE)三者等价 Regular Expression Finite Automata 证明RE等价 可以证明它们对应的最小DFA同构 Regular Grammar
作业 教材 P105:3.7.3(4) 教材 P109:3.8.1
附加思考题 教材 P118:3.9.3 ( 用算法 3.36 构造 ),3.9.4
Lex 3.8 词法分析器的开发
3.8 词法分析器的开发 LEX Lexical Analyzer Generator 即词法分析器的生成器 是由贝尔实验 室于1972年在UNIX操作系统上首次开发的 最新版本是FLEX(Fast Lexical Analyzer Genrator) 工作原理 LEX通过对Lex源文件(.l文件)的扫描 经过宏替换将规则部分的正 则表达式转换成与之等价的DFA 并产生DFA的状态转换矩阵 利用该矩阵 和Lex源文件中的C代码一起产生一个名为yylex()的词法分析函数 并将 yylex()函数拷贝到输出文件lex.yy.c中.l RE-like definition Lex/Flex lex.yy.c ( yylex() )
3.8 词法分析器的开发 Lex 源程序 *.l Lex lex.yy.c lex.yy.c C 编译器 a.out 输入流 a.out Token 序列 用 Lex 创建一个词法分析器的过程
3.8 词法分析器的开发 Lex源文件 声明部分 %% 转换规则 %% 辅助函数 动作中需要使用的函数 int Change() { /*将字符串形式的常数 转换成整数形式*/ } %{ 常量 %{ ID,NUM,IF,ADD }% }% 正则定义 letter [A-Za-z] digit [0-9] id {letter}({letter} {digit})* num {digit}+ 模式 {动作} 模式是一个正则表达式或 者正则定义 动作通常是C语言代码 表示匹配该表达式后应该 执行的代码 if {return (IF);} + {return(add);} {id} {yylval = strcpy(yytext, yylength); return(id) } {num} {yylval = Change(); return(num);} yylval token的值 yytext token的lexeme yyleng lexeme的长度
3.8 词法分析器的开发 Lex 例子
3.8 词法分析器的开发 冲突解决 当输入与长度不同的多个模式匹配时 Lex选择长模式进行匹配 当输入与长度相同的多个模式匹配时 Lex选择列于前面的模式进行匹配 %% program printf( %s\n,yytext);/*模式1*/ procedure printf( %s\n,yytext);/*模式2*/ [a-z][a-z0-9]* printf( %s\n,yytext);/*模式3*/ 当输入串为 programming 时 模式1 匹配 program 和模式3 programming 都匹配 但会选择匹配串长的模式3 当输入串为 program 时 因为模式1和模式3匹配的串长度相等故会选择 模式1.
3.8 词法分析器的开发 需要定义的词法组成 TOKEN 结构图 单词类别 语义信息