【形式语言与自动机/编译原理】CFG->Greibach->NPDA(1)

2023-12-31 17:00:51

本文将详细讲解《形式语言与自动机》(研究生课程)或《编译原理》(本科生课程)中的上下文无关文法(CFG)转换成Greibach范式,再转成下推自动机(NPDA)识别语言是否可以被接受的问题。此外,本文还给出了python代码的具体实现。

由于内容比较多,所以为了讲清楚,分成了3篇博客,第一篇(即本篇)主要讲 解从上下文无关文法到Greibach范式的具体步骤和流程,并给出了相应的算法及具体的例子;第二篇主要讲解从Greibach范式到下推自动机NPDA,同样给出了相应的算法及具体的例子;第三篇主要是对前两篇中给出的算法用python语言进行实现,并测试之前的例子。

它们的地址如下:

第一篇:

第二篇:

第三篇:


整体流程

这里先来介绍以下从上下文无关文法到Greibach范式再到下推自动机的整体流程,如下所示:

由上下文无关文法转换成下推自动机的过程,可以分为两个步骤,即:(1)上下文无关文法转换成Greibach范式(2)Greibach范式转换成下推自动机NPDA。这两个过程包括的具体步骤以及它们的顺序如下,

上下文无关文法-->消除左递归-->消除无用符号-->消除单一产生式-->消除空产生式-->得到Greibach范式-->生成状态转移函数-->得到下推自动机NPDA

以下将按照这个顺序分步骤进行讲解。

1?上下文无关文法转换成Greibach范式

1.1 消除左递归

c25af6d51bb64bdba7d34d14469a8dc6.png

d520400d5748483a9a0e69514049588f.png

86c9c7113874438096f0e92a82fb02e5.png

给出两个消除直接左递归的例子:

例子1:

8049239d739d4714b26a6b3aba1df46b.png

7e09c46bc833490397185e0a6ee31381.png

e3b75242a80a43689d656dcb4ed67de0.png

下面举3个消除间接左递归,并将其转换成直接左递归的例子:

bca32d7209564724a7fbcae58f81a68f.png

1c208926ef7441e4bf7260f3efe4e1e1.png

0964ee4ccd1842ad8316c5e040846646.png

1.2 消除无用符号

b6de6d92fa324eb88f22de6bdb170da0.png

简单来说,无用符号包括不可达符号和非产生符号两种。不可达符号是指不能直接或间接推出终结符号的非终结符号。非产生符号是指由开始符号S推不出的非终结符号。

bc1b4e4116ae4a18bfa9c754088e8ba4.png

f2a4ffbb69cd45ef908728ca061fa258.png

下面给出2个例子:

1de82e78e9d74b01bebe1b72446a7977.png

例子2:

41fe8b97501c449bb6d4658e2f9a33a6.png

1.3 消除单一产生式

71fd0401cc7f4a21a838feb6c18a54fb.png

97f7a3abf7f24222b148bde77e3a1901.png

8962cbdfd5ce47d5a6cd71ee7ed32555.png

0720487f7a6d45628b839ce4fcee43dc.png

以下给出4个例子:

227f634ae0824b86986028fa9de0998b.png

6796207c1f834b7b8fff8dac1889ab6c.png

10122aeb06af47faac1550f3c7859cec.png

1.4 消除空产生式

4641aaf629ba425f90537f4b090742ad.png

f54fb35baaef4205b0ebf217161cc3d9.png

763456b08d8e43068b8023f7be8f2a1b.png

以下给出3个例子:

9b036ac2e76b495ab63dbc8f4c5a3fb6.png

例子3:

bacd887604d745e7a6e8754d442de058.png

1.5 得到Greibach范式

56f83b8ea34b4a9cb438914cbbf237ec.png

7203f176c7244ce0ac5a27c72ff055fd.png

以下给出2个例子:

3e800830f782467cbd4b176aae08f218.png


本篇博客主要介绍了从上下文无关文法到Greibach范式的各个步骤,下一篇将讲解从Greibach范式到下推自动机NPAD的各个步骤。

?

?

文章来源:https://blog.csdn.net/m0_56367027/article/details/135313301
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。