精华内容
下载资源
问答
  • 构造预测分析表 编译原理 C语言版本 构造预测分析表 编译原理 C语言版本
  • 编译原理构造预测分析表

    千次阅读 多人点赞 2018-04-11 15:59:08
    构造预测分析表算法 对于文法G的每个产生式A -> α ,进行如下处理: 1. 对于FIRST(α)中的每个终结符号α,将A -> α加入到M[A , a]中。 2. 如果 ε 在FIRST(α) 中,那么对于FOLLOW(A)中的每个...

    构造预测分析表算法

    对于文法G的每个产生式A -> α ,进行如下处理:
    1. 对于FIRST(α)中的每个终结符号a,将A -> α加入到M[A , a]中。
    2. 如果 ε 在FIRST(α) 中,那么对于FOLLOW(A)中的每个终结符号b,将A -> α加入到M[A , b]中。如果 ε 在FIRST(α) 中,且$在FOLLOW(A)中,也将A -> α加入到M[A , $]中。
    在完成上面的操作之后,如果没有M[A , a]中没有产生式,那么将M[A , a]设置为error(我们通常采用一个空条目表示)

    举个小栗子

    文法G[E]:
    1. E -> TE’
    2. E’-> +E| ε
    3. T -> FT’
    4. T’-> T| ε
    5. F -> PF’
    6. F’ -> *F’| ε
    7. P -> (E) | a | b | ∩
    证明该文法是LL(1)文法

    (1) FIRST集合(这里只求非终结符号的FIRST集合)

    FIRST(E) = { ( , a , b , ∩ }
    FIRST(T) = { ( , a , b , ∩ }
    FIRST(F) = { ( , a , b , ∩ };
    FIRST(P) = { ( , a , b , ∩ };
    FIRST(E’) = { + , ε };
    FIRST(T’) = { ( , a , b , ∩ , ε };
    FIRST(F’) = { * , ε };

    (2) FOLLOW集合

    FOLLOW(E) = FOLLOW(E’) + { ) ,$}
    FOLLOW(E’) = FOLLOW(E) = { ) ,\$ }
    FOLLOW(T) = FIRST(E’) / ε +FOLLOW(T’) = { + , ) , \$ }
    FOLLOW(T’) = FOLLOW(T) = { + , ) , \$ }
    FOLLOW(F) = FIRST(T’) / ε +FOLLOW(T) = { ( , a , b , ∩ , + , ) ,\$ }
    FOLLOW(F’) = FOLLOW(F) = { ( , a , b , ∩ , + , ) ,\$ }
    FOLLOW(P) = FIRST(F’) / ε + FOLLOW(F) = {* , ( , a , b , ∩ , + , ), \$ }

    注:关于FIRST集合和FOLLOW集合的计算,请参照这篇博客编译原理之计算FIRST集合和FOLLOW集合

    (3) 构造预测分析表

    • 终结符号:+ , * , ( , ) , a , b , ∩ , $

    • 非终结符号:E , E’ , T , T’ , F , F’ , P

    nonter\terminal+*()ab$
    EE -> TE’E -> TE’E -> TE’E -> TE’
    E’E’-> +EE’-> εE’-> ε
    TT -> FT’T -> FT’T -> FT’T -> FT’
    T’T’-> εT’-> TT’-> εT’-> TT’-> TT’-> TT’-> ε
    FF -> PF’F -> PF’F -> PF’F -> PF’
    F’F’ -> εF’ -> *F’F’ -> εF’ -> εF’ -> εF’ -> εF’ -> εF’ -> ε
    PP -> (E)P -> aP -> bP ->∩

    练习

    对于下面的文法:
    1. Expr -> -Expr
    2. Expr -> (Expr) | Var ExprTail
    3. ExprTail -> -Expr | ε
    4. Var -> id VarTail
    5. VarTail -> (Expr) | ε

    (1) 构造LL(1)分析表。
    (2) 给出对句子id - - id((id))的分析过程。

    思考十分钟再往下看哦~~~

    (1)首先计算FIRST集合

    FIRST(Expr) = {- , ( } + FIRST(Var ) = {- , ( , id}
    FIRST(ExprTail ) = {- , ε }
    FIRST(Var ) = { id }
    FIRST(VarTail) = {( , ε }

    在计算FOLLOW集合

    FOLLOW(Expr) = FOLLOW(ExprTail ) + { ) , $} = { ) , $}
    FOLLOW(ExprTail ) = FOLLOW(Expr) = { ) , $}
    FOLLOW(Var) = FIRST(ExprTail) / ε + FOLLOW(Expr) = {- , ) , $}
    FOLLOW(VarTail) = FOLLOW(Var) = {- , ) , $}

    构造预测分析表

    • 终结符号:- , id , ( , ) , $

    • 非终结符号:Expr , ExprTail , Var , VarTail

    nonter\ter-id()$
    ExprExpr -> -ExprExpr -> Var ExprTailExpr -> (Expr)
    ExprTailExprTail -> -ExprExprTail ->εExprTail ->ε
    VarVar -> id VarTail
    VarTailVarTail -> εVarTail -> (Expr)VarTail -> εVarTail -> ε

    (2) 句子id - - id((id))的分析过程

    分析栈输入串所用产生式
    $ Exprid - - id((id))$
    $ ExprTail Varid - - id((id))$Expr -> Var ExprTail
    $ ExprTail VarTail idid - - id((id))$Var -> id VarTail
    $ ExprTail VarTail- - id((id))$
    $ ExprTail- - id((id))$VarTail -> ε
    $ Expr -- - id((id))$ExprTail -> -Expr
    $ Expr- id((id)) $
    $ Expr -- id((id)) $Expr -> -Expr
    $ Exprid((id))$
    $ ExprTail Varid((id))$Expr -> Var ExprTail
    $ ExprTail VarTail idid((id))$Var -> id VarTail
    $ ExprTail VarTail((id))$
    $ ExprTail ) Expr (((id))$VarTail -> (Expr)
    $ ExprTail ) Expr(id))$
    $ ExprTail ) ) Expr ((id))$VarTail -> (Expr)
    $ ExprTail ) ) Exprid))$
    $ ExprTail ) ) ExprTail Varid))$Expr -> Var ExprTail
    $ ExprTail ) ) ExprTail VarTail idid))$Var -> id VarTail
    $ ExprTail ) ) ExprTail VarTail))$
    $ ExprTail ) ) ExprTail))$VarTail -> ε
    $ ExprTail ) )))$ExprTail ->ε
    $ ExprTail ))$
    $ ExprTail$
    $$ExprTail ->ε
    展开全文
  • 不用first 和follow集怎么做啊,老师规定不能用,我没有币啊![图片说明](http://forum.csdn.net/PointForum/ui/scripts/csdn/Plugin/001/face/24.gif)不都要算selected集吗
  • 预测分析表构造 预测分析器的总控程序对于不同的 LL(1)LL(1)LL(1) 文法都是相同的,而预测分析表对于不同的 LL(1)LL(1)LL(1) 文法是不相同的。 产生式的 SELECT 集 由 SELECT 集得预测分析表 分析过程 ...

    预测分析法

    预测分析法也称为LL(1)分析法,是确定的自上而下分析法,这种分析法要求文法是LL(1)文法。



    预测分析表的构造

    预测分析器的总控程序对于不同的 L L ( 1 ) LL(1) LL(1) 文法都是相同的,而预测分析表对于不同的 L L ( 1 ) LL(1) LL(1) 文法是不相同的。

    产生式的 SELECT 集
    在这里插入图片描述
    由 SELECT 集得预测分析表
    在这里插入图片描述

    分析过程

    在这里插入图片描述

    展开全文
  • 本程序采用预测分析表方法实现词法分析,实现简单,便于理解!
  • TL,其中FIRST(E)={+,-},那么在分析表中[E,+]和[E,-]对于的框框就应该填写E–>TL。 注意:如果FIRST(E)中含有空集。emm,还是同样假设有E–>TL,其中FIRST(E)={+,-,空},其FOLLOW(E)={mod,*},那么[E,+]...

    方法

    在这里插入图片描述
    我的理解:

    1. 首先分别计算出FIRST()和FOLLOW()集合
    2. 在对每一个非终结符的FIRST()依次分析,假设有E–>TL,其中FIRST(E)={+,-},那么在分析表中[E,+]和[E,-]对于的框框就应该填写E–>TL。
    3. 注意:如果FIRST(E)中含有空集。emm,还是同样假设有E–>TL,其中FIRST(E)={+,-,空},其FOLLOW(E)={mod,*},那么[E,+]和[E,-]对于的框还是E–>TL,而这里还需要加上[E,mod]和[E, 乘法 ] 对应的框为

    举例说明

    文法为:
    在这里插入图片描述
    FIRST()和FOLLOW()集合为:
    在这里插入图片描述
    按照上述的方法构造的预测分析表为:
    在这里插入图片描述

    展开全文
  • LL(1)文法-构造预测分析表 复习笔记 LL(1)文法分析是语法分析中比较重要的一个方法,其中比较重要的环节是构造预测分析表。 当然,在构造预测分析表之前,需要掌握两个集合的求法:FIRST集合和FOLLOW集合。 注意:...

    LL(1)文法-构造预测分析表

    复习笔记

    LL(1)文法分析(自上而下)是语法分析中比较重要的一个方法,其中比较重要的环节是构造预测分析表。

    当然,在构造预测分析表之前,需要掌握两个集合的求法:FIRST集合和FOLLOW集合。

    注意:下文的测试用例中使用的文法如下:
    E→TE’
    E’→+TE’|ε
    T→FT’
    T’→*FT’|ε
    F→(E)|i

    FIRST集合的求法

    • 方法步骤如下:

    1、X∈VT (终结符号集合)
    FIRST(X)={X}(即:终结符号的FIRST集仍然是其本身)。

    2、X∈VN(非终结符号集合)
    (1)若X→a…, 则 a 加入FIRST(X);若有X→ε,则ε加入 FIRST(X)(a是X可以推出的首个终结符号)。
    (2)若有X→Y…, 且Y∈VN ,则FIRST(Y)中非ε元素全部加入FIRST(X);
    (3)若有X→Y1Y2Y3…YK ,且Yi∈VN ,ε∈FIRST(Yj) ,则FIRST(Yi)中非ε元素加入FIRST(X);若所有的FIRST(Yj)都含有ε,则ε加入FIRST(X)。

    • 例解:

    求非终结符号的First集:
    First(E)={(,i}
    First(E’)={+,ε}
    First(T)={(,i}
    First(T’)={*,ε}
    First(F)={(,i}

    FOLLOW集合的求法

    我个人觉得FOLLOW集合比FIRST集合的求解难度较大,并且也涉及到FIRST集合的运算。

    • FOLLOW的求解步骤
      (1)对于文法开始符号S, 将#(作用:结束标记)加入FOLLOW(S)。
      (2)若有A→ αBβ,则FIRST(β)-{ε}加入FOLLOW(B)。
      (3)若有A→αB, 或A→αBβ且ε ∈ FIRST(β),则将FOLLOW(A) 加入FOLLOW(B)中。

    NOTE
    (1)FOLLOW集合中没有 ε;
    (2)以上步骤中的α,β是任意的文法符号串。

    • 例解

    非终结符的Follow集:
    Follow(E)={),#}
    Follow(E’)={),#}
    Follow(T)={+,),#}
    Follow(T’)={+,),#}
    Follow(F)={*,+,),#}

    构造预测分析表

    预测分析程序由分析栈(倒序),分析表和分析程序三部分组成,其中分析表的构成与文法有关,是比较重要的。其要求的文法是LL(1)文法,所以先补充一下LL(1)文法的知识。

    LL(1)文法

    • LL(1)文法的条件
      (1)文法不含左递归
      (2)对文法中每一个非终结符A的各个产生式的FIRST集合两两不相交。
      (3)对文法中每一个非终结符A,若存在某个FIRST集合包含ε,则: First(A)∩ Follow(A)=∅。

    以上三个条件可以用来判断一个文法是不是LL(1)文法。一般情况下,我们见到的文法不全是不含有左递归的文法,但是我们可以通过一定的方式消除左递归,继而寻求方法构造一个LL(1)文法。

    • 消除左递归

    1、消除直接左递归
    在这里插入图片描述

    2、消除间接左递归
    将间接左递归转为直接左递归进行消除

    3、消除文法中全部的左递归
    在这里插入图片描述

    构造预测分析表

    一般来说, 预测分析表可以用矩阵M表示:
    (1)矩阵的行表示非终结符号
    (2)列表示终结符号和#(结束符号)
    (3)矩阵元素M(U,a)表示非终结符号U+输入符号a时,向下推导所应该采取的产生式。

    • 构造预测分析表的步骤
      (1)对每个终结符a∈FIRST(a),将A->a加到M[A,a]中。
      (2)如果ε∈FIRST(a),则对于任何b∈FOLLOW(A),将A->a加到M[A,b]中。
      (3)表格填完后仍然空缺的位置表明没有对应的产生式,即:非终结符号U+输入符号a无法继续向下推导,所以将空缺的位置填写错误信息。(一般默认,可以不写)

    • 例解:
      在这里插入图片描述
      (1)求文法对应的FIRST和FOLLOW集合
      在这里插入图片描述
      (2)构造预测分析表初步:
      行(非终结符号):E,E’,T,T’,F
      列(终结符号):i,+,*,(,),#
      填写:非终结符号U+输入符号a->下一条执行的产生式
      在这里插入图片描述
      (3)预测分析表如下:
      在这里插入图片描述

    展开全文
  • 【20200416】编译原理课程课业打卡十六之构造预测分析表&递归下降分析程序 一、课业打卡十六之构造预测分析表&递归下降分析程序 二、知识巩固 1、预测分析表构造步骤 2、预测分析表【LL(1)分析表】的构造实例详解 3...
  • 编译原理实验,词法分析,LL1自顶向下的递归分析,LL1文法自动构造预测分析表、消除左递归、提取公共左因子以及预测分析,功能比较完善,有什么bug欢迎指正,Main文件中有几个测试案例,里面打开的文件都是工程...
  • 预测分析程序的构造判断是否为合法表达式预测当前句型中,出现A,若A有多个产生式,需预测选择哪个产生式,从而可不要回溯,形如A→α|BA \to \alpha|B 使用的是以下的结构其中左边那个叫做parsing stackparsing \...
  • 编译原理上机实验系列(3) 一、预习准备 1.实验目的 掌握First和Follow集合求法,深入理解LL(1)文法分析过程。 2.实验要求 根据文法求出First和Follow集合 3.实验环境 Xcode 二、实验过程 1.实验步骤 (1)First集 ...
  • 编译原理预测分析表一篇解决你所有问题(c++版) 实验 预测分析表方法 一、实验目的 理解预测分析表方法的实现原理。 二、实验内容 编写一通用的预测法分析程序,要求有一定的错误处理能力,出错后能够使程序继续...
  • 用C语言实现了一个简单的预测分析程序。将预测分析表中的推导过程用二维函数指针的形式存储,对于给定的文法能正确推导并给出过程.若不能推导出来,程序会运行错误(暂未做处理)
  • 预测分析表构造0 目录9 语法分析-自上而下分析39.2 预测分析表构造9.2.1 课堂重点9.2.2 测试与作业10 下一章 0 目录 9 语法分析-自上而下分析3 9.2 预测分析表构造 9.2.1 课堂重点 9.2.2 测试与...
  • 编译原理的预测分析程序,对于初始输入的文法构造其FIRST集合和FOLLOW集合,再根据这两个集合构造预测分析表
  • 编译原理LL(1)预测分析表构造

    千次阅读 2020-05-10 15:59:28
    LL(1)预测分析表构造算法 对文法G的每个产生式A->α执行如下步骤: (1)对每个a∈First(α),把 A->α加入M[A,a] (2)若 ε∈First(α),则对任何b∈Follow(A) ,把 A->ε加 至M[A,b]...
  • 如何构造预测分析表 1.什么是语法分析器? 先上一张图,虽然不太清晰,但大致能够看出语法分析器在编译程序中的位置。说白了,它就是按文法的产生式,识别输入串是否为一个句子。 可以简单地将语法分析分为...
  • 编译原理预测分析法实验报告(C语言)编 译 原 理实验报告目的要求构造文法的语法分析程序,要求采用预测分析法对输入的字符串进行语法分析。加深对预测分析LL(1)分析法的理解和掌握。实验内容对文法G进行语法分析,...
  • 没想到,内容还是很多的,幸亏分了好多部分,要不然没法理解。 ******************************************************* ...
  • 编译原理】LL1分析表构造

    千次阅读 2020-08-14 16:06:05
    首先要构造FIRST集合和FOLLOW集合 例题 首先构造比较简单的FIRST集合 上面两个的FIRST集合非常好计算 直接提取候选式最开始的终结符即可 答案 接着构造它的FIRST集合 我们去找F的fist集合 由于F的fist集合...
  • 编译原理:LL(1)文法 语法分析器(预测分析表法)

    万次阅读 多人点赞 2016-05-22 20:54:31
    设计要求:对于任意输入的一个LL(1)文法,构造预测分析表,并对指定输入串分析其是否为该文法的句子。 思路:首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法,再根据FIRST和FOLLOW集合构造预测分析表,并...
  • 编译原理--预测分析法 由java编写 从求first集 follow集合开始 构造预测分析表 输出分析过程 完整过程!!!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,002
精华内容 2,400
关键字:

编译原理构造预测分析表