编译原理第三章.ppt

对句型：i*i+I进行分析G[E]：E→E+T|T

T→T*F|F

F→(E)|i句型：i*i+iEE+TTFT*Fi3Fi2i1短语：i1*i2+i3、i1*i2、i1、i2、i3直接短语：i1、i2、i3句柄：i1S?aSBE(S→aSBE) ?aaBEBE(S→aBE) ?aabEBE (aB→ab) ?aabBEE (EB→BE) ?aabbEE （bB→bb) ?aabbeE （bE→be) ?aabbee （eE→ee)

文法和语言的关系：G生成的每个串都在L(G)中

L(G)中的每个串确实能被G生成文法的等价若L（G1）=L（G2），则称文法G1和G2是等价的。

如文法G1[A]：A→0R与G2[S]：S→0S1等价A→01S→01R→A1L(G1)=L(G2)={0n1n|n≥1}注：从文法得到的语言句子在结构上等价，含义上不一定等价。3.4文法的类型通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)*且至少含有一个非终结符，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外另一种定义：设G=(VN,Vt,P,S)，如果它的每个产生式有如下形式：xAy→xβy，A∈VN，β∈(VN∪VT)+，x、y∈(VN∪VT)*，则G是一个1型文法例：1型（上下文有关）文法文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bDL(G)={ww|w∈{a,b}*}2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*例：2型（上下文无关）文法文法G[S]： S→aB|bA A→a|aS|bAA B→b|bS|aBB3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VNB∈VN，a∈VT例：定义标识符的3型（正规）文法文法G[I]：I→lT I→l T→lT T→dT T→l T→d2型文法1型文法0型文法四级文法之间逐级“包含”的关系：3型文法文法和语言0型文法产生的语言称为0型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言或上下文有关语言（CSL）2型文法或上下文无关文法（CFL）产生的语言称为2型语言或上下文无关语言（CFL）3型文法或正则（正规）文法（RG）产生的语言称为3型语言正则（正规）语言（RL）文法和语言四种文法之间的关系是将产生式做进一步限制而定义的。语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。 3.5上下文无关文法及其语法树上下文无关文法有足够的能力描述现今程序设计语言的语法结构，很多高级语言由上下文无关文法描述。算术表达式语句条件语句赋值语句读语句算术表达式上下文无关文法表示例：文法G=({E},{+,*,i,(,)},P,E} P: E→i E→E+E E→E*E E→(E)E表示一类算术表达式，i表示变量，该文法定义了由变量、＋、*、（和）组成的算术表达式的语法结构。条件语句上下文无关文法表示描述一种简单赋值语句的产生式：赋值语句→i:=E描述条件语句的文法片断为：条件语句→if条件then语句

|if条件then语句else语句用于描述上下文无关文法的句型推导的直观方法例:G[S]: S→aAS A→SbA A→SS S→a A→baS