PPT《编译原理》

3、正规文法和正规式的等价性 一个正规语言可以由正规文法定义,也可以用正规式定义.对于任意一个正规文法,存在一个定义同一语言的正规式.对每一个正规式,存在一个生成同一语言的正规文法.即正规式?正规文法 ? 正规式?正规文法: (把正规式转换为正规文法所要求的规则形式)将Σ上的一个正规式r转换为一个正规文法G=(VN,VT,P,S)的规则:令VT=Σ,对正规式r,选择一个非终结符S生成S→r,S为G的开始符号.不断拆分r直到符合正规文法要求的规则形式: ? 若x,y都是正规式,对形如A→xy的产生式,写成A→xB,B→y.其中B? VN ? 对形如A→x*y的产生式,重写为:A→x A A→y B为新的非终结符,B? VN对形如A→x|y的产生式,重写为: A→x A→y 不断利用上述规则进行变换即可. 例:将R=a(a|d)*变换成正规文法.令S是文法开始符号. 例:将R=a(a|d)*变换成正规文法.令S是文法开始符号. 解: S→ a(a|d)* S→aAA→(a|d)* A→(a|d) AA→ ? ? 最后得到: S→aAA→aAA→dAA→ ? ???正规文法?正规式:将一个正规文法转换为正规式的规则:转换规则:? A→xB,B→y 正规式为: A=xy ? A→xA|y 正规式为: A=x*y A→x,A→y 正规式为: A=x|y 不断收缩产生式规则,直到剩下一个开始符号定义的正规式 例:文法G[S]: S→ aAS→ aA→ aAA→ dAA→ aA→ d 转换为正规式 S→ aAS→ aA→ aAA→ dAA→ aA→ d S=aA|a A=aA|dA A=a|d A=(aA|dA)|(a|d) ?A=(a|d)A|(a|d) ?A=(a|d)*(a|d) 根据上述规则3A→x,A→y推出A=x|y 将它化为正规文法变成A→ (a|d)A|(a|d) 再根据上述规则2转换x=y= (a|d) 将A代入S=aA|a得到如下: S=a( (a|d)*(a|d)) |a =a(a|d)+|a =a((a|d)+|?)= a(a|d)*

二、有穷自动机 有穷自动机:是一种自动识别装置,能正确识别正规集;

是词法分析程序的工具和方法,可自动识别(且是正确识别)正规集. 分为 确定的有穷自动机(DFA)不确定的有穷自动机(NFA)

(一) 确定的有穷自动机DFA 自动识别装置 一个确定的有穷自动机M是一个五元组: M=(K,Σ,f,S,Z),其中:① K是一个有穷集,每个元素表示一个状态;

②Σ是一个有穷字母表,每个元素是一个输入字符;

③ f是转换函数,是在K*Σ→K上的映象,如: f(Ki ,a)= Kj (Ki, Kj?K);

④ S是初态,S?K;

⑤ Z?K,是终态集. 含义:当前状态为Ki,输入字符a,转换为Kj状态

1、用状态

图表示: 方法如下: 初始态用 ? 或 - 表示;

终态点用 + 或 ? 表示;

若f(Ki ,a)= Kj ,则从状态点Ki 到Kj画弧,标记为a. 例:DFA的M=({S,U,V,Q},{a,b},f,S,{Q})其中f为: f(S,a)=U, f(S,b)=V, f(U,a)=Qf(U,b)=V, f(V,a)=U, f(V,b)=Qf(Q,a)=Q, f(Q,b)=Q 画出状态图 状态图如下: a,b - + a a a b b b S U V Q

2、用矩阵表示DFA :方法:? 行表示状态 ? 列表示输入字符 ? 元素表示相应状态行和输入字符下的新状态. a,b ? 标明初态,默认第一行是初态. 终态行在表右端标1,非终态标0 上例矩阵表示如下: Q Q Q Q U V V Q U V U S b a 字符 状态

0001 例: - + b a S Z a,b 表示:f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z Z Z Z Z Z S b a

0 1 写成正规式是: (a|b)(a|b)*

3、接受(识别)的概念: 自动识别单词 对于Σ*中的任何字符串t,若存在一条初态到某一终态的路,且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受........