3.2正规文法和状态转换图 ·正规文法定义了3型语言，常见的单词可由正 规文法定义。 ●状态转换图可用于识别3型语言；它是设计和 实现扫描器的一种有效工具，是有限自动机的 直观图示
3.2 正规文法和状态转换图 •正规文法定义了3型语言，常见的单词可由正 规文法定义。 •状态转换图可用于识别3型语言；它是设计和 实现扫描器的一种有效工具，是有限自动机的 直观图示
3.2.1由正规文法构造状态转换图 ·一般说来，凡能用正规文法描 ·程序设计语言的单词都能 述的语言，均可由某种有限状 用正规文法描述； 态算法—状态转换图进行分 ·例如，标识符可定义为 析。 →字母 ● 状态转换图由有限个结点所 →数字 组成的有向图。 →字母 ● 每个结点代表在识别分析过程 ·若把字母、数字视为终结 中扫描器所处的状态，其中含 符，则上述产生式为（左 有一个初始状态和若干个终态。 线性)正规文法 在图中，状态用圆圈表示，终 。 态用双层圆圈表示。 若我们用d表示0-9间的 。 数字，则C语言的的文法也是（右线 向边的射出状态出发，识别 性)正规文法（见P49) 字符a后，将进入箭头所指状 态（结点）
3.2.1 由正规文法构造状态转换图 • 程序设计语言的单词都能 用正规文法描述； • 例如，标识符可定义为 →字母 →数字 →字母 • 若把字母、数字视为终结 符，则上述产生式为（左 线性）正规文法 • 若我们用d表示0-9间的 数字，则C语言的的文法也是（右线 性）正规文法（见P49） • 一般说来，凡能用正规文法描 述的语言，均可由某种有限状 态算法——状态转换图进行分 析。 • 状态转换图 由有限个结点所 组成的有向图。 • 每个结点代表在识别分析过程 中扫描器所处的状态，其中 含 有一个初始状态和若干个终态。 在图中，状态用圆圈表示，终 态用双层圆圈表示。 • 状态之间可用有向边连接，其 上标记一字符a，表示从有 向边的射出状态出发，识别一 字符a后，将进入箭头所指状 态（结点）
由右线性文法构造状态转换图 设G=(VN,Vī，P,S)是一右线性文法，并设VN=K,则所要构造的状态转换 图共有K+1个状态（结点）.用Vw中的每个符号分别标记其中的K个 结点，且令G的开始符S为初态结点；余下的一个结点作为终态结点， 用F(VN)标记.我们用如下规则来连接这K+1个结点： (1)对于G中产生式A→aB,从结点A引一有向边到结点B,并用a标记这 一有向边； (2)对于G中产生式A→a,从结点A引一有向边到终态结点F,并用a标记 这一有向边； (3)对于G中产生式A→（若有的话），则将结点A设为终态 例如，P49中定义的无符号数的文法对应的~为（化简后）：
由右线性文法构造状态转换图 设G=(VN,VT,P,S)是一右线性文法,并设|VN|=K,则所要构造的状态转换 图共有K+1个状态(结点).用VN中的每个符号分别标记其中的K个 结点,且令G的开始符S为初态结点;余下的一个结点作为终态结点, 用F(VN)标记.我们用如下规则来连接这K+1个结点: (1)对于G中产生式A→aB,从结点A引一有向边到结点B,并用a标记这 一有向边; (2)对于G中产生式A→a,从结点A引一有向边到终态结点F,并用a标记 这一有向边; (3)对于G中产生式A→(若有的话),则将结点A设为终态. 例如,P49中定义的无符号数的文法对应的~为(化简后): 0 4 5 2 d 1 3 6 . d d d d . E +|- E d d
利用状态转换图识别符号串的方法 对于已给的字符串w=aa2.an,aieV1,利用~对w识别的步 骤如下： (1)从初始状态S出发，自左至右逐个扫描w的各个字符（当 前为a),此时在结点S所射出的诸矢线中，寻找标记为a 的矢线（若不存在，则表明w有语法错误），读入ā并沿矢 线所指方向前进，过渡到下一状态（设为A): (2)设当前处在A状态，所扫描的字符为a,在结点A所射出 的诸矢线中，寻找标记为a的矢线（若不存在，则表明W 有语法错误)，读入a+,并进入状态A+1; (3)重复(2)，直到w中所有字符被读完且恰好进入终态F时， 宣告整个识别结束，W可被接受. 显然，若我们从初态出发，分别沿一切可能的路径到达终态 结点，并将中径中矢线上所标记的字符依次连接起来，便 得到状态转换图所能识别的全部符号串，这些符号串组 成的集合构成了该~识别的语言
利用状态转换图识别符号串的方法 对于已给的字符串w=a1a2…an,aiVT,利用~对w 识别的步 骤如下: (1)从初始状态S出发,自左至右逐个扫描w的各个字符(当 前为a1),此时在结点S所射出的诸矢线中,寻找标记为a1 的矢线(若不存在,则表明w有语法错误),读入a1并沿矢 线所指方向前进,过渡到下一状态(设为A1). (2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所射出 的诸矢线中,寻找标记为ai+1的矢线(若不存在,则表明w 有语法错误),读入ai+1,并进入状态Ai+1; (3)重复(2),直到w中所有字符被读完且恰好进入终态F时, 宣告整个识别结束,w可被接受. 显然,若我们从初态出发,分别沿一切可能的路径到达终态 结点,并将中径中矢线上所标记的字符依次连接起来,便 得到状态转换图所能识别的全部符号串,这些符号串组 成的集合构成了该~识别的语言
状态转换图与文法雅导 用状态转换图识别符号串w的过程，就是为w建立一个 推导S→*w的过程。 在第一步（在初始状态S下，扫描到a而过渡到下一状 态A)，由状态转换图的构造规则可知，G中必有产 生式S→aA;对于识别过程的后续步骤，由状态A识别 a+1后过渡到A恰好对应了使用产生式A→a+1A,, 最后在状态Aa-识别a后到达终态F,对应了使用产生 式 A→a进行推导： ·S→aA1→a1a2A2→…→a1a2…an-1An-1 →a1a2.an
状态转换图与文法推导 • 用状态转换图识别符号串w的过程，就是为w建立一个 推导S* w的过程。 • 在第一步（在初始状态S下，扫描到a1而过渡到下一状 态A1），由状态转换图的构造规则可知，G中必有产 生式S→a1A1;对于识别过程的后续步骤，由状态Ai识别 ai+1后过渡到Ai+1恰好对应了使用产生式Ai →ai+1Ai+1,…, 最后在状态An-1识别an后到达终态F，对应了使用产生 式 A →an进行推导： • S a 1A1a 1a 2A2…… a 1a2…an-1An-1 a 1a2…an
右线性文法与状态转换图 设G是一右线性文法，M是相应的状态转换图，则从前面的 讨论可以看出如下事实： (1)在利用M对符号串w进行识别时，M中每次状态的转换都模拟了 步直接推导，即识别方法或称分析方法)是“↓”的； (2)因右线性文法只有形如A→aB、A→a的产生式，所以推导的每 一步所得句型只含一个非终结符，所以推导的规范的，每步所 得的句型也必为规范句型； (3)对于M所识别的任一符号串x,必存在G中的一个推导S→*x(即 有xL(G反之，对于L(G中任一句子y,必存在一条从初态S到终 态F的路径，此路径上各矢线的标记依次拼接起来所组成的符号串 恰为y
右线性文法与状态转换图 • 设G是一右线性文法,M是相应的状态转换图,则从前面的 讨论可以看出如下事实： (1)在利用M对符号串w进行识别时,M中每次状态的转换都模拟了一 步直接推导,即识别方法(或称分析方法) 是“”的; (2)因右线性文法只有形如A→aB、A →a的产生式，所以推导的每 一步所得句型只含一个非终结符，所以推导的规范的，每步所 得的句型也必为规范句型； (3)对于M所识别的任一符号串x,必存在G中的一个推导S * x (即 有xL(G);反之,对于L(G)中任一句子y,必存在一条从初态S到终 态F的路径,此路径上各矢线的标记依次拼接起来所组成的符号串 恰为y
虫左线性文法构造状态铸换图 设G=(VN,V,P,S)是一左线性文法，构造相应的状 态转换图的方法是： ·首先用G的V符标记M的结点，其中，开始符S对应 的结点为终态结点.另外，再引入一个新结点 R(V)作为初态.矢线的连接规则为： (1)对于G中形如Aa的产生式，引矢线：RA, 且标记为a; (2)对于G中形如A→Ba的产生式，引矢线B→A, 且标记为a
由左线性文法构造状态转换图 • 设G=(VN,VT ,P,S)是一左线性文法,构造相应的状 态转换图的方法是: • 首先用G的VN符标记M的结点,其中,开始符S对应 的结点为终态结点.另外,再引入一个新结点 R(VN)作为初态.矢线的连接规则为: (1)对于G中形如A→a 的产生式,引矢线:R→A, 且标记为a; (2)对于G中形如A→Ba 的产生式,引矢线 B→A, 且标记为a
由左线性文法构造状态转换图的例子 已给文法G=({S,U,{0,1,{SS1IU1,U→U010,S) U→0U→U0S→U1S→S1 用左线性文法构造出的状态转 换图来识别文法的句子其过程 与前面右线性文法构造的状态 步骤 当前状态余留的符号串 转换图用法一样这里不再赘述 R 00011 不过，就识别的方法而言，它却 2 0011 属于“个”分析. 3 U 011 我们以句子00011为例，给出其 4 U 11 识别的的步骤。见右表， 5 S 1 6 S (识别结束)
由左线性文法构造状态转换图的例子 已给文法G=({S,U},{0,1},{S→S1 |U1, U→U0 | 0},S) R U S U→0 0 U →U0 S →U1 0 1 S →S1 1 用左线性文法构造出的状态转 换图来识别文法的句子,其过程 与前面右线性文法构造的状态 转换图用法一样,这里不再赘述. 不过,就识别的方法而言,它却 属于“”分析. 我们以句子00011为例,给出其 识别的的步骤.见右表. 步骤 当前状态 余留的符号串 1 R 00011 2 U 0011 3 U 011 4 U 11 5 S 1 6 S (识别结束)
识别符号串与归约 由构造状态转换图的方法可知，从初 态R到下一状态A的转换，对应了形如 B→a的产生式，即将终结符a归约成 非终结符B, S 类似地，从状态B转换到状态A,对应 了形如A→Ba的产生式，即将Ba归约 为A; ● 如此下去，直到从某状态A转换到状 态S(终态)，对应了形如S→Aa的产 生式，即将Aa归约为开始符S.此时归 约成功，也恰好进入了终态，即状态转 U 换图识别了（或接受）该符号串. 前面识别00011的例子对应的归约 过程见右图 0 0 0 1
识别符号串与归约 • 由构造状态转换图的方法可知,从初 态R到下一状态A的转换,对应了形如 B→a 的产生式,即将终结符a归约成 非终结符B; • 类似地,从状态B转换到状态A,对应 了形如A→Ba的产生式,即将Ba归约 为A; • 如此下去,直到从某状态A转换到状 态S(终态),对应了形如S →Aa的产 生式,即将Aa归约为开始符S.此时归 约成功,也恰好进入了终态,即状态转 换图识别了(或接受)该符号串. • 前面识别00011的例子对应的归约 过程见右图 0 0 0 1 1 U U U S S
3.2.2状态转换图的实现-状态矩阵法 我们已看到，状态转换图可方便地用于识别单词.但是，如何让 计算机利用状态转换图来进行词法分析呢？ 一个简单实用的方法就是将图以矩阵的形式保存在内存中. 这就是所谓的状态矩阵法 ·状态矩阵以图中各个状态S,S2,,S为行，以各个输入符号 a1,a2,,am为列，组成一个nXm矩阵B,其元素Bu=BS,a指 明下一状态S和扫描器此时应完成的语义动作其含义是，在 S状态下，扫描到a符时，按序偶S,a查矩阵B,扫描器根据B 的指示，先执行相应的语义动作，再转换到下个状态S 若B为“出错”，则说明输入符号串有误，拒绝接受.扫描器 将调用出错处理程序进行处理
3.2.2 状态转换图的实现-状态矩阵法 • 我们已看到,状态转换图可方便地用于识别单词.但是,如何让 计算机利用状态转换图来进行词法分析呢? • 一个简单实用的方法就是将图以矩阵的形式保存在内存中. 这就是所谓的状态矩阵法. • 状态矩阵 以图中各个状态S1,S2,…,Sn为行,以各个输入符号 a1,a2, …,am为列,组成一个nm矩阵B,其元素Bij=B[Si,aj]指 明下一状态Sk和扫描器此时应完成的语义动作.其含义是,在 Si状态下,扫描到aj符时,按序偶(Si,aj)查矩阵B,扫描器根据Bij 的指示,先执行相应的语义动作,再转换到下个状态Sk. • 若Bij为“出错” ,则说明输入符号串有误,拒绝接受.扫描器 将调用出错处理程序进行处理