《语法分析（5）》由会员分享，可在线阅读，更多相关《语法分析（5）（38页珍藏版）》请在金锄头文库上搜索。
1、1,Pushdown Automata 下推自动机,2,Pushdown Automata,正则语言 正则文法 有限状态自动机 上下文无关语言 上下文无关文法 下推自动机(PA),3,Pushdown Automata,正则语言 正则文法 NFA = DFA 上下文无关语言 上下文无关文法 NPA DPA 仅定义了上下文无关语言一个真子集 大部分程序设计语言可以用DPA描述 DPA can model parsers 如果没有特殊说明，本节课中提及的PA一般都是非确定PA,(NPA DPA),4,PA的直观思考,下推自动机可以看作是一个具有栈操作能力的-NFA PA = -NFA + 栈(及其
2、操作) PA迁移取决于: 当前状态 当前输入符号 (可以为 ) 当前栈顶符号,5,PA的直观思考,在每次迁移中，PA做以下动作： 改变状态 将栈顶符号替换为一个长度可以为0符号序列 长度为零时 = “pop” 出栈 长度大于0时 = sequence of “pushes”,6,PA 的形式化定义,A PA is defined by a seven tuple (Q, , , , q0, Z0, F): Q, a finite set of states , an input alphabet , a stack alphabet , a transition function q0 in
3、Q, a start state Z0 in , a start stack symbol F Q, a set of final states,与有限状态自动机的区别是什么？,栈！,7,常用符号,a, b, 输入符号. But sometimes we allow as a possible value. , X, Y, Z 栈符号 , w, x, y, z 输入符号串 , , 栈符号串,8,迁移函数,表达为： (q, a, Z)=(p1, 1), (p2, 2), . 函数有3个参数: q, a state in Q a, an input, which is either a symbo
4、l in or Z, A stack symbol in 函数(q, a, Z) 的结果为 a set of actions of the form (p, ) p is a state; is a string of stack symbols. 为什么是a set of actions?,9,迁移函数,(q, a, Z)=(p1, 1), (p2, 2), . 直观含义： 当前，状态为q, 栈顶符号为Z, 遇到了输入符号a, 该下推自动机迁移到状态pi, 从输入符号串首去掉符号a, 栈顶符号Z退出, i进入 (pi, i) in (p1, 1), (p2, 2), . 如果是确定的, (q
5、, a, Z)=(p, ),10,迁移函数,pi,a1,a2,.,i, Z1, .,(q, a, Z)=(p1, 1), (p2, 2), .,q,a, a1,a2,.,Z,Z1,11,PA的图形表示,是否可以像FSA那样，可以有一个PA的图形表示？,0,Z0/0,q1,1,Z0/1,0,0/e,1,1/e,q3,e,Z0/e,q2,1,Z0/1,12,Example,设计一个下推自动机接收语言 0n1n | n 1. 状态: q = 初始状态. 到目前为止，只看到了0 p = weve seen at least one 1 and may now proceed only if the i
6、nputs are 1s. f = final state Accept.,13,Example,栈符号: Z0 = start symbol 标记栈底 so we know when we have counted the same number of 1s as 0s. X = marker used to count the number of 0s seen on the input.,14,Example,迁移： (q, 0, Z0) = (q, XZ0). (q, 0, X) = (q, XX). These two rules cause one X to be pushed i
7、nto the stack for each 0 read from the input. (q, 1, X) = (p, ). When we see a 1, go to state p and pop one X. (p, 1, X) = (p, ). Pop one X per 1. (p, , Z0) = (f, Z0). Accept at bottom.,15,Actions of the Example PA,q,0 0 0 1 1 1,Z0,16,Actions of the Example PA,q,0 0 1 1 1,X Z0,17,Actions of the Exam
8、ple PA,q,0 1 1 1,X X Z0,18,Actions of the Example PA,q,1 1 1,X X X Z0,19,Actions of the Example PA,p,1 1,X X Z0,20,Actions of the Example PA,p,1,X Z0,21,Actions of the Example PA,p,Z0,22,Actions of the Example PA,f,Z0,23,PA的瞬时描述,瞬时描述(instantaneous description, ID) is a 3-triple (q, w, ) 表达了PA当前的情况:
9、the current state, q. the remaining input, w. stack contents, (top at the left),24,The “Goes-To” Relation,Let I and J be two different IDs IJ: ID I can become ID J in one move of the PA Formally： (q, aw, X)(p, w, ) for any w and , if (q, a, X) contains (p, ). Extend to *, meaning “zero or more moves
10、” .,25,Example: Goes-To,The previous PA of 0n1n | n 1 We 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?,26,Answer,(q, 0001111, Z0)(q,
11、001111, XZ0) (q, 01111, XXZ0)(q, 1111, XXXZ0) (p, 111, XXZ0)(p, 11, XZ0) (p, 1, Z0)(f, 1, Z0) Note the last ID has no move. 0001111 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),27,Language of a PA,The commo
12、n way to define the language of a PA is by final state. If 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 .,28,Language of a PA (2),Another language defined by the same PA is by empty stack. If P is a PA, then N(P) is the set of strings w such
13、that (q0, w, Z0) * (q, , ) for any state q. (q0, w, Z0) * (f, , ) (q0, w, Z0) * (q, , ),29,Equivalence of Language Definitions,For any L(P), there exists a PA P such that N(P)=L(P). For any N(P), there exists a PA P such that L(P)=N(P).,30,Proof: L(P) - N(P) 直观思考,用P模拟 P. Idea: 当P接收时，将P的栈置空. 特殊情况：栈空且
14、没有接收的情况 用一个特殊的栈底标记来表示栈空且没有接收的情况,31,Proof: L(P) - N(P),P 包含P的所有状态、符号、以及迁移，另外: 栈符号X0 (used to identify the stack bottom against accidental emptying) New start state s and “erase” state e. (s, , X0) = (q0, Z0X0). Get P started. (f, , X) = (e, , X) = (e, ) for any final state f of P and any stack symbol
15、 X.,32,Proof: L(P) - N(P),P,q0,e,s,start, X0/Z0X0, X/, X/, X/,33,Proof: N(P) - L(P) 直观思考,P” simulates P. P” 通过一个特殊的栈底标志来表示P的栈为空的情况 If so, P” accepts.,34,Proof: N(P) - L(P),P 包含P的所有状态、符号、以及迁移，另外: Stack symbol X0, used to guard the stack bottom. New start state s and final state f. (s, , X0) = (q0, Z0X0). Get P started. (q, , X0) = (f, ) for any state q of P.,35,Proof: N(P) - L(P),P,q0,f,s,start, X0/Z0X0, X0/, X0/, X/, X0/,36,Aside: FA and PDA Notations,We represented moves of a FA by an extended , which did not m
