精华内容
下载资源
问答
  • 2019-06-21 15:33:45

    复习编译原理,理了一下几个基本概念的判断思路:

    1. 根据句型画语法推导树。

    2. 判断短语:短语是语法推导树中每一个非叶子节点作为根的子树,从左到右的叶子节点。注意:短语可以是非终结符。

    3. 判断直接短语:直接短语在短语中找,它们作为子树的叶子节点,根节点必须是它们所有节点的父亲节点。

    4. 判断句柄:最左直接短语。

    5. 判断素短语:素短语递归定义,满足三个条件:

        ① 素短语是短语。

        ② 素短语中必须包含至少一个终结符。

        ③ 素短语中不能包含其它素短语。

    6. 最左素短语:在语法推导树中最靠左的素短语。

     

    更多相关内容
  • 短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ β,则称 β 是句型 αβδ 相对于非终结符 A 的短语。语法树: 在语法树中表示所有分支结点对应子树,短语即子树...

    (一)明确概念:
    名称 概念
    短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ β,则称 β 是句型 αβδ 相对于非终结符 A 的短语。语法树: 在语法树中表示所有分支结点对应子树,短语即子树叶子对应的符号。注: 子树包括语法树本身,及句型本身也可以称为短语。
    直接短语 定义: 若 S ⇒* αβδ,且文法中包含产生式 A → β,则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。语法树: 在语法树中表示为该短语只有上下相邻父子两代
    句柄 “可规约串”,句柄对应某个产生式的右部,是某个,但不是任意一个。作为一种规约对象,句柄表示最左直接短语。语法树: 在语法树上,则表示为最左边的只包含相邻父子节点的短语(最左直接短语)
    素短语 定义: 是指一个短语至少包含一个终结符,并且除它自身之外不再包含其他素短语
    最左素短语 定义: 最左素短语就是句型最左边的素短语,是算符优先分析法的规约对象。语法树: 通过语法树分析时,要注意先判断是否为素短语,再找相对最左端的素短语。
    例题1:求短语,直接短语,句柄
    给定句型:

    TP↑(TF)

    给定文法:

    G[T]:
    T → T*F|F
    F → F↑P|P
    P → (T)|i

    解析:
    推导步骤为:

    T ⇒ TF
    ⇒ T
    F↑P
    ⇒ TP↑P
    ⇒ T
    P↑(T)
    ⇒ TP↑(TF)

    画出语法树为:

    在这里插入图片描述

    该语法树的 5 个子树及 5 个短语为:
    在这里插入图片描述

    求直接短语方法: 该句型的语法树有两颗直接子树(最左边的两颗子树),由这两颗直接子树的叶子结点组成的符号串(或者说只包含两层的子树叶子结点对应的),就是句型的两个直接短语,直接短语 P 和 T*F。

    求句柄: 因为 P 相对 T*F,在语法树上的左侧,所以句柄是 P

    最终结果:

    类型 内容
    短语 5 个 P,TF,(TF),P↑(TF),TP↑(TF)
    直接短语 2 个 P,T
    F
    句柄 P
    例题二:求素短语,最左素短语
    给定句型:

    FF↑a

    给定文法:

    G[T]:
    T → T*F|F
    F → F↑P|P
    P → (T)|i

    解析:
    推导步骤为:

    T ⇒ TF*
    ⇒ TFF
    ⇒ TF↑\F*
    ⇒ TF↑a*

    画出语法树:
    在这里插入图片描述

    最终结果:

    根据定义可以找出素短语有:

    类型 内容
    素短语 2 个 F↑,a
    最左素短语 F↑

    展开全文
  • 句柄最左素短语、可归前缀

    千次阅读 2018-06-23 13:48:02
    句柄最左素短语、可归前缀 1.定义 句柄左直接短语(一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语); 最左素短语:处于矩形左边的素短语(素短语是包含有终结符的短语); 可归...

    句柄、最左素短语、可归前缀

    1.定义

    • 句柄:最左直接短语(一个句型的语法树中任一子树叶结点所组成的符号串都是该句型的短语);
    • 最左素短语:处于矩形最左边的素短语(素短语是包含有终结符的短语);
    • 可归前缀:规范句型的一个前缀,这种前缀包含句柄且不包含句柄之后的任何符号;
      总结一下:目测可归前缀就是句柄(当前要归约的字符串),最左素短语是包含终结符的最左边的子树。

    2.示例

    给定文法G[E]:
    E→AaA
    A→B∣BBa
    B→d∣ca
    句型Bacacaa的句柄是( ) ,最左素短语是( ) ,可归前缀是( ) ,

    2.1做出语法树

    根据句子规约,结合文法。
    这里写图片描述

    2.2由图可知

    句柄:B(A→B)
    素短语: ca(B→ca), a(A→a)
    最左素短语:ca(B→ca)
    可归前缀:B(A→B)

    展开全文
  • 短语 每棵子树的叶子节点的拼接(整棵树也算) 直接短语短语的子集,区别是这里的子树只能有一个叶子节点 句柄 左边的直接短语 例子

    短语

    在这里插入图片描述
    每棵子树的叶子节点的拼接(整棵树也算)

    直接短语

    在这里插入图片描述
    是短语的子集,区别是这里的子树只能有一个叶子节点

    句柄

    在这里插入图片描述
    最左边的直接短语

    例子

    在这里插入图片描述

    素短语

    在这里插入图片描述
    是短语的子集,至少含一个终结符,并且不包含其他素短语

    最左素短语

    最左边的素短语

    例子

    在这里插入图片描述

    展开全文
  • 短语、句柄、素短语、最左素短语

    万次阅读 多人点赞 2015-04-07 21:31:39
    很久没写博客了=== 今天写一发=== 关于编译原理 语法树 句柄 简单短语 短语 的区分,通过两个例子来理解概念以及方法: ...句型(Sd(T)db)是S的一个推导,其中___是句柄;____是最左素短语;____是该句型的
  • 《编译原理》求短语,直接短语,句柄,素短语,最左素短语 - 例题解析 笔记 (一)明确概念: 名称 概念 短语 定义: 若 S 为文法 G 的开始符号,αβδ 是该文法的一个句型,即 S ⇒* αβδ,且有 A ⇒+ ...
  • 先画出语法树(最左推导): 短语:在语法树中,先找出所有的非终结符,然后用叶子节点去替换他们,最后得到的集合就是短语的集合。 这里的非终结符从上到下为:E、E、T、E、T、F、T、T、F。我们用叶子节点全部替换...
  • 短语 直接短语 句柄 素短语 区别短语直接短语句柄素短语 短语 一个节点的叶节点的组合即为短语 直接短语 一个节点的子节点没有子节点,则其子节点构成的短语即为直接短语(即子节点均为叶节点) 句柄 左边的直接...
  • --句型与句子 如果 S⇒*α,α∈(VT∪VN)*,则称α是G的一个句型(sentential form) 一个句型中既可以包含终结符,又可以...如果S αAβ且Aγ,则称γ是句型αγβ的相对于非终结符A的短语 。 如果SαAβ 且...
  • 编译原理:短语、直接短语、句柄最左素短语 短语: 同一子树的所有叶子(终结符类型的)节点 直接短语: 同一父节点一步推出的所有叶子节点,即末端的单一子树(不拼凑)的所有叶节点 句柄左直接短语 素...
  • 2、实例二求解短语、直接短语、句柄素短语和最左素短语详解 3、实例三求解短语、直接短语、句柄素短语和最左素短语详解 4、实例四求解短语,直接短语,句柄详解 叮嘟!这里是小啊呜的学习课程资料整理。好记性...
  • 分析句型(T,(^,a)),求全部的短语、直接短语和句柄。 S=>(T)=>(T,S)=>(T,(T))=>(T,(T,S))=>(T,(S,S))=>(T,(^,S))=>(T,(^,a)) 语法树图如下: 短语:(T,(^,a)) 、T,(^,a...
  • 编译原理 —— 短语、直接短语、素短语和句柄

    万次阅读 多人点赞 2019-03-17 13:11:54
    如果 βββ 中至少含有一个终结符,而且除它自身之外不再含任何更小的素短语,那么称 βββ 为 素短语 题目 令文法 G1G_1G1​ 为: ①S−>(L)∣aS∣a①S->(L)|aS|a①S−>(L)∣aS∣a...
  • 素短语,最左素短语-编译原理

    万次阅读 多人点赞 2017-01-01 15:58:27
    素短语,最左素短语-编译原理
  • 消除无用符合无用产生式、单一产生式、空符产生式
  • 语法树,短语,直接短语句柄

    千次阅读 2019-09-26 01:10:10
    分析句型(T,(^,a)),求全部的短语、直接短语和句柄。 推导步骤为: S=> ( T ) =>( T , S )=> ( T ,( T ) )=> ( T ,( T , S ) )=> ( T ,( T , a ) )=> ( T ,( S , a ) )...
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄。 其实简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 ...
  • 句柄的概念:一个句型的最左直接短语汇称为该句型的句柄 例子1: E->T|E+T T->F|T*F F-> (E) | i 给出句型T*F+i的右推导。 1.首先通过右推导(也叫规范推导): E=>E+T=>E+F=>E+i=&
  • γ,则称γ是句型αγβ的相对于变量A的直接(简单)短语 最左直接短语叫做句柄 其实简单的判断方法直接画出语法树了。 文法 S->(L)|aS|a L->L,S|S 分析(S,(a)) 1.先画出语法树 2.判断短语 一个句型的...
  • 素短语的概念:它是一个递归的定义,至少含有一个终结符,并且除它自身之外不再含任何更小的素短语,所谓最左素短语就是处于句型左边的素短语的短语。而一个算符优先文法G的任何句型的最左素短语是满足以下条件的...
  • 对输入符号串自左向右进行扫描,并将输入符逐个移入一个栈中,边移入边分析,一旦栈顶符号串形成某个句型的句柄时,就用该产生式的左部非终结符代替相应右部的文法符号串,这称为归约。 重复这一过程,直到栈中只剩...
  • 短语、直接短语、句柄素短语

    千次阅读 2014-04-17 16:55:11
    短语、直接短语、句柄素短语、 以此为例子: 先画出语法树,例:   S   / / | \   ( T )   / | \   T d S   / | \ |

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 345
精华内容 138
关键字:

句柄和最左素短语