编译原理-2015lecture02-grammer第二章文法与语言

lecture lecture 号集合上的、按一定规则组成的符号串 lecture 语 句子的集程序设计语 程序的集把程序看做程序设计语言的句程程序是(程序设计)语言的句 lecture 2.1 lecture 符号串与符号串集语言实际上是一个符号串集 定语言中句子的构造规 lecture 符号串与符号串集一.字母表:有穷非空的符号集合 A={a,b,c ∑={0,1C字母，数字，界限符={AZ,az,09,+,-,*,/,<,=,>,_,&,^,~,\,:,‘,”,空格字字母表上的元素（即符号）组成符号 lecture 符号串与符号串集二.注意：顺序是重要的,ab≠ba lecture 2.1.1符号串与符号串集子符号若u=xvy，其中 (则v是u中的子符号串 a+(b-c)/d中的子符号符号串的头(前缀)与尾(后缀abc的前缀：a,ab,abc, abc的后缀：c,bc,abc, lecture 2.1.1符号串与符号串集 对任何符号串xx=x=x xn=xx…xx自身联结n次) |xn|=n lecture 符号串与符号串集三.符号串集合 枚举法1，11，111，1111省略法描述法{1i|i≥1或{x|x全由1组成注意：一定不能涉及含义如{x|x=∑10i lecture 符号串与符号串集 三.符号串集乘积：AB=xy|xA且yB对任何符号串x有

{1,0}An=AA…A(n个A乘积特例，字母表A ，x∈An,|x lecture 符号串与符号串集 三.符号串集 正闭包A+=x∈A+,则 x∈A*,则 lecture 句子分析Thegreywolfwilleatthe lecture 句子::=主语谓语 主语::=冠词形容词名词 冠词::= 形容词 谓语::=动词直接宾语 动词::=助动词动 助动词::= 动 ::= 直接宾语::=冠词名词 名词::= 名词::= lecture VT={the,grey,wolf,will,eat,VN={句子，主语谓语，冠词形容词，名词，动词，直接宾语， } 则P={句子主语谓语4S句子 lecture 句子主语谓语冠词形容词名词谓语the形容词名词谓语thegreywolf谓语thegreywolf动词直接宾语thegreywolfwilleatthe lecture 文法与语言的形式一.文法的形式定重写规则(简称规则定义：有序对 规则表示法： 或E::=E+T|T lecture 文法与语言的形式定术术表大写字母表示:A,B,C,靠后的大写字母表示:Z,X,Y小写字母表示:a,b,c靠后的小写字母表示:s,t,w

一.文法的形式定其中：VN V=VN lecture

文法与语言的形式文法的定例 G2[E]：E::=E+T F::=(E) F::=(E)|文法的四要素 lecture VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；SVN形式是A::=α，AVN，α∈(VTVN)*，开始符 lecture 2.1.2文法与语言的形式定 2.文法的定3步骤1步骤2对当前符号串中的一个非终结符号进行替换，步骤3重复步骤2 lecture 句子+thegreywolfwilleatthethegreywolfwilleatthewolfthegreygoatwilleatthewolfthegreygoatwilleatthethegreywolfwilleatthe lecture 2.<主语>::=<名词<名词<名词<介词 lecture 直接推导‹句子‹主语谓语状语‹主语‹谓语状语‹名词‹谓语›‹状语‹名词‹谓语›‹状语›=>Peter‹谓语›‹状语›Peter‹谓语‹状语›=>Peter‹动词‹状语›Peter‹动词‹状语›=>Peterswims‹状语›Peterswims‹状语=>Peterswims‹介词›‹名词›Peterswims‹介词‹名词Peterswimsin‹名词›Peterswimsin‹名词=>Peterswimsinriver lecture 直接推导时，给定找到规则U::=u，把u代替U，得到w=xuy称v直接推导到w，记为：v=> 或xUy=> lecture 推导(直接推导序列或推导序列)‹主语‹谓语›‹状语‹名词‹谓语›‹状语Peter‹谓语‹状语›Peter‹动词‹状语=>Peterswims‹状语› 词=>Peterswimsin

v=>u1=>u2=>…=>un- v 从识别符号<句子> Peter‹谓语›‹状语<句子> Peterswimsin lecture 4若有句型v=xUy，应用规则U::=uw=xuy，称vw或者xUyv=>u1=>u2=>…=>un-v=>+w其中，n广义推导：若v=>+w或v=w，则称v广义推导到w或广 lecture 句型：Z=>* xT句子：Z=>* x∈VT例Peterswimsin例riverswimsinPeter lecture <数字序列数字序列><数字 5)<数字 7)<数字 8)<数字 9)<数字10)<数字 11)<数字

<无正负号整数>=><数字序列=><数字序列><数字=><数字序列><数字><数字=><数字><数字><数字=>1<数字><数字>=>12<数字 lecture <无正负号整数=><数字序列数字><数字><数字递归地定义规则，即，U::=U使得有穷个规则可能定义潜 lecture 程序设计语言 T L （∑ TTL(G[Z])={x|Z=>*x,x∈V+TTL(G[<程序P|程序>=>*PP∈VT lecture 规则左递归：U::=U… U::=…U…规则右递归：U::=…U文法左递归:U=>+ U… 文法右递归：U=>+ …U lecture <因式因式<条件语句if(<表达式>)<语句>else<语句<语句…<语句<语句>=>+…<语句 lecture L1={aibjck|i,j,k≥1aa…aabb…bbcc… ABCABCABCSABCG1[S]: lecture AAABBaa…aabb…bbcc…AAABBSSSG1’[S]: lecture L2={aibick|i,k≥1AAASa…aabb…bcc…AAASSG2[S]: lecture L3={aibici|i≥1G3[S]:S::=abC|CB::=CDCD::=BD 2i2L4={ |i≥1G4[S]:S::=ACaB Ca::=aaC AE::=ε lecture Chomsky文法类和语言 其中U,T lecture 0型文法(短语结构文法u::=v，其中:u v1型文法(上下文有关文法CSG)xUy::=xuy，其中:U∈VN,x,y∈(VN∪VT)*,2型文法(上下文无关文法CFG)U::=xuy，其中:U∈VN,x, 3型文法(正则文法RG):左线性：U::=Va或U::=a右线性：U::=aV或U::=a，其中 U, lectureG[S]:S::=Sc|Bc B::=Bb|Ab A::=Aa|aG1=（VN,VT,P1,S1)VN={S1,A, VT={a,b,P1: B::=Bb A::=AaL(G1)={aibjck|i,j,G2=（{S2,A},{a,b,c},P2,S2)P2:S2::=S2c|AcAL(G2)={aibick|i, lecture 相应地有4类Chomsky语言0型语言(短语结构语言1型语言(上下文有关语言2型语言(上下文无关语言3型语言(正则语言注意ε规则：Uε句子：Z=>* lecture 3型语言~有穷状态 2型语言~下推 1型语言~线性界限 0型语言~图灵机 lecture U::=u，其中: goto<标号>::=goto<标识符><函数标识符>'('<实在参数表<数组变量[下标表达式表<变量>=<表达式(标识符由后跟符号确定是函数标识符、数组变量还是变量 lecture 语法分析树的引 <句子结点根结点末端结 <主语><谓语 边分 <名词><动词><介词><名词分支结 Berry lecture Berryswinsinriver=><名词><谓语><状语Berry动词><状语Berryswins状语Berryswins介词><名词Berryswinsin名词=>Berryswinsin lecture 步骤1以识别符号为根结点，对应于第一个直 步骤2从第二个直接推导左边被替换的非终结符号相应的结点 分支,对应于此直接推导步骤3类似地对应于每个直接推导,从左边被替换的非终结符号对应的结点向分支相应于此直 lecture i

lecture

例G[E]: lecture EE+EEE+Ea+E*EEEEEE+EE*EaaaEE*EE+Eaaa最左推 lecture 4.对于程序设计语言来说，重要的是：描述它的文不存在一种算法，能在有限步骤内确切判定一个鉴于二义性不可判定，所能做的是寻找一组充分条件，使得满足这些条件的文法必定是无二义性的。注意，这些条件只是充分条件，未必是无二义性的 lecture lecture lecture E短T,a1,a1,T*F,a1+F*a1,F,F*F,a1+a2a1,a2,a1+a2*F,a2a1+a2a1,a2,a3,a2*a3a1+a2*a3EE+TTT*FFFEE+TTT*FFF)EE+TTT*FFF)EE+TTT*FFFEE+F*E+a2*T+a2*F+a2*a1+a2 lecture 最左推导=最右推导= lecture xUy=>如果某推导v=>+ 则称该推导为规范的，记作v=>+w。v=>v1=>v2=>…=>vn-1=> lecture 概程序设计语 程序的集合程序是在程序设计语言字母表上按一定规则构造的符号串；程序设计语言是其字母表正闭包的文法四要素：VN、VT、P、文法的句型：由识别符号推导所得的符号串文法的句子：全由终结符号组成的 文法确定，则语言确定 lecture 推导、归短语、简单短语、句递归（规则递归、文法递归 lecture 应用文法生成句子的 步骤2对当前句型进行直接推导（非终结符号替换为以其为左部的规步骤3重复步骤2，直到无非终结符号可被替换通常应以系统