东北大学秦皇岛分校编译原理 第二章第三章课件.pptVIP

第三章 文法和语言本章目的 ;本章知识点(内容)引言和预备知;3.1 文法的直观概念和语言概;“我是大学生”。是汉语的一个句;有了一组规则以后，按照如下方式;“我是大学生”的构成符合上述规;3.2 编译原理所涉及到的一;3.2.1 集合 概念 ;3.2.2 笛卡儿乘积 序;3.2.3 关系 定义 ;3.3 有关定义和记号符号：可;介绍有关符号串的一些运算 ?符;符号串的连接：设x和y是符号串;符号串集合：若集合A中所有元素;例：Σ={a,b} Σ*=;有关定义和记号语言是由句子组成;3.4文法和语言的形式定义语言;程序设计语言的概念和描述方法 ;语言研究的三个方面 ;每种语言具有两个可识别的特性，;如果不考虑语义和语用，即只从语;文法和语言的形式定义如何来描述;文法即是生成方式描述语言的：语;定义文法G定义为四元组(VN，;文法的定义例 文法G=（V;例 文法G=（VN，VT，;文法的写法 1 G：S→aAb;元符号: → ;推导的定义直接推导“?”α→β;程序?分程序. 分程;推导的定义 若存在v ?w0 ;例：G： S→0S1， S→0;句型、句子的定义句型有文法G，;例：G[E]： E→E+T;文法，语言的定义由文法G生成的;例 文法G[S]： （1;S ?a S BE (;使用产生式(1)n-1次，得到;文法的等价若L（G1）=L（G;文法的类型通过对产生式施加不同;文法的类型例：1型（上下文有关;文法的类型例：2型（上下文无关;3型文法G[S]： ;文法的类型2型文法1型文法0型;文法和语言0型文法产生的语言称;根据形式语言理论,文法和识别系;带 a0 a1 ;2型文法（上下文无关文法CFG;上下文无关文法及其语法树上下文;例文法G=(｛E｝,｛+,*,;句型、推导G[E]： E→;规范推导 规范句型最左（最右）;语法树设G=( VN,VT,P;构造语法树G[E]： E→;E?E+T ?T+T ?F+T;上下文无关文法的语法树的用处用;上下文无关文法的语法树推导过程;一棵语法树表示了一个句型的种种;例：G[E]: E → i ;二义文法 若一个文法存在某个;文法的二义性和语言的二义性是两;句型的分析句型分析就是识别一个;句型的分析算法分类分析算法可分;两种方法反映了两种语法树的构造;自上而下的语法分析例：文法G：;自下而上的语法分析例：文法G：;(1)S → cAd (2;(1)S → cAd (2;句型分析的有关问题1）在自上而;刻画“可归约串”文法G[S]句;例 ：i*i+i 的短语、直接;G1[S]： S→0|0A|E;G2[S]： S→;化简文法文法实用中的一些说明 ;对于文法G[S]，为了保证任一;化简文法例：G[S] ： 1;上下文无关文法中的ε规则上下文;消除单一产生式 例：算术表达式;G[E]： E→E+T| E;文法的其它表示方法 扩充的BN;扩充的BNF（EBNF） 花括;语法图的构造法则 （1）每一个;（3）在xi中每出现一个非终结;（5）形如x→y1y2…yn的;【例】设有文法G： A→x|（;Ax（B）BACCA+朗躬眷蜒;Ax（）AA+攒套烹昂贪氧控培;[本章小结]1.本章出现的概念;[本章小结]考察本章知识点最典;练习 1. 写一文法，使其语言;练习4. 给出生成下述语言的