woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

FIRST集和FOLLOW集

明天就考试了,在这里纠结这个问题。

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

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

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

如: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)中【在这里,如果FirstP)中有空字符,那么就要把左部(假设是S)的FollowS)送入到FollowU)中。还有就是Follow集中是没有空字符的】。

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

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

PsFollow集比First要复杂一点,不过记住算法多做练习就是小Case啦。

 

posted on 2010-02-22 18:20 肥仔 阅读(3654) 评论(2)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: FIRST集和FOLLOW集  回复  更多评论   

看起来简单易懂~~~
2011-06-28 08:04 | yunbang11573

# re: FIRST集和FOLLOW集  回复  更多评论   

很不错
2012-01-06 21:00 | df

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理