三语法分析da.ppt

Pushdown Automata下推自动机2Pushdown Automatau正则语言w正则文法w有限状态自动机u上下文无关语言w上下文无关文法w下推自动机(PA)3Pushdown Automatau正则语言w正则文法wNFA=DFAu上下文无关语言w上下文无关文法wNPAuDPA 仅定义了上下文无关语言一个真子集w大部分程序设计语言可以用DPA描述wDPA can model parsersu如果没有特殊说明，本节课中提及的PA一般都是非确定PA(NPA DPA)4PA的直观思考u下推自动机可以看作是一个具有栈操作能力的-NFAwPA=-NFA+栈(及其操作)uPA迁移取决于:1.当前状态2.当前输入符号(可以为)3.当前栈顶符号5PA的直观思考u在每次迁移中，PA做以下动作：1.改变状态2.将栈顶符号替换为一个长度可以为0符号序列u长度为零时=“pop”出栈u长度大于0时=sequence of“pushes”6PA 的形式化定义uA PA is defined by a seven tuple(Q,q0,Z0,F):1.Q,a finite set of states 2.,an input alphabet 3.,a stack alphabet 4.,a transition function 5.q0 in Q,a start state 6.Z0 in,a start stack symbol 7.F Q,a set of final states 与有限状态自动机与有限状态自动机的区别是什么？的区别是什么？栈！栈！7常用符号ua,b,输入符号.wBut sometimes we allow as a possible value.u,X,Y,Z 栈符号u,w,x,y,z 输入符号串u,栈符号串8迁移函数u表达为：(q,a,Z)=(p1,1),(p2,2),.u函数有3个参数:1.q,a state in Q2.a,an input,which is either a symbol in or 3.Z,A stack symbol in u函数(q,a,Z)的结果为 a set of actions of the form(p,)wp is a state;is a string of stack symbols.w为什么是a set of actions?9迁移函数 (q,a,Z)=(p1,1),(p2,2),.u直观含义：w当前，状态为q,栈顶符号为Z,w遇到了输入符号a,w该下推自动机迁移到状态pi,w从输入符号串首去掉符号a,w栈顶符号Z退出,wi进入w(pi,i)in(p1,1),(p2,2),.w如果是确定的,(q,a,Z)=(p,)10迁移函数pia1,a2,.i,Z1,.(q,a,Z)=(p1,1),(p2,2),.qa,a1,a2,.Z,Z1,.11PA的图形表示u是否可以像FSA那样，可以有一个PA的图形表示？0,Z0/0q11,Z0/10,0/e1,1/eq3e,Z0/eq21,Z0/112Exampleu设计一个下推自动机接收语言 0n1n|n 1.u状态:wq=初始状态.到目前为止，只看到了0wp=weve seen at least one 1 and may now proceed only if the inputs are 1s.wf=final stateAccept.13Exampleu栈符号:wZ0=start symbol标记栈底so we know when we have counted the same number of 1s as 0s.wX=markerused to count the number of 0s seen on the input.14Exampleu迁移：w(q,0,Z0)=(q,XZ0).w(q,0,X)=(q,XX).wThese two rules cause one X to be pushed into the stack for each 0 read from the input.w(q,1,X)=(p,).When we see a 1,go to state p and pop one X.w(p,1,X)=(p,).Pop one X per 1.w(p,Z0)=(f,Z0).Accept at bottom.15Actions of the Example PAq 0 0 0 1 1 1Z016Actions of the Example PAq 0 0 1 1 1XZ017Actions of the Example PAq 0 1 1 1XXZ018Actions of the Example PAq1 1 1XXXZ019Actions of the Example PAp1 1XXZ020Actions of the Example PAp1XZ0THANK YOUSUCCESS2024/5/8 周三21可编辑22Actions of the Example PApZ023Actions of the Example PAfZ024PA的瞬时描述u瞬时描述(instantaneous description,ID)is a 3-triple(q,w,)u表达了PA当前的情况:1.the current state,q.2.the remaining input,w.3.stack contents,(top at the left)25The“Goes-To”RelationuLet I and J be two different IDsuIJ:ID I can become ID J in one move of the PAuFormally：(q,aw,X)(p,w,)for any w and,if(q,a,X)contains(p,).uExtend to*,meaning“zero or more moves”.26Example:Goes-TouThe previous PA of 0n1n|n 1uWe can describe the sequence of moves by:(q,000111,Z0)(q,00111,XZ0)(q,0111,XXZ0)(q,111,XXXZ0)(p,11,XXZ0)(p,1,XZ0)(p,Z0)(f,Z0)(q,000111,Z0)*(f,Z0)What would happen on input 0001111?27Answeru(q,0001111,Z0)(q,001111,XZ0)(q,01111,XXZ0)(q,1111,XXXZ0)(p,111,XXZ0)(p,11,XZ0)(p,1,Z0)(f,1,Z0)uNote the last ID has no move.u0001111 is not accepted,because the input is not completely consumed.Legal because a PA can use input even if input remains.(p,Z0)=(f,Z0)28Language of a PAuThe common way to define the language of a PA is by final state.uIf P is a PA,then L(P)is the set of strings w such that(q0,w,Z0)*(f,)for final state f and any.29Language of a PA (2)uAnother language defined by the same PA is by empty stack.uIf P is a PA,then N(P)is the set of strings w such that(q0,w,Z0)*(q,)for any state q.(q0,w,Z0)*(f,)(q0,w,Z0)*(q,)30Equivalence of Language Definitions1.For any L(P),there exists a PA P such that N(P)=L(P).2.For any N(P),there exists a PA P such that L(P)=N(P).31Proof:L(P)-N(P)直观思考u用P模拟 P.uIdea:w当P接收时，将P的栈置空.w特殊情况：栈空且没有接收的情况w用一个特殊的栈底标记来表示栈空且没有接收的情况32Proof:L(P)-N(P)uP 包含P的所有状态、符号、以及迁移，另外:1.栈符号X0(used to identify the stack bottom against accidental emptying)2.New start state s and“erase”state e.3.(s,X0)=(q0,Z0X0).Get P started.4.(f,X)=(e,X)=(e,)for any final state f of P and any stack symbol X.33Proof:L(P)-N(P)Pq0esstart,X0/Z0X0,X/,X/,X/34Proof:N(P)-L(P)直观思考uP”simulates P.uP”通过一个特殊的栈底标志来表示P的栈为空的情况uIf so,P”accepts.35Proof:N(P)-L(P)uP 包含P的所有状态、符号、以及迁移，另外:1.Stack symbol X0,used to guard the stack bottom.2.New start state s and final state f.3.(s,X0)=(q0,Z0X0).Get P started.4.(q,X0)=(f,)for any state q of P.36ProofN(P)-L(P)Pq0fsstart,X0/Z0X0,X0/,X0/,X/,X0/37Aside:FA and PDA NotationsuWe represented moves of a FA by an extended,which did not mention the input yet to be read.uWe could have chosen a similar notation for PDAs,where the FA state is replaced by a state-stack combination,like the pictures just shown.38FA and PDA Notations (2)uSimilarly,we could have chosen a FA notation with IDs.wJust drop the stack component.w(q,w)=p iff(q,wx)*(p,x).uWhy do not adopt ID for FA?wCan you answer it?39Deterministic PAsuDPA 的表达能力严格的大于正则语言uDPA的表达能力严格的小于上下文无关语言uDPA表达的语言并不恰好等于CFL的非固有歧义的子集uMore about DPAs,please read the book!THANK YOUSUCCESS2024/5/8 周三40可编辑