本文主要是介绍【形式语言与自动机/编译原理】CFG-＞Greibach-＞NPDA（1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文将详细讲解《形式语言与自动机》（研究生课程）或《编译原理》（本科生课程）中的上下文无关文法（CFG）转换成Greibach范式，再转成下推自动机（NPDA）识别语言是否可以被接受的问题。此外，本文还给出了python代码的具体实现。
由于内容比较多，所以为了讲清楚，分成了3篇博客，第一篇（即本篇）主要讲 解从上下文无关文法到Greibach范式的具体步骤和流程，并给出了相应的算法及具体的例子；第二篇主要讲解从Greibach范式到下推自动机NPDA，同样给出了相应的算法及具体的例子；第三篇主要是对前两篇中给出的算法用python语言进行实现，并测试之前的例子。
它们的地址如下：
第一篇：
第二篇：
第三篇：
整体流程
这里先来介绍以下从上下文无关文法到Greibach范式再到下推自动机的整体流程，如下所示：
由上下文无关文法转换成下推自动机的过程，可以分为两个步骤，即：（1）上下文无关文法转换成Greibach范式（2）Greibach范式转换成下推自动机NPDA。这两个过程包括的具体步骤以及它们的顺序如下，
上下文无关文法-->消除左递归-->消除无用符号-->消除单一产生式-->消除空产生式-->得到Greibach范式-->生成状态转移函数-->得到下推自动机NPDA
以下将按照这个顺序分步骤进行讲解。
1 上下文无关文法转换成Greibach范式
1.1 消除左递归
给出两个消除直接左递归的例子：
例子1：
下面举3个消除间接左递归，并将其转换成直接左递归的例子：
1.2 消除无用符号
简单来说，无用符号包括不可达符号和非产生符号两种。不可达符号是指不能直接或间接推出终结符号的非终结符号。非产生符号是指由开始符号S推不出的非终结符号。
下面给出2个例子：
例子2：
1.3 消除单一产生式
以下给出4个例子：
1.4 消除空产生式
以下给出3个例子：
例子3：
1.5 得到Greibach范式
以下给出2个例子：
本篇博客主要介绍了从上下文无关文法到Greibach范式的各个步骤，下一篇将讲解从Greibach范式到下推自动机NPAD的各个步骤。
这篇关于【形式语言与自动机/编译原理】CFG-＞Greibach-＞NPDA（1）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
