《PDA和CFG的相互转换.docx》由会员分享，可在线阅读，更多相关《PDA和CFG的相互转换.docx（3页珍藏版）》请在三一办公上搜索。
1、PDA和CFG的相互转换开始屏幕输出 0： CFG To PDA 1： PDA To CFG 29：Exit用户选择要进行的转换用户输入数字0判断用户的输入291调用CFG To PDA 函数退出输入要转化的CFG (以表示结束输入)调用PDA To CFG函数输入PDA状态转换图*是否有结束符*构造CFG构造PDA判断用户输入并进行存储处理查找终结符形成表达式的右边输出CFG的推导式对CFG中的终结符和非终结符进行统计处理表达式标识终结符/非终结符进栈出栈操作显示转换的CFG构造PDA显示转换的PDA设计思想： 首先定义最大结点数，CFG表达式的最大长度 ，和栈的最大深度，防止用户无限制的输
2、入。 定义用到的数据结构，包括CFG结点，CFG表达式，PDA结点，PDA表达式，用到的临时栈的数据结构。 定义用到的函数，包括CFG转化为PDA的函数，PDA转化为CFG的函数，标识终结符和非终结符的函数，构建PDA的函数，出栈和入栈函数，程序的主函数。 各种函数的算法流程： CFG转化为PDA： 创建存放用户输入的CFG结点的数组，用户输入要转化的CFG表达式，然后进行初始化处理。找出CFG表达式的变量，起始符，终结符，产生式表分别放入相应的数组中。进行初始化之前首先进行判断，看用户输入的CFG表达式是否合法。查看的过程如下：首先判断确定用户输入的是否是不为空的CFG表达式，也就是判断数组
3、的第一个元素是否不为，如果不为空则判断存放CFG表达式的数组的第二个和第三个元素是否是- 和符号，如果合法则新建CFG产生式。建立一个存放产生式体的数组，创建CFG表达式的头，并将数组中的第一个元素赋值给产生式的头，创建一个指向下一个结点的指针，指针指向一个空的数据元素。然后依次从CFG表达式的第一个元素开始，取出产生式的右边放在产生式体的数组中。输出CFG的推导式，利用终结符和非终结符函数标识函数标识CFG推导式中的终结符和非终结符，创建终结符和非终结符的指针，将标识的分别加入到其中。接下来构建PDA，将CFG的非终结符复制到PDA的非终结符数组中，将CFG的终结符复制到PDA的终结符数组中，创建PDA结点，定义一个栈，压入栈底符号，让开始符号入栈，接下来依次处理CFG结点，以空栈方式接受PDA，最后输出转化后的PDA。 PDA转化为CFG： PDA向CFG的转换分为两步，一步是用户输入PDA的状态转换图，然后进行PDA的初始化，另一部就是PDA转化为CFG。PDA转化为CFG的过程利用出栈和入栈操作将每一个转换转化成一至多个产生式的过程。它分为两步，即产生产生式的左部和右部。
