可直接打开网站的网页,一个软件开发团队需要哪些人,教你免费申请个人平台,怎么找上海网站建设一、词法分析程序的设计
1、词法分析程序的输出
在识别出下一个单词同时验证其词法正确性之后#xff0c;词法分析程序将结果以单词符号的形式发送至语法分析程序以回应其请求。
单词符号一般分下列5类#xff1a;
关键字#xff1a;如#xff1a;begin、end、if、whil…一、词法分析程序的设计
1、词法分析程序的输出
在识别出下一个单词同时验证其词法正确性之后词法分析程序将结果以单词符号的形式发送至语法分析程序以回应其请求。
单词符号一般分下列5类
关键字如begin、end、if、while和var。标识符如常量名、变量名和过程名常数各种类型的常数如25、TRUE和ABC等。运算符如、*、、等。界符如逗号、分号、括号等、
2、词法分析程序中如何识别单词
常见的可以用于词法规则描述的工具有状态转换图、扩展巴克斯范式EBNF、有限状态自动机、正规表达式以及正规文法等。
二、单词的形式化描述工具
1、正规文法
正规文法也称3型文法G{VNVTSP}其P中的每一条规则都有下述形式A→aB或A→a其中A,BVNa。正规文法描述的是VT上的正规集。
2、正规式
设字母表Σ{|.*}。 1ε和Ø都是Σ上的一个正规式它们所表示的正规集为{ε}和Ø。 2任何a∈Σa是Σ上的一个正规式它所表示的正规集为{a}。 3假设e1和e2是Σ上的正规式它们所表示的正规集分别为L(e1)和L(e2)则 ·e1|e2是Σ上的正规式它所表示的正规集为L(e1|e2) L(e1)∪L(e2)。 ·e1e2是Σ上的正规式它所表示的正规集为L(e1e2) L(e1)L(e2)。 ·(e1)*是Σ上的正规式它所表示的正规集为L((e1)*) L(e1)*。 4仅由有限次上述3个步骤而定义的表达式才是Σ上的正规式仅由这些正规式所表示的符号串的集合才是Σ上的正规集。 例子令Σ{ab}则有 1正规式a表示的正规集为{a}。 2正规式a|b表示的正规集为{ab}。 3正规式ab表示的正规集为{ab}。 4正规式(a|b)(a|b)表示的正规集为{aaabbabb}。 5正规式a*表示的正规集为{εaaaaaa…}。 6正规式(a|b)*表示的正规集为{εabaaabbabbaaa…}。 7正规式a|a*b表示的正规集为包含字符串a和包含0个或多个a后跟随一个b的所有的符号串。 若两个正规式e1和e2所表示的正规集相同则说e1和e2等价写作e1e2。 设rst为正规式正规式服从的代数规律如下 1r|ss|r 2r|(s|r)(r|s)|t 3(rs)tr(st) 4r(s|t)rs|rt(s|t)rsr|tr 5rrrr 6r|rr
3、正规式转正规文法
字母表Σ上的正规式r到正规文法G-(VNVTSP)的转换方法为 1选择一个非终结符S生成类似产生式的形式Sr并将S定为G放识别符号。为表述方便将Sr称作正规式产生式因为在右部中含有“.”“*”或“|”等正规式符号不是V中的符号。 2若x和y都是正规式对形如Axy的正规式产生式重写成AxBBy两个产生式其中B是新选择的非终结符。 例对于ra(a|d)* 首先形成Sa(a|d)*然后形成SaA和A(a|d)*在形成 SaA A(a|d)B A B{a|d)B B 4、正规文法转正规式
文法产生式正规式规则1AxB ByAxy规则2AxA|yAx*y规则3Ax AyAx|y 例如文法G[S]如下 SaA Sa AaA AdA Aa Ad 解首先有 SaA|a A(aA|dA)|(a|d) 再将A的正规式变换成A(a|d)A|(a|d)又变换为A(a|d)*(a|d)再代入S得 Sa(a|d)*(a|d)|a 再利用正规式的代数变换可依此得到 Sa(a|d)*(a|d)| Sa(a|d)* 三、有穷自动机
1、确定的有穷自动机
1.定义一个确定的有限自动机(DFA) M是一个五元组M(KΣfSZ)其中 1K是一个有限集它的每一个元素称为一个状态。 2Σ是一个有穷字母表它的每个元素称为一个输入字符。 3f是一个转换函数是KΣK上的映像。 4S∈K是唯一的初态。 5Z⊆SF是一个终态集可以为空。 2.DFA的状态转移矩阵 DFA可用一个二维矩阵表示矩阵的行表示状态列表示输入字符矩阵元素表示δ(sa)的值。 3.DFA是状态转换图 若设DFA M含有m个状态和n个输入字符则这个图含有m个状态结点每个结点至多有n条箭弧射出与其它的状态结点相连接每个箭弧用Σ中的一个不同输入字符作为标记。整张图含有唯一的初态结点和若干终态结点。 例子设DFA M({0,1,2,3}{a,b}δ{3})其中δ定义为 δ(0a)1δ(0b)2δ(1a)3δ(1b)2δ(2a)1δ(2b)3δ(3a)3δ(3b)3。 4.DFA的识别字符串 1对Σ上的任何符号串w∈Σ*若存在一条从初态结点到某一终态结点的通路且该通路上所有弧的标记符连接成的字符串等于w则称w可被DFA M所识别。若M的初态结点同时又是终态结点则空字符串ε被M所识别。 2DFA与语言的关系DFA M所能识别的符号串的全体记为L(M)。
2、不确定的有穷自动机
1.定义一个不确定有限自动机(NFA) M是一个五元组M(SΣδS0F)其中 1S是一个有限集它的每一个元素称为一个状态。 2Σ是一个有穷字母表它的每个元素称为一个输入字符。 3δ是一个从S×Σ到S的子集的映射即δS×Σ*→2S 4S0⊆SS0是一个非空初态集。 5F ⊆SF是一个终态集可以为空。 2.NFA的状态转换图 若设NFA M含有n个状态和m个输入符号则这个图含有n个状态结点每个结点可射出若干箭弧与其它的状态结点相连接。对于w∈{ε}∪Σ若δ(q0a){q1q2…qk}(k≥0)则从q0出发分别到q1q2…qk的k条弧弧上均标记为a。整张图含有唯一的初态结点和若干终态结点。 3.NFA识别字符串 1对Σ*上的任何符号串若存在一条从某一初态结点到某一终态结点的通路且该通路上所有弧的标记符号依次连接成的字符串等于w则称w可被NFA M所识别。若M的某些结点同时又是终态结点则空字符串ε被M所识别。 2NFA与语言的关系Σ*中所有可被NFA M所识别的符号串的集合记为L(M)。 4.DFA和NFA的关系 1DFA是NFA的特例NFA是DFA概念的推广。 2NFA能识别的语言都能被一个DFA识别。 3DFA相对NFA的识别程序更容易实现。
3、NFA转换为等价的DFA
1.NFA的确定化对任给的NFA M。都能相应地构造一个DFA M‘使得L(M’)L(M)。 2.NFA的子集法DFA的每一个状态代表NFA状态集合的某个子集构造的DFA使用它的状态去记录NFA读入输入符号之后可能到达的所有状态的集合。 3.状态集合I的a弧转换表示为ε-Closure(I)定义为一个状态集是状态集I中的一组任何状态S经任意条ε弧而能够到达的状态的集合。 4.状态集合I的a弧转换表示为move(Ia)定义为状态集合J其中J是所有那些可以从I中的某一状态经过一条a弧而到达的状态的全体。
4、确定有限自动机的化简
1.化简的目的去除多余或等价的状态降低存储代价提高句子识别的效率。 2.有限自动机的多余状态从初态出发任何可识别的输入串也不能到达的状态。 3.状态等价在两个状态s和t等价的条件是以下两个 一致性条件--状态s和t必须同时为可接受状态或不可接受状态。 蔓延性条件--对于所有输入符号状态s和状态t必须转换到等价的状态里。 4.DFA的化简分割法 i将DFA M的状态集S划分为两个子集终态集F和非终态集F ̃形成初始划分Π。 ii对Π建立新的划分Πnew。对Π中的每个状态子集G进行如下变换 a把G划分成新的子集使G的两个状态s和t属于同一个子集当且仅当对任何输入符号a状态s和t转换到的状态都属于Π的同一子集。 b用G划分出的所有新子集替换G形成新的划分Πnew。 iii若Πnew和Π相等则执行第iv步否则令ΠΠnew重复第ii步。 iv划分结束后对划分中的每个状态子集选出一个状态作为代表删去其它一切等价的状态并把射向其它状态的箭弧改为射向这个代表的状态。
四、正规式与有限自动机之间的等价性
1.由正规式构造有限自动机 消去结点的规则如下
