有一道编译原理试题是关于语法制导与翻译的,我不太懂怎么做考试时候没有做出来.请指点一下,谢谢! (编译原理太难学了,我只会做常规题目,惭愧啊……)
题目如下:
已知一个有向图的描述语言G[S]及其语法制导定义:
产生式 语义规则
S---->S′N N.owner:=S.graph; S′.graph:= S.graph
S---->N N.owner:= S.graph
S---->S′E E.owner:= S.graph; S′.graph:= S.graph
S---->E E.owner:= S.graph
N---->digit AddNode(N.owne,digit.val)
E---->(digit1,digit2) AddEdge(E.owner,digit1.val,digit2.val)
其中,属性S.graph表示与S对应的一个有向图;属性N.owner表示结点N所属的有向图;属性E.owner表示边E所属的有向图;digit.val表示终结符digit的数值;函数AddNode(g,n)表示n为图g的一个结点;函数AddEdge(g,s,t)表示(s,t)为图g的一条边.
例如:1(1,2)(1,3)2(2,3)(3,1)3表示一个有向图.
①
↙ ↘↖
② → ③
试为文法G[S]写出翻译规程,使得:
(1)在翻译结束的时候,语义栈顶的S.graph属性表示一个翻译出的有向图;
(2)在翻译过程中,如果输入语言中包含重复的结点或边,能够提醒用户并忽略重复的结点或边;
(3)在翻译结束的时候,能够检测有向图中是否存在无效的边并删除,例如1(1,2)中包含一条无效的边(1,2)
附:翻译规程中能够使用的库函数:
(1)GRAPH*CreateGraph();创建一个有向图,并返回该有向图的指针;
(2)void CreateNode(GRAPH*pGraph,int nNode);在图pGraph中创建一个编号为nNode的结点;
(3)bool IsNodeExist(GRAPH*pGraph,int nNode);判断编号为nNode的结点是否存在于图pGraph中;
(4)int GetNodeCount(GRAPH*pGraph);得到图pGraph中的结点数;
