软件设计师-上下文无关文法
1 什么是文法
在编译原理中，文法（Grammar）是用于精确描述一种形式语言的规则集合。
本题给出的是一个上下文无关文法，由以下要素组成：
非终结符：S（可以继续推导的符号）
终结符：x, y（最终句子中出现的实际字符）
产生式：S → xSx | y（表示S可以替换成什么）
2 产生式的含义
S → xSx：递归规则，在S的外层左右各加一个x
S → y：基础规则，递归结束，S直接变成y
竖线 | 表示“或”，即有两种选择
3 推导过程分析
我们从起始符号S开始，逐步推导出所有可能的句子。
3.1 基础推导（n=0）
选择规则 S → y：
S ⇒ y
得到句子：y
3.2 一次递归（n=1）
先选 S → xSx，再选 S → y：
S ⇒ xSx ⇒ xyx
得到句子：xyx
3.3 二次递归（n=2）
先选两次 S → xSx，再选 S → y：
S ⇒ xSx ⇒ xxSxx ⇒ xxyxx
得到句子：xxyxx