编译原理课件.pptxVIP

编译基础---形式语言;第一节 字母表、串、语言;连接： xy 称为x和y的连接 例：int x x=100;A+中的每一个元素即为一个语句 例： x=3.14159*r*r;第二节 文法的引例; 句子→主语谓语;第三节 文法的形式定义;二、文法的定义;P：α→β α∈V+ ，β∈ V* V=VN ∪ VT; 句子→主语谓语;再给出一个描述算术表达式的文法例子; * 句型：S= α, α ∈ V* α为句型 例：主语谓语 I am 冠词名词 ;推导的定义; 例：G[E]： E→E+T|T T→T*F|F F→(E)|a;; 通过对产生式施加不同的限制，Chomsky将文法分为四种类型：;文法的类型;文法的类型;3型文法;文法的类型;文法和语言;根据形式语言理论,文法和识别系统间有这样的关系; 2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。 3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合;第四节 正规文法与有穷自动机;第四节 正规文法与有穷自动机;L(G)={ambncp/m,n,p≥1};例1：写出产生语言L(G)={ambcn/m,n≥0}的正规文法;例2：C语言标识符的文法描述 L（G）={w/w为字母或‘-’打头的字母数字串};二、有穷自动机;二、有穷自动机 1、特点：接收离散输入，状态有穷，只需考虑当前输入和当前内部状态;３、模型;５、形式定义 确定的有穷自动机是一个五元组 M=（Q，∑ ，δ ，q0，Z）;∈ ;映射函数： δ（ q０,０)= q０ δ（ q０,１)= q１ δ（ q1,０)= q１ δ（ q1,１)= q０;三、正规表达式与有穷自动机 关系：等价、交换;映射函数： １、Ｐ： Ａ１ →aＡ2 , 则δ（ Ａ１,a)= A2 2、Ｐ： Ａ１ →a, 则δ（ Ａ１,a)= T 3、δ（ Ｔ,a)= φ 空动作;例：已知正规文法 Ｇ＝（｛A,B,C},｛a,b,c},P,S} 其中： P:A →aA A →aB B →bB B →bC C →cC C→c 试写出与其等价的ＦＡ;映射函数： δ（ A,a)= A δ（ A,a)= B δ（B,b)= B δ（B,b)= C ??（C,c)= C δ（C,c)= T;练习：Ｌ＝｛w/w是０和１的个数都为偶数的０、１串｝ 试写出能识别该语言的自动机和描述该语言的文法;第五节　上下文无关文法－－语法基础;二、自嵌套性 　　如果上下文无关文法Ｇ中存在一个终结符，且Ａ＝ α１Ａα２( α１,α２ 不空），称该上下文无关文法具有可嵌套性;三、下推自动机;２、操作 ;４、定义 ＰＤＡ是一个七元组， M=（Q,∑ ,Г,δ ,q0, Ｚ0 , Ｆ）;例：Ｌ＝｛wcwr/w ∈（a |b)＊, wr是w的反置},写出识别该语言的ＰＤＦ;映射函数： δ( q0,a,Z0)= (q1, AZ0),δ( q0,b,Z0)= (q1, BZ0) δ( q1,a,A)= (q1, AA),δ( q1,a,B)= (q1, AB) δ( q1,b,A)= (q1, BA),δ( q1,b,B)= (q1, BB) δ( q1,c,A)= (q2, A),δ( q1,c,B)= (q2, B) δ( q2,a,A)= (q2, ε),δ( q2,b,B)= (q2, ε) δ( q2, ε, Z0)= (q0, ε),δ( q0, c, Z0)= (q0, ε);句型、推导;规范推导 规范句型;语法树;语法树---句型推导的直观表示;构造语法树;构造语法树;E?E+T ?T+T ?T+T*F ?F+T*F ?F+F*F ?a+F*F ?a+F*a ?a+a*a;上下文无关文法的语法树的用处; 但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?;例：G[E]: E → i E → E+E E → E*E E → (E);二义文法;二义文法改造