编译原理-西安交通大学第三章上下文无关文法课件

15三月2024编译原理-西安交通大学第三章上下文无关文法本章内容引言 -文法文法与语言 -上下文无关文法 -推导与语言语法树与二义性第三章上下文无关文法(context-freegrammar)文法（grammar)问题： 如何描述语言定义： 文法是描述语言的语法结构的形式规则（即语法规则)目的： 解决语言的有穷说明问题，包含对语法的描述，但 却不表达任何语义一、引言1、文法的描述应达到要求：2、文法分类：分为四类（0、1、2、3型文法），对应四类语言； 与程序语言语法有关的是上下文无关文法 形式上严格、准确； 易于理解； 具有较强的描述能力； 有利于句子的分析和翻译，构造语法分析器3、上下文无关文法的特点： 它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的说明上下文无关文法只能描述一部分语言，但已足够描述现今的程序设计语言自然语言要用其他的文法来描述二、文法与语言1、

一个上下文无关文法G是一个四元式（VT,VN,S,P），其中:VT：是非空有限集，它的每个元素是终结符号；VN：是非空有限集，它的每个元素是非终结符号； VT∩VN=Φ; VT∪VN=V;P：产生式集合（有限），每个产生式形式是{P->α|P∈VN，α∈(VT∪VN)*，S至少一次为P}；S：S∈VN，称为开始符号；例1、考虑下面的算术表达式的文法及语言 VT： id+－*/↑() VN： 表达式、运算符 S： 表达式 P： 表达式->表达式运算符表达式 表达式->（表达式） 表达式->－表达式 表达式->id 运算符->+|－|*|/|↑得到文法G1(E):E->EAE|(E)|－E|idA->+|－|*|/|↑该文法的： VN是出现P的左部所有符号集合

V是P的所有符号 ∴VT=V\VN S是该文法所定义的句子名字∴写出了P，就能找出其它三元素由此可见，文法G1(E)所定义的语言是上述算术表达式，如：id+id，id*(id+id)等它表达了简单算术表达式由id用A连接起来2、从此可见

终结符：是用以组成语言中的串的基本符号，与程序语言中“单词”是同义语；如：表达式id+(id)*(-id)中，+、－、*、/、↑、id均为终结符

非终结符：是标记某种串的集合的特定符号，与“语法变量”、“语法范畴”是同义词；如：表达式、运算符都表示一个串的集合该语法范畴叫“句子”，在程序语言中叫“程序”语言的句子是由一串VN定义，到最后才是一串VT

开始符号：一个VN，标记感兴趣的语法范畴。其它非终结符用以定义其它的串集，这有助于定义该语言，也有助于为它处理的语言提供一个分层的结构；

产生式：规定由终结符和别的语法范畴组成一个新的语法范畴的办法；结构：非终结符->一串非终结符和终结符如：A->α A -> α ↓ ↓ 左部符号右部候选式 VN α=X1X2…Xn，Xi∈V3、习惯记号VN: 大写字母A、B、C、S等VT: 小写字母，0~9，+、－等运算符， 标点，分界符，黑体字母串id、ifX、Y、Z： 文法符号，或VN或VT一个符号u、v、w…z：VT中串α、β、γ: 文法符号串∈(VT∪VN)*S: 开始符号，第一个产生式中出现->: 定义为（元语言符号）|： 或（元语言符号）有穷条产生式，产生无穷集，要求产生式必须递归定义算术表达式，用了两条浓缩的产生式，一般定 义一个语言的产生式是很复杂的对递归的算术表达式的产生式，进行反复推导产生 表达式语言问题：表达式语言无穷，如何定义？4、推导与语言问题：用文法如何定义一个语言？思路：从S出发，反复使用P，对非终结符替换展开，最后得到全由终结符串组成的一个串涉及到：替换->推导->句型->句子->语言②推导：如两个串u0、un，存在一个串序列

u0u1…un 则u0

R1

un，R1记为或u0un：表示从u0出发，经一步或若干步，可推导出unu0un：表示从u0出发，经0步或若干步，可推导出un①直接推导：是两个字符串之间的一种关系R如：（αAβ）R（αγβ），它表示： 若 A->γ∈P，α、β∈V* 则R就是直接推导，R记为 即：αAβαγβ如令u0为S，即推导要从开始符号开始，那么： Sα，α∈V*，称α为G的句型如再要求α∈VT*，则α为G的句子文法G所产生的句子的全体是一个语言，记为L(G)

L(G)={α|Sα&α∈VT*}③怎样由推导引出语言？只需在推导中加一些限制即对： u0un 或 u0un①由文法G定义语言L是依赖一种运算，关系 V*中有许多的串，仅有那些(S,u)(S,v)存在关系的u、v才有可能成为语言中的句子。②α、β、γ是句型，表示(S，α)(S，β)，有 的关系，但它的构成不全为VT的字符。③G的句型集，是指存在Sα关系的所有α，该 集的子集是L(G)④V*句型集L(G)说明例2根据文法G: E->E+E|E*E|(E)|i句子i1*(i2+i3)推导过程如下：②E=>E*E=>E*(E)=>E*(E+E)=>E*(E+i3)=>E*(i2+i3)=>i1*(i2+i3)①E=>E*E=>i1*E=>i1*(E)=>i1*(E+E)=>i1*(i2+E)=>i1*(i2+i3)注意：从一个句型到另一个句型的推导过程并不唯一，但 通常只考虑最左推导和最右推导。最左推导最右推导

最左推导是指，任何一步α=>β都是对α中的最左非终结符进行替换的

最右推导是指，任何一步α=>β都是对α中的最右非终结符进行替换的三、语法树与二义性1、语法树定义：句型推导的图形表示，它与替换顺序的选取无关作用：明显的形成文法所暗含的句子分层语法结构， 为语法分析提供一些新的途径目的：为了理解句子的语法，得到句子如何从开始符 号推导得到，因此引入“图”树的叶：非终结符|终结符，对应一个句型语法树为语法分析提供一些新的途径树的内节点：非终结符A标记 若A->α，则该产生式的一棵子树为AXYZ在语法树中找出文法中的概念内结点A VN叶 文法符号子树 直接推导根结点 S任一次全剪 句型叶子∈VT时，将叶子顺序排列 句子例3E－(id+id)的语法树最左推导：E-E-(E)-(E+E)-(id+E)－(id+id)最右推导：E-E-(E)-(E+E)-(E+id)－(id+id)

E－Eidid(E)E+E语法树由此可见，每一中间过程，句型很容易获得树忽略了符号的替换顺序的不同，不同推导过程 得到相同的语法树有的语法，对于同一句子、应用不同规则进行推 导得到不同的语法树例4根据文法G对句子id+id*id进行推导①文法G E->E+E|E*E|(E)|i②推导1E=>E+E=>id+E=>id+E*E=>id+id*E=>id+id*id③推导2E=>E*E=>E+E*E=>id+E*E=>id+id*E=>id+id*id②与③两种推导对应两棵不同的语法树，如下所示：推导1的语法树推导2的语法树EE*ididEidE+E+ididEEEE*EidE=>E+E=>id+E=>id+E*E=>id+id*E=>id+id*idE=>E*E=>E+E*E=>id+E*E=>id+id*E=>id+id*id2、二义性问题定义： 文法G的某一句子有两棵不同的树，则G为二义的。二义性对语法分析不便，因此希望： 1）判定二义否 2）无二义性的充分条件 3）如何消除二义性解决办法：尽量去掉二义性 ①如对