自底向上分析一LR分析概述 ●自底向上分析的思想和主要问题 几种LR分析方法: LR(0) SLR 1) LR(1) LALR(1
自底向上分析－LR分析概述 ⚫ 自底向上分析的思想和主要问题 ⚫ 几种LR分析方法： LR(0) SLR(1) LR(1) LALR(1)
主要内容: LR的几个基本概念 线性正则式的状态机LRSM
主要内容： LR的几个基本概念 线性正则式的状态机LRSM
●短语:设S是文法的开始符,是句型(即 有S→*amB),如果满足条件: s→oAβB A→+π ●则称π是句型a的一个短语。 ●直接短语(简单短语):如果满足条件: S→*aA A→兀 则称π是句型a的一个简单短语 句柄:一个句型可能有多个简单短语,其中 最左的简单短语称之为句柄
⚫ 短语：设S是文法的开始符，是句型(即 有S *），如果满足条件： ⚫ S * A ⚫ A + ⚫ 则称是句型的一个短语。 ⚫ 直接短语（简单短语）：如果满足条件： ⚫ S * A ⚫ A ⚫ 则称是句型的一个简单短语。 ⚫ 句柄：一个句型可能有多个简单短语，其中 最左的简单短语称之为句柄
个有用的定理 ●定义:由某一结点及其所属分支组成的部分 树称为原树的一颗子树。只有单层分支的子 树称为简单子树。 定理: 1.每个句型都有一颗语法树,每个语法 树的叶组成一句型。 2.每棵子树的叶组成短语,每颗简单子 树的叶组成简单短语,最左简单子树的叶组 成句柄
一个有用的定理 ⚫ 定义：由某一结点及其所属分支组成的部分 树称为原树的一颗子树。只有单层分支的子 树称为简单子树。 ⚫ 定理： ⚫ 1.每个句型都有一颗语法树，每个语法 树的叶组成一句型。 ⚫ 2.每棵子树的叶组成短语，每颗简单子 树的叶组成简单短语，最左简单子树的叶组 成句柄
●句型:(T+i)*i+F ●短语: 1.(T+i)*i+F 2.(T+i)*i 3.(T+i) 4.T+ 5.T 6.第一个i 7.第二个i 8.F ●简单短语: T第一个i,第二个i,F ●句柄:T
⚫句型: (T+i)*i+F E E + T T T * F F i ( E ) E + T T i F F ⚫短语： 1.(T+i)*i+F 2.(T+i)*i 3.(T+i) 4.T+i 5.T 6.第一个i 7.第二个i 8.F ⚫简单短语： T,第一个i,第二个i,F ⚫句柄：T
规范句型:用最右推导导出的句型(也称右句 型) ●规范前缀:若存在规范句型a,且m是终极符 串或空串,则称α为规范前缀。 ●规范活前缀:若规范前缀α不含句柄或含一个 句柄并且具有形式=!π(π是句柄,则称规范 前缀α为规范活前缀(简称活前缀)。 ●归约规范活前缀:若活前缓c是含句柄的活前 缀,即有=aπ,且π是句柄,则称活前缀c为 归约规范活前缀(简称归约活前缀)
⚫ 规范句型：用最右推导导出的句型(也称右句 型）。 ⚫ 规范前缀：若存在规范句型，且是终极符 串或空串，则称为规范前缀。 ⚫ 规范活前缀：若规范前缀不含句柄或含一个 句柄并且具有形式=(是句柄)，则称规范 前缀为规范活前缀(简称活前缀）。 ⚫ 归约规范活前缀：若活前缀是含句柄的活前 缀，即有=，且是句柄，则称活前缀为 归约规范活前缀（简称归约活前缀）
逆过程:(分析栈,输入流) 例:S→> aAcBe[1 abode) A→b[2 →(a,bcde) A→Ab[3 (ab, bcde) B→d[4 →(aA,bcde) 输入流: abbcde →(aAb,cde) 规范推导过程为: →(aA,cde) s→ aAcBe →(aAc,de) →aAcd4e[1 →(aAcd,e) →(aAcB,e) →aAb3cd4]e[1] →( aAcBe,-) →ab[21b③lcd4]em1→(S,-)
例：S → aAcBe [1] A → b [2] A → Ab [3] B → d [4] 输入流：abbcde。 规范推导过程为： 逆过程:(分析栈，输入流) ( -, abbcde) (a,bbcde) (ab,bcde) (aA,bcde) (aAb,cde) (aA,cde) (aAc,de) (aAcd,e) (aAcB,e) (aAcBe,-) (S,-) S aAcBe[1] aAcd [4]e [1] aAb[3]cd[4]e [1] ab [2]b [3]cd[4]e [1]
活前缀的描述性定义:形成可归前缓之 前,包括可归前缀在內所有规范句型的 前缀都称为活前缀 ●活前缀为一个或若干规范句型的前缀。 ●在规范归约过程中的任何时刻已分析过 的部分,即在分析栈(符号栈)中的符 号串均为规范句型的活前缀,表明输入 串的已被分析过的部分是该文法某规范 句型的一个正确部分
⚫ 活前缀的描述性定义：形成可归前缀之 前，包括可归前缀在内所有规范句型的 前缀都称为活前缀。 ⚫ 活前缀为一个或若干规范句型的前缀。 ⚫ 在规范归约过程中的任何时刻已分析过 的部分，即在分析栈（符号栈）中的符 号串均为规范句型的活前缀，表明输入 串的已被分析过的部分是该文法某规范 句型的一个正确部分
线性正则式状态机一LRSM 线性正则式:不含*符号的正则表达式 LRSM:( Linear Regular States Mach ine (1)从LRSM可构造出恰好接受给定所有正 则式的确定自动机DA (2)从LRSM的终止状态可判定接受的是哪 个正则式; (3)从LRSM的状态可判定一个正则式是不 是另一正则式的前缀
线性正则式状态机－LRSM ⚫ 线性正则式：不含*符号的正则表达式 ⚫ LRSM：(Linear Regular States Machine) (1)从LRSM可构造出恰好接受给定所有正 则式的确定自动机DA； (2)从LRSM的终止状态可判定接受的是哪 个正则式； (3)从LRSM的状态可判定一个正则式是不 是另一正则式的前缀
●项目:假设αBP是一个正则式,则我们称形 如a[P的表示为项目,其中P是正则式编号。 其中黑点可出现于任何位置上 ●项目集:用S表示 S Sub ltems(IS, X= aXB[P]|aXβ[P]∈|S,X∈ SymbSet 简记为|S
⚫ 项目：假设[P]是一个正则式，则我们称形 如•[P]的表示为项目，其中P是正则式编号。 其中黑点可出现于任何位置上。 ⚫ 项目集：用IS表示 ⚫ IS(X) ： SubItems(IS,X)= {X•[P]|•X[P]IS,XSymbSet} 简记为IS(X)