虾米俊

虾米俊的博客


  • 首页

  • 标签

  • 分类

  • 归档

  • 搜索

怎样求First集与Follow集

发表于 2015-03-05 | 分类于 计算机基础 | | 阅读次数:
字数统计: 831 字 | 阅读时长 ≈ 3 分钟

文法:

S→ABc
A→a\ ε
B→b\ ε
First集合求法:
能 由非终结符号推出的所有的开头符号或可能的ε,但要求这个开头符号是终结符号。如此题A可以推导出a和ε,所以FIRST(A)={a,ε};同理 FIRST(B)={b,ε};S可以推导出aBc,还可以推导出bc,还可以推导出c,所以FIRST(S)={a,b,c}
Follow集合的求法:
紧跟随其后面的终结符号或#。但文法的识别符号包含#,在求的时候还要考虑到ε。 具体做法是把所有包含你要求的符号的产生式都找出来,再看哪个有用。 Follow(S)={#}
如求A的,产生式:S→ABc A→a\ ε ,但只有S→ABc 有用。跟随在A后年的终结符号是FIRST(B)={b,ε},当FIRST(B)的元素为ε时,跟随在A后的符号就是c,所以 Follow(A)={b,c} 同理Follow(B)={c}

一,要知道什么是终结符和非终结符

终结符:通俗的说就是不能单独出现在推导式左边的符号,也就是说终结符不能再进行推导。

非终结符:不是终结符的都是非终结符。(非男即女,呵呵)

如:A——>B,则A是非终结符。

(一般书上终结符用小写,非终结符用大写。)

二,文法产生语言句子的基本思想:从识别符号(开始符)开始,把当前产生的符号串中的非终结符替换为相应规则右部的符号串,直到全部由终结符组成。

三,FIRST集求法

​ First集合最终是对产生式右部的字符串而言的,但其关键是求出非终结符的First集合,由于终结符的First集合就是它自己,所以求出非终结符的First集合后,就可很直观地得到每个字符串的First集合。

\1. 直接收取:对形如U->a…的产生式(其中a是终结符),把a收入到First(U)中

\2. 反复传送:对形入U->P…的产生式(其中P是非终结符),应把First(P)中的全部内容传送到First(U)中【意思就是只需要把第一个非终结符的First集传过去~这个地方是要注意的地方,也是难点】。

四,FOLLOW集的求法

​ Follow集合是针对非终结符而言的,Follow(U)所表达的是句型中非终结符U所有可能的后随终结符号的集合,特别地,“#”是识别符号的后随符。注意Follow集合是从开始符号S开始推导。

  1. 直接收取:注意产生式右部的每一个形如“…Ua…”的组合,把a直接收入到Follow(U)中。因a是紧跟在U后的终结符。

  2. 直接收取:对形如“…UP…”(P是非终结符)的组合,把First(P)直接收入到Follow(U)中【在这里,如果First(P)中有空字符,那么就要把左部(假设是S)的Follow(S)送入到Follow(U)中。还有就是Follow集中是没有空字符的】。

  3. 直接收取:若S->…U,即以U结尾,则#∈Follow(U)

  4. 反复传送:对形如U->…P的产生式(其中P是非终结符),应把Follow(U)中的全部内容传送到Follow(P)中。

语法推导树之短语,直接短语,句柄

发表于 2015-03-05 | 分类于 计算机基础 | | 阅读次数:
字数统计: 374 字 | 阅读时长 ≈ 1 分钟

概念

  • 短语:任意一颗子树中,如果根结点经过若干步才推导出了叶子结点,则这些叶子结点组成的序列就是相对于这棵子树的短语
  • 直接短语:属于短语,只不过不能经过若干步的推导了,必须一步就能推导出来叶子结点来,这些叶子结点组成的序列才是相对于这颗子树的直接短语
  • 句柄:属于直接短语,它是这些有直接短语的子树中最左边的那颗子树的直接短语

例子

找出下面的这颗语法推导树的短语,直接短语,句柄。

  1. 找出这棵树的所有子树

  1. 找出每一颗子树的短语

第1棵:a1ɛb1b2a2a3

第2棵:ɛb1b2

第3棵:a2a3

第4棵:a1

第5棵:ɛ

第6棵:b1

第7棵:b2

第8棵:a2

  1. 找出每一颗子树的直接短语

第1棵:因为这棵树的叶子结点是经过若干步推导出来的没有一步就推导出来的,所以没有直接短语

第2棵:同上

第3棵:同上,虽然a3是直接推导出来的,但是a2不是,所以它们组成的序列不能说是直接短语

第4棵:a1

第5棵:ɛ

第6棵:b1

第7棵:b2

第8棵:a2

  1. 从这些直接短语中找那个排在最左边的直接短语,即句柄,这道题的句柄就是a1
1…89
虾米俊

虾米俊

雨会下雨会停,这是不变的道理

82 日志
15 分类
11 标签
GitHub
© 2018 — 2019 虾米俊 | Site words total count: 47.8k