浏览 1328 次
|
锁定老帖子 主题：引入新的非终结符转换直接递归文法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2013-04-02
这个所谓的公式法，一开始着实看不懂，做了几个题目后再反复看了书上的例题，终于明白了怎么回事，主要是利用了等价文法的思想：文法到语言是一对第一，语言到文法是一对多，在描述同样的语言的情况下，可以有多种文法，所以存在不改变所定义的语言的情况下改造文法的可能。
1.假设有如下直接左递归 U→Ux|y 该文法所表示的语言为yx* 2.引入新的非终结符V V→xV|空 该文法所表示的语言为x* 3.所以原来的文法可以改造为 ①U→yV ②V→xV|空 该文法表示的语言为yx* 因为改造前后的两种文法所表示的语言相同，所以为等价文法 至此原来的直接左递归文法已变换为右递归，反向变换同理 声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
