我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:多盈娱乐注册 > 多带图灵机 >

编译原理语法1(文法和语言)

归档日期:07-03       文本归类:多带图灵机      文章编辑:爱尚语录

  编译原理语法1(文法和语言)_数学_高中教育_教育专区。西北农林科技大学本科教程 第 4 讲 主讲教师:赵建邦 第三章 语法分析 ? 3.1 ? 3.2 文法和语言 推导与语法树 ? 3.3 ? 3.4 自顶向下的语法分析 自底向上的语法分析

  西北农林科技大学本科教程 第 4 讲 主讲教师:赵建邦 第三章 语法分析 ? 3.1 ? 3.2 文法和语言 推导与语法树 ? 3.3 ? 3.4 自顶向下的语法分析 自底向上的语法分析 ? 3.5 规范规约的自底向上语法分析方法 本讲目标 ? 第三章《语法分析》 ? 3.1 文法和语言 ? 文法和语言的基本概念 ? 形式语言分类(4类) ? 正规表达式与上下文无关文法 ? 重点掌握 ? 正规表达式与上下文无关文法 语法分析: ? 定位 –语法分析是编译过程的第二个阶段,也是核心部分 ? 任务 – 根据语言的语法规则对单词序列进行语法分析,识别合法的 语法单位(如表达式、语句、程序段等),若不存在语法错 误则给出正确的语法结构 – 理论依据:上下文无关文法 ? 方法 – 自顶向下分析(推导:开始符号 – 自底向上分析(规约:句子 句子) 开始符号) 3.1 ? 文法和语言 文法(Grammar)是程序语言的生成系统,用文法可以精确定义一 个语言,并依据该文法构造出识别这个语言的自动机 ? 文法对程序语言和编译程序的构造具有重要意义,如程序语言的 词法可用正规文法描述,语法可用上下文无关文法描述,而语义 则要借助于上下文有关文法描述 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 1、语言 ? 通常我们用Σ表示字母表,字母表中的每个元素称为字符 或符号。不同语言的字母表可能是不同的,程序语言的字 母表通常是ASCII字符集。 由字母表Σ中的字符所组成的有穷系列称为Σ上的字符串 ? 或字,字母表Σ上的所有字符串(包括空串)组成的集合用 Σ*表示。 ? 那么,对字母表Σ来说,Σ*上的任意一个子集都称为Σ上 的一个语言,记为L( L ? ?* ),该语言的每一个字符串称 为语言L的一个语句或句子。 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 1、语言 例如,设Σ?=?{a, b, c},则: L?=?{ε, a, aa, ab, aaa, aab, aba, abb, …} 为Σ上的一个语言。 如果a表示字母,b表示数字,c看做其它符号,则L即 是程序语言中的标识符集,其中的每个标识符就是标识 符集中的一个句子。 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 2、文法 (定义) ? 文法通常表示成四元组G[S]?=?(VT,VN,S,ξ): (1) ?VT为终结符号集,这是一个非空有限集,它的每个元素 称为终结符号。 (2) ?VN为非终结符号集,它也是一个非空有限集,其每个元 素称为非终结符号,且有VT∩VN?=?Φ; (3)? S为文法开始符,是一个特殊的非终结符号,即S∈VN; 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 2、文法(文法中的基本概念) ? 终结符号:是指语言不可再分的基本符号,通常是一个语 言的字母表;终结符代表了语法的最小元素,是一种个体 记号。 ? 非终结符号:也称语法变量,它代表语法实体或语法范畴; 非终结符代表一个一定的语法概念,因此,一个非终结符 是一个类、一个集合。 注意: 1、字母表可以称为文法中的终结符集 2、非终结符不能是字母表中的字符 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 2、文法 (定义) ? 文法通常表示成四元组G[S]?=?(VT,VN,S,ξ): (4) ? ξ是产生式的非空有限集,其中每个产生式(或称规则)是 一序偶(α,β),通常写作 α?→?β 或 α?::=?β 读作“α产生β”、 “α是β”或“α定义为β”。在此,α为产生 式的左部,而β为产生式的右部,α、β是由终结符和非终结 符组成的符号串,α∈(VT∪VN) +?且至少有一个非终结符, 而β∈(VT∪VN) *。 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 2、文法(文法中的基本概念) ? 文法开始符号S:是一个特殊的非终结符,它代表文法所 而其它语法实体只是构造语言目标的中间变量 定义的语言中我们最终感兴趣的语法实体,即语言的目标, ? 产生式: (也称产生规则或规则)是定义语法实体的一种书 写规则。一个语法实体的相关规则可能不止一个。 3.1 文法和语言 如果: P→α1 P→α2 …… P→αn P?→?α1 α2 … αn 其中,每个αi(i=1, 2, …, n)称为P的一个候选式,直竖“ ” 读为“或”,它与“→”一样是用来描述文法的元语言符 号(即不属于Σ的字符)。 3.1 文法和语言 例如,定义一个仅包含加和乘运算的表达式的文法G[E]: G[S]?=?(VT,VN,S,ξ): VT ={+ * ( ) i} VN = {E, T, F} S = E ξ 为以下产生式的集合: VT ={+ * VN = {E} S =E ξ: ( ) i} E→E + T T T→T * F F F→ (E)i E→i E+E E*E (E) 两种文法都可以识别包含加和乘运算的表达式,它们的区 别将在后面的课程中讲解 2.3 ? 正规表达式与优先自动机简介 3.1.1 文法和语言的基本概念 关于文法表示的约定: – 在此后的讨论中,用大写字母A、B、S、E等表示非终结符, 用小写字母a、b、i、j等表示终结符,并用希腊字母等表示文 法符号串,即α、β、δ、γ等均属于(VT∪VN)*。 课本例题 例3.1 试构造产生标识符的文法。 [解答] 首先,标识符是以字母开头的字母数字串, 用L表示“字母”类非终结符, 用D表示“数字”类非终结符, 而用T表示“字母或数字”类非终结符,则有: L?→?a b … z D?→?0 1 … 9 T?→?L D (单个的字母或数字字符) 其次,如果用S表示“字母数字串”类,则T是一字母或数字, ST也是字母数字串,即有 S?→?T ST (字母或数字串) 其中,产生式S→T ST是一种左递归形式,由它可以产生一串T 课本例题 最后,作为“标识符”的非终结符I,它或者是一单个字 母,或者为一字母后跟字母数字串,即 I?→?L LS 因此,产生标识符的文法G[I]为: G[I] = ( VT , VN, I,ξ): = ({a, b, …, z, 0, …, 9}, {I, S, T, L, D}, I, ξ) ξ : I?→?L LS ?S?→?T ST ?T?→?L D L?→?a b … z ?D?→?0 1 … 9 课本例题 例3.2 写一文法,使其语言是奇数集合,但不允许出现以0打 头的奇数。 [解答] 根据题意,我们可以将奇数划分为如图3-1所示的三个部 分,即最高位允许出现1~9,用非终结符B表示;中间部分可 以出现任意多位数字0~9,每一位用非终结符D表示;最低位 只允许出现1、3、5、7、9等奇数,用A表示。 课本例题 图3-1 奇数划分示意 课本例题 由于中间部分可出现任意位,所以另引入了一个非终结符M, 它包括最高位和中间位部分。假定开始符为N,则可得到文法 G[N]为 G[N]?=?({0, 1, …, 9}, {N, A, M, B, D}, N, ξ) ξ : N→A MA M→B MD /*一位数字 多位数字*/ /*仅两位数字(无中间位) 多于两位数字*/ A→1 3 5 7 9 B→1 2 3 4 5 6 7 8 9 D→0 B 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 3、文法产生的语言 ? 设文法G[S]?=?(VT, VN, S, ξ),且α、β∈(VT∪VN)*,如果存 在产生式A?→?δ(δ∈(VT∪VN)*),则称αAβ可直接推出αδβ, 即 αAβ?=αδβ ? 其中 “=”表示直接推导,是应用产生规则进行推导的记号, 这里仅使用一次规则 注意“=”与“→”不同,“→”是产生式中的定义记号。直 接推导是指对文法符号串αAβ中的非终结符A用相应的产生 式A→δ的右部δ来替换,从而得到αδβ 3.1 ? 文法和语言 推导的说明: – (1)如果α1可直接推出α2,α2可直接推出α3,…,αn-1可直接推 出αn ,即存在一个自α1至αn的推导序列: + α1=α2=α3=…=αn(n0),则称α1可推导出αn,记为α1 =αn, 它表示从α1出发经过一步或若干步可推导出αn。 – 0 * α 则表示从α 出发,经过0步或若 (2) 如果记α1 = α1, α1 = n 1 * α ,意味着或者α =α ,或者 干步可推导出α ;也即α = n 1 n 1? n + α1 =αn。这个概念叫做“广义推导” 显然:直接推导的长度是1,推导的长度≥1, 广义推导的长度≥0 3.1 ? 文法和语言 推导的举例: 例如,对下面的文法G[E]: E?→?E?+?E E?*?E (E) i (3.1) 其中,惟一的非终结符E可以看成是代表一类算术表达式。可以 从E出发进行一系列的推导,如表达式 i+i*i 的推导如下: E=E+E = E+E*E = E+E*i = E+i*i =i+i*i 注意:在每一步推导过程中,只能对其中的一个非终结符用其对应 的产生式右部的一个候选式来替换。 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – * , 句型:假定G[S]是一个文法,S是它的开始符号,如果S=α α∈(VT∪VN)*,则称α是文法G[S]的一个句型; – 句子:如果α∈ VT *,则称α是文法G[S]的一个句子。仅含终 结符的句型是一个句子。 ? 由定义可知,开始符S本身只能是文法的一个句型而不可 能是一个句子; 句子是特殊的句型。 ? 上面推导出的i+i*i是文法G[E]的一个句子(当然也是一个句 型),而E+E、E+E*E、E+E*i和E+i*i都是文法G[E]的句型 思考:文法 G[S]: S→aBBb B→ab 的句型和句子有多少个? 3.1 ? 文法和语言 3.1.1 文法和语言的基本概念 – 文法产生的语言:对于文法G[S],它所产生的句子的全体称 为由文法G[S]?产生的语言,记为L(G),即有: + L(G)?=?{α S=α且α∈ VT *} 注意: (1) S至少进行一次推导; (2) S所推导出的α必须全部由终结符组成; (3) 当文法给定,语言也就唯一地确定,即G→ L(G) ; 给定一个语言,它所对应的文法不是唯一的; (4) L(G)是VT *的子集,属于VT *的符号串不一定属 于L(G); 3.1 ? 文法和语言 3.1.2 形式语言分类 – 语言学家Noam Chomsky于1956年首先建立了形式语言的描 述,定义了四类文法及相应的形式语言,它对程序语言的设 * 计、编译方法、计算复杂性等方面都产生了重大影响: ? 0型文法与0型语言(对应图灵机) ? ? ? 1型文法与1型语言(对应线性界限自动机,自然语言) 2型文法与2型语言(对应下推自动机,程序设计语言) 3型文法与3型语言(对应有限自动机) 3.1 ? 文法和语言 3.1.2 形式语言分类 – 1、0型文法与0型语言 如果文法G[S]的每一个产生式具有下列形式: α→β 其中,α∈V*VNV*?(注:V?=?VN∪VT),即至少含有一个非终 结符;β∈V*;则称文法G[S]为0型文法或短语文法,记为 PSG(Phrase Structure Grammar)。0型文法相应的语言称为0型 语言或称递归可枚举集,它的识别系统是图灵(Turing)机。 例如: S ? ACaB CB ? DB aD ? Da aE ? Ea Ca CB AD AE ? ? ? ? aaC E AC ? 3.1 ? 文法和语言 3.1.2 形式语言分类 – 2、1型文法与1型语言 文法G[S]的每一个产生式α→β,均在0型文法的基础上增加了 字符长度满足 α ≤ β 的限制,则称文法G[S]为1型文法或上下 文有关文法,记为CSG。1型文法相应的语言称为1型语言或上 下文有关语言,它的识别系统是线型文法的等价定义 文法G[S]的每一个产生式具有下列形式: αAδ?→αβδ 其中,α、δ∈V*,A∈VN,β∈ V+ 。显然,它满足前述定 义的长度限制,但它更明确地表达了上下文有关的特性,即A必 须在α、δ的上下文环境中才能被β所替换。 3.1 ? 文法和语言 3.1.2 形式语言分类 – 3、2型文法与2型语言 文法G[S]的每一个产生式具有下列形式: A?→?α 其中,A∈ VN ,α∈V*,则称文法G[S]为2型文法或上下文无 关文法,记为CFG。2型文法相应的语言称为2型语言或上下文 无关语言,它的识别系统是下推自动机。 例:G[S]=({a,b},{S} S, { S?aSb , S?ab} ) 产生的语言为: L(G) ? {a b i ? 1} i i 3.1 ? 文法和语言 3.1.2 形式语言分类 3、2型文法与2型语言 上下文无关文法有足够能力描述现今程序设计语言的语法结 构。 例如:产生条件句的文法片段 – 语句-if 条件 then 语句 if 条件 then 语句 else 语句 其他语句 3.1 ? 文法和语言 3.1.2 形式语言分类 – 4、3型文法与3型语言 A?→?a 或 A?→?aB 其中,A、B∈ VN ,a∈ VT *,则文法G[S]称为3型文法、 文法G[S]的每个产生式具有下列形式: 正规文法或右线型 语言或正规语言,它的识别系统是有限自动机。3型文法还可以 呈现左线性形式: A?→?a 或 A?→?Ba 3.1 ? 文法和语言 3.1.2 形式语言分类 – 4、3型文法与3型语言 A?→?a 或 A?→?aB 其中,A、B∈ VN ,a∈ VT *,则文法G[S]称为3型文法、 文法G[S]的每个产生式具有下列形式: 正规文法或右线型 语言或正规语言,它的识别系统是有限自动机。3型文法还可以 呈现左线性形式: A?→?a 或 A?→?Ba 3.1 ? 文法和语言 3.1.2 形式语言分类 – 5、4类文法的关系与区别 关系: (1) 从0型文法到3型文法的限制逐渐增; (2) 1~3型文法都属于0型文法; (3) 2、3型文法不一定属于1型文法:因为1型文法不允许存 在“A?→ε”形式的产生式,则:如果2、3文法不含有类似产 生式,则该文法属于1型文法。 3.1 ? 文法和语言 3.1.2 形式语言分类 – 5、4类文法的关系与区别 (1) 1型文法中不允许有形如“A→ε”的产生式存在,而2、3 区别: 型文法则允许形如“A→ε”的产生式存在; (2) 0、1型文法的产生式左部存在含有终结符号的符号串或 两个以上的非终结符,而2型和3型文法的产生式左部只允许是 单个的非终结符号。 3.1 ? 文法和语言 3.1.3 正规表达式与上下文无关文法 – 1. 正规表达式到上下文无关文法的转换 ? 正规表达式所描述的语言结构均可用上下文无关文法描述, 反之则不一定 正规表达式构造上下文无关文法: (1)构造正规表达式的NFA; ? (2)若0为初始状态,则A0为开始符号; (3)如果存在映射关系f(i,a)=j,则定义产生式Ai (4)如果存在映射关系f(i, ε)=j,则定义产生式Ai (5)如果i为终态,则定义产生式Ai ε aAj; Aj; 例题: 用上下文无关文法描述正规表达式1(01)*101 正规式1(01)*101相应的非确定自动机 构造的上下文无关文法: G[A0]: A0-1A1 A1-0A11A11A2 A2-0A3 A3-1A4 A4- ε 3.1 ? 文法和语言 3.1.3 正规表达式与上下文无关文法 – 2. 正规表达式与上下文无关文法描述的对象 ? 正规表达式描述词法: (1)词法规则简单,采用正规表达式足以描述; (2)正规表达式的表示比上下文无关文法更加简洁、直观和 易于理解; (3)有限自动机的构造比下推自动机简单且分析效率高; ? 正规表达式适于描述线性结构,如标识符、关键字等; 上下文无关文法适于描述具有嵌套(层次)性质的非线性 结构,如if-else、while 等。

本文链接:http://cakesbyrita.net/duodaitulingji/758.html