精华内容
下载资源
问答
  • 《编译原理》构造 LR(1) 分析表的步骤与例题解析

    《编译原理》LR 分析法与构造 LR(1) 分析表的步骤 - 例题解析

    笔记

    直接做题是有一些特定步骤,有技巧。但也必须先了解一些基本概念,本篇会通过例题形式解释概念,会容易理解和记忆,以及解决类似问题。

    如果只想做题可以直接下拉至习题部分。

    (一)关于状态

    对于产生式 A→aBcD,就可以分解为下面几个不同的识别状态:

    (1)A→.aBcD
    (2)A→a.BcD
    (3)A→aB.cD
    (4)A→aBc.D
    (5)A→aBcD.

    “.” 的左部符号表示已被识别出来的那部分句柄符号

    状态(1)表示:处于句柄的头
    状态(2)表示:已经识别出字符 a,等待 形成以 B 为产生式左部的右部
    状态(3)表示:刚刚进行了一次规约,即把关于 B 的产生式右部规约成 B
    状态(4)表示:已经识别出字符 c,等待 形成以 D 为产生式左部的右部
    状态(5)表示:已经到达句柄的尾巴,可以把 aBcD 规约为产生式左部的符号 A

    (二)什么是 LR(k) 分析法?

    字面意思理解:

    字符含义
    L表示 从左到右 扫描输入串
    R表示利用 最右分析方法 来识别句子,即构造一个 最右推导的逆过程
    k表示向右查看输入串符号的个数

    LR 分析过程是规范归约的过程

    规范规约是最右推导的逆过程,最右推导是规范推导,所以 最左规约是规范规约。

    LR 分析法根据当前分析栈中的符号串和向右顺序查看输入串的 k 个符号就可以唯一确定分析器的动作是移进还是归约、利用那个产生式进行归约。

    当没有指明 k 是几的时候,默认为 1

    (三)文法的拓广?

    文法的拓广是对现有文法,添加一个 S’,并对文法进行展开。

    例如:

    对于文法 G[E]:
    E → E+T|T
    T → T*F|F
    F → i|(E)

    可以把它拓广为

    文法 G[E’]:
    E’ → E
    E → E+T|T
    T → T*F|F
    F → i|(E)

    此时可能会有疑问,不就是加了个开始符号,有什么意义呢?为什么要再加个开始符号呢?

    加开始符号是为了状态的表示,这样原来的 S 会成为右部,可以表示 .S 和 S.

    那同一非终结符的右部有多种情况为什么不展开呢?

    这里是说拓广文法,是添加开始符号,可以展开可以不展开,但是一般默认要展开,一般一道题不会只让求拓广文法,而是为了后面。一般题目中是说 “求该文法的拓广文法并编号”,此时请一定要展开。展开后应该是这样:

    1.E’→E
    2.E → E+T
    3.E → T
    4.T → T*F
    5.T → F
    6.F → i
    7.F → (E)

    (四)什么是项目?项目有哪些分类?等价状态?

    上面提到拓广文法,展开,以及编号。

    先看例题:

    对于文法 G[S]:
    S → vI:T
    I → I,i
    I → i
    T → r

    可以把它拓广并编号,如下:

    文法 G[S’]:
    1.S’ → S
    2.S → vI:T
    3.I → I,i
    4.I → i
    5.T → r

    它的全部 LR(0) 项目,如下:

    1.S’ → .S
    2.S’ → S.
    3.S → .vI:T
    4.S → v.I:T
    5.S → vI.:T
    6.S → vI:.T
    7.S → vI:T.
    8.I → .I,i
    9.I → I.,i
    10.I → I,.i
    11.I → I,i.
    12.I → .i
    13.I → i.
    14.T → .r
    15.T → r.

    对上面 LR(0) 项目进行分类

    类型包含特点
    规约项目2, 7, 11, 13, 15. 在右部的末尾
    接收项目2. 在开始符号的末尾
    移进项目3, 5, 9, 10, 12, 14. 后面跟着终结符,表移进
    待约项目1, 4, 6, 8. 后面跟着非终结符,表等待后面非终结符的规约,简称待约

    谁和谁是等价状态?

    例如:

    待约项目 4 即 S→v.I:T 它的含义是等待栈顶规约出 I,但尚未识别对应 I 的那些句柄的任何符号;

    项目 8 即 I→.I,i 和项目 12 即 I→.i 的含义也是期待栈顶形成 I 的句柄,所以这三个项目的含义是一样的,即 4, 8, 12 三个状态是等价的。

    同理:项目 6 即 S → vI:.T 和项目 14 即 T → .r 也是等价的

    为什么它们是等价状态?怎么判断等价状态?

    上面有说因为他们表示的含义是一样的,并且会发现等价肯定涉及至少一个待约项目,以及一个 . 在最左端的移进项目。

    这是因为,待约项目是 . 后面跟非终结符,这个 . 是在非终结符的前面;当存在该非终结符的产生式时,且 . 在最左端的时候。因为 . 在最左端,其实也是相当于在该非终结符的前面。所以是一个等价的状态。

    (五)LR 分析表介绍

    LR 分析器的关键部分是 分析表的构造。分析表有以下几种:

    规范的 LR 分析表:

    • LR(0),能力最弱,局限性较大,但理论上最重要。
    • LR(1),它功能最强,但代价也最大。

    简单的 LR 分析表:

    • 简称 SLR ,最容易实现,但功能最弱。

    向前看的 LR 分析表:

    • 简称 LALR,功能和代价处于前两者之间,适用于绝大多数程序语言的文法

    总结: LR(0) 功能最弱,功能弱是说当文法中产生式比较复杂,出现某些问题时,无法解决。这些问题一部分可以由 SLR 分析法解决。但还有一部分 SLR 解决不了,可以用 LR(1) 来解决。

    (六)关于 “展望

    在规范归约过程中,一方面记住已移进和归约出的整个符号串,即记住 “历史”,另一方面根据所用的产生式推测未来可能碰到的输入符号,即对未来进行 “展望”。

    当一串貌似句柄的符号串呈现于分析栈的顶端时,根据所记载的 “历史” 和 “展望” 材料,来确定栈顶的符号串是否构成句柄。

    为了记住分析的 “历史” 和汇集 “展望” 的信息,LR 分析法这样处理:

    将归约过程的 “历史” 和 “展望” 材料综合抽象成某些状态,存放在一个状态栈中,栈中每个状态都概括了从分析开始直到某一归约阶段的全部“历史”和“展望”材料。

    LR(1) 分析法这样处理:

    首先,明白了在 LR(1) 分析法中展望是为了解决其他分析法解决不了的问题。简单的说就是,状态会出现冲突,我们不能只通过后 1 个输入串符号,直接确定选用哪个产生式,这是严重的错误。

    所以 展望(向前搜索符) 是通过展望后面的内容,所以展望对应的终结符,应该 属于该非终结符的 FOLLOW 集(确切的说,属于 FOLLOW 集中的具体哪个个终结符,应该根据产生式的推导过程确定,通过语法树来分析,是比较直观的方法。也可以直接通过求该非终结符后的 FIRST 集来确定,但要注意是对谁求 FIRST 集,可表示为 FIRST(βa),例题中会提到),来帮助唯一确定选择产生式。

    拓展注:这里提到的 FOLLOW 集和 FIRST 集不是冲突的,因为我们要求的向前搜索符时 FOLLOW 集的子集,有时候不能确定,所以用 FIRST(βa), β 表示由谁哪个非终结符推导的,这个非终结符的后面的剩余串,a 表示它上一个状态中的向前搜索符。它俩拼接起来的串,对该串求 FIRST 集。
    那么可能会有疑问,利用上一个状态?那第一个状态呢?第一个状态是固定的 S’→S,#
    其实 # 就是 S 的 FOLLOW 集中的唯一的元素,它也是开始符号的向前搜索符
    所以说 FOLLOW 集和 FIRST(βa) 是都可以求的,FIRST(βa) 是准确的向前搜索符,它是 FOLLOW 集的一部分

    在 LR(1) 中,用

    状态, 终结符
    例如:S’ → # (#表示开始符号FOLLOW集会提到那个符号,有的地方用 $,是一样的 )

    这种形式是表式展望,终结符就是展望的后面的终结符,具体的下面例题中还会提到。

    (七)终极例题 - LR(1) 分析表的构造

    给定文法 G[S]:

    S→L=R | R
    L→*R | id
    R→L

    回答以下问题:

    (1)文法的拓广并编号
    (2)LR(1) 项目集规范族所对应的识别活前缀的 DFA
    (3)构造 LR(1) 分析表

    解析:

    1)文法的拓广并编号:

    拓广文法 G[S’]:

    (0)S’→S
    (1)S→L=R
    (2)S→R
    (3)L→*R
    (4)L→id
    (5)R→L

    2)LR(1) 项目集规范族所对应的识别活前缀的 DFA*

    这里就涉及到 “展望” 这个知识点了

    向前搜索符的 FIRST 集求法:

    求法 FIRST(βa)

    • β 表示由谁哪个非终结符推导的,这个非终结符的后面的剩余串
    • a 表示它上一个状态中的向前搜索符。

    对于 I0
    首先 S’ → .S, # 这个是固定的,就是第一个状态的核心项目
    下面对 S 求向前所有符都没问题,都是 #
    到了 L→.*R,这里,求向前搜索符,使用 FIRST(βa)
    应该是求 FIRST(=R#) 所以就是 = 了

    为什么是 =R#?

    因为 β 表示由谁哪个非终结符推导的,这里就是上面状态【S→.L=R, #】这个非终结符 L 的后面的剩余串是 =R,a 表示它上一个状态中的向前搜索符,就是 #,拼接起来就是 =R#。
    在这里插入图片描述
    (图片来源:中国大学慕课 -《编译原理》哈尔滨工业大学 陈老师)

    该 DFA 有穷自动机的解释:

    (1)这样表示形式就是自动机,每个方框表示一个状态,从 I0 到 I13 所以共有 14 个状态。
    (2)每个状态中包含的多个项目,都是等价的。
    (3)每个项目中逗号后面的终结符或者 # 表示展望的终结符。
    (4)关于画出 DFA 的步骤:

    • 以 I0 为例,首先对于 0 号产生式 S’ → S,可知应该有 S’ → .S 和 S’ → S. 两个状态,因为 S’ 是开始符号,展望是属于 FOLLOW 集的,展望应该是 #,可以得出 S’ → .S, #
    • 因为 .S 表示等待规约出 S 的状态。并且 S→L=R,所以 .S 和 .L=R 是两个等价的状态。但需要注意的是此时的 FOLLOW 集应该 S 的 FOLLOW 集,而不是 L 的,也不 R 的
    • 同理,因为有 S→R,则 .S 和 .R 是两个等价的状态。
    • 有了 .R,应该继续去找 R 为左部的产生式,因为有 R→L,所以 .S 和 .L 是两个等价的状态。
    • 注意: 在找 R 的展望终结符时,展望 是通过展望后面的内容,所以展望对应的终结符,应该 属于该非终结符的 FOLLOW 集(确切的说,属于 FOLLOW 集中的具体哪个个终结符,应该根据产生式的推导过程确定,通过语法树来分析,是最直观的方法)
      在这里插入图片描述
      (图片来源:中国大学慕课 -《编译原理》哈尔滨工业大学 陈老师)

    可以看出来 R 的展望应该有两种情况,一个是 =,一种是 #

    但此时,我们通过 S → R 找到的 R,所以应该是 #

    不断循环通过,将 . 后移,判断下一个状态,找出等价状态,直到判断完成。

    3)构造 LR(1) 分析表

    根据自动机即可构造 LL(1) 分析表:
    在这里插入图片描述
    (图片来源:中国大学慕课 -《编译原理》哈尔滨工业大学 陈老师)

    LL(1) 分析表解释补充:

    (1)内容 LL(1) 分析表 = 动作表 (ACTION) + 状态转移表(GOTO)

    (2)动作表 中的每一个元素 ACTION[S,a] 规定了当 栈顶状态 为 S,且面临输入符号 a 时应采取的动作。根据自动机中的终结符边可判断。

    (3)状态转换表 中的每一个元素 GOTO[S,x] 规定了当状态 S 面对文法符号位 x 时的下一个状态。根据自动机中的非终结符边可判断。

    (4)动作表 的列对应所有终结符加上 #

    (5)状态转换表 的列对应所有非终结符,不包括 S’,因为 S 就是开始符号,S’ 是为了使 “接收状态” 易于识别,所引入的。

    (6)动作表 中例如:

    • ACTION[0, *] 的 S4 表示移进,入栈,就是当前状态为 0,当输入串为 *,则将状态 4 移进状态栈,将 * 移进文法符号栈
    • ACTION[5, =] 的 r4 表示符合产生式 4,将栈顶符号 id 规约为产生式左部
    • acc 表示接收

    (7)状态转换表 中例如:

    • GOTO[0, S] 的 数字为 1 表示转入 1 状态,置当前文法符号栈顶为 S,栈顶状态为 1

    (8)构造 LL(1) 分析表的步骤,重要 !!!:

    • 确定对应行 ,行就是所有状态

    • 确定对应列 ,列有两部分 ACTION 表和 GOTO 表,ACTION 表中列是所有终结符,以及 #。 GOTO 表的对是所有非终结符,不包括 S’

    • !!!GOTO 表的构造:判断当前输入串,如果存在自动机的边,且边为非终结符就把状态编号填入 GOTO 表

    • !!!ACTION 表的构造:

      • 查找该状态中是否有 . 在最后的状态,如果有先根据向前搜索符确定哪一列,再用 rn,填入表示,r 的含义是规约,n 表示的是产生式的序号;如果没有则说明没有没有 r
      • 判断是否存在该状态输出的边,如果存在则用 Sn 表示,S 表示移进,入栈,n 表示下一个状态的序号

    (9)上面也更深入的了解了展望的意义,首先,展望是存在一个状态中的,终结符,对应的应该为是当前等价的状态,操作也就应该是移进。如果是自动机的边,就是说不是当前状态了,所以对应的是规约。


    总结

    易错点:

    • 展望对应的终结符 是通过展望后面的内容,所以展望对应的终结符,应该 属于该非终结符的 FOLLOW 集(确切的说,属于 FOLLOW 集中的具体哪个个终结符,应该根据产生式的推导过程确定,通过语法树来分析,是最直观的方法)
    • 各教材描述可能存在差异,但思想是相同的
      • 比如 $ 和 #
      • 比如展望终结的表示方法,有的分开写,有的直接用或
    展开全文
  • 层次分析法步骤及源代码

    千次阅读 2020-08-04 23:18:03
    层次分析法步骤及matlab源码层次分析法步骤例题matlab源代码 层次分析法步骤 建立层次结构模型。在深入分析实际问题的基础上,将有关的各个因素按照不同属性自上而下地分解成若干层次,同一层的诸因素从属于上一层...

    层次分析法步骤及matlab源码

    层次分析法步骤

    1. 建立层次结构模型。在深入分析实际问题的基础上,将有关的各个因素按照不同属性自上而下地分解成若干层次,同一层的诸因素从属于上一层的因素或对上层因素有影响,同时又支配下一层的因素或受到下层因素的作用。最上层为目标层,通常只有1个因素,最下层通常为方案或对象层,中间可以有一个或几个层次,通常为准则或指标层。当准则过多时(譬如多于9个)应进一步分解出子准则层。

    2. 构造成对比较阵。从层次结构模型的第2层开始,对于从属于(或影响)上一层每个因素的同一层诸因素,用成对比较法和1—9比较尺度构造成对比较阵,直到最下层。(由自己主观意识构建比较矩阵

    3. 计算权向量并做一致性检验。对于每一个成对比较阵计算最大特征根及对应特征向量,利用一致性指标、随机一致性指标和一致性比率做一致性检验。若检验通过,计算比较矩阵最大特征值,并将其所对应的特征向量(归一化后)作为权向量:若不通过,需重新构造成对比较阵。(由于按照理论建立得比较矩阵为正反矩阵,但通常来说,比较矩阵表示的是两两之间在自己心中重要性的比较,因此可能会造成矩阵不是正反矩阵,因此要对其一致性进行检验

    4. 计算组合权向量并做组合一致性检验。计算最下层对目标的组合权向量,并根据公式做组合一致性检验,若检验通过,则可按照组合权向量表示的结果进行决策,否则需要重新考虑模型或重新构造那些一致性比率较大的成对比较阵。

    例题

    挑选合适的工作。经双方恳谈,已有三个单位表示愿意录用某毕业生。该生根据已有信息建立了一个层次结构模型,如下图所示。
    在这里插入图片描述
    准则层的判断矩阵如表1所示。

    表1
    AB1B2B3B4B5B6
    B111141 1 2 \frac{1}{2} 21
    B211241 1 2 \frac{1}{2} 21
    B31 1 2 \frac{1}{2} 21153 1 2 \frac{1}{2} 21
    B4 1 4 \frac{1}{4} 41 1 4 \frac{1}{4} 41 1 5 \frac{1}{5} 511 1 3 \frac{1}{3} 31 1 3 \frac{1}{3} 31
    B511 1 3 \frac{1}{3} 31311
    B6222331
    表2

    在这里插入图片描述

    matlab源代码

    clc,clear
    fid=fopen('txt3.txt','r');
    n1=6;n2=3;
    a=[];
    for i=1:n1
        tmp=str2num(fgetl(fid));
        a=[a;tmp]; %读准则层判断矩阵
    end
    for i=1:n1
        str1=char(['b',int2str(i),'=[];']);
        str2=char(['b',int2str(i),'=[b',int2str(i),';tmp];']);
        eval(str1);%将文本变为代码并执行
        for j=1:n2
            tmp=str2num(fgetl(fid));
            eval(str2); %读方案层的判断矩阵
        end
    end
    ri=[0,0,0.58,0.90,1.12,1.24,1.32,1.41,1.45]; %一致性指标
    [x,y]=eig(a); %求解特征向量及特征根
    lamda=max(diag(y));%查找最大的特征根
    %查找最大特征根的值作为权值
    num=find(diag(y)==lamda);
    w0=x(:,num)/sum(x(:,num));
    %一致性检验
    cr0=(lamda-n1)/(n1-1)/ri(n1)
    if(cr0<0.1)
        fprintf('一致性检验通过\n')
        %对下一层进行一致性检验及总权值排序
        RI = [];
        for i=1:n1
            [x,y]=eig(eval(char(['b',int2str(i)])));
            lamda=max(diag(y));
            num=find(diag(y)==lamda);
            w1(:,i)=x(:,num)/sum(x(:,num));
            cr1(i)=(lamda-n2)/(n2-1)/ri(n2);
            RI = [RI ri(n2)];
        end
        cr=cr1*w0/(RI*w0)
        if(cr<0.1)
            fprintf('层次总排序一致性检验通过\n')
            cr1, ts=w1*w0
        end
    end
    

    其中,纯文本文件txt3.txt中的数据格式如下:

    1 1 1 4 1 1/2 
    1 1 2 4 1 1/2 
    1 1/2 1 5 3 1/2 
    1/4 1/4 1/5 1 1/3 1/3 
    1 1 1/3 3 1 1 
    2 2 2 3 3 1 
    1 1/4 1/2 
    4 1 3 
    2 1/3 1 
    1 1/4 1/5 
    4 1 1/2 
    5 2 1 
    1 3 1/3 
    1/3 1 1/7 
    3 7 1 
    1 1/3 5 
    3 1 7 
    1/5 1/7 1 
    1 1 7 
    1 1 7 
    1/7 1/7 1 
    1 7 9 
    1/7 1 1 
    1/9 1 1
    
    展开全文
  • 构造 LL(1) 分析表的步骤与例题解析 易错点及扩展: 1、求每个产生式的 SELECT 集 2、注意区分是对谁 FIRST 集 FOLLOW 集 3、开始符号的 FOLLOW 集包含 # 4、各集合对对应的对象以及含义 集 对象 含义 FIRST...

    《编译原理》构造 LL(1) 分析表的步骤 - 例题解析

    易错点及扩展:

    1、求每个产生式的 SELECT 集

    2、注意区分是对谁 FIRST 集 FOLLOW 集

    3、开始符号的 FOLLOW 集包含 #

    4、各集合对对应的对象以及含义

    对象含义
    FIRST 集是对产生式右部右部内部的所有终结符集,可能为 ε
    FOLLOW 集是对产生式左部(非终结符)非终结符后面紧跟的终结符,可能为 #,和该非终结符推导出的右部无关(因为LL(1)文法不包含递归,所以右部不会再有该非终结符,所以不能通过该右部判断该非终结符后跟集合)
    SELECT 集是对产生式需要考虑产生式右部的不同情况,进一步确定是根据 FIRST 集还是 FOLLOW 集

    5、SELECT 集的定义
    注: 注意区分 FIRST 集 FOLLOW 时是对 α 还是 A

    给定文法 G,对于产生式 A→α,α ∈ V*,则可选集 SELECT(A→α) 有:
    (1)若 α ≠ ε,且 α ≠+> ε,则 SELECT(A→α) = FIRST(α)
    (2)若 α ≠ ε,但 α =+> ε,则 SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)
    (3)若 α = ε,则 SELECT(A→α) = FOLLOW(A)

    描述:

    • 第 1 条是,当 α ≠ ε,且通过1次或多次推不出 ε,SELECT(A→α) = FIRST(α)

    • 第 2 条是,当 α ≠ ε,但 α 经有限步可推出 ε,SELECT(A→α) = FIRST(α) ∪ FOLLOW(A)
      (注意是一个 α,一个 A)

    • 第 3 条是,当 α = ε,SELECT 集就等于左部 A 的 FOLLOW 集

      解题时,先判断是否为 ε,是则用第(3)条,否则再判断能否通过1次或多次推出 ε,是则用第(2)条,否则用第(1)条

      求 FIRST,FOLLOW,SELECT 集详细例题可参考:
      《编译原理》-用例题理解-自顶向下语法分析及 FIRST,FOLLOW,SELECT集,LL(1)文法

    6、LL(1) 分析表的结构

    分析表是一个二维数组 M[A,a],其中 A 表示行,是非终结符,a 表式列是终结符或 #。

    • M[A,a] 中若有产生式,表明 A 可用该产生式推导,以求与输入符号 a 匹配。
    • M[A,a] 中若为空,表明 A 不可能推导出与 a 匹配的字符串

    7、LL(1) 分析表构造方法:

    • 若 a∈SELECT(A→α),则把 A→α 加至 M[A, a] 中
    • 把所有无定义的 M[A, a] 标上“出错标志”。为了使表简化,表中空白处为出错

    例题:

    已给文法:

    G[S]: S→aH
    H→aMd
    H→d
    M→Ab
    M→ε
    A→aM
    A→e

    (1)求 SELECT 集
    (2)证明文法是 LL(1) 文法
    (3)构造 LL(1) 分析表

    解析:

    求 SELECT 集:

    产生式FIRST 集FOLLOW 集SELECT 集
    S→aH 分析: 对该产生式,可知 FIRST(aH) = {a};也可知应将 FOLLOW(S) = {#} 加到 FOLLOW(H) 中{a}FOLLOW(S) = {#}SELECT(S→aH) = FIRST(aH) = {a}
    H→aMd 分析: 对该产生式,可知 FIRST(aMd) = {a};也可知应将 d 加到 FOLLOW(M) 中{a}FOLLOW(H) = {#}SELECT(H→aMd) = FIRST(aMd) = {a}
    H→d 分析: 对该产生式,可知 FIRST(d) = {d}{d}SELECT(H→d) = FIRST(d) = {d}
    M→Ab 分析: 对该产生式,可知 FIRST(Ab) = {a, e};也可知应将 b 加到 FOLLOW(A) 中{a, e}FOLLOW(M) = {b, d}SELECT(M→Ab) = FIRST(Ad) = {a, e}
    M→ε{ε}SELECT(M→ε) = FOLLOW(M) ={d, b} 求法: 由产生式 H→aMd,所以将 d 放入 FOLLOW(M);由产生式 A→aM 所以把 FOLLOW(A) 加至 FOLLOW(M) 中。同理 求 FOLLOW(A),由产生式 M→Ab,FOLLOW(A) = {b}。故 FOLLOW(M) = {d ,b}
    A→aM 分析: 对该产生式,可知 FIRST(aM) = {a};也可知应将 FOLLOW(A) 加到 FOLLOW(M) 中{a}FOLLOW(A) = {b}SELECT(A→aM) = FIRST(aM) = {a}
    A→e 分析: 对该产生式,可知 FIRST(e) = {e}{e}SELECT(A→e) = FIRST(e) = {e}

    证明文法是 LL(1) 文法(2 分)

    定理:同一非终结符的 SELECT 交集为空集,则该文法是 LL(1) 文法:

    • SELECT(H→aMd) ∩ SELECT(H→d) = ∅

    • SELECT(M→Ab) ∩ SELECT(M→ε) = ∅

    • SELECT(A→aM) ∩ SELECT(A→e) = ∅

    所以该文法是 LL(1) 文法

    构造 LL(1) 分析表(1 分)

    分析表是一个二维数组 M[A,a],其中 A 表示行是非终结符,a 表式列是终结符或 #。根据 SELECT 集构造分析表:

    abde
    SS→aH
    HH→aMdH→d
    MM→AbM→εM→εM→Ab
    AA→aMA→e
    展开全文
  • 回溯的解题步骤与例子解析

    万次阅读 2016-06-19 18:28:31
    回溯有“通用解题”之称。用它可以系统地搜索问题的所有解。回溯是一个既带有系统性又带有跳跃性的搜索算法。  在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当...

        回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。

        在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。(其实回溯法就是对隐式图的深度优先搜索算法)。若用回溯法求问题的所有解时,要回溯到根,且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,只要搜索到问题的一个解就可以结束。

     

    1.回溯法的解题步骤

    (1)针对所给问题,定义问题的解空间;

    (2)确定易于搜索的解空间结构;

    (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

     

    2.子集树与排列树

    下面的两棵解空间树是回溯法解题时常遇到的两类典型的解空间树。

    (1)当所给问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间树称为子集树。例如从n个物品的0-1背包问题(如下图)所相应的解空间树是一棵子集树,这类子集树通常有2^n个叶结点,其结点总个数为2^(n+1)-1。遍历子集树的算法需Ω(2^n)计算时间。


    (2)当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。例如旅行售货员问题(如下图)的解空间树是一棵排列树,这类排列树通常有n!个叶结点。遍历子集树的算法需Ω(n!)计算时间。



    用回溯法搜索子集树的一般算法可描述为:

    	/**
    	 * output(x)     记录或输出得到的可行解x
    	 * constraint(t) 当前结点的约束函数
    	 * bount(t)      当前结点的限界函数
    	 * @param t  t为当前解空间的层数
    	 */
    	void backtrack(int t){
    		if(t >= n)
    			output(x);
    		else
    			for (int i = 0; i <= 1; i++) {
    				x[t] = i;
    				if(constraint(t) && bount(t))
    					backtrack(t+1);
    			}
    	}

    用回溯法搜索排列树的一般算法可描述为:

    	/**
    	 * output(x)     记录或输出得到的可行解x
    	 * constraint(t) 当前结点的约束函数
    	 * bount(t)      当前结点的限界函数
    	 * @param t  t为当前解空间的层数
    	 */
    	void backtrack(int t){
    		if(t >= n)
    			output(x);
    		else
    			for (int i = t; i <= n; i++) {
    				swap(x[t], x[i]);
    				if(constraint(t) && bount(t))
    					backtrack(t+1);
    				swap(x[t], x[i]);
    			}
    	}

    3.回溯法的应用例子

    (a)子集树

    (为了便于描述算法,下列方法使用了较多的全局变量

    I.输出集合S中所有的子集,即limit为all;

    II.输出集合S中限定元素数量的子集,即limit为num

    III.输出集合S中元素奇偶性相同的子集,即limit为sp。

    public class Subset {
    		
    	private static int[] s = {1,2,3,4,5,6,7,8};
    	private static int n = s.length;
    	private static int[] x = new int[n];
    	
    	/**
    	 * 输出集合的子集
    	 * @param limit  决定选出特定条件的子集
    	 * 注:all为所有子集,num为限定元素数量的子集,
    	 *    sp为限定元素奇偶性相同,且和小于8。
    	 */
    	public static void all_subset(String limit){
    		switch(limit){
    		case "all":backtrack(0);break;
    		case "num":backtrack1(0);break;
    		case "sp":backtrack2(0);break;
    		}
    	}
    	
    
    	/**
    	 * 回溯法求集合的所有子集,依次递归
    	 * 注:是否回溯的条件为精髓
    	 * @param t
    	 */
    	private static void backtrack(int t){
    		if(t >= n)
    			output(x);
    		else
    			for (int i = 0; i <= 1; i++) {
    				x[t] = i;
    				backtrack(t+1);
    			}
    		
    	}
    	
    	/**
    	 * 回溯法求集合的所有(元素个数小于4)的子集,依次递归
    	 * @param t
    	 */
    	private static void backtrack1(int t){
    		if(t >= n)
    			output(x);
    		else
    			for (int i = 0; i <= 1; i++) {
    				x[t] = i;
    				if(count(x, t) < 4)
    					backtrack1(t+1);
    			}
    		
    	}
    
    	/**
    	 * (剪枝)
    	 * 限制条件:子集元素小于4,判断0~t之间已被选中的元素个数,
    	 *        因为此时t之后的元素还未被递归,即决定之后的元素
    	 *        是否应该被递归调用
    	 * @param x
    	 * @param t
    	 * @return
    	 */
    	private static int count(int[] x, int t) {
    		int num = 0;
    		for (int i = 0; i <= t; i++) {
    			if(x[i] == 1){
    				num++;
    			}
    		}
    		return num;
    	}
    
    	/**
    	 * 回溯法求集合中元素奇偶性相同,且和小于8的子集,依次递归
    	 * @param t
    	 */
    	private static void backtrack2(int t){
    		if(t >= n)
    			output(x);
    		else
    			for (int i = 0; i <= 1; i++) {
    				x[t] = i;
    				if(legal(x, t))
    					backtrack2(t+1);
    			}
    		
    	}
    	
    	/**
    	 * 对子集中元素奇偶性进行判断,还需元素的数组和小于8
    	 * @param x
    	 * @param t
    	 * @return
    	 */
    	private static boolean legal(int[] x, int t) {
    		boolean bRet = true;   //判断是否需要剪枝
    		int part = 0;  //奇偶性判断的基准
    		
    		for (int i = 0; i <= t; i++) {  //选择第一个元素作为奇偶性判断的基准
    			if(x[i] == 1){
    				part = i;
    				break;
    			}
    		}
    		
    		for (int i = 0; i <= t; i++) {
    			if(x[i] == 1){
    				bRet &= ((s[part] - s[i]) % 2 == 0);
    			}
    				
    		}
    
    		int sum = 0;
    		for(int i = 0; i <= t; i++){
    			if(x[i] == 1)
    				sum += s[i];
    		}
    		bRet &= (sum < 8);
    		    
    		return bRet;
    	}
    
    
    	/**
    	 * 子集输出函数
    	 * @param x
    	 */
    	private static void output(int[] x) {
    		for (int i = 0; i < x.length; i++) {
    			if(x[i] == 1){
    				System.out.print(s[i]);
    			}
    		}
    		System.out.println();	
    	}
    
    }


    (b) 排列树

    (为了便于描述算法,下列方法使用了较多的全局变量)

    I.输出集合S中所有的排列,即limit为all;

    II.输出集合S中元素奇偶性相间的排列,即limit为sp。

    public class Permutation {
    
    	private static int[] s = {1,2,3,4,5,6,7,8};
    	private static int n = s.length;
    	private static int[] x = new int[n];
    	
    	/**
    	 * 输出集合的排列
    	 * @param limit  决定选出特定条件的子集
    	 * 注:all为所有排列,sp为限定元素奇偶性相间。
    	 */
    	public static void all_permutation(String limit){
    		switch(limit){
    		case "all":backtrack(0);break;
    		case "sp":backtrack1(0);break;
    		}
    	}
    	
    
    	/**
    	 * 回溯法求集合的所有排列,依次递归
    	 * 注:是否回溯的条件为精髓
    	 * @param t
    	 */
    	private static void backtrack(int t){
    		if(t >= n)
    			output(s);
    		else
    			for (int i = t; i < n; i++) {
    				swap(i, t, s);
    				backtrack(t+1);
    				swap(i, t, s);
    			}
    		
    	}
    
    	/**
    	 * 回溯法求集合中元素奇偶性相间的排列,依次递归
    	 * @param t
    	 */
    	private static void backtrack1(int t){
    		if(t >= n)
    			output(s);
    		else
    			for (int i = t; i < n; i++) {
    				swap(i, t, s);
    				if(legal(x, t))
    					backtrack1(t+1);
    				swap(i, t, s);
    			}
    		
    	}
    	
    	/**
    	 * 对子集中元素奇偶性进行判断
    	 * @param x
    	 * @param t
    	 * @return
    	 */
    	private static boolean legal(int[] x, int t) {
    		boolean bRet = true;   //判断是否需要剪枝
    		
    		//奇偶相间,即每隔一个数判断奇偶相同
    		for (int i = 0; i < t - 2; i++) {
    			bRet &= ((s[i+2] - s[i]) % 2 == 0);
    		}
    		    
    		return bRet;
    	}
    
    
    	/**
    	 * 元素交换
    	 * @param i
    	 * @param j
    	 */
    	private static void swap(int i, int j,int[] s) {
    		int tmp = s[i];
    		s[i] = s[j];
    		s[j] = tmp;
    	}
    	
    	/**
    	 * 子集输出函数
    	 * @param x
    	 */
    	private static void output(int[] s) {
    		for (int i = 0; i < s.length; i++) {
    				System.out.print(s[i]);
    		}
    		System.out.println();	
    	}
    }


    参考文献:

    1. 《算法设计与分析


    展开全文
  • 社会网络分析法包括中心性分析、子群分析、角色分析和基于置换的统计分析等。 另外,该软件包有很强的矩阵分析功能,如矩阵代数和多元统计分析。它是最流行的,也是最容易上手、最适合新手的社会网络分析软件。
  • 汉诺塔C语言步骤解析

    千次阅读 多人点赞 2020-03-05 19:39:52
    汉诺塔问题在C语言中一般采用递归来写,假设有A、B、C三根棒,A棒放着若干个圆盘,将其移动到C棒上,中途可在B棒中暂时放置圆盘。 分析: (1) 如果只有一个圆盘,则把该圆盘从A棒移动到C棒 (2) 如果圆盘数量n>...
  • 数学建模层次分析法步骤解读,专注于解决数学建模问题,文档免费,欢迎下载,解决问题 数学建模层次分析法步骤解读,专注于解决数学建模问题,文档免费,欢迎下载,解决问题 数学建模层次分析法步骤解读,...
  • 机器学习 | AHP层次分析法

    千次阅读 多人点赞 2019-05-15 20:39:47
    3 AHP层次分析法的实现3.1 步骤3.2 实际的例子3.2.1 背景3.2.2 Step1 构建层次结构模型3.2.3 Step2 构造成对比较矩阵3.2.4 Step3 一致性检验3.2.5 Step4 确定权重和最优方案3.3 Python实现3.3.1 直接将打分ok的excel...
  • 过程FMEA步骤五:风险分析

    千次阅读 2020-06-08 15:04:01
    目的 过程风险分析的目的是通过严重度、频度和...• 产品或过程优化步骤的基础 有两种不同的控制类型:当前预防控制和当前探测控制。 当前预防控制(PC) 过程策划 定义:当前预防控制有助于优化过程策划,从而最大程度
  • 目录语法分析:自上而下分析知识背景计算海明校验码步骤一:计算校验码位数步骤二:确定校验组步骤三:计算校验码的值得出海明校验码利用海明校验码校验数据其他总结 知识背景 百度百科: “语法分析是编译过程的一...
  • 简述回归分析法

    千次阅读 2019-06-11 17:08:30
    清楚了回归分析的目的后,下面我们以回归分析预测法的步骤来说明什么是回归分析法: 1.根据预测目标,确定自变量和因变量 明确预测的具体目标,也就确定了因变量。如预测具体目标是下一年度的销售量,那么销售量Y...
  • 本文介绍了根据上下文无关文法,使用预测分析法生成语法分析树的步骤
  • 用Excel做回归分析的详细步骤

    千次阅读 2018-05-30 21:08:00
    清楚了回归分析的目的后,下面我们以回归分析预测法的步骤来说明什么是回归分析法:  回归分析是对具有因果关系的影响因素(自变量)和预测对象(因变量)所进行的数理统计分析处理。只有当变量与因变量确实存在...
  • 简单优先分析法 1.基本概念 通过语法树来理解这三个概念更加简单: 文法G1[S]: S→AB A→bB A→Aa B→a B→Sb 语法树 短语:若S=*=&gt;αAδ且A=+=&gt;β,则称β是相对于非终结符A的句型αβδ...
  • 穷举(枚举)实例解析

    千次阅读 2020-09-13 19:55:57
    穷举在c\c++编程上的实际运用 生活中我们常常会遇到很多看似简单,却比较繁琐的问题。例如写出1000以内的素数集合,破解三位数密码的无数次尝试等比较繁琐的工作,但是计算机处理这类反反复复的作业,却比较轻松。...
  • MATLAB-层次分析法

    千次阅读 2019-08-23 11:35:47
    AHP (Analytic Hierarchy Process)层次分析法是美国运筹学家T. L. Saaty教授于二十世纪70年代提出的一种实用的多方案或多目标的决策方法,是一种定性与定量相结合的决策分析方法。常被运用于多目标、多准则、多要素...
  • 因子分析建模步骤

    千次阅读 2018-01-27 18:02:31
    转载一:http://blog.csdn.net/guang_mang/article/details/78724142 转载二:http://blog.csdn.net/ITzym/article/details/70140429
  • 清楚了回归分析的目的后,下面我们以回归分析预测法的步骤来说明什么是回归分析法:  回归分析是对具有因果关系的影响因素(自变量)和预测对象(因变量)所进行的数理统计分析处理。只有当变量与因变量...
  • 拆卸程序是整个鲁班锁计算机分析程序的核心部分它的主要思路是优先考虑 拆出一根柱当待拆的柱组拆出一根柱或 1 组柱时下一步还是试拆一根 柱 以下是我根据我在鲁班锁结构分析法用的思路做的拆卸程序的逻辑过程 ...
  • 常用算法设计方法详细解析(含源代码) 算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务...、回溯 六、贪婪 七、分治 八、动态规划
  • Retrofit2源码分析:架构全面解析

    千次阅读 2018-08-30 16:14:38
    目录   一、概述 ...、源码分析 1、Retrofit的内部成员变量 2、Retrofit内部类Builder 3、创建Retrofit实例 4、Builder.build()方法 5、retrofit.create() 6、loadServiceMethod() ...
  • 针对传统的协议解析方法在...该算法包括预处理、交叉引用分析、协议帧重构和语义提取等步骤,具有针对性强、通用性好的特点。将算法实现后应用于某组态软件,能够得到正确的分析结果,证明了该方法的正确性与有效性。
  • 8.1.4 系统评价决策模型的步骤 8.1.5 评价指标的规范化处理 1.评价指标类型的一致化处理 2.评价指标的无量纲化 8.1.6 系统评价模型的建立 1.线性加权综合(加权和) 2.非线性加权综合(加权积) 3....
  • 导读: 跟随世界主流经济学的研究范式,数量化研究已经成为了中国经济研究的主流。...一篇严谨的经济学论文,一般需要三个基本的要素:视点(Perspective),参照(Benchmark),分析方法 (Analytical Tool)(...
  • 首先推导了功能梯度材料位移 形式的平衡方程和边界条件,然后阐述了线功能梯度材料结构分析的基本步骤和数值原理。该方法的基本思 想是通过有限差分将问题的控制方程半离散为定义在沿梯度方向离散节线上的常微分...
  • 什么是网络分析法  网络分析法(ANP)是美国匹兹堡大学的T.L.Saaty教授于1996年提出的一种适应非独立的递阶层次结构的决策方法,它是在层次分析法(Analytic Hierarchy Process,简称AHP)的基础上发展而形成的一种新...
  • source性能分析工具Oprofile详细解析

    千次阅读 2010-01-28 16:39:00
    Oprofile Introduction 内容概要 * oprofile 介绍 * .oprofile 安装及 Linux 内核编译 * oprofile 使用 * oprofile 实例演示及性能分析 * gprof 介绍 * Kprof 分析 * gcov 简介 一、 oprofile 介绍 oprofile 是 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,507
精华内容 15,402
关键字:

内容分析法五步骤解析