从程序流程图自动生成C代码
作者：牛锐
来源：《数字技术与应用》2013年第04期
作者：牛锐
来源：《数字技术与应用》2013年第04期
摘要：本文设计并实现了标准程序流程图的C代码自动生成算法。
关键词：代码自动生成
中图分类号：TP3 文献标识码：A 文章编号：1007-9416（2013）04-0200-01
1 研究背景
本文阐述的算法可以识别、分析正确的结构化以及半结构化的流程图，并生成相应C代码。
2 识别与分析流程图的结构
2.1 循环结构的识别
直观上看，循环结构在流程图中对应着环路结构，而程序流程图是一幅有向图，在图论中，有向图的环路结构形成了强连通分量。因此本文将循环结构的识别问题转化为寻程序流程图的强连通分量问题。
2.2 菱形结点类型的判定
在程序流程图中，菱形结点既可以表示循环的条件判断结点（引领一个强连通分量），又可以表示普通的分支结点。为了方便判断菱形结点的类型，首先定义强连通分量的Head结点和Tail结点：
Head结点：强连通分量的起始寻结点。
Tail结点：有出边走向强连通分量外部；且Tail==Head或Tail->Next == Head
结合强连通分量以及Head、Tail结点的信息，我们用如下方法判断菱形结点的类型：该结点为矩形结点，不需要判断类型；该结点为菱形结点，且构成自循环，则为while循环结点；否则为if结点。
2.3 环路的消除
要计算嵌套在循环结构内部的强连通分量，必须将外层强连通分量的环路破坏掉。
while类型循环。对于while类型的循环结构，构成强连通分量环路的流程回线是循环体中最后一个结点连向Head结点的那条边。除此之外，循环体内部可能存在其他多条Head结点的入边，在半结构化流程图中，这些边都是具有continue含义的半结构化元素，对于while类型的循环结构，Head结点的来自于强连通分量内部的入边应全部消除。
do-while类型循环与while类似。
2.4 半结构化流程线的识别与转化
在识别与判定循环结构类型的过程中，内部嵌套的if结构中有可能存在半结构化元素（continue，break，return）。识别半结构化流程线的方法如下：
continue：是循环判断结点的入度流程线，且尾结点属于强连通分量；
break：位于循环结构内部嵌套的分支结构中，且连向循环出口结点；
return：位于循环结构内部嵌套的分支结构中，且连向end结点。
3 循环结构线性化与分支结构的分析
3.1 循环结构线性化
流程图中的循环结构对应于环路结构，为了将循环结构转为线性结构，从而方便代码生成，本文引入循环上下界来记录循环结构的起始位置和结束位置。
while类型循环。
将while循环转为上下界的过程如下：
（1）循环判断结点变为循环上界：id仍为原菱形结点的id，记录循环的条件表达式。循环上界在生成代码时对应的代码为“while（expr）”。
（2）增加循环下界：id是循环上界id的相反数，条件表达式为空。循环下界在生成代码时对应的代码为“}”。
（3）下界的前驱和后继：下界的前驱结点应为while循环体内部各控制流汇聚后的最后一个结点，由于此时还未进行分支结构的分析，所以无法确定最后的汇聚结点，因此循环下
界的前驱结点暂时留空；下界结点的后继结点为while出口结点。
（4）删边：删去循环判断结点到循环出口结点的那条边。
do-while类型循环与while类似。
3.2 分支结构的分析
识别并分析流程图结构并将循环结构线性化之后，只需要再确定出分支结构的域，以及半结构化结点的后继以及循环下界的前驱，就可以顺序遍历流程图生成代码了。
分支结构域的确定：分支结构“域”的确定是指if-else结构复合语句块右花括号的定位。分支结构的汇合点指的是if-else结构中两个分支执行完后控制流相汇合的结点。因此，汇合点表示的是分支结构的出口，定位右花括号的位置的问题就转化为了如何分支结构的汇合点。
4 代码生成算法实现
代码生成算法首先完成流程图中循环结构的识别、菱形结点类型的判定以及半结构化流
程线的识别，然后给循环添加上下界，将含有环路结构的流程图变为顺序结构的非连通的流程图，进而在确定分支结构域的过程中确定半结构化节点的后继以及半结构化结点的前驱，将上一阶段的非连通图变为连通图；最后将遍历转化好的顺序的结构化的流程图，拼接各结点对应的代码生成最终C代码。
5 实验结果
以下仅选取一个典型结构的流程图作为测试用例进行实验：
6 总结与展望
本文处理的流程图还比较简单，下一步希望能处理更复杂的流程图。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论