先算后套的编译原则 C++ 实现
最编程
2024-04-12 08:57:42
...
设文法G[S]=(VN,VT,P,S),则首字符集为:
FIRST(α)={a | αaβ,a∈VT,α,β∈V *}。
若αε,ε∈FIRST(α)。
由定义可以看出,FIRST(α)是指符号串α能够推导出的所有符号串中处于串首的终结符号组成的集合。所以FIRST集也称为首符号集。
设α=x1x2…xn,FIRST(α)可按下列方法求得:
令FIRST(α)=Φ,i=1;
- 若xi∈VT,则xi∈FIRST(α);
- 若xi∈VN;
① 若εFIRST(xi),则FIRST(xi)∈FIRST(α);
② 若ε∈FIRST(xi),则FIRST(xi)-{ε}∈FIRST(α);
- i=i+1,重复(1)、(2),直到xi∈VT,(i=2,3,…,n)或xi∈VN且若εFIRST(xi)或i>n为止。
当一个文法中存在ε产生式时,例如,存在A→ε,只有知道哪些符号可以合法地出现在非终结符A之后,才能知道是否选择A→ε产生式。这些合法地出现在非终结符A之后的符号组成的集合被称为FOLLOW集合。下面我们给出文法的FOLLOW集的定义。
设文法G[S]=(VN,VT,P,S),则
FOLLOW(A)={a | S… Aa …,a∈VT}。
若S…A,#∈FOLLOW(A)。
由定义可以看出,FOLLOW(A)是指在文法G[S]的所有句型中,紧跟在非终结符A后的终结符号的集合。
FOLLOW集可按下列方法求得:
- 对于文法G[S]的开始符号S,有#∈FOLLOW(S);
- 若文法G[S]中有形如B→xAy的规则,其中x,y∈V *,则FIRST(y)-{ε}∈FOLLOW(A);
- 若文法G[S]中有形如B→xA的规则,或形如B→xAy的规则且ε∈FIRST(y),其中x,y∈V *,则FOLLOW(B)∈FOLLOW(A);
求First集合的流程图:
求follow集合的流程图:
代码
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define MAX 50
int NONE[MAX] = { 0 };
string strings; //产生式
string Vn; //非终结符
string Vt; //终结符
string first[MAX]; //存放每个终结符的first集
string First[MAX]; //存放每个非终结符的first集
string Follow[MAX]; //存放每个非终结符的follow集
int N; //产生式个数
struct STR
{
string left;
string right;
};
void rec(STR *p) //识别Vn和Vt
{
int i, j;
for (i = 0;i < N;i++) //第i个产生式
{
for (j = 0;j < (int)p[i].left.length();j++)//左侧
{
if ((p[i].left[j] >= 'A'&&p[i].left[j] <= 'Z')) //左侧第j个字母是大写
{
if (Vn.find(p[i].left[j])>100) //Vn里没找到返回很大的值
Vn += p[i].left[j];
}
else
{
if (Vt.find(p[i].left[j])>100) //小写字母放Vt
Vt += p[i].left[j];
}
}
for (j = 0;j < (int)p[i].right.length();j++)//右侧
{
if (!(p[i].right[j] >= 'A'&&p[i].right[j] <= 'Z'))
{
if (Vt.find(p[i].right[j])>100)
Vt += p[i].right[j];
}
else
{
if (Vn.find(p[i].right[j]) > 100)
Vn += p[i].right[j];
}
}
}
}
void getlr(STR *p, int i) //将产生式的左右部分别放入left,right
{
int j;
for (j = 0;j<strings.length();j++)
{ if (strings[j] == '-'&&strings[j + 1] == '>')
{ p[i].left = strings.substr(0, j);
p[i].right = strings.substr(j + 2, strings.length() - j);
}
}
}
string Letter_First(STR *p, char ch)
{
int t;
if (!(Vt.find(ch)>100)) //在Vt里,first就是自身
{
first[Vt.find(ch)] = ch;
return first[Vt.find(ch) - 1];
}
if (!(Vn.find(ch) > 100)) //在Vn中的第i个
{
for (int i = 0;i < N;i++) //第i个产生式
{
if (p[i].left[0] == ch) //左侧字符是ch
{
if (!(Vt.find(p[i].right[0])>100))
{
if (First[Vn.find(ch)].find(p[i].right[0]) > 100) //右侧第一个字符是Vt,加入Vni的first集合中
{
First[Vn.find(ch)] += p[i].right[0];
}
}
if (p[i].right[0] == '#')
{
if (First[Vn.find(ch)].find('#') > 100) //右侧第一个字符是空,加入Vni的first集合中
{
First[Vn.find(ch)] += '#';
}
}
if (!(Vn.find(p[i].right[0]) > 100)) //右侧第一个字母是Vn
{
if (p[i].right.length() == 1) //只有一个字母
{
string ff;
ff = Letter_First(p, p[i].right[0]); //把右侧字母的first集合加入到左侧字母中
for (int k = 0;k < ff.length();k++)
{
if (First[Vn.find(ch)].find(ff[k])>100)
{
First[Vn.find(ch)] += ff[k];
}
}
}
else //多个字母都是Vn
{
for (int j = 0;j < p[i].right.length();j++)
{
string TT;
TT = Letter_First(p, p[i].right[j]);
if (!(TT.find('#')>100) && (j + 1) < p[i].right.length()) //右侧非末位字母的first集里有空
{
for (int t = 0;t < TT.length();t++)
{
if (TT[t] != '#'&&First[Vn.find(ch)].find(TT[t])>100) //右侧字母的无空first集加入到Vni的first集
First[Vn.find(ch)] += TT[t];
}
//cout << p[i].right[j]<<"already ";
}
else //集合里无空或有空但是最后一个,直接加入
{
for (t = 0;t < TT.length();t++)
{
if (First[Vn.find(ch)].find(TT[t])>100)
First[Vn.find(ch)] += TT[t];
}
break;
}
}
}
}
}
}
return First[Vn.find(ch)];
}
}
string Letter_Follow(STR *p, char ch)
{
int t, k;
NONE[Vn.find(ch)]++; //扫过1遍
if (NONE[Vn.find(ch)] == 2)
{
NONE[Vn.find(ch)] = 0;
return Follow[Vn.find(ch)]; //第二次扫到,直接返回
}
for (int i = 0;i < N;i++)
{
for (int j = 0;j < p[i].right.length();j++)
{
if (p[i].right[j] == ch) //右侧扫描到A
{
if (j + 1 == p[i].right.length()) //A是末尾 S->aA
{
string gg;
gg = Letter_Follow(p, p[i].left[0]);
// NONE[Vn.find(p[i].left[0])] = 0; //NONE[S]=0 A->aA NONE[A]置0重扫
for (int k = 0;k < gg.length();k++)
{
if (Follow[Vn.find(ch)].find(gg[k])>100) //S的follow加入到A中
{
Follow[Vn.find(ch)] += gg[k];
}
}
}
else //A不是末尾 S->AB
{
string FF;
for (int m = j + 1;m < p[i].right.length();m++)
{
string TT;
TT = Letter_First(p, p[i].right[m]);
if (!(TT.find('#') > 100) && (m + 1) < p[i].right.length()) //A后面的Vn的first集有空且不是最后一个
{
for (t = 0;t < TT.length();t++)
{
if (FF.find(TT[t])>100 && TT[t] != '#') //去掉空加入
FF += TT[t];
}
}
else { //first集没有空或者最后一个有空
for (t = 0;t < TT.length();t++)
{
if (FF.find(TT[t])>100)
FF += TT[t];
}
break; //没空的直接break
}
}
if (FF.find('#') > 100)
{
for (k = 0;k < FF.length();k++)
{
if (Follow[Vn.find(ch)].find(FF[k])>100)
Follow[Vn.find(ch)] += FF[k];
}
}
else {
for (k = 0;k < FF.length();k++)
{
if ((Follow[Vn.find(ch)].find(FF[k])>100) && FF[k] != '#')
{
Follow[Vn.find(ch)] += FF[k];
}
}
string dd;
dd = Letter_Follow(p, p[i].left[0]); //最后一个有空 S的follow加入A的follow
//NONE[Vn.find(p[i].left[0])] = 0;
for (k = 0;k < dd.length();k++)
{
if (Follow[Vn.find(ch)].find(dd[k])>100)
{
Follow[Vn.find(ch)] += dd[k];
}
}
}
}
}
}
} return Follow[Vn.find(ch)];
}
int main()
{
int i, j, k;
cout << "请输入产生式总数:";
cin >> N;
cout << "\n请输入各产生式(#代表空):" << endl;
STR *p = new STR[MAX];
for (i = 0;i < N;i++)
{
cin >> strings;
getlr(p, i);
}
rec(p);
cout << endl;
cout << "\n=========================================" << endl;
cout << "非终结符" << "\t" << "FIRST" << "\t\t" << "FOLLOW" << endl;
for (i = 0;i < Vn.length();i++)
{
cout << " " << Vn[i] << "\t\t{";
string pp;
pp = Letter_First(p, Vn[i]);
for (j = 0;j + 1 < pp.length();j++)
{
cout << pp[j] << ",";
}
cout << pp[pp.length() - 1] << "} ";
Follow[0] += '$'; //开始符加入$
cout << " {";
string ppp;
ppp = Letter_Follow(p, Vn[i]);
for (k = 0;k + 1 < ppp.length();k++)
{
cout << ppp[k] << ",";
}
cout << ppp[ppp.length() - 1] << "}" << endl;
}
cout << "\n=========================================" << endl;
return 0;
}
实验
测试数据:
- S->AB
- S->bC
- A->~
- A->b
- B->~
- B->aD
- C->AD
- C->b
- D->aS
- D->c
结果:
问题和难点
- 本次实验使用需要计算非终结符的first和follow集合,在求解过程中,如果遇到类似FOLLOW(A)=FOLLOW(B)的情况,此时,B的FOLLOW集合还未求解,因此需要使用递归调用solveFollow的函数。
- 由于本次是上下文无关的文法,不是正规文法求解集合,因此需要要注意文法产生式右部长度大于等于3的情况,这种情况可以在求解程序中一个一个分析产生式的右部。这样才能保证不遗漏。
推荐阅读
-
先算后套的编译原则 C++ 实现
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为: