一个文法的算法设计小问题

jeanlove

问题:
1. 需要得到{a^nb^nc^n|n>=0}这样的字符串，怎么用一个最简单的形式文法来表示它的生成过程?
2. 假如我有aaaabbbcc，编程输出这个字符串的文法分析的过程，大概需要什么样子的思路呢?

是不是需要弄一个状态机来分析它? 请大人指点一下，谢谢!

gta

{a^nb^nc^n|n>=0}，这个不能用上下文无关文法来描述，但可以用下面的乔姆斯基1型文法(Context-sensitive grammar)生成:

S->aBSc
S->abc
Ba->aB
Bb->bb



ps:楼主干什么项目的啊，居然要用到这些东西。在下很好奇

[ 本帖最后由 gta 于 2009-7-17 20:58 编辑 ]

aaaaa5aa

这个很难，你可以参考下逆向工程

rollin7

帮顶一下，可惜我水平太低，帮不了忙，连问题都没看懂

chenzengjie

是不说正则表达式引擎的实现? 龙书上讲的很详细. 词法分析那一章.

sunyu_bit

先写上下文无关文法，然后用有穷自动机进行分析，很简单

cjaizss

很多计算理论课程会拿第一种语言作为例子,它是典型的1类语言,并非由上下文无关文法,乃上下文相关文法生成.
S->aBSc
S->abc
S->
Ba->aB
Bb->bb
以上的文法因为并非2类文法,所以对你的分析作用可能不大.倒不如a^nb^nc^n来的简单

openspace

有本书《代码之美》，好像第一个讲的就是正则表达式的识别
LZ可以看看
网上有下载，但是不全，不过第一章构了

蓝色神话

原帖由 aaaaa5aa 于 2009-7-17 15:43 发表
这个很难，你可以参考下逆向工程

和逆向工程有关系吗？这应该是属于编译原理范围内的东西。我原来编译原理学的很好，现在都忘记了，悲哀啊！