自底向上分析一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