在编译原理中： 文法S——>SS+|SS*|a能产生什么语言，并验证！ 求高人指导！

Question

如题所述

Answer 1

为了使问题简化，我们考虑文法S->ss+|a，考虑s->ss*时，只要把+换成*即可。
0层递归是，s->a,文法的语言是{a}。是后缀表达式。
1层以内递归时，文法语言是{a,aa+}。是后缀表达式。
2层以内递归时，文法语言是{a,aa+}.{a,aa+}.{+}。其中.表示连接，是后缀表达式。
依此类推，多少层的递归都是后缀表达式。
把表达式的+换成*后依然为后缀表达式。
下面证明文法产生的语言是所有的以a为变量，以+和*为运算符的后缀表达式。
因为每个表达式都对应一个常规的表达式（如1*2+3就是常规表达式），下面只需证明语言能产生的后缀表达式对应所有的常规表达式。当常规表达式只有一个运算符，对应aa+或aa*。当常规表达式有两个运算符，可写成(表达式1）.{+|*}.(表达式2），因为表达式1和2都只含一个运算符，所以可以用语言表示，上述常规表达式可用后缀表达式（表达式1）.（表达式2）.{+l*}表示。所以不管常规表达式有多少个运算符，都可以由语言的后缀表达式对应。

Answer 2

文法S，一般都是被当成 开始符号.
+ 一般表示为 1次或者多次以上.
* 一般表示为 0次或者多次以上.
S有三个候选式: ss+ , ss*, a
按照我以前学习概念，我感觉这个 P（产生式）有左递归问题，需要消除左递归，但是如果是做题的话，应该不需要解决这个问题。
a,或者没有 aa .., aaaaaaaaaa, aaa...就是这样吧！
不会有什么语言，只是串. 这些可以导出 非终结符S的 first集 fllow的集,不过介于只有一个产生式，
介意你多看看 编译原理的书籍，把概念弄好，我相信你，一步步来学习。
先去弄明白 终结符和非终结符的概念，再弄明白文法.追问

一个文法可以定义一种语言，在这里，S是开始符号，a、+、*都是作为终止符号。就像文法：S——>0S1|01可以定义语言L(G)={0^n 1^n,n>=1}一样，我想问上面这个文法定义的语言是什么！

本回答被网友采纳

Answer 3

a 的所有可能的加法 (+) 和 乘法 (*) 的 postfix （后缀） 表达式